💻 CPU 스케줄링

📌 CPU 스케줄링 개요

1. 프로그램들이 실행되면 메모리에 올라가 프로세서가 되고

2. 프로세서들은 1개 이상의 쓰레드가 있으며

3. CPU를 차지하기 위해 운영체제의 명령을 기다린다.

✅ CPU 스케줄링 고려사항

1. 어떤 프로세스에게 CPU 사용권을 줘야 하나?

2. CPU를 할당받은 프로세스가 얼마의 시간동안 CPU를 사용할 수 있는가?

CPU Burst: 프로세스가 CPU를 할당받아 연속적으로 실행하는 구간

I/O Burst: 프로세스가 입출력(I/O) 작업을 수행하는 구간

📌 다중큐

✅ 프로세스 실행 과정

1. 프로세스가 생성되면 준비 상태로 전환

2. 준비 상태에서 CPU 사용권을 받으면 실행 상태

3. 실행 중 I/O 요청은 대기 상태, 할당시간을 초과하면 준비 상태

4. 작업이 끝난다면 완료 상태로 전환된다.

✅ 준비 & 대기 상태 관리

1. PCB 정보 내에 우선순위 정보를 탐색하여 준비 상태 다중 큐(Ready Queue) 에 넣는다.

2. 준비 상태 다중 큐에서 운영체제는 적당한 PCB를 선택하여 실행 상태로 전환시킨다. (적당한 - 스케쥴링 정책에 따라)

3. I/O 요청으로 대기 상태가 된다면 I/O 작업에 따라 분류된 큐에 들어간다.

4. I/O 작업이 마무리되면 인터럽트를 발생시켜 실행 상태로 전환한다.

준비 & 대기 상태 -> Queue로 관리

📌 스케줄링 목표

1. 리소스 사용률

- CPU, I/O device

2. 오버헤드 최소화

- 스케쥴링 계산, 컨텍스트 스위칭의 빈도

3. 공평성

- 모든 프로세스 공평하게 할당

- 프로세스의 중요도에 따라 상대적으로 공평하게 할당

4. 처리량

- 같은 시간 내 더 많은 처리

5. 대기 시간

- 작업 요청부터 작업 실행 전까지 대기 시간을 짧게

6. 응답 시간

- 작업 응답 시간을 짧게

모든 목표를 동시에 달성할 수는 없다.

사용자가 사용하는 시스템에 따라 목표를 다르게 설정한다.

- 터치 스크린 -> 응답시간이 중요

- 과학 계산 -> 처리량이 중요

- 일반 목족 -> 밸런스 유지

📌 FIFO

FIFO(First In First Out): 스케줄링 큐에 들어온 프로세스 순서대로 먼저 실행된다.

✅ 특징

1. 한 프로세스가 완전히 끝나야 다른 프로세스가 시작함.

2. 짧은 작업의 프로세스가 긴 작업의 프로세스를 대기할 수도 있음.

3. I/O 작업을 대기하는 동안 CPU는 다른 작업을 하지 않음 => CPU 사용률 저하

✅ 평균대기시간

프로세스가 여러 개 실행될 때 모두가 실행되기까지의 평균 대기 시간

- 프로세스_1 (Burst Time: 25초) - 대기 시간: 0초

- 프로세스_2 (5초) - 대기 시간: 25초

- 프로세스_3 (4초) - 대기 시간: 30초

❗평균 대기 시간: 55 / 3 = 18.3초

- 프로세스_3 (4초) - 대기 시간: 0초

- 프로세스_2 (5초) - 대기 시간: 4초

- 프로세스_1 (Burst Time: 25초) - 대기 시간: 9초

❗ 평균 대기 시간: 13 / 3 = 4.3초

프로세스 실행 순서에 따라 평균 대기 시간의 편차가 크기 때문에, 현대 운영체제에서는 사용 X

일괄처리시스템에서 주로 사용

📌 SJF

SJF(Shortest Job First): Burst Time이 가장 짧은 작업부터 우선 실행

✅ 특징

1. FIFO의 단점이었던 '실행 순서에 따른 평균 대기 시간 차이'를 극복하기 위해 설계

2. 프로세스의 종료 시간를 예측하기 어려움 (Burst Time 파악이 힘듦)

3. Burst Time이 긴 프로세스는 계속 뒤로 밀려가서 대기 시간이 점차 길어진다.

4. 2,3 의 문제점으로 CPU 스케쥴링으로 채택되지 않음.

📌 RR

RR(Round Robin): 일정 시간동안만 프로세스를 실행하고 다음 프로세스를 실행

✅ 특징

1. 타임 슬라이스(`Time Slice`) : CPU가 할당되는 일정한 시간

✅ 평균대기시간

타임 슬라이스 : 10s

- 프로세스\_1 (Burst Time: 25초) - 대기 시간: 0 + 14 + 0초

- 프로세스\_2 (4초) - 대기 시간: 10초

- 프로세스\_3 (10초) - 대기 시간: 14초

❗평균 대기 시간: 38 / 3 = 12.67초

FIFO 알고리즘과 평균 대기 시간이 비슷하다면 RR 알고리즘이 더 비효율적

RR 알고리즘은 Context Switching이 일어나기 때문에 자원의 사용이 더 필요.

- 타임 슬라이스가 큰 경우

- 먼저 들어온 프로세스가 실행되니 FIFO 알고리즘과 동일 (타임 슬라이스: 무한대)

- 웹 브라우저, 음악 플레이어가 5초마다 끊김(타임 슬라이스: 5s)

- 타임 슬라이스가 작은 경우

- 여러 프로세스가 동일하게 실행되는 것처럼되지만 Context Switching 처리량의 증가로 오버헤드가 너무 크다(1ms)

최적의 타임 슬라이스

1. 여러 프로세스가 버벅이지 않고 동시에 실행하는 것 같은

2. 오버헤드가 너무 크지 않은

운영체제 타임 슬라이스

1. Windows: 20ms

2. Unix: 100ms

📌 MLFQ

MLFQ(Multi Level Feedback Queue):

✅ 가정

- CPU Bound Prcess(P1): CPU 연산만 하는 프로세스 - CPU 사용률, 처리량 중요

- I/O BOund Process(P2): 대부분 I/O 작업만 진행 - 응답 속도

1. Time Slice가 100초일 때

P2 (1초) 작업 후 I/O 작업 요청

P1 (100초) 실행

P1 10초 정도 작업 중, P2의 작업이 완료되어 인터럽트 발생 후 준비 큐에 삽입

P1 90초 나머지 실행

P2 1초 실행 I/O 작업

...

2. Time Slice가 1초일 때

P2 (1초) 작업 후 I/O 작업 요청

P1 (1초) 실행

P2 I/O 작업이 마무리되지 않았기 때문에 P1 준비 큐에 삽입되었다가 바로 실행

10 번 과정

P2 I/O 작업 완료 후, 인터럽트 실행, 준비 큐 삽입

P2 1초 실행 후 I/O작업

- 1번 CPU 사용률을 100% 지만 I/O 사용률은 10/101 (I/O 작업 시간 / 두 프로세스 총 실행시간) = 약 10%

- 2번 CPU 사용률을 100% 지만 I/O 사용률은 10/11 (I/O 작업 시간 / 두 프로세스 총 실행시간) = 약 90%

- 1번에 비해서 CPU와 I/O 이용률이 높아 효율적이지만

- 컨텍스트 스위칭을 자주하기 때문에 P1은 손해

- P2는 이득

✅ 특징

- MLFQ는 기본적으로 CPU 사용률과 I/O 사용률이 좋게 나오는 타임 슬라이스를 가진다.

- CPU Bound Process는 큰 타임슬라이스를 준다.

- 주어진 타임 슬라이스 내에 작업이 완료되면 I/O Bound Process, 초과하면 CPU Bound Process로 추측

- 우선순위가 매겨진 여러 큐를 준비하여 우선순위가 높을 수록 타임 슬라이스가 크게 설정한다.

- 타임슬라이스가 초과될수록 점처 우선순위가 낮은 큐로 이동

- 결국 FIFO처럼 프로세스 연속적으로 작업이 가능

📌 더 찾아본 점

❓선점형(preemptive) VS 비선점형(non-preemptive)?

✅ 선점형 스케쥴링은 하나의 프로세스가 현재 사용중인 CPU의 사용권을 점유할 수 있다.

반대로 비선점형 스케쥴링은 하나의 프로세스가 마무리되어야 CPU의 사용권을 할당받을 수 있다.

❓추가적인 스케쥴링 방식?

✅

1. SRTF(Shortest-Remaining-Time First)

- SJF의 단점 "100초짜리 A가 실행 중에 1초, 2초의 B,C 프로세서가 준비 상태라면, 100 초를 기다려야 한다"

- SJF는 비선점형이기 때문에 작업을 기다려야 하지만, STCF는 큐의 남아있는 작업 시간을 계산하여 CPU의 점유를 뺏는 선점형이다.

- 100초 A작업 도중 2초 작업 B가 도착하면, A의 남은 작업 시간과 비교하여 짧은 B가 먼저 실행된다.

2. Priority

- 비선점형: 도착한 프로세스마다 우선순위가 부여되고 동시에 도착한 프로세스의 경우 우선순위로 실행

- 만약 우선순위가 낮더라도 먼저 실행 중이라면 작업이 종료될 때까지 대기

- 선점형: 도착한 순서가 다르더라도 프로세스의 priority에 따라 높은 우선순위 별로 CPU 점유

3. MLQ(Multi-Level Queue)

- 여러 개의 우선순위가 부여된 큐로 관리되며 프로세스의 우선순위에 따라 각 큐에 삽입

- 프로세스의 타입, 특징, 중요도에 따라 우선순위가 부여 - I/O 작업은 백업과 같은 배치 작업보다 높은 우선순위를 갖는다.

- 각 큐의 요구조건마다 다른 CPU 스케쥴링 알고리즘을 사용한다.

1. 고정 우선순위 선점 스케쥴링 (선점형)

- 큐별로 우선순위가 고정되어 있고, 가장 하위 큐는 상위 큐에 프로세스가 없을 때만 동작이 가능하다.

- 하위 큐의 프로세스가 동작하는 도중, 상위 큐의 프로세스가 들어오면 CPU 사용권을 빼앗긴다.

2. 타임 슬라이싱 (비선점형)

- 큐의 우선순위 별로 CPU 사용 시간의 점유율을 산출한다. > 1순위 50% / 2순위 30% / 3순위 20%

- 프로세스의 큐 간 이동이 불가하여 유연성이 떨어진다.

- 특정 큐에 프로세스가 몰리거나 우선순위 큐에 의해 하위 우선순위의 프로세스 대기 시간이 길어질 수 있음(기아 현상)

4. MFLQ(Multi-Level Feedback Queue)

- MLQ에서 큐 간 이동이 불가하여 유연성이 부족한 문제 극복

- 우선순위에 따른 여러 큐가 존재하며 프로세스의 우선순위는 동적으로 변경된다.

- CPU 점유 시간을 초과하면 우선 순위가 낮아지며, 점유 시간 이내에 작업이 마무리된다면 우선 순위 유지

- 에이징 - 모든 프로세스를 일정 주기마다 최상위 큐로 이동 / 오래 기다린 프로세스 상위 큐로 승격 (기아 현상 방지)

📔 회고

블로그 글을 통해 "인프런 워밍업 클럽"에 대해 알게 되었고 마침 CS 공부를 계획하였던 나는 새로운 기수가 시작되자마자 바로 신청하였다.

이번에 CS 로드맵에 참여하면서 목적없이 강의를 듣고 공부하기 보다는

이 로드맵을 통해 어떤 것을 얻고 싶고 클럽이 진행하는 동안 어떤 것을 꾸준히 지켜나갈 것인지 정하여 공부하는 것이 나의 성장을 더 효율적으로 끌어올려 줄 것 같아, 미리 선정하고 수업에 임하였다.

🚀 최종 목표 : 더 효율적인 백엔드 개발을 위해 기본적인 운영체제 지식들을 확실히 잡아가기

🚀 매주 규칙:

1. 각 섹션마다 하나의 .md 파일을 생성하고, 섹션 내 각 유닛은 헤더로 구분

2. 강의를 듣고 최대한 이쁘게 (?) 정리해놓기

3. 매 강의를 듣고 궁금하거나 이해가 안가는 부분은 추가적으로 더 찾아서 정리해두기

강의를 듣고 정리하는 것이 손에 익지 않아, 초반에는 공부하는 시간보다 틀을 잡는데 시간이 더 소요되었지만

점차 강의를 듣고 정리하는 방법이 손에 익으면서 정리하는 시간이 많이 줄었고 요약에 대한 아웃라인도 대강 잡혀나갔다.

다만 회고를 하다보니 목표는 "백엔드 관점에서의 운영체제"로 설정하였는데, 1주차는 운영체제에 대해서만 공부를 한 것 같아서 다음 주부터는 각 강의를 듣고 백엔드 관점에서 고민해보는 시간을 가져보고 다양한 의견을 GPT와 주고 받으며 정리해보면 좋을 것 같다.

4. 매 강의 내용을 백엔드 관점에서 고민해보고 GPT와 대화를 통해 정리