⚠️ 해당 포스팅은 인프런 공룡책 강의를 듣고 개인적으로 정리하는 글입니다. 정확하지 않은 정보가 있을 수 있으니 주의를 요합니다.
Section 05
Chapter 5 CPU scheduling
CPU Scheduling Basic Concepts
- 멀티 프로그래밍을 채택한 O/S에서는 기본적으로 사용하고 있다.
- 멀티 프로그래밍의 기본적인 목표는 일정 프로세스를 항상 실행하고, CPU 사용량을 증대하는 것으로, 이를 위해 CPU 스케줄링이 필요한 것이다.
- CPU 스케줄러(CPU Scheduler)는 메모리 안의 실행 준비를 마친 프로세스 중 하나를 선택하여 CPU로 할당하는 역할을 수행한다.
- 그럼, 다음 프로세스를 선택하는 방법으로 무엇을 채택해야 할까?
- Linked List? Binary Tree?
- FIFO Queue? (First-In, First-Out)
- Priority Queue : 우선순위 큐, 어떻게 우선순위를 결정할건지?
선점형(Preemptive) vs 비선점형(Non-preemptive)
- 비선점형은 프로세스가 CPU에서 실행을 마치고 종료할 때까지 나머지 프로세스가 대기함을 의미한다.
즉, 프로세스가 terminaiting 상태나 waiting 상태로 변할 때까지 대기 - 선점형은 스케줄러에 의해 프로세스가 실행 도중에 CPU에서 빠져나올 수 있음을 의미한다.
CPU 스케줄링에 의한 의사 결정
- 프로세스가
running상태에서waiting상태로 스위칭될 때 - 프로세스가
running상태에서ready상태로 스위칭될 때 - 프로세스가
waiting상태에서ready상태로 스위칭될 때 - 프로세스가
terminates상태가 될 때
- 1번과 4번은 프로세스가 자발적으로 CPU에서 빠져나오는, 즉 비선점 유형이다.
- 2번과 3번은 스케줄러에 의해 실행 중 CPU에서 빠져나올 수 있어 비선점 유형일수도, 선점 유형일수도 있다.
Dispatcher
- 디스패처는 CPU 스케줄러에 의해 선택된 프로세스에게 실질적으로 CPU의 제어권을 주는 역할을 수행한다.
(즉, 무엇을 변경할지 선택하는 것은 스케줄러, 변경을 실제로 수행하는 것은 디스패처) - CPU 스케줄러 내부에 포함되어 있으며, 프로세스의 레지스터를 적재하고(Context Switching) 커널 모드에서 사용자 모드로 전환시키는 역할을 수행한다.
- Context Switching 을 하는데 소요되는 시간을 dispactcher latency 라고 칭하고, 이 소요 시간을 줄이기 위해 디스패처는 최대한 빨라야 한다.
- 넓은 의미의 스케줄링은 스케줄러와 디스패처 기능을 동시에 수행함을 의미하기도 한다.
Scheduling Criteria
- CPU utilization : CPU는 바쁜 상태를 유지해야 한다. 즉, 사용률을 늘려야 한다.
- Throughput : 특정 시간 내에 많은 양의 프로세스를 처리해야 한다.
- Turnaround time : 프로세스 실행 후 종료까지의 시간을 최소화해야 한다.
- Waiting time : 프로세스가
Ready큐에 상주하는 시간을 최소화해야 한다.(waiting time 을 개선하면 시스템의 효율을 크게 증대시킬 수 있다.) - Response time : 응답시간을 최소화해야 한다.
Scheduling Algorithms
- 스케줄링 문제에 관해 여러 솔루션이 존재한다.
- FCFS : First-Come, First-Served - 먼저 온 프로세스를 먼저 실행하는 방법
- SJF : Shortest Job First - 순서와 상관없이 실행 시간이 짧은 프로세스를 먼저 실행하는 방법
- RR : Round-Robin - 정해진 시간동안만 프로세스를 실행하는 방법
- Priority-based - 우선 순위에 따라 프로세스를 실행하는 방법
- MLQ : Multi-Level Queue - 프로세스를 중요한 순으로 레벨을 나눠 큐를 생성하고, 큐마다 다양한 알고리즘을 적용하는 방법
FCFS(First-Come, First-Served) Scheduling
- 먼저 온 프로세스를 먼저 실행하는 방법으로, 비선점 스케줄링 유형이다.
- FIFO 큐를 참고하여 만들어진 방법으로 구현이 가장 쉽고 간단하다.
- CPU 버스트 타임이 긴 프로세스가 먼저 실행되는 경우 waiting time이 크게 늘어나 효율성이 하락하는 치명적인 단점이 존재한다.
SJF(Shortest Job First) Scheduling
- 도착 순서와 무관하게 짧은 작업을 먼저 수행하는 스케줄링 유형이다.
- 크기가 동일할 경우 먼저 도착한 프로세스를 실행한다.
- SJF 스케줄링은 평균 waiting time 을 최대한 줄일 수 있는 최적의 옵션이다.
- 그러나, 다음 프로세스의 CPU burst 시간을 확실히 알 수 없기 때문에 현실적으로 구현하기 어렵다.
- 이에 대한 방안으로, 다음 프로세스의 CPU burst 시간을 예측하여 비슷하게라도 구현한다.
- 실행할 프로세스가 과거에 얼마나 CPU burst 시간을 소요했는지 저장하고, 이를 이용하여 현재 소요할 시간을 예측한다.
- 그러나, 시간을 얼마나 쓰는지 기록하는 것 역시 CPU에 저장되는 것이기 때문에 부담스러울 수 있다.
- 기본적으로, SJF 스케줄링은 선점 유형일수도, 비선점 유형일수도 있는 방법이다.
- 만약, 현재 실행중인 프로세스보다 새로 도착한 프로세스의 실행 시간이 더 짧다면 어떻게 처리할 것인지 생각해보아야 한다.
- 여기서 다음 프로세스에게 대기 명령을 내리면 비선점 유형, 현 프로세스를 중단하고 다음 프로세스를 실행시키면 선점 유형이 된다.
SRTF(Shortest-Remaining-Time-First) Scheduling
- 현재 실행중인 프로세스보다 다음 프로세스의 실행 시간이 짧다면 바로 다음 프로세스를 실행하는 방법이다.
- SJF, SRTF 스케줄링의 경우 계속해서 짧은 실행 시간을 가진 프로세스가 도착하면, 긴 실행 시간을 가진 프로세스는 영영 실행하지 못할 가능성이 있다.
RR(Round-Robin) Scheduling
- 먼저 들어온 프로세스를 실행하지만, 시간 단위(time quantum)에 따라 끊임없이 스위칭하는 선점형 스케줄링 방법이다.
- 레디 큐는 원형 큐, 즉 순환 큐로 처리된다.
- 평균 waiting 시간을 줄일 수 있으나, 평균 response 시간이 크게 늘어날 수 있다는 단점이 있다.
- 이 스케줄링을 사용할 때 두 가지 상황이 일어날 수 있다.
- 프로세스의 CPU 버스트 시간이 설정한 시간 단위보다 적다면?
-> 프로세스가 CPU에서 자발적으로 탈출하고 스케줄러는ready큐에 있는 다음 프로세스를 실행한다. - 프로세스의 CPU 버스트 시간이 설정한 시간 단위보다 길면?
-> O/S에 의해 인터럽트와 함께 컨텍스트 스위칭이 발생한 후 다음 프로세스를 바로 실행한다. 그리고 현재 프로세스는ready큐의 끝으로 가 대기한다.
Priority-base Scheduling
- 각 프로세스에게 우선 순위를 할당하고, 우선 순위 순으로 프로세스를 CPU에 할당하는 방법이다.
- 같은 우선 순위를 가지고 있다면, 먼저 온 프로세스를 실행한다.
- CPU burst 시간이 클 때 우선 순위를 낮게 설정할 경우 SJF 스케줄링과 비슷한 결과가 나올 수 있다.
- 기본적으로 선점 유형이 될수도, 비선점 유형이 될수도 있는 방법이다.
- 가장 경계해야 할 문제는, 기아(starvation) 현상이다.
- 우선 순위가 낮은 프로세스의 경우 무한정 대기할 수도 있기 때문이다.
- 이에 대한 솔루션으로, 오랜 기간 대기한 프로세스는 점진적으로 우선 순위를 높이는 방법이 있다.
- 위에서 이야기한 RR 스케줄링과 섞어서 쓰는 방법도 있다.
- 높은 우선 순위를 가진 프로세스를 실행하고, 같은 우선 순위를 가진 프로세스끼리는 RR 스케줄링, 즉 시분할로 실행하는 방법이다.
Multi-Level Queue(MLQ) Scheduling
- 우선 순위별로 큐를 지정하고, 큐에 따라 각각 다른 스케줄링을 적용하는 방법이다.
- 이 경우 새로운 프로세스가 들어왔을 때 어느 큐로 분류해야 하는지 애매하다는 단점이 있다.
Multi-Level Feedback Queue(MLFQ) Scheduling
- 위의 MLQ 를 보완한 방법으로, 우선 순위별로 큐를 지정하는 것까진 똑같으나, 최하단 우선 순위의 큐를 제외하고는 모두 RR 스케줄링을 적용한 방법이다.
- 처음 실행한 큐는 최상단 우선 순위의 큐로 들어가게 된다.
- 최상단 우선 순위의 큐에 시간 단위를 가장 낮게 설정하고, 시간 단위 안에 실행한 경우 프로세스는 해당 큐에 유지된다.
- 시간 단위안에 프로세스 실행을 마치지 못한 경우 해당 프로세스의 우선 순위를 한 단계 낮춘다.
- 계속해서 시간 단위 내에 실행하지 못한다면 최하단 우선 순위로 내려가 순서대로 실행된다.
- 실행 시간이 길어 우선 순위가 낮아진 프로세스의 경우 기아 현상이 발생할수도 있다.
Thread Scheduling
- 최신 O/S에서 대부분의 태스크는 프로세스가 아닌 커널 스레드이며 사용자 스레드들은 스레드 라이브러리에 의해 관리된다.
- O/S 커널은 사용자 스레드를 인식하지 못하므로, 사용자 스레드는 커널 스레드에 매핑되어야만 O/S의 스케줄링을 받을 수 있다.
Real-Time CPU Scheduling
- 리얼타임 O/S에서의 스케줄링은 Soft Realtime 혹은 Hard Realtime 으로 구성된다.
- Soft real-time 시스템의 경우 반드시 정해진 시간 내에 실행하는 것은 아니며, 중요 태스크가 먼저 실행된다는 것만 보장한다.
- Hard real-time 시스템의 경우 요구 사항이 매우 엄격하여 태스크는 반드시 시간 내에 실행되어야 한다.
즐겁게 하자 🤭
잘 읽었습니다 :)