운영체제 2023-04-05 수업정리

Flow

• FCFS Scheduling
• SJF Scheduling
• Priority Scheduling
• Round-Robin Scheduling
• Multilevel Queue Scheduling

FCFS Scheduling

---

• 먼저 도착한 프로세스를 먼저 처리하는 Scheduling Algorithm
• non-preemptive scheduling algorithm이다.
• 장점(?)
  • 구조가 단순하여 구형하기가 매우 쉽다.
  • Straving이 발생하지 않는 구조이다. 따라서 모든 프로세스의 실행이 보장된다.
• 단점
  • 도착 순서에 따라 waiting time이 크게 달라진다.
  • convey effect 에 따른 문제로 인해 miminum waiting time을 제공하지 못한다.
    • convey effect : burst time이 짧은 프로세스가 긴 프로세스 뒤에 위치하는 상황
    • 현실에서는 CPU process, I/O process의 속도 차이가 심하기 때문에 매우 큰 단점으로 다가온다. 이는 burst time이 긴 프로세스가 CPU자원을 내려놓을 때까지 다른 프로세스가 대기해야 하기 때문이다.

Example with Gantt Chart

• Waiting time$$P_1=0,\ P_2=24,\ P_3=27$$
• Average Waiting time$$(0+24+27)/3=17$$
• 앞서 살펴본 것처럼 P1이 먼저 수행될 경우 convey effect에 의해 Average Time이 늘어나는 것을 확인할 수 있다.
• 만약 , P2, P3, P1순으로 도착하였다면 평군 waiting time 은 아래와 같다.$$(0+3+6)/3=3$$
  • 앞서 단점으로 언급한 것처럼 도착 순서에 따라 Average waiting time의 편차가 심한 것을 확인할 수 있다.

SJF Scheduling

---

• Shortest Job First Scheduling
• optimal scheduling solution이다.
• 프로세스의 도착 순서와 관계없이, burst time이 짧은 것부터 실행하는 scheduling algorithm이다.
• Priority가 burst time이 작은 순으로 정렬했을 때의 순서와 같은 Priority Scheduling이다.
• 두 프로세스의 CPU burst time이 같다면, FCFS scheduling을 사용한다.
• SJF는 preemptive, non-preemptive모두 구현 가능하다.

Prediction of Burst Time

• SJF는 이론상으로 모든 job들이 최소 waiting time을 가지게 되므로 optimal 하다.
• 하지만 실제 job의 burst time은 실행 전에 알 수 없다.
• 따라서 이전 실행시간에 따른 예측값을 burst time으로 사용한다.
• 이를 위해 Local linear regression을 사용한다.$$t_n\ :\ actual\ length\ of \ n^{th}\ CPU\ burst$$$$\tau_{n+1}\ :\ predicted\ value\ for\ next\ CPU\ burst$$$$\alpha,\ (0\leq\alpha\leq 1)$$$$\tau_{n+1} = \alpha t_n+(1-\alpha)\tau_n$$
  • 보통 알파 값은 1/2로 설정된다.
• 이 공식을 이용해서 실행 시간을 예측해 보면 아래와 같다. 파란색 선은 예측된 burst time, 검은색 선은 실제 burst time이다.

Example with Gantt Chart

• Average Waiting Time$$P_1=3,\ P_2=16,\ P_3=9,\ P_4=0\ \ Avg = (3+16+9+0)/4=7$$

Shortest-Time-to-Completion First(STCF)

• SJF가 Preemptive로 동작하는 경우이다.
• Preemptive Shortest Job First(PSJF)라고 부르기도 한다.
• 완료까지 남은 시간이 가장 적은 job을 우선적으로 실행한다.
• response time 관련 issue가 있다.(Starving 등)
  • 실행시간이 긴 프로세스가 waiting 중일 떄, 계속해서 실행시간이 짧은 프로세스가 ready하게 되면, 실행시간이 긴 프로세스는 영원히 실행되지 않을 것이다.

Priority Scheduling

---

• 각 프로세스는 priority값을 가지게 된다.
• CPU는 priority가 높은 프로세스를 먼저 처리한다.
• priority가 같은 프로세스에 대해서는 FCFS로 처리한다.
• priority는 internally, externally로 모두 설정 가능하다.
• SJF scheduling은 priority scheduling의 한 종류이다.
• Priority Scheduling은 preemptive, non-preemptive모두 구현 가능하다.

Problem

• SJF에서도 다루었듯이, 어떤 프로세스가 낮은 우선순의를 가지고 있을 경우, 해당 프로세스는 영원히 실행되지 않을 수도 있다.
  • 이를 indefinite blocking 또는 Starvation 이라고 한다.
• Starvation은 aging기법으로 해결 가능하다.
  • 시스템에서 오랬동안 waiting하는 job의 priority를 점진적으로 증가시키는 것

Example with Gantt Chart

Round Robin(RR) Scheduling

---

• 각각의 프로세스는 time quantum(usually 10~100 ns, also known as schedular quantum)동안 실행된다. time quantum이 끝나면 ready queue로 돌아가고 다음 프로세스가 실행된다.
• run queue에 있는 job들을 순차적으로 처리한다. run queue는 circular FIFO형태로 구성된다.
• run queue의 모든 job들이 끝날 때까지 이를 반복한다.
• timer-interrupt에 의해 일어난다. 따라서 time quantum은 timer-interrupt period의 배수여야 한다.
• Preemptive Scheduling Algorithm with no Starvation
• Starvation문제가 없기 때문에 fair하다. 하지만 Turnaround time 등의 metric 지표에 의하면 좋지 않은 성능을 보인다.

비교

• Round Robin Scheduling은 Preemptive Scheduling이지만 Starvation문제로부터 자유롭다.
  • aging등의 솔루션이 필요없다.
  • 이는 N개의 job이 있을 때, 어떠한 job이 최소한 n-1개의 job이 실행된 이후에는 실행이 보장되는 특성이 있기 때문에 가능하다.
• 일반적으로Round Robin은 SJF와 비교하여 response time은 좋은 지표를 보이지만, turnaround에서는 다소 떨어지는 결과를 보여 준다.
• time quantum이 큰 값을 가질수록 FCFS와 같은 성능으로 수렴하고, 작은 값을 가질수록 사실상 process sharing(1/n의 속도로 동작)이 된다.
  • context switching time에 의한 성능 오버헤드가 커진다.
  • 이를 고려하여 time quantum은 통상적으로 context switching time이 10us보다 작을 때, 10~100ns정도로 설정하는 것이 적당하다.
  • 또한, time quantum이 너무 작은 값을 가지게 되면 대부분의 프로세스가 여러 번 자신의 차례를 맞이하고 나서 종료되게 된다. 이는 turnaround time을 증가시키는 원인이다.
  • 물론, time quantum이 짧다면 response time을 중요시하는 metric에서는 좋은 지표를 얻을 수 있다.
• 경험적으로 CPU burst의 80%가량이 time quantum보다 작을 경우 가장 높은 성능을 보인다고 알려져 있다.

Example with Gantt Chart

• Average Waiting Time$$P_1=(0+6),\ P_2=4,\ P_3=7\ Avg = (6+4+7)/3=5.66$$

Multilevel Queue Scheduling

---

• Ready Queue를 memory size, process type, process priority등 여러 기준으로 나누어 여러 개를 가진다.
  • response time이 작아야 하는 경우는 RR을 사용
  • turnaround time을 줄여야 하는 령우 SJF, STCF 사용
  • foreground process 는 RR scheduling을 사용하고, background process 는 FCFS를 사용하는 것을 예시로 들 수 있다.
• 각 ready queue들은 fixed priority를 가지거나 Time slice를 바탕으로 동작한다.
  • fixed priority : 각 ready queue마다 priority가 존재하며, 특정 queue의 동작이 모두 처리된 후 다음 priority queue의 동작이 처리된다.
    • Starvation이 발생할 가능성이 있다.
  • Time Slice : 각 ready queue에 대해 단위 시간 당 일정 비율의 CPU점유를 주는 방식
    • Starvation문제에서 자유롭다.
    • foreground process에 대해서 time slice가 80%, background process에 대해서 time slice가 20%로 설정하여 scheduling하는 것을 예시로 들 수 있다.(당연하지만 각각의 queue는 별도로 존재하는 상황이다.)
• Fixed priority방식으로 MLQ(Multilevel Queue)를 구현했을 경우 Starvation문제를 해결하기 위해 aging을 사용한다.
• 아래는 fixed priority방식으로 구현한 MLQ의 예시이다.
  • ststem process queue에 있는 process가 가장 먼저 실행되고 나면, 그 다음 priority의 interactive process queue에 있는 process가 실행되는 방식이다.
  • 앞서 설명한 것처럼 starvation의 가능성이 있으므로 aging을 사용해야 한다.(MLFQ)

Multilevel Feedback Queue(MLFQ)

• MLQ에서 각각의 queue에 있던 process들이 다른 level의 queue로 옮겨갈 수 있는 구조이다.
  • 따라서 MLFQ는 아래와 같은 method를 추가적으로 제공해야 한다.
    • Method used to when to upgrade a process
    • Method used to when to demote a process
• Example