강의 주소 : 이화여대 반효경 교수님 운영체제 강의 (2014년)
Chapter 5. CPU Scheduling 1, 2
5.1 Scheduling Criteria(성능 척도)
CPU utilization(이용률)
시스템 입장 전체 시간 중 CPU가 놀지 않고 일한 시간의 비율
Throughput(처리량)
시스템 입장 주어진 시간 동안 몇 개의 작업을 완료했는지
Turnaround time(소요시간, 반환시간)
프로세스 입장 CPU를 사용하러 들어오고 CPU를 사용한 후 나가는 시간
Waiting time(대기 시간)
프로세스 입장 CPU를 사용하기까지 기다린 시간
Response time(응답 시간)
프로세스 입장 CPU를 사용하러 들어와서 CPU를 처음 사용하기까지 걸린 시간
5.2 Scheduling Algorithms
1. FCFS(First-Come-First-Served)
먼저 온 순서대로처리
-> 단점 1. Convoy effect(short process behind long process) : 위 사진처럼 CPU 사용시간이 긴 작업이 먼저 들어올 경우, 작업이 효율적으로 처리되지 못함
2. SJF(Shortest-Job-First)
- 각 프로세스의 다음번 CPU burst time을 기반으로 스케줄링에 활용
CPU birst time이 가장 짧은 프로세스를 제일 먼저 스케줄- Nonpreemptive
- 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점당하지 앟음
- Preemptive
- 현재 수행중인 프로세스의 남은 burst time보다 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
- 이 방법을
SRTF(Shortest-Remaining-Time-First)라고도 부름 - optimal : 주어진 프로세스들에 대해 minimum average waiting time 보장
-> 단점 1. starvation = 기아 현상(CPU 사용 시간이 긴 작업들은 CPU를 할당받지 못할 수도 있음)
-> 단점 2. CPU 사용 시간을 미리 알 수 없음 : 과거의 CPU burst time을 이용해 추정(exponential averaging)
3. Priority Scheduling
우선순위(highest priority)가 가장 높은 프로세스에게 CPU 할당- smallest integer = highest priority
- Nonpreemptive/Preemptive로 나뉨
- SJF도 일종의 priority scheduling이다.
-> 단점 1. starvation = 기아 현상 -> Aging(노화) 기법 도입
4. Round Robin(RR)
현대적인 컴퓨터에서 사용하는 스케줄링 기법- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
할당 시간이 지나면 프로세스는 선점 당하고 ready queue의 제일 뒤에 가서 줄을 섬- 응답 시간이 빨라짐
대기 시간과 CPU 사용 시간이 비례함- q large : FCFS와 비슷해짐 & q small : context switch 증가로 오버헤드가 커짐
- 일반적으로 SJF보다 average turnaround time이 실시간 response time은 더 짧음
5. Multilevel Queue
- Ready queue를 여러 개로 분할
- foreground(interactive) : 사용자와 소통 중심
- background(batch ~ no human interaction)
- 각 큐는 독립적인 스케줄링 알고리즘을 가짐
- foreground : RR
- background : FCFS
- 큐에 대한 스케줄링이 필요
- Fixed priority scheduling : serve all from foreground then from background -> starvation
- 각 큐에 CPU time을 적절한 비율로 할당 : 예) 80% to foreground in RR, 20% to background in FCFS
6. Multilevel Feedback Queue
- CPU를 기다리는 프로세스를 여러 큐에 줄세운다는 측면에서 멀티 레벨 큐와 동일하나
프로세스가 다른 큐로 이동 가능하다는 점이 다름 - 에이징을 다음과 같은 방식으로 구현할 수 있음
- Queue의 수
- 각 큐의 scheduling algorithm
- 프로세스를 상위 큐/하위 큐로 보내거나 내쫓는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
- CPU 사용 시간이 짧은 프로세스에게 우선 순위를 주는 방식
7. Multiple-Processor Scheduling
CPU가 여러 개인 경우의 스케줄링
- Homogeneous processor인 경우
- 큐에 한 줄로 세워 각 프로세서(CPU)가 알아서 꺼내가게 할 수 있음
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
- Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
- 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
- Symmetric Multiprocessing(SMP)
- 각 프로세서가 각자 알아서 스케줄링 결정
- Asymmetric Multiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
8. Real-Time Scheduling
- Hard real-time systems : 정해진 시간 안에 반드시 끝내도록 스케줄링
- Soft real-time computing : 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
9. Thread Scheduling
- Local Scheduling : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정(프로세스 내부에서 어떤 스레드에게 CPU를 줄지 결정, 커널은 모름)
- Global Scheduling : Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정(OS가 알고리즘에 근거해 어떤 스레드에게 CPU를 줄지 결정)
5.3 Algorithm Evaluation
어떤 알고리즘이 좋은지를 평가하는 방법
- Queueing models : 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산(이론적으로 사용)
- Implementation(구현) & Measurement(성능 측정) : 실제 시스템에 알고리즘을 구현해 실제 작업에 대해 성능을 측정, 비교
- Simulation(모의 실험) : 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교
Software Engineer