프로세스 특성 분류
I/O bound process
- CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
- many short CPU bursts
CPU bound process
- 계산 위주의 job
- few very long CPU bursts
CPU Scheduler & Dispatcher
CPU Scheduler
- Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다.
Dispatcher
- CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다.
- 이 과정을 Context Switch라고 한다.
CPU 스케줄링이 필요한 경우
- Running -> Blocked (I/O 요청하는 시스템 콜): nonpreemptive(CPU 자진반납)
- Running -> Ready (할당시간 만료로 timer interupt): preemptive(CPU 강제로 빼앗음)
- Blocked -> Ready (I/O완료 후 인터럽트): preemptive(CPU 강제로 빼앗음)
- Terminatie: nonpreemptive(CPU 자진반납)
CPU 스케줄링의 성능 척도
- CPU utilization (이용률): CPU 이용률
- Throughput (처리량): 단위 시간 당 처리 완료된 프로세스 개수
- Turnaround time (소요시간, 반환시간): CPU 사용 시간 + 기다린 시간
- Waiting time (대기 시간): Ready queue에 머무른 전체 시간 (기다린 시간의 합)
- Response time (응답 시간): 프로세스가 최초로 CPU를 얻기까지 기다린 시간 (최초로 기다린 시간)
CPU 스케쥴링 알고리즘
FCFS(First-come First-Served)
- nonpreemptive
- 먼저 들어온 작업을 순서대로 처리해주는 방법
- CPU burst time이 긴 작업이 먼저 오게 되면 전체 프로세스의 평균 대기 시간이 길어지는 문제가 있다.
- Convoy Effect: 긴 프로세스 뒤에 짧은 프로세스가 위치되어 대기시간이 길어지는 현상
SJF(Shortest Job First)
- CPU burst time이 가장 짧은 프로세스를 먼저 처리한다.
- 대기시간의 평균을 최적화하는 데에 가장 좋은 알고리즘
- Nonpreemptive 방식: CPU를 한번 선점하면 CPU burst가 완료될 때까지 선점 당하지 않음
- Preemptive 방식: 현재 수행중인 프로세스의 남은 burst time 보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김 (SRTF(Shortest Remaining Time First))
- Starvation 문제 발생: Long job은 평생 CPU를 선점할 수 없을 수 있음
- CPU burst time을 정확하게 알 수가 없어서 예측한다.
- 과거의 CPU burst time을 이용해서 추정한다.
- n+1 burst time = a(n 실제 burst time) + (1-a)(n 예측 burst time) => exponential averaging
priority scheduling
- 우선순위가 높은 프로세스가 CPU를 선점한다.
- preemptive, nonpreemptive 모두 구현 가능
- SJF도 priority scheduling의 일종, CPU burst time = priority
- Starvation 문제 발생 가능
- Aging 기법으로 문제 해결
- 대기 시간이 길어질수록 priority를 높여주는 방법
Round Robin
- 모든 프로세스는 동일한 크기의 할당시간을 가짐
- 할당시간이 지나면 CPU는 회수되고 reqdy queue 맨 뒤로 들어감
- preemptive 방식
- 모든 프로세스는 (n-1)q time unit 이상 기다리지 않는다.
- performance
- q large = FCFS
- q small = context switch 오버헤드가 커진다.
- 일반적으로 SJF 보다 평균 turnaround time은 길지만 response time 은 더 짧다.
- burst time이 동일한 잡들을 Round Robin으로 했을 때 turnarount time이 길어지면서 오히려 더 비효율적일 수 있다.
Multilevel Queue
- Ready queue를 여러개로 분할 한다. 프로세스는 각 특성에 맞게 queue에 적재되고 다른 queue로 이동할 수 없다.
- foreground (interactive): Round Robind
- background (batch-no human interaction): FCFS
- 두 Reqdy queue 스케쥴링 방법
- Fixed priority scheduling: 무조건 foreground를 먼저 처리하고 더이상 처리할 foreground가 없을 때 background를 처리하는 방법, starvation 가능성이 있음
- Time slice: 각 큐 CPU time을 적절한 비율로 할당하는 방법 ex. 80% foreground, 20% background
Multilevel Feedback Queue
- 프로세스가 서로 다른 큐 간에 이동이 가능하다.
- aging으로 starvation을 방지할 수 있음
- 보통 가장 우선순위가 높은 queue에 들어와서 정해진 시간 내에 처리가 되지 않으면 다음 큐로 강등되는 방식으로 구현
- Multilevel feedback queue 파라미터 예
- Queue의 수
- 각 큐의 scheduling algorithm
- Process를 상위 큐로 보내는 기준
- Process를 하위 큐로 보내는 기준
- Process가 ready할 큐를 결정하는 기준
특수한 경우의 Scheduling
Multiprocessor Scheduling
- CPU가 여러개 있는 경우의 스케쥴링
- Homogeneous processor 인 경우
- 하나의 Queue를 사용해 각 processor가 process를 꺼내가게 할 수 있다.
- 반드시 특정 processor에서 처리되어야하는 작업의 경우 문제가 복잡해짐
- Load sharing
- 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 매커니즘이 필요하다.
- Symmetric Multiprocessing
- 각 프로세서가 각자 알아서 스케쥴링
- Asymmetric mulltiprocessing
- 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
Real-Time Scheduling
- Hard real-time task의 경우 정해진 시간 안에 반드시 끝내도록 해야하기 때문에 offline에서 스케쥴링을 모두 해놓고 작업을 진행시키는 경우가 많다.
- Soft real-time task(ex. 동영상 스트리밍)는 일반 프로세스에 비해 높은 priority를 갖도록 해야한다.
Thread Scheduling
- Loacl Scheduling
- User Level Thread의 경우 OS가 스레드의 존재를 모르기 때문에 프로세스가 자체적으로 thread library를 이용해 thread 스케줄을 결정한다.
- Global Scheduling
- Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케쥴할지 결정
댓글