이 글은 KOCW에 공개되어있는 '반효경 교수님'의 운영체제 강의 및 강의 교재 Operation System Concepts(a.k.a 공룡책🦕)의 내용을 기반으로 작성했습니다.
이번 챕터에서는 CPU Scheduling에 관해 정리해보겠습니다
오류가 있다면 댓글로 정정 부탁드립니다
CPU/IO Bursts
CPU Burst : CPU를 실행하는 단계
IO Burst : IO를 실행하는 단계
- 어떤 프로그램이든 빈도만 다를 뿐 CPU Burst -> IO Burst -> CPU Burst -> ... 의 반복하는 작업을 거치게 된다
- 사람이 interaction 하는 경우에는 IO 작업이 빈번하게 일어난다(화면 사용률이 높음)
| CPU Burst 분포
CPU Burst time 확률 분포도
- IO Bound Job: CPU Burst 빈도가 높고, CPU 점유 시간이 적음
- CPU Bound Job : 계산 위주의 Job으로, CPU 작업만 진득하게 함
- CPU Bound Job이 오랫동안 CPU를 잡게 되면 IO Bound Job(사람과의 interaction 빈번함)이 CPU를 잡지 못하고 사람은 답답함을 느끼게 된다
- CPU Scheduling을 통해 IO Bound Job에 CPU를 우선적으로 할당해주게 된다
CPU Scheduler/Dispatcher
| CPU Scheduler
Ready 상태의 프로세스 중 누구에게 CPU를 줄 지 결정한다
| Dispatcher
CPU Scheduler에 의해 선택된 프로세스에 CPU 제어권을 넘겨주는 역할을 하는 것
- CPU Scheduler, Dispatcher 모두 다 운영체제 내의 코드이다
- CPU 스케쥴링이 필요한 경우는 다음과 같다
1) Running -> Blocked(I/O 요청 시스템 콜)
2) Running -> Ready (Time Interrupt)
3) Blocked -> Ready (I/O 완료 후 Interrupt)
4) Terminate - 1)의 경우에 I/O를 요청한 프로세스의 우선순위가 가장 높다면 I/O가 끝난 직후 그 프로세스에 CPU를 바로 넘겨줘야 할 수도 있다
- 1/4번은 nonpreemptive(자진 반납), 2/3번은 preemptive(강제 반납)
Scheduling Algorithms
| FCFS(First-Come First-Served)
- 먼저 들어온 프로세스를 먼저 처리해주는 것
- CPU를 오래 사용하는 프로세스가 CPU를 얻게 되면, 대화형 프로세스가 지나치게 오래 기다리는 문제 발생
| Round Robin(RR)
- CPU 할당할 시간을 미리 세팅해서 그 시간만 CPU를 사용하도록 하고 시간이 지나면 줄 서 있는 프로세스에 CPU를 할당해주는 것
- 각 프로세스가 동일한 크기의 할당 시간(time quantum)을 가짐
- 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready Queue의 맨 뒤로 가서 줄을 선다
- CPU를 기다리는 시간이 CPU를 사용하는 시간과 비례하는 측면에서 공정함
- Process의 Context를 Save 하고 다시 CPU를 얻었을 때 그 지점부터 재개할 수 있다는 메커니즘을 제공해주기 때문에 가능하다
- 할당 시간이 커지면 FCFS 방식에 가까워지고, 할당 시간이 너무 작아지면 context switch 오버헤드가 발생하게 된다
| Mulitilevel Queue
- Ready Queue를 여러개로 분할한다
- 각 Queue마다 스케쥴링 방식을 달리 한다
예시 : foreground, background
- foreground Queue의 경우 Round Robin 방식을 이용해 사람과의 interaction을 할 수 있도록 한다
- background Queue의 경우 context switch overhead를 줄이기 위해 FCFS를 사용한다
- 큐에 CPU를 줄 때 우선순위에 따라서만 CPU를 준다면 Starvation(우선순위가 낮은 Job은 CPU를 할당받지 못하는 현상)이 발생할 수 있다
- 각 줄별로 CPU를 나누어 주는 방법을 생각해볼 수 있다(ex 우선순위 높으면 80%, 낮으면 20% 할당)
| Multilevel Feedback Queue
- 프로세스가 다른 큐로 이동 가능하게 한다
- 오래 대기할 수록 우선순위를 높게 책정하는 방식인 에이징(aging)을 이와 같은 방식으로 구현할 수 있다
- 큐 설정에 기준들이 많이 필요하다(Queue의 수, 각 큐의 스케쥴링 알고리즘, Process를 상위/하위 큐로 보내는 기준, 프로세스가 CPU 서비스를 받을 때 들어갈 큐를 결정하는 기준)
예시 : 큐의 흐름이 다음과 같은 형태를 지닐 수 있다
- 처음 들어오는 프로세스는 우선 순위가 가장 높은 큐에 배정을 한다(RR 할당 시간 짧음)
- 밑으로 갈수록 RR 할당 시간을 길게 준다
- 마지막에는 FCFS 스케쥴링 방식을 사용하는 큐에 배정한다
- 할당 시간 내에 처리가 안되면 강등되는 방식으로 운영할 수 있다
- CPU 시간이 짧은 프로세스에 우선 순위를 더 많이 주고 긴 프로세스는 점점 밑으로 쫓겨나게 된다
| Multiple-Processor Scheduling
- CPU가 여러 개 있는 시스템에서의 스케쥴링
| Homogeneous Processor
- Queue에 한 줄로 세워서 처리할 수도 있고, 각각의 CPU마다 별도의 줄을 서도록 할 수 있다
- 특정 프로세서에 의해 처리되어야 하는 JOB이 있을 경우 복잡한 방식을 사용해야한다
| Load Sharing
- 특정 CPU에 Job이 몰리지 않도록 부하를 적절하게 공유하는 메커니즘이 필요하다
- 별개의 큐를 두는 방식, 공동 큐를 사용하는 방식 중 택할 수 있다
| Symmetric Multiprocessing(SMP)
- 모든 CPU가 대등하기 때문에 각자 알아서 스케쥴링을 결정한다
| Asymmetric multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따른다
| Real-Time Scheduling
- Deadline 이 있도록 하는 스케쥴링
- 그때그때 스케쥴링 하기 보다는 deadline에 맞게 미리 Job을 배치하는 방식을 사용한다
- periodic하거나 주기적으로 activated 되어야 하기 때문에 dead line을 보장하는 것이 중요한 스케쥴링
| Hard real-time systems
- task를 정해진 시간 안에 반드시 끝내도록 스케쥴링
| Soft real-time computing
- 다른 프로세스와 함께 진행이 되며, 일반 프로세스에 비해 우선순위를 높여 빨리 진행될 수 있도록 한다
| Thread Scheduling
- 프로세스 안에 CPU 실행단위가 여러 개 있는 것이 스레드
- User Level Thread : 사용자 process가 스레드 관리
- Kernel Level Thread : 운영체제가 스레드의 존재를 알고 있음
| Local Scheduling
- User Level Thread의 경우 사용자 Thread Library에 의해 어떤 Thread를 스케쥴 할지 결정
| Global Scheduling
- Kernel Level Thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케쥴러가 어떤 Thread를 스케쥴 할지 결정
Algorithm Evaluation
알고리즘의 성능을 평가할 수 있는 척도
| Queueing Models
- 확률분포로 주어지는 arrival rate와 service rate를 통해 각종 performance index 값을 계산
- arrival rate : Queue에 Job들이 도착해 쌓이게 되는 확률
- service rate : 도착한 프로세스를 CPU가 처리하고 내보내는 비율
- 이론적인 방법이라고 할 수 있다
| 구현 후 측정(Implementation&Measurement)
- 실제 시스템에 알고리즘을 구현해보고 실제 작업에 대해 성능을 측정해보는 것
| 모의 실혐(Simulation)
- 알고리즘을 모의 프로그램으로 작성한 후 trace를 입력으로 하여 결과 비교
- 구현 후 측정 방식이 어렵기 때문에 시뮬레이션을 돌리게 된다
- 실제 burst pattern을 따와서 시뮬레이션 프로그램의 input(trace)로 넣어야 신빙성이 있다
나는야 누워있는 개발머신