운영체제(OS) - 5. Scheduling

CPU Scheduling

• CPU 자원을 최대한 활용할 수 있는가에 대한 process이다.
• 보통 CPU를 짧은 시간 내에 최대한 활용하기에 이를 적절히 분배하기 위해 필요하다.
• ready queue에 들어간 순서대로 실행을 하는데 이를 우선순위에 따라 다시 정렬하는 방식이다.

Short-Term scheduler

• 4가지의 경우 프로세스를 새로 선택해야 한다.(scheduling decision)
  1. running -> wating state(I/O를 받으려고 기다림)
  2. running -> ready state(interrupt가 발생했을 경우)
  3. wating -> ready state(interrupt가 발생했을 경우)
  4. terminate
• 1번과 4번 case에서는 nonpreemptive하다. 즉, 중간에 끊기지 않은 경우
• 2번과 3번 case에서는 preemptive하다. 즉, 중간에 끊기는 경우

Dispatcher

• context switching이 일어나게 해준다. (하나의 프로세스를 멈추고 다른 프로세스를 실행시킬 때), 하나의 프로그램으로 scheduling decision을 할 때도 호출된다.
• Dispatch latency = context switching delay
  • 순수 overhead
• latency가 짧을 수록 시스템의 효율성은 빠르다.

무슨 기준으로 scheduling ? what criteria ?

• CPU utilization: CPU가 특정 시간에 얼마만큼 바빴는지, 이를 최대화 시켜야 한다. 여러 개의 프로세스가 동작하는 상황에서 dispatch latency 때문에 100프로를 만족시킬 수는 없다.(스케쥴링 기법에서는 latency가 거의 없다고 생각한다.)
• 아래 4개는 순서에 영향
• Throughput: 일정 시간 동안 프로세스를 끝마친 수, 최대화 시켜야 한다.
• waiting time: 하나의 process가 ready queue에서 기다리는 시간
• turnaround time과 waiting time은 최소화
• Response time: ready queue에 들어가서 첫 반응을 보인 시간, 최소화 시켜야 한다.

First-come, First-served(FCFS)

• P1 > P2 > P3 vs P2 > P3 > P1
• 가장 먼저 온 process부터 수행
• Convoy effect: short process가 long process 뒤에 있어서 시간 손해를 많이 본 경우
• waiting time 기준에서는 최적이 아니다.
• 하나의 CPU bound process, 많은 I/O bound process(비교적 짧은)인 경우를 생각한다.

Shortest Job First(SJF)

• 평균 waiting time이 최소가 되는 것을 보장한다.
  • OS입장에서 waiting time이 최선으로 보지 않는 경우도 있다.
• 일반적으로 각 process가 task를 수행하는데 얼마나 걸리는지 알기 힘들다. 그렇다면 어떻게 SJF를 수행할까 ?
  • 얼마나 걸릴 것인가에 대한 예측을 해야한다. 프로세스가 처음 실행된게 아니라면 바로 이전에 실행되었던 시간 정보를 이용해서 그 시간에 가깝게 task 수행시간을 정하고 예측한다.
  • 이전의 수행시간 정보는 어디에 ? OS가 관리
  • 처음 시작되는 프로세스는 예측값의 defualt값으로 두고 시작한다.
• Burst time이 짧은 순으로 스케쥴링한다. (preemptive인지 nonpreemptive에 따라 다르다.)
• preemptive라면 중간에 수행해야할 프로세스보다 더 짧은 프로세스가 interrupt할 수 있다. shortest-remaining-time-first, 매 클락마다 짧은 것을 수행하도록 확인한다.
• nonpreemptive라면 레디 큐에 있는 프로세스가 끝났을 때 가장 짧은 프로세스를 선택해서 수행한다. arrival time 순으로 수행되고 이 후에 수행시간이 짧은 순으로 한다.
• arrival time은 preemptive SJF에서 필요하다.
• waiting time은 process가 ready queue에서 기다리는 시간이라는 것을 인지한다. (arrival time 기준으로 수행될 때까지 걸리는 시간)
• 시간이 똑같다면 utilize 측면에서 context switching latency 때문에 먼저 수행하던거 수행한다.

Priority Scheduling

• Priority Number를 할당 (작은 숫자가 높은 우선순위를 갖는다.)
• preemptive: interrupt 우선순위 높은 순으로
• nonpreemptive: 하던거 진행
• realtime scheduling에서 사용된다. OS가 user program인지 kernel program인지에 따라 우선순위를 정해주거나 scheduler가 priority를 정해준다.
• Starvation problem
  • priority가 낮은 프로세스가 계속 높은 우선순위의 프로세스 interrupt로 전혀 실행되지 않는 경우, 한 프로세스라도 전혀 실행되지 않을 것 같은 경우 발생한다.
  • Aging solution으로 해결한다.
• Aging solution
  • 언젠가는 수행될 것을 보장한다. 천천히(시간이 지날 수록) 우선순위를 높여준다.
• arrival time이 같을 때(다 ready queue에 있을 때)
  • priority가 높은 순으로 (작은게 높은거)

---

위의 스케쥴링 방식은 multitasking이 안된다.

Round Robin

• RR자체가 preemptive, 단 interrupt는 quantum q가 지나고 1번 수행된다.
• 실제 쓰이는 방식과 유사
• 원형 큐를 만들어놓고 수행
• time quantum q를 정하고(특정 프로세스가 정함) process가 q만큼 수행하고 빠지면서 수행되는 방식
• 전체 시간을 1/n로 분리하고 q만큼의 시간을 주고 interrupt, (n-1)q만큼
• q가 크다면 사실상 FIFO (순서대로 수행)처럼 수행
• q가 작다면 context switching이 일어나는 시간을 고려해야 한다.
• response tiem 측면에서는 SJF보다 좋은편이다.
• q는 짧아서 나쁠 것은 없지만 context switching 시간이 자주 일어난다는 뜻이고 이 시간보다 q가 커야 한다. 그렇기에 q를 몇으로 잡을지가 중요하다. (q는 ms context switch는 usec 단위)

Multilevel Queue

• foreground queue와 background queue가 존재
  • 각 queeu에 다른 스케쥴링 방식을 적용하여 운영될 수 있다.
• 이 둘 간에 어떤 큐부터 실행되는지도 스케쥴링해야 한다.

Multilevel FeedBack Queue

• multilevel queue가 서로 간 연결되어 있어 아니다 싶으면 다른 큐로 옮길 수 있는 방식
• 어떤 프로세스를 수행하는데 있어서, 손해볼 가능성이 있는 큐에서 그 가능성이 덜한 큐에서 수행시킬 수 있다.
• 어떤 큐에 어떤 방식이 적용되는지에 따라 performance가 다르다.

Thread Scheduling

• Thread에서는 User Thread끼리의 경쟁, Kernel Thread끼리의 경쟁이 존재.
• kernel thread는 system level에서 경쟁 (SCS)
• User thread는 process 내에서 경쟁 후, system level에서 경쟁해야 수행될 수 있다.
• LWP에 의해 결정되는 thread를 PCS(process 내에서의 경쟁)
  • user thread들끼리는 일반적으로 preemptive하다.
• SCS에서는 스케쥴링 방식으로 경쟁

Multiple-processor scheduling

• Homogeneous processors 가정(다 똑같은 성능의 processor라고 가정)
• Asymmetric: master process만 data structure에 접근해서 data를 분배
• symmetric: 각각의 CPU마다 독립적인 스케쥴러가 존재, 각 CPU가 알아서 스케쥴링, 공통의 레디큐 data sharing에서 동기화의 문제가 발생할 수 있다.
• processor affinity
  • soft affinity: 어떤 프로세스에서 수행되었다면, 이를 유지하되(이 프로세스에서 계속 수행되도록), 무조건은 아님
  • hard affinity: 어떤 프로세스에 종속, 무조건 이 프로세스가 수행되도록

NUMA(중요)

• Non Uniform Memory Access
• 각 CPU는 가능한 빨리 접근할 수 있는 메모리에 적재되면 좋다.(affinity도)
• Multiprocess system에서 메모리에 접근하는 시간이 메모리의 위치마다 다르다.( 버스에서 전기적인 신호를 보내서 메모리에서 주소를 가져오기 때문에 멀다면 전기적인 신호가 느리게 간다.)

UMA

• 어떤 메모리가 어떤 공간에 있든 접근하는 시간이 같다.
• 프로세스 affinity의 개념은 data sharing 때문에 존재하지만, 메모리의 위치에 신경을 덜 쓴다.
• 둘은 메모리 할당할 때 신경써야 하는 부분이 다를 수 밖에 없다.

Load balancing(중요)

• 모든 CPU가 효율적으로 적재되는 것을 유지하는 것이 필요하다.(symmetric multiple processor에서)
• 공평하게 분배된 workload를 유지하도록 하는 것
• symmetric에서는 보장하기 힘들다.
• push migration: 상대적으로 바쁜 CPU가 overload되지 않은 CPU에게 task를 넘겨준다.
  • 상대적으로 바쁜 processor가 덜 바쁜 processor에게 process를 넘겨준다.
• pull migration: 상대적으로 바쁘지 않은 CPU가 overloaded CPU에게 task를 가져온다.

Multicore Processors

• processor는 하나, 이 안에 core가 여러 개인 경우
• memory stall(대기) 시간을 잘 이용할 수 있기에 multi thread에서 굳굳
• memory stall: 메모리에 접근해서 data를 읽어오는데 걸리는 시간, 메모리에 락이 걸려 기다리는 시간
• Compute와 memory stall cycle을 번갈아가며 multi thread가 가능하기에 효율이 좋다.

Real-Time CPU scheduling

• deadline의 개념이 도입된 system, deadline 내에 task를 수행하도록 하는게 real time system이다.
• deadline이 갑자기 지켜지지 못하더라도 큰 영향을 주진 않는 경우 - soft real-time systems
• 자율 주행 자동차의 경우, 로켓의 경우 deadline을 무조건 보장해야 한다. - Hard real-time systems
• 생길 수 있는 변수: interrupt latency, dispatch latency(메모리를 접근하는건데 메모리가 사용 중이라면 메모리 stall이 발생하여 예측이 힘들다.)
• dispatch latency: conflicts가 생길 수 있음
• interrupt latency: 언제 interrupt가 들어올지 모름
• 이 둘이 non-determinstic이기에 realtime에서 큰 변수이다. 신경을 써주어야 한다. 이 뿐만 아니라 scheduling을 신경써주어야 모든 task의 deadline을 만족시켜 줄 수 있다.
• soft real time system에서 보자면,
• priority-based scheduling: preemptive 지원, admission control(무조건 프로세스를 받는게 아닌 real time을 만족시킬 수 있느냐 없느냐에 따라 프로세스를 처리할지 말지 결정하는 기능)한 이 필요
• process들이 periodic(주기성을 갖고 나타남)- 멜론, 자율 주행, 로켓 모두 소리를, 센서를 주기적으로 요구

Rate Montonic scheduling

• 자주 나타나는가 드물게 나타나는가에 따라 스케쥴링하는 방식
• p랑 d가 일치하다고 본다.
• P1(50, 20): 50의 주기 처리하는데 20이 걸린다. (50전에 처리되어야 한다.)
• P1(50, 25), P2(80, 35)인 경우 deadline을 만족시키지 못한다.
• utilization P1: 25/50(50%), P2: 35/80(43.xx%) -> 93.xx% (프로세스의 개수가 늘어날 수록 최대 max utilization은 69%라는 치명적인 단점) 실시간 스케쥴링 만족 못 한다.

Earliest Deadline First scheduling

• deadline을 기준으로 우선순위 부여
• deadline에 임박하면 우선순위가 높아진다.
• P1(50, 25), P2(80, 35)인 경우 deadline을 만족, realtime scheduling 만족
• utilization이 100%안에만 들면 만족시킬 수 있다.

Proportional Share scheduling

• 전체 process들 간에 N만큼 나눠주는 스케쥴링

Virtualization and scheduling

• 어떤 식으로 가상화가 되어있는가에 따라 스케쥴링 방식이 다르다.

Performance aspect

Algorithm Evaluation

• Deterministic modeling
  • throughput, waiting time 등을 기준으로 performance 측정
• Queueing Models
  • Deterministic 보다 성능이 더 좋을 수 있음, 확률분포를 통해 계산을 하기에 좀더 현실적임, 모든 요소가 queue로 이루어져 있고 각 queue들이 overflow, underflow없는 경우 안정적이다라고 한다.
• Simulations
  • 어떤 스케쥴링을 했을 때 어떤 성능이 나올지 시뮬레이션
• Implementation
  • 스케쥴링 기법을 직접 구현하여 성능을 검증하는 방법

버클리에서 만든 미니 OS를 통해 직접 스케쥴링 구현 가능하다.