리루
Process scheduling 본문
1. CPU Scheduler
- nonpreemptive step : running->waiting, terminate (나로 인해서 발생)
- preemptive step : running->ready, waiting->ready (나보다는 다른 작업에 의해서 발생)
1-1) Dispatcher
- 선택된 프로세스에 CPU의 제어권을 준다.
- Dispatch latency : 한 프로세스를 멈추고 다음 프로세스를 실행할때 까지의 시간
- Context switching 포함
- Switching to user mode
- jumping to the proper location in the user program to restart the program
1-2) Scheduling Goal
- All systems
- Fairness : fair share of the CPU
- Balance : balance of H/W usage
- Batch System : 하나 끝나면 하나 처리해주는 system, 시간적 요소 보다는 Throughput이 더 중요시됨
- Throughput : maximize jobs per hour
- Turnaround time : minimize time
- CPU utilization : keep the CPU busy all the time
- Interactive system
- Response time : minimize average time spent on ready queue
- Waiting time : minimize average time spent on wait queue
- Proportionality : meet user's expectations(비례적으로)
- Real-time system (시간제약 조건)
- Meeting deadline : 시간제약 조건을 지키는 것이 가장 중요
- Predictability : Avoid quality degradation(품질저하) in multimedia system
1-3) Scheduling non-goals
- Starvation : Poor scheduling policy and synchronization can cause starvation
1-4) Scheduling
[1] FCFS/FIFO : First-Come, First-Served
- Typically, non-preemptive
- No starvation
- 가장 fair한 알고리즘이라 가장 많이 사용된다.
- Problems
- Convoy effect, 실행시간이 짧더라도 앞의 대기열이 많을 시에는 오래 기다려야한다.(전체 평균 waiting time 측면에서 좋지않다.), SJF 알고리즘으로 해결.
[2] SJF : Shortest Job First
- CPU burst 시간이 가장 짧을 것이라고 예상되는 작업부터 실행
- Non-preemptive
- 평균대기시간이 가장 짧다.
- Problems
- Impossible to know size of future CPU burst (수행시간에 대한 예측이 어렵다)
- 작업 시간이 긴 작업 앞에 짧은 작업시간의 작업이 계속 들어올 때.
[3] Priority scheduling
- 생성될 때, 해당 프로세스의 중요도에 따라 우선순위 부여
- SJF 또한 Priority scheduling의 일종
- 우선순위가 있다보니 Starvation 발생 가능성 있음
- Aging 방식을 통한 해결(As time progresses increase the priority of the process)
- 우선순위가 같은 작업들 간에는 Round Robin이라는 Time sharing 방식을 적용.
[4] Round Robin (Time sharing)
- 각 Process는 Time quantum이라는 작은 단위의 CPU time을 갖는다.(보통 10-100ms)
- Time quantum을 모두 소진한 process는 ready queue 제일 끝으로 이동한다.
- Waiting time, Response time 측면에서 훌륭하다.
- Problems
- Time quantum이 너무 크면 FIFO와 같아진다.
- Time quantum이 너무 작으면, Context switching overhaed가 너무 커진다.
- A rule of thumb : 80% of the CPU bursts should be shorter than the time quantum
[5] Multilevel Feedback Queue
-
- 윗쪽에 위치해 있을 수록 우선순위가 높다.
- 윗쪽에 있을수록 CPU-Burst가 작다(= I/O bound일 가능성이 크다, 사용자와 Interactive해야 해서 우선순위가 높다.)
- 제일 아래 FCFS는 CPU Bound일 가능성이 크다.(처리율을 높혀야 한다. 시간이 중요한 애들이 아니라서 I/O Bound보다 천천히 수행해도 된다.)