운영체제(OS) - CPU Scheduling (4)
본 글은 (KOCW) 운영체제, 이화여자대학교 반효경 교수님의 강의를 듣고 내용을 요약 및 정리했습니다.
개인 공부에 목적이 있으며, 자세한 사항은 http://www.kocw.or.kr/home/cview.do?mty=p&kemId=1046323에 참고하시면 됩니다.
Chapter 5.
- CPU Scheduling 1 - 1시간 5분
- CPU Scheduling 2 / Process Synchronization 1 - 1시간 7분
(+) 인프런의 주니온 박사님의 운영체제 공룡책 강의를 듣고 내용을 보충했습니다. 자세한 사항은 여기를 참고하시면 됩니다.
CPU and I/O Bursts in Program Execution
- CPU와 I/O가 번갈아가면서 실행한다.
- 프로그램은 CPU burst와 I/O burst의 연속이다. 하지만, 프로그램의 종류에 따라 각 버스트들의 빈도 및 길이가 다르다.
- 여러종류의 job(=process)이 섞여있기 때문에 CPU 스케쥴링이 필요하다.
CPU-burst Time의 분포
- 여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다.
- Interactive job에게 적절한 response 제공 요망
- CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용
프로세스의 특성 분류
- 프로세스는 그 특성에 따라 다음 두 가지로 나눔
- I/O-bound process
- CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
- (many short CPU bursts)
- CPU-bound process
- 계산 위주의 job
- (few very long CPU bursts)
- I/O-bound process
CPU Scheduler & Dispatcher
- 시스템은 프로세스 이용률을 극대화하고 사용자는 편리하고 융통성있길 원한다.
- CPU Scheduler : Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
- 스케줄러는 많은 요소를 고려하여 스케줄링을 수행한다.
- performance, throughput, priority, fairness, realtime-ness, workload adaptation
- 스케줄러는 많은 요소를 고려하여 스케줄링을 수행한다.
- Dispatcher : CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다. (위 그림 참조) 이 과정을 context switch (문맥 교환)라고 한다.
- 실행 중인 프로세스를 전환하려면 시스템이 현재 프로세스의 상태(state)를 저장하고 다음 프로세스의 상태를 로드해야 한다.
- context switch는 오버헤드(overhead)이다.
- CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다.
- Running -> Blocked (ex. I/O 요청하는 시스템 콜)
- Running -> Ready (ex. 할당시간만료로 timer interrupt)
- Blocked -> Ready (ex. I/O 완료후 인터럽트)
- Terminate
- 1,4에서의 스케줄링은 nonpreemptive (비선점형) (=강제로 빼앗지 않고 자진 반납)
- All other scheduling is preemptive (선점형) (=강제로 빼앗아 context switch를 시행한다.)
Scheduling Criteria (성능 척도)
- CPU utilization (이용률) : 전체 시간 중 CPU가 놀지 않고 일한 비율
- Throughput (처리량) : 주어진 시간동안 과연 몇 개의 작업을 처리했느냐
- Turnaround time (소요시간, 반환시간) : [고객 입장] CPU를 얻어서 쓰고 나갈 때까지의 시간
- Waiting time (대기 시간) : [고객 입장] CPU를 쓰기 위해 기다린 시간
- Response time (응답 시간) : [고객 입장] : 처음으로 CPU를 얻기까지의 시간
Scheduling Algorithms
FCFS (First-Come First-Served)
- 먼저 온 순서대로 처리한다.
- 스케줄 순서를
Gantt Chart로 나타내면 다음과 같다. - FCFS는 앞에 어떤 프로세스가 버티냐에 따라서 기다리는 시간에 많은 영향을 끼친다.
- FCFS 알고리즘은 non-primitive이다.
- Convoy effect : 긴 프로세스 앞에 놓인 짧은 프로세스가 있을 때
- 다른 모든 프로세스는 하나의 큰 프로세스가 CPU에서 벗어날 때까지 기다린다.
- Wiating time for $P_1$ = 0; $P_2$ = 24; $P_3$ = 27
- Average waiting time : (0 + 24 + 27)/3 = 17
SJF (Shortest-Job-First)
- 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용한다.
- CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
- Two schemes:
- Nonpreemptive : 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption)당하지 않음
- Preemptive : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
- 이 방법을 Shortest-Remaining-Time-First (
SRTF)이라고도 부른다.
- 이 방법을 Shortest-Remaining-Time-First (
- SJF is optimal
- 주어진 프로세스들에 대해
minimum average waiting time을 보장한다.
- 주어진 프로세스들에 대해
- Waiting Time for $P_1$=3, $P_2$=16, $P_3$=9, $P_4$=0
- Average Waiting Time: (3+16+9+0)/4=7
Priority Scheduling
- 각 job은 우선순위(priority)가 있다.
- 우선순위 스케줄링이라고 하는데, highest priority를 가진 프로세스에게 CPU 할당한다.
- smallest integer = highest priority
SJF는 일종의 priority scheduling이다.priority= predicted next CPU burst time
- 문제점 : (Starvation) 낮은 우선순위 프로세스는 절대로 실행되지 않는다.
- 해결 : (Aging) 오래 기다리면 우선순위를 높여준다.
Round Robin (RR)
- 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가진다.
- time quantum : 일반적으로 10-100 milliseconds
- 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
- n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
- 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.
- Performance
- q large -> FCFS
- q small -> context switch 오버헤드가 커진다.
- RR 스케줄링 알고리즘은 preemptive이다.
- 프로세스의 CPU 버스트가 1회 퀀텀을 초과하면 해당 프로세스가 우선 처리되고 다시 준비 대기열에 들어간다.
- Waiting Time for $P_1$=10−4=6, $P_2$=4, $P_3$=7
- Average Waiting Time: (6+4+7)/3=5.66
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
- Possibility of starvation
- Time slice
- 각 큐에 CPU time을 적절한 비율로 할당
- ex. 80% to foreground in RR, 20% to background in FCFS
- Fixed priority scheduling
Multilevel Feedback Queue
- 프로세스가 다른 큐로 이동 가능
- 에이징(aging)을 이와 같은 방식으로 구현할 수 있다.
- Multilevel-feedback-queue scheduler를 정의하는 파라미터들
- Queue의 수
- 각 큐의 scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 내쫓는 기준
- 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준
Multiple-Processor Scheduling
- CPU가 여러 개인 경우 스케줄링은 더욱 복잡해진다.
- load balancing은 워크로드를 균등하게 분산하려는 시도이다.
- Homogeneous processor인 경우
- Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
- 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해진다.
- Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요하다.
- 별개의 큐를 두는 방법 vs. 공동 큐를 사용하는 방법
- Symmetric Multiprocessing (SMP)
- 각 프로세서가 각자 알아서 스케줄링(self-scheduling) 결정
- 각 peer CPU 프로세서가 모든 일을 처리
- Asymmetric multiprocessing
- 하나의 프로세서(=master node)가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따른다.
- 각 프로세서는 특정한 작업에 할당한다.
Real-Time Scheduling
- Hard real-time systems : Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 한다.
- Soft real-time computing : Soft real-time task는 일반 프로세스에 비해 높은 우선순위를 갖도록 해야 한다.
Thread Scheduling
Local Scheduling: User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정Global Scheduling: Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
Algorithm Evaluation
Queueing models: 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산Implementation (구현) & Measurement (성능 측정): 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교Simulation (모의 실험): 알고리즘을 모의 프로그램을 작성 후 trace를 입력으로 하여 결과 비교
댓글남기기