08 > CPU scheduling

* 해당 게시물은 경북대학교 컴퓨터학부 강의초빙교수, 배준현 교수님의 강의를 보고 작성되었음을 미리 알려드립니다. ( 개인적인 공부를 정리한 글입니다. )

 

> 주니온 TV Youtube Channel.  https://www.youtube.com/channel/UCOcPzXDWSrnaKXse9XOPiog

주니온TV 아무거나연구소

 

> 주니온 TV Inflearn page.  https://www.inflearn.com/users/@joonion

주니온님의 소개 - 인프런 | 온라인 강의 플랫폼

---

[  ] CPU Scheduling is

- the basis of multprogrammed operating systems.

- The objective of multiprogramming is to have some processes running at all times and to maximize CPU utilization.

시피유가 노는 시간을 없애서 효율적으로 사용하기 위한 목적이 크다.

 

- selects a process from the processes in memory that are ready to execute and allocates the CPU to that process.

 

[★] Preemptive vs Non-preemptive 선점, 비선점

- Non-preemptive scheduling is a process to keep the CPU until it releases it, either by terminating or by switching to the waiting state.

작업이 끝날 때 까지 CPU를 선점함.

- Preemptive scheduling is a process can be preempted by the scheduler.

고의적으로 CPU의 선점을 바꿀 수 있음.

 

[  ] The dispatcher is

- a module that gives control of the CPU's core to the process selected by the CPU scheduler.

- The functions of dispatcher:

  switching context from one process to another

  switching to user mode

  jumping to the proper location to resume the user program

 

- The dispatcher latency is the time to stop one process and start another running.

 

Figure 5.3 The role of the dispat c her.

[  ] Scheduling Criteria

- CPU utilization: to keep the CPU as busy as possible.

- Throughput: the number of processes completed per time unit.

- ★Turnaround time:

  how long does it take to execute a process?

  from the time of submission to the time of completion.

실행부터 종료까지의 시간을 최소화 시키는 것.

- ★Waiting time:

  the amount of time that a process spends waiting in the ready queue.

  the sum of periods spend waiting in the ready queue.

ready 시간을 최소화한다.

- Response time:

  the time it takes to start responding

 

[  ] FCFS : First-come, First-served.

- the simplest CPU-scheduling algorithm.

FIFO Queue를 사용해서 쉽게 구현 가능.

ex) Process / Burst Time : P1 / 24, P2 / 3, P3 / 3

If the processes arrive in the order P1, P2, P3

waiting time = P1 / 0, P2 / 24, P3 / 27 = Average / 17

turnaround time = P1 / 24, P2 / 27, P3 / 30

 

If the processes arrive in the order P3, P2, P1

waiting time = P1 / 6, P2 / 3, P3 / 0 = Average / 3

turnaround time = P1 / 30, P2 / 6, P3 / 3

 

- Convoy Effect

앞에 있는 긴 Process때문에 뒤에 있는 짧은 Processes이 다 밀린다.

호송하는 것처럼 뒤에 줄줄이 달려있는 상태를 의미한다.

  all the other processes wait for the one big process to get off the CPU.

  results in lower CPU and device utilization than might be possible

  if the shortest processes were allowed to go first.

 

[  ] SJF : Shortest Job First

- Shortest-next-CPU-burst-first scheduling.

- The SJF scheduling algorithm is provably optimal, it gives the minimum average waiting for a given set of processes.

완벽하게 CPU burst를 계산해서 정렬할 수는 없기에 예측을 해서 구현한다.

 

- How to predict the next CPU burst?

과거의 측정된 값을 사용한다.

과거에 측정된 값이 계속 일정하다는 보장이 없기에, 지수적 평균을 내서 사용한다.

a = 0 > Tn (과거만을 생각함), a = 1 > Tn1 (최근만을 생각함)

사실상 이론적인 최적화이고 실질적으로 사용하는 알고리즘은 아니다.

 

Figure 5.4 Predict i on of the length of the next CPU burst.

 

[  ] SRTF (SRTF : Shortest Remaining Time First)

- Preemptive SJF scheduling

프로세스가 점유하고 있을 때, remain시간과 비교해서 더 짧은 Burst Time이 들어오면 CPU를 이후의 작업에 선점시킨다.

 

[★] RR : Round-Robin

- Preemptive FCFS with a time quantum.

- A time quantum (or time slice) is a small unit of time.

  generally from 10 to 100 milliseconds in length.

- The ready queue is treated as a circular queue.

- The scheduler goes around the ready queue,

  allocating the CPU to each process

  for a time interval of up to 1 time quantum.

 

ex) Process / Burst Time : P1 / 24, P2 / 3, P3 / 3

If the processes arrive in the order P1, P2, P3

waiting time = P1 / 6, P2 / 4, P3 / 7 = Average / 17

turnaround time = P1 / 30, P2 / 6, P3 / 10

When we use a time quantum of 4 milliseconds.

RR algorithm은 Time slice를 얼마나 주냐에 따라 성능이 달라진다.

Figure 5.5 How a smaller time quantum in c reases context switches.

Figure 5.6 How turnaround time varies with the time quantum.

 

[  ] Priority-based

- A priority is associated with each process,

  and the CPU is allocated to the process with the highest priority.

  Processes with equal priority are scheduled in FCFS order.

- Note that the SJF is a special case of the priority-based scheduling.

  in this case, the priority is the inverse of the next CPU burst.

 

ex) Process / Burst Time / Priority

P1 / 10 / 3

P2 / 1 / 1

P3 / 2 / 4

P4 / 1 / 5

P5 / 5 / 2

If the processes arrive in the order P1, P2, P3

waiting time = P1 / 6, P2 / 0, P3 / 16, P4 / 18, P5 / 1 = Average / 8.2

turnaround time = P1 / 16, P2 / 1, P3 / 18, P4 / 19, P5 / 6

 

- Priority scheduling can be either preemptive or non-preemptive.

  preemptive = SRTF, non-preemptive = SJF

 

- The problem of starvation (indefinite blocking)

우선순위가 높은 Process는 계속해서 뒤로 밀려 처리가 안될 수 있다.

 

보통은 RR과 Priority 를 혼합해서 사용한다.

Priority를 주되, 처리는 끝날 때 까지 하지 않고, time quantum에 따라 쪼개어 처리한다. 즉 마지막 우선순위인 프로세스도 CPU를 점유받게 된다.

 

[  ] MLQ : Multi-level Queue

Figure 5.8 Multi-L e vel Queue scheduling.

 

 

[  ] MLFQ : Multi-level Feedback Queue

Figure 5.9 Multi-Level Feedback Qu e ue scheduling.

 

 

현대에서는 Process scheduling을 하지 않는다. 왜? Thread scheduling로 하기 때문에.

즉 Kernel threads만 관리한다. user thread는 library가 관리하기에 kernel은 user thread를 알 수 없다.

단순히 맵핑만 해서 service 시켜주면 된다.

O/S kernel은 CPU scheduling을 가지고 kernel thread를 관리한다.

 

[  ] Real-Time Operating System.

주어진 시간 내에 task를 완료할 수 있어야한다.

- soft real-time systems > critical process를 반드시 끝내지는 않지만, noncritical 보다는 먼저 끝낸다.

- hard real-time systems > task가 반드시 deadline 안에 실행되는 것을 의미한다.