Ch 5-(1),(2) Process Scheduling

#CPU Scheduling

 

 

=> 여러명의 사람이 하나의 TV를 언제 볼 지 나누는 것처럼, CPU를 각각의 프로세스가 언제 차지할지를 할당하는 것을 CPU Scheduling이라고 한다.

 

 

 

: CPU를 스케줄링 할때도 목적이라는 것이 존재한다. scheduling algorithm을 통해서 얻는 결과 또는 목적이라는 게 존재하는데, 이를 scheduling criteria라고 한다.

 

 

#preemptive scheduling

: 기존 프로세스가 안끝났어도 우선순위 높은 task가 도착하면 그 우선순위 높은 task가 먼저 실행된다.

ex) 아들이 tv를 보고 있는데, 아버지가 집에 도착하면 아들을 방으로 들여보내고 본인이 tv를 본다.

 

#non-preemptive scheduling

: 우선순위 높아도 기존 task가 종료되길 기다려준다.

 ex) 아버지가 집에 도착했지만, 아들의 애니메이션이 끝날때까지 기다려준다.

 

 

#Basic Concepts

  1. property of process

: process에서는 CPU burst와 I/O burst를 번갈아가면서 수행한다.

 

 

- CPU burst는 복잡한 수학연산을 실행하는 burst로, 시간이 좀더 오래 걸린다. 이때 CPU burst를 중점적으로 하는 scheduling을 CPU-intensive하다고 한다.

- I/O burst는 word processor와 같이 계속 I/O 를 하는 작업으로, 짧게 번갈아가면서 수행된다. 이를 IO-intesive한다고  한다. (Intensive 대신에 bound를 사용해도 똑같은 말이다.)

 

cpu burst가 io burst보다 시간이 오래 걸린다.

 

 

 

따라서 Scheduling에는 rule이 하나 존재하는데,

 바로 I/O bound process에게 더 높은 priority를 주어서, 프로세스가 Ready queue 에서 기다리는 시간을 최소화하는 것이다. =>  I/O 가 빨리빨리 먼저 처리되면은 프로세스가 덜 기다려도 된다.

 

 

#CPU Scheduler

: cpu scheduler가 하는 일은 메모리에서 실행할 준비가 되어있는 process를 선택해서, 선택된 프로세스를 cpu에게 allocate하는 것이다.

 

-CPU scheduling을 결정해야 할 때는 네가지의 경우일 때 가능하다. 

 1. Switches from Running to waiting state

 2. Switches from running to ready state

: 위 두가지의 경우일 때는 running state의 프로세스가 공석이므로, ready 상태의 프로세스 중 하나를 선택해서 running state로 바꿔준다.

 

 3. Switches from waiting to ready

: waiting에서 ready 상태로 바뀐 task가 우선순위가 높다면, 기존 수행됐던 task를 ready 상태로 바꾸고, 우선순위가 높은 task를 먼저 실행한다.

 

4. Terminates (from running to termination)

: terminate 되면은 running state에서 돌아가는 프로세스가 하나도 없기 때문에 선택을 해주어야 한다.

 

1, 4 번째 case는 non-preemptive scheduling으로, CPU를 자발적으로 반환하는 경우이다.

1, 2, 3, 4 번째 case 모두 preemptive scheduling이 가능하다.

 

 

 

# 스케줄러는 어떻게 decision을 내리는가?

1. Non-preemptive or cooperative (프로세스 간에 도움이 필요하다)

  : 중요한 것은 process가 자발적으로 cpu를 놓았는가? 이다. 두가지 경우가 존재한다.

 - process가 block 되었을 때 ( I/O 요청하여 running-> waiting state로 바뀌었을때)

 - process가 terminate 되었을 때

 

2. Preemptive (이 때, 기존 수행되었던 task 문맥을 저장하고, 새로 수행되는 task의 문맥을 load해야 한다,)

- 위 경우 둘 다 포함된다.

 - Event가 종료되어서 ready state로 block되었ㅇ을 때

 - Timer interrupt : 가장 대표적인 예시이다.

 - shared data access

 

+) Preemption scheduling에서 고려해야 할 사항은?

: kernel code 수행 중인데 preemption 일어났다고 하자, 이와 같은 경우 어떻게 처리하는가?

: shared data 영역을 다른 process가 읽는다면?

 

 

 

 

# Kernel에서 pre/ non-pre를 어떻게 구별하는가?

 

 

 

- A 가 커널에게 system call을 요청했을 때,  A system call 이 수행중이데 우선순위 높은 B가 ready state가 되었다면

preemption이 허용되었을 시에는 프로세스 B가 먼저 수행된다.

- 그렇지만 A system call 이 끝날 때 까지 기다린다면, non-preemptive kernel이다.

=> 거의 오래된 버전의 unix는 system call이 끝나길 기다린다. non-preemptive model이 더 간단하기 때문에 채택되었다.그렇지만 매우 부적절한 모델이다. preemption이 지원되어서 긴박한 task부터 빠르게 완료될 수 있도록 지원해야 되기 때문이다.

 

+) 커널 내에서 수행될 경우에, interrupt routine 때는 preemption을 허용하지 않는다. 

-> interrupt는 빠르게 실행되어야 하기 때문이다. 

= system call때는 preemption이 가능하지만, interrupt routine때는 preemption이 허용되지 않는다.

 

---

#Dispatcher

-Dispatcher에서는 무슨 일을 하는가?

 1. switching context

 2. swiching to user mode (새로운 task 수행을 위해서)

 3. jumping to the proper location in the user program to restart that program

 

+) Dispatch latency 란?

: dispatcher가 하나의 프로세스 수행을 멈추고, 새로운 프로세스가 running state로 진입할 때 까지 걸리는 시간이다.

: 시간이 오래걸리는 연산을 줄이기 위한 기법이 개발되어 왔다.

 

 

 

#Scheduling criteria

: Scheduling algorithm이 추구하고자 하는 목적, 또는 기준이다.

 

1. CPU utilization

: CPU가 실제로 일하는 시간을 비율로 나타낸 것으로, ( 실제로 일한 시간/ 실제로 일한 시간+ idle한 시간) 의 비율을 의미한다. 

2. Throughput

: 특정 시간 내에 unit에서 process 수행을 완료한 개수 => 높을 수록 cpu를 잘 이용한 것이다.

=> 전체 프로세스에 적용되는 기준이다.

 

3. Turnaround time

: 프로세스 끝나는 시간 - 시작 시간

4. Waiting time

: ready queue에서 기다린 시간

5. Response time

: 첫번째로 request가 실행될 때 까지 걸리는 시간

=> 세가지 프로세스는 개별 프로세스에 적용되는 기준이다.

 

 

turnaround -프로세스 전체 걸린 시간, waiting time- ready queue에서 기다린 시간.

 

=> response time은 처음 cpu burst, 즉 response가 일어날때 까지 걸린 시간이고,

 waiting time은 ready queue에서 기다린 총 시간이다.

 따라서 a의 response time은 a, waiting time은 (a+b) 시간 만큼 걸린다.

 

 

 

 

---

1. FCFS scheduling: first come, first served scheduling

: 먼저 온 순서대로 우선순위를 높게 준다.

 

 

 

=> 예시로써 확인해보자. 각각 process들의 burst time을 차트로 정리하면 waiting time이 한눈에 확인이 쉽다.

1. waiting time => p1=0, p2= 24, p3=27

2. average waiting time => (24+0+27)/3= 17

 

 

 

 

=>  p2, p3, p1 순서대로 도착했다고 가정해보자.

 p1= 6초, p2= 0초, p3=3초 기다렸고, average waiting time도 3초라 이전의 케이스보다 훨씬 낫다

* 어떻게 도착하느냐에 따라서 average waiting time이 상당히 차이가 많이 난다. 

 

+) Convoy effect란?

=> long process이후에 short process가 오는것으로, average waiting time을 높이는 문제가 발생한다.

 : 이를 해결하고 scheduling decision을 잘 내리기 위해서 short process즉, cpu burst가 짧은 i/o bound process 에게 우선순위를 높여주면 waiting time을 효과적으로 줄일 수 있다.

 

 

---

2. Shortest-Job-First (SJF) scheduling

:CPU burst 크기가 할당되어 있을때, 가장 짧은 CPU burst length를 갖는 프로세스에게 우선순위를 높게 준다.

=> 두가지 방법이 존재한다.

 

1. Non-preemptive: CPU가 이미 프로세스에게 할당되었으면 cpu burst가 끝날때까지 기다린다.

2. Preemptive: Shortest-remaining-time-first (SRTF)으로, 먼저 수행된 task가 있어도, 새로 도착한 task의 수행 시간이 짧다면 새로운 task로 context를 수행하는 것이다. (수행 시간이 남은걸로 계산한다)

 

=> SJF는 상당히 바람직한 최적의 스케줄링으로, average waiting time을 최소화 할 수 있다.

: I/O bound가 먼저 수행되는게 average waiting time 측면에서 좋으므로, SJF가 가장 그 원칙에 충실한 scheduling이라고 할 수 있다.

 

 

 

=> gant chart를 계산한다면, 계수가 가장 큰 la만큼의 시간이 작을수록 average waiting time과 average turnaround time( 시작~끝까지 걸리는 시간) 에 유리하다.

 

 

 

- 일단 수행 시간을 기준으로 우선순위를 정하는데, 일하는 시점에 새로운 task 가 도달한다 하더라도 non-preemptive하기 때문에 미리 수행되던 task가 끝날 때까지 기다린다.

 

1. p1이 가장 먼저 도착했으므로 7초동안 수행된다. -> 그 사이으 p2, p3, p4는 모두 도착되어있다.

2. 7초동안 기다리고, 다음 프로세스는 cpu burst 시간이 가장 짧은 p3가 수행된다.

3. 1초동안 수행이되고, p2, p4같이 수행 시간이 같다면 먼저 도착한 process를 먼저 수행한다.

 

이때 average waiting time은 (0+6+3+7)/4= 4초이다.

 

 

 

 

1. p1이 먼저 2초동안 수행되고 있는다. 이때 2초에 p2가 도착하고, remain time이 5초인 p1과 4초 인 p2중에 p2가 먼저 수행된다.

2. p2가 또 2초만큼 수행되는데, 이때 4초에 p3가 도착하고, remain time을 또 비교한다. 

5초인 p1과, 2초인 p2, 1초인 p3중에 p3가 우선순위가 높으므로 p3가 1초동안 수행된다.

3. p3의 수행이 끝나고 5초에서는 또 p4가 도착하여 p1, p2, p4의 remain time을 비교해야 한다.

 p1- 5초, p2- 2초, p4- 4초이므로, p2가 2초동안 나머지 수행이 된다.

4. 7초에서 p1, p4를 비교하고, p4가 마저 수행이 끝난다.

5. 이제 11초에서 p1이 5초만큼 수행되어 모든 프로세스가 수행이 끝난다.

 

이때 average waiting time을 계산해보면 

p1: 9초, p2: 1초, p3: 0초, p4: 2초여서 average waiting time이 3초로 줄게 된다.

따라서 preemption을 허용해야 상당히 빠른 것을 알 수 있다.

 

 

=> SJF 알고리즘으로 스케줄링하기 위해서는 미래에 수행될 CPU burst length를 예측할 수 있어야 한다.

: 이를 위한 메소드가 정해져 있고, Exponential averaging을 기반으로 과거 중에서도 가장 최근의 결과를 가지고 다음 CPU burst를 예측한다.

 

 

 

 

 

1. tn= n번째 실제 CPU burst length 

2. τn = n번째 CPU burst length의 예측 값

3. a=> 반영 비율

 

 

 

=> 이 식을 잘 뜯어 보면 최신 결과에 가중치를 가장 높게 뒀음을 알 수 있다.

 

 

 

1. a= 0 또는 1이면, 가장 최신의 기록은 count되지 않으며, cpu burst count 만 count된다.

 

2. Tn+1 점화식을 잘 뜯어보면, (1-a) x Tn 에서 Tn은 a x tn-1 + (1-a)Tn-2값이다. 

따라서 Tn+1= a x tn + a(1-a) x tn-1 + (1-a)Tn-2이다. 

 이렇게 계속 이어나가다 보면 tn-j 값에 1보다 작은 (1-a)가 계속 곱해져서 Tn+1 값에 영향을 끼치는 가중치가 점점 낮아지게 된다. 따라서 가장 최근 값인 tn이 가장 다음 CPU time에 영향을 많이 끼친다.

 

 

예제로 확인 가능하다.

 

=> 최근 history에 높은 가중치를 두는 exponential averaging에 충실하다.

 

 

                

 

   표를 통해서도 확인이 가능하다. 그래프를 그려서 전체적으로 확인해볼 수 있다.

 

---

3. Priority Scheduling

: 철저하게 우선순위에 기반하여 스케줄링한다. priority 숫자가 작을수록 우선순위가 높다.

-> 높은 우선순위를 가진 프로세스가 CPU를 가져간다. 

 : SJF가 P.S의 일종이라고 할 수 있다. CPU burst length가 짧을수록 우선순위를 높게 주기 때문이다.

 

=> 그렇지만 Priority Scheduling의 문제점은 우선순위 높은 task 가 Ready state에 들어가버리면 우선순위 낮은 task는 절대 수행이 안되고, strarvation 현상이 발생할 수 있다

: priority를 점진적으로 바꿔줌으로써 해결할 수 있다. 오랫동안 수행이 안된 task는 우선순위를 높여준다.

 

ex) task 1, task 2가 있다고 가정했을때, task 1이 우선순위가 더 높을 때는 Starvation이 발생할 가능성이 있으므로

task2의 priority를 10에서 ->7 -> 5 처럼 점진적으로 높여준다. 이를 Aging 기법이라고 한다.

 

 

+) P.S의 종류

1) Static priority

: Priority number가 처음으로 할당된 이후로 바뀌지 않는다.

 

2) Dynamic priority

: Priority number가 점진적으로 바뀔 수 있다.

 

 

---

 

4. Round-Robin Scheduling (RR)

: 각각 프로세스가 time quantum 만큼 의 시간을 할당 받아서, 이 시간만큼 running되고, 이 프로세스가 끝나면 다음 큐에서 기다리고 있는 프로세스가 time quantum 만큼 추가되고, ready queue의 맨 끝에 추가된다.

 

=> 따라서 프로세스가 n 개 라고 했을때, 어떤 프로세스도 (n-1) *quantum 보다 더 기다리진 않는다.

 (n-1) *quantum 이 worst time이고, 이 worst time이 보장되기 때문에 response 측면에서 상당히 좋다.

 

- Quantum 이 크다면 ? FIFO 식으로 운용될 것이고,

- Quantum이 작다면, context switch가 너무 자주 일어나서 경제적이지 못한 overhead가 자주 일어날 것이다.

 

 

 

 

1이 20만큼 수행되고, 2가 또 20만큼 수행되지만 17이 burst time이니, p2가 끝나버리면 바로 다음 p3가 스케줄링된다.

또 20만큼 수행되고... 이렇게 모든 프로세스 가 terminate될때까지 스케줄링을 실행한다.

=> SJF보다 average turnaround time이 크지만, response 측면에서는 훨씬 낫다. ( 요청하고 처음 실행되기까지 걸리는 시간) + time quantum이 작을수록 response time도 빨라진다.

 

---

5. Multi-Level queue

: 핵심은 Ready queue가 여러개로 분리되는 것이다.

각각의 큐는 독자적인 스케줄링 알고리즘을 갖고있고, 큐에서 다음 스케줄링 할 대표 프로세스가 정해졌다면, 

각각의 큐들을 스케줄링하는 큐간의 알고리즘을 통해 최종적으로 다음 프로세스가 스케줄링된다.

 

ex) foreground process를 RR로 스케줄링 하고, background process queue를 FCFS로 스케줄링하고, 큐 들 사이를 priority를 따져서 더 우선순위 높은 큐의 프로세스를 먼저 실행하게 될 수 있다.

 

 

 

 

=> 5개의 큐가 존재할 때, 큐 마다 하나의 task가 scheduling될 대표로 나오게 됩니다. 이후에 이 task들을 큐들 사이 대표 프로세스로 scheduling할 수 있습니다.

 

---

6. Multi-level Feedback Queue

: multi-level queue는 큐 간에 프로세스들이 이동할수 없는등 유동적이지 못하다는 단점이 있다. 또 priority scheduling을 적용하면 우선순위가 낮은 큐는 영원히 스케줄링이 되지 못할 수도 있다.

 

그러므로 starvation이 발생하는 것을 막기 위해서, 프로세스가 queue안에서 이동하는 것을 허용하는 MFQ가 등장하게 된다.  MFQ는 다음의 기준에 의해 정의된다.

 

- 큐의 개수, 각 큐에 적용될 스케줄링 알고리즘

- 프로세스를 위의 큐로 이동시킬 방법, 프로세스를 아래의 큐로 이동시킬 방법 (upgrade&demote a process)

- 프로세스가 가장 처음에는 어떤 큐로 진입할 지를 결정해야 한다.

 

 

 

 

 

=> 큐 안에서의 scheduling algorithm이 따로 존재하고, 각 큐들 사이에서 이동할 method 또한 존재해야 한다.

이 경우에서는 Q0 로 가장 처음 진입하여 8ms 동안 실행한 후, 아직 실행 시간이 남았다면 Q1으로 이동하여 16ms동안 실행한다.  그 후에도 프로세스 실행 시간이 남았다면, 마지막 Q2 로 이동하여 preemptive하게 남은 프로세스를 다 처리한다. : 이처럼 프로세스들 사이에 반드시 queue를 언제 upgrade하고 demote할 지 정해야 한다.

 

 

 

 

 

 

 

---

#Multiple-Proecessor Scheduling

= CPU scheduling은 만약 multipble CPU가 가능해진다면, 매우 복잡해질 여지가 존재한다.

: 그렇다면, task를 어떻게 각 프로세서에게 할당할 것인가?

 

- Symmetric Multiprocessing (SMP)

 : 각 프로세서들이 그들만의 scheduling decision을 내린다.

=> 동일한 역할을 병렬적으로 수행하게 된다. 따라서 Asymmetric Multiprocessing 보다 효율적이며, 한 CPU에

특정한 프로세스가 몰리는 것 또한 방지할 수 있다.

 

 

 

- Asymmetric Multiprocessing 

: 각 CPU들이 각자의 역할을 가지고 있다. 따라서 Data sharing의 필요를 경감해준다.

그렇지만, 특정 역할을 하던 CPU가 문제가 생겨서 동작이 어렵게 되면, 이 프로세서의 작업 결과를 기다리던 다른

프로세서들 까지 기다리게 만들어서 작업 효율이 매우 낮아질 수 있다.

 

 

 

http://www.tipssoft.com/bulletin/board.php?bo_table=FAQ&wr_id=334

팁스소프트 > MFC/API 가이드 > [용어] 대칭적 멀티프로세싱과 비대칭적 멀티프로세싱에 대하여...

 

 

 

Q. Multi Processing에서 중요한 키워드는 무엇인가?

A: Task Allocation이다.

 

1. Process Affinity 

: 프로세서와 Task간에 affinity(친밀도)가 존재할 수 있다. 이때, 두가지 경우의 Affinity 가 존재한다.

   1) Soft Affinity

 => 웬만하면 관계가 있는 CPU에게 할당하려고 하지만, 보장은 하지 못한다.

 

   2) Hard Affinity

 => 프로그래머가 OS에게 반드시 친밀도가 있는 CPU에게 할당하도록 요청했을 때는 이가 보장되어야 하고, 다른 프로세서로 이동되서는 안된다.

  : 이는 Linux에서는 가능하다. 특정 CPU에게 할당을 요청할 수 있는 System call 이 필요하다.

 

 

 

=> Process 1이 CPU1 과의 affinity가 존재하여 CPU 1에 할당 되었을 때는, 굳이 CPU2 로 이동할 필요가 없다.

: CPU 2로 task를 옮길 때는 cache 메모리에 있는 프로세스도 같이 옮겨야 하는데, 이때 overhead가 발생한다.

 

 

2. Load Balancing

: 특정 프로세서에 Task가 몰려서는 안된다. 모든 프로세서가 골고루 일하도록 해줘야 한다.

=> 따라서 특정 task가 어떤 프로세서가 바쁜지 계속 모니터링 하고 있다.

=> 이 task가 idle한 프로세서를 발견하게 되면, 바쁜 processor로부터 task를 이동시킨다. 

: 이 migration 기능을 통해서 멀티 프로세싱의 의미를 극대화시킬 수 있게 된다.

 

 

 

 

=> 잘 관찰해보면, CPU1과 CPU3 에 task들이 몰려있는 것을 발견할 수 있다. 이때, Idle 한 프로세서로 

task 를 PUSH 하게 된다.

 

 

=> 이때 Idle 한 프로세서는 PUSH 된 task들을 PULL 하게 된다. 이렇게 task들을 PUSH&PULL 함으로써

각 CPU간의 Load balance를 맞추게 된다.

 

 

 

---

# Thread Scheduling

 

- 하나의 kernel thread에 여러개의 user thread가 매핑될 때는

: Kernel thread를 수행할 때 mapping된 user thread 중에 하나의 thread가 스케줄링되어서 수행되어야 한다.

=> 이때, Thread Library가 Mapping 된 스레드 중에 어떤 스레드를 스케줄링 할 것인가?를 결정하는 스케줄링을

:Local scheduling & Process contention scope이라고 한다.

 

=> 또, OS kernel이 어떤 커널 스레드를 설정할 것인가? 를 결정하는 스케줄링 방식을

 : System content scope & Global Scheduling이라고 한다.

 

 

그러나, 이 스레드 스케줄링 방식은 One-to-one Model 방식에서는 존재하지 않는다. 예를 들어, Linux는 One-to-one Model을 사용한다. 이때, User thread또한 별도의 PCB를 갖고 있기 때문에 Kernel Thread와 User Thread의 구분 의미가 없다. => 따라서 별도로 Scheduling 되는 개체로, User thread에 바로 적용이 가능하다.