05. CPU scheduling

cpu scheduling이란? CPU를 더 효율적으로 사용하기 위한 것. 프로세스 스케줄링을 위한 queue에는 job queue, ready queue, wait queue가 있다.

 

 

프로세스 스케줄링의 과정

• 새로운게 들어오면 먼저 레디큐로 간다. 레디큐에서 스케줄러를 통해 CPU로 가고 목적에 따라 I/O(I/O를 요청한 디바이스들의 웨이팅 큐에서 I/O를 기다리다가 I/O 작업을 수행), time slice expired(타이머가 끝났을때), fork a child(일반적인 wating queue에 들어가서 child가 끝날때까지 기다림), wait for an interrupt(특정 interrupt 발생을 기다림) 등의 작업을 수행한다. 수행이 끝나면 다시 레디큐로 들어감
• CPU burst(CPU 작업을 하는 단계) -> I/O burst(기다리는 단계) 가 반복됨. 이때 주어진 시간보다 더 많은 시간이 걸리는 작업을 하면 중간에 작업을 강제로 내리고 switching한다. (이럴 경우 context switching이 두번 일어남)
• I/O burst에서는 wait queue에서 I/O 작업을 기다림.
• CPU burst에서는 ready queue에서 CPU 작업을 수행함. 작업이 끝나면 자발적으로 wait.
• wait -> ready -> terminated 순서로 종료하므로 언제나 CPU 베스트에서 종료가 됨. (CPU 베스트란? 주어진 시간보다 작업이 빨리 끝나서 CPU burst가 context switching이 일어나지 않은 것)

 

CPU burst Time

 ex) 대부분이 8 미만의 짧은 CPU 작업을 한다고 가정하자. 이때 CPU burst time을 5로 잡으면 작업을 하던 도중 끊기는 일이 빈번하여 context switching이 더 자주 일어나서 오버헤드가 발생함. time을 16으로 늘리면? 작업을 끝내고 스스로 내려오는 경우가 많아 context switching 빈도가 낮아짐. 여기서 더 늘리면? 작업 시간에 비해 지나치게 많은 시간을 준 것 이므로 공정성이 떨어짐.

=> 적절한 time을 찾아야함!

 

 

ready queue와 waiting queue의 개수

 레디큐는 프로세스별로 하나씩 / 웨이팅큐는 여러개. 웨이팅 큐를 사용하면 disk에서 신호가 왔을때 어떤 프로세스가 wait를 원하는지 끝까지 순환하며 찾아내야함. 웨이팅큐에 unit을 연결하면 마그네틱에게 작업 종류에 관한 신호를 받고 그 번호를 기다리는 프로세스들만 검색해주면 wating을 원하는 프로세스를 빨리 찾을 수 있음. ex) unit 0은 마그네틱 0번에게 신호를 받아 0번을 기다리는 프로세스를 검색함

 

 

Schedulers

• Short-term scheduler(=CPU scheduler)
  위에서 이야기한 스케줄러를 말함. 레디큐에 있는 작업중 하나를 고르는 것. 밀리단위임.
• Medium-term scheduler
  degree of multiple program(얼마나 많은 프로세스를 메모리에 올릴 수 있냐는 것. CPU util을 계속 높게 유지)을 적절히 맞춰주는 역할. 분단위.
  너무 오래 웨이팅 할때 등 비효율적인 일이 발생하면 프로세스를 교체함. 기존에 있는 프로세스를 스토리지로 억지로 내리고 다른 것을 메모리로 올림.
  ex) 아래의 표를 보면 I/O 시간이 실행 시간보다 훨씬 길다. 따라서 실행을 금방 끝내고 나면 남은 CPU가 없으니 스토리지를 살펴서 새로운 작업을 찾게 된다.(롱텀 스케줄러) 100동안 동작하는 P4 작업을 찾았다고 가정하면 P1+P2+P3+P4=124이므로 P4까지 CPU 작업을 할 동안 P1의 I/O는 끝이난다. P4가 끝나면 다시 P1 작업을 시작한다. =>CPU util이 계속 높게 유지됨!
  
  

  	P1	P2	P3
  실행 시간	10	8	6
  I/O 시간	100	1000	10

• Long-term scheduler(=Job scheduler)
  스토리지에 있는 job중에 어떤걸 메모리로 올릴지 고름. 시간단위임.
  롱텀 스케줄의 역할은 적절한 process mix를 만드는 것.
  프로세스가 종료될떄마다 메모리 공간이 충분히 확보되면 long-term 스케줄러가 동작하여 storage에 있는 작업을 프로세스화 함.
• 옛날 OS는 이 세가지가 계층적으로 구성됨. 요즘에는 Short-term scheduler만 사용됨.
  옛날 OS와 요즘 OS는 메모리 공간의 차이가 있음. 옛날 OS는 메모리에 있지 못하고 스토리지에 감.
  타임슬라이스란? 프로세스에게 할당해주는 시간. 타임 슬라이스마다 스케줄러가 실행됨. 작업이 자발적으로 웨이팅큐에 간 상황이면 타임슬라이스보다 짧게 동작했다는 것임.타임슬라이스란? 프로세스에게 할당해주는 시간. 타임 슬라이스마다 스케줄러가 실행됨. 작업이 자발적으로 웨이팅큐에 간 상황이면 타임슬라이스보다 짧게 동작했다는 것임.

 

 

스케줄러의 동작 두가지

• Non-preemptive(비선점형)
  강제로 내릴 수 없는 것. 프로세스가 자발적으로 CPU를 놓을때까지 계속 기다림.
  waiting queue로 들어가거나 terminated 될때.
  switching이 최소화되지만 공평성이 부족함.
• All other scheduling is preemptive(선점형)
  타이머가 있어서 강제로 내릴 수 있는 것. boosting 매커니즘이 가능함.
  프로세스에게 우선권을 주기 위해 강제로 내리는 권한을 쓰는 것임.
  동기화 문제가 발생함.(동작중인 프로세스를 갑자기 내렸을때)
  ex) OS가 동작중(커널 모드 상태)에도 CPU를 빼앗길 수 있음 -> 커널쉐어데이터가 불안정한 상태로 마무리됨
  ex)A라는 프로세스가 파일을 열어 작업중이었는데 프림티브 스케줄러가 A를 강제로 중단시킴. B라는 프로세스가 스케줄링되어 A가 쓰다만 파일에 접근하려는데 접근하지 못함.(한 파일을 하나의 process만 열 수 있다고 가정) B는 파일을 언제 열 수 있는지 계속 체크만 하다가 자신의 타임 슬라이스를 다 쓰고 다시 레디큐로 돌아감.
  -> B에게 CPU를 준 의미가 없다. 이런 식으로 불필요하게 CPU를 낭비하는 경우가 발생. A가 작업중이면 뺏지 않는 동작 필요.

Dispatcher(별로 안 중요)

숏텀 스케줄러에서 스위칭하고 다른 프로세스로 전환해주는 코드를 말함.

숏텀 스케줄러 안에서 실제로 context를 바꿔줌.

 

Scheduling Criteria

• CPU를 평가하는 지표를 말함.
• CPU utilization) 스케줄러의 목표는 CPU utilization을 최대로 높게 하는 것
• Throughput) 특정한 단위시간동안 몇개의 프로세스가 완료되었는지 볼 수 있음. ex) 한 시간동안 백개의 프로세스가 완료됐다
• Turnaround time) 어떤 프로세스를 수행시키는데 걸린 총 시간 (프로세스가 시작한 시간~ 끝난 시간)
• Waiting time) Turnaround time중 웨이팅큐에서 기다리는 시간
• Response time) 어떤 요청이 왔을때 해당 프로세스가 그 요청에 응답하기까지 걸린 시간. (=프로세스가 시스템에 로딩된 시간. 프로세스가 로드되고 맨처음 스케줄링 받기까지 걸린 시간) / 인터렉티브 프로세스는 응답시간이 낮게 나오길 기대함. 스케줄러가 웨이팅 큐에서 레디큐로 온 프로세스를 빠르게 스케줄링할 수록 응답시간은 낮아짐.

Scheduling Algorithm Optimization Criteria

• Max CPU utilization ) context switching을 적게 할수록 높아짐. 높을수록 좋음.
• Max throughput
• Min turnaround time ) 짧을수록 중간에 웨이팅 타임이 없음.
• Min waiting time )
• Min response time ) context switching을 많이 할수록 낮아짐.
• 이것들을 한번에 달성할 수 없음!! 메인 요구사항에 맞춰야함.
• ex) 슈퍼컴퓨터는 CPU를 최대한 활용해야하므로 CPU utilization을 본다.
  ex) 사용자가 요청했을때 최대한 빠르게 답을 주는 것이 중요하므로 Response time을 준다.

Scheduling Algorithms

• First-Come, First-Served Scheduling (FCFS)
• Shortest-job-First Scheduling (SJF)
• Priority Scheduling
  -----------가장 기본적인 배치시스템-----------
• Round-Robin Scheduling
• Multilevel Queue Scheduling
• Multilevel Feedback Queue Scheduling
  -----------더 복잡한 배치시스템------------

FCFS

• 순서대로 스케줄링함.
• 오래걸리는 것이 뒤로갈 수록 waiting time, average waiting time이 줄어듦.
• 마트 계산대에서 나는 살게 많고 뒷사람은 하나만 있다고 가정했을때 내가 차례를 양보하면 난 조금 더 기다리지만 전체적으로 기다리는 시간이 짧아지는 것과 같은 이유.

 

SJF

• 짧은 순서로 스케줄링함.
• 평균 대기시간을 줄이는데에 가장 이상적인 방법. BUT 실제로 다음 버스트 타임을 잘 모르기 때문에 달성하기 어려움. CPU에 올려봐야 버스트 타임을 알 수 있음. 이 방법을 쓰려면 버스트 타임을 예측해야함.
• CPU 바운드=CPU 버스트 긺.
• I/O 바운드=CPU 버스트 짧음.

 

Shortest-remaining-time-first

• SJF에 arrival time을 추가함. remaintime을 따져서 더 조금 남은 프로세스를 실행시킴.
• ex) 8만큼 수행하는 P1이 1까지 실행하던 도중 4만큼 실행하는 P2가 들어온 상황이면 P1을 프림션 시키고 P2를 수행함. 이후로 들어오는 P3, P4와 비교해봤을때도 P2가 더 짧으면 P2는 프림션되지않고 burst time이 0이 될때까지 수행함.

 

Priority Scheduling

• burst time은 신경쓰지 않고 오직 우선순위만 봄. (우선순위는 사용자에 의해 결정됨. 따라서 유저의 의도가 정확히 반영되는 스케줄링)
• 높은 우선순위를 가지는 이유는 시스템 작업을 하는 프로세스이거나 사용자가 그 프로세스의 우선순위를 일시적으로 높게 했기 때문임.
• SJF는 priority 방식이기도 함. 다만 우선순위를 부여할때 CPU burst time의 역수를 취해서 그것을 priority number로 삼음.(=CPU burst가 길수록 낮은 priority를 가짐)
• 낮은 우선순위는 영원히 실행이 안 되는 Starvation문제가 발생함.
  ex) P1 실행도중 우선순위가 더 높은 P2가 들어옴. 그럼 P1은 프림션되고 P2가 실행됨. P2가 끝나면 다시 P1 실행. 그런데 P1보다 우선순위가 더 높은 프로세스가 계속 들어오면? P1은 실행을 못함.
  -> 우선순위를 높여줌(Aging 기법) 실행 도중 끼어드는 프로세스가 발생할 때 마다 원래 실행중이던 프로세스의 우선순위를 -1함.

 

Round Robin (RR) Scheduling

• 라운드가 반복되면서 스케줄링하는 것.
• 위에서 말한 기법들은 주로 배치 시스템에 이용됨. 타임 쉐어링에서는 RR을 사용함.
• 사용이유) 프로세스들이 CPU burst만하고 끝나는 것도 아니고, CPU burst는 계속해서 바뀔 수 있으므로 위에서 말한 것들은 현실적인 알고리즘이 아님.
• 라운드 로빈이라는 틀 안에서 각 라운드마다 다른 스케줄링 방식을 쓸 수 있다. (어떤 알고리즘을 쓰는지 반드시 명시)
• 단위는 퀀텀으로, 할당할 수 있는 가장 작은 단위임. 1퀀텀=1ms라고 가정하고 퀀텀을 ms단위로 표현함.
  때문에 1ms 이하의 스케줄링은 할 수 없음. 1ms 단위라서 그 중간엔 OS가 개입할 수 없음.
  타임 퀀텀이 1이라는 말은, 1ms가 되었을때 타이머 interrupt가 오고 CPU가 interrupt를 받아서 OS에게 처리할 것을 요청한다는 것임. OS가 깨어나서 현재 동작중인 프로세스가 타임 슬라이스를 얼마나 썼는지 확인하고 다 썼으면 내리고 다른 프로세스를 올림. 즉, 1ms마다 OS가 상태를 확인한다는 
• 라운드 크기는 유동적이고 돌릴때마다 바뀔 수 있음.
• H/W 타이머 설정에 따라 필요시에 그때마다 커널이 스케줄링됨.
• 각 라운드마다 타임 슬라이스가 부여됨. (라운드마다 해당 프로세스가 쓸 수 있는 시간이 부여됨)
  ex) 타임 슬라이스를 각 프로세스마다 10개씩 줬다=각 타임 슬라이스는 10ms=10 of time quantum
• 각 프로세스들이 타임슬라이스를 다 쓰면 라운드가 종료됨. 현재 프로세스가 끝나고 다음 프로세스가 시작될때 각 프로세스들의 타임슬라이스를 리필함.
• P1에는 4ms, P2에는 2ms, P3에는 3ms의 타임 슬라이스를 부여함. 현재 레디큐에서 대기하고 있는 프로세스가 P1, P2, P3이라고 하면 라운드 길이는 9ms.
• 타임슬라이스를 어떻게 부여할 것인가? 타임 슬라이스는 context switch을 고려해 충분히 커야한다. 안 그러면 오버헤드 발생.
  1. 아주 길게 => FIFO 방식이 됨
  2. 짧게 => responsiveness는 높아지지만 성능은 낮아짐. CPU를 비효율적으로 쓰게됨.
  ex) P1 P2 순서로 실행된다고 가정하자. 이때 P1은 30ms 동안 동작하고 P2는 10ms 동안 동작한다. 한 라운드에 P1, P2에게 주어진 타임 슬라이스는 각 3, 1이다. 총 10라운드가 실행되어야 끝나는 것이다. context switching이 많이 발생한다. 타임 슬라이스를 30, 10으로 늘리면? 1라운드만에 실행이 끝난다. 이것은 FIFO를 쓴 것과 다름없다. context switching은 한번 발생한다. 이에 따른 오버헤드도 더 적게 발생하고 CPU utilization이 좋아짐. 반면에 response time은 느리다. 클릭을 하면 P2에서 반응이 온다고 가정하자. 각 타임 슬라이스가 3, 1인 프로세스에서 P1이 실행되는 도중에 클릭을 해도 곧 P2 프로세스가 스케줄링되므로 response time이 짧다. 타임 슬라이스가 30, 10인 프로세스는 P1 실행도중에 클릭을 하면 P2가 실행되기까지 많은 시간이 걸리므로 response time이 길다.

 

Multilevel Queue

• 레디큐가 여러개 있는 것. 실제 시스템들은 대부분 이걸 사용함. 큐마다 다른 알고리즘을 사용함.
• 시스템에는 여러가지 특성을 가진 프로세스들이 동시에 돌아감. 
  응답률이 중요한 프로세스들은 RR로 스케줄링해야함. CPU utilization이 중요한 프로세스들은 FIFO로 스케줄링해야함. 이 상황에서 둘을 어떻게 동시 스케줄링할것이냐?
• 두가지 큐가 있는데, 첫번째 큐는 foreground 큐이고 interactive 프로세스를 관리하기 위한 큐. RR 스케줄링으로 동작. 두번째 큐는 background 큐이고 배치 프로세스(CPU 바운드 프로세스)를 관리하기 위한 큐. 두 큐를 번갈아가며 동작시킨다. 첫번째 프로세스를 먼저 실행시키고 더 이상 레디큐에 작업이 없으면 두번째 프로세스를 동작함. 두번째 큐의 사용시간이 지나면 다시 첫번째 프로세스 동작.
• Fixed priority scheduling) 여러 큐에 우선순위를 부여하고 높은 우선순위에 존재하는 여러개의 큐 안의 프로세스들이 전부 수행되어야 다음 레벨의 큐를 수행함.
• 대부분의 OS들은 두 세개의 큐로 나눔.
  system processes) 이 안에 있는 프로세스들이 CPU 시간을 다 써버림. 그럼 아래에 있는 프로세스들은 전혀 실행이 안됨.(fixed priority Scheduling) 너무 중요한 작업이라 강력한 방식을 쓰는 것으로, 어쩌다가 한번 발생함.
                                                                  ↓
  interactive processes
                                                                  ↓
  interactive editing processes
                                                                  ↓
  batch processes) 위의 세개가 다 수행되어야 배치 프로세스가 수행된다고 생각할 수 있는데 실제로 대부분의 경우엔 배치 프로세스가 기본적으로 수행되고 있고 어쩌다가 한번씩 저런 프로세스가 생기면 빠르게 처리함.
                                                          

Multilevel Feedback Queue

• 실제로는 사용하지 않음. 시스템 프로세스가 쓰는 특별한 클래스임. 우리가 쓰는 건 대부분 제너럴한 프로세스.
• 단점) CPU 바운드 프로세스와 interactive process를 큐 안에 넣어줘야함. 특성에 따라 큐를 만들어 놨는데, 돌리기 전까지는 모른다는 모순이 발생함. -> 프로세스가 각각의 큐에서 벗어나 다른 큐로 이동할 수 있게 만들어줌.
• 프로세스가 생성되면 첫번째 큐에 그냥 넣어줌. 작업이 끝나고 안 빠져나오고 주어진 시간을 다 써야 CPU burst가 길다고 판단하여 다음 큐로 넘김. 
  두번째 큐에서 주어진 슬라이스를 다 안쓰면 interactive한 작업이라고 판단함. 반대로 타임 슬라이스를 다 쓰면 I/O할 생각이 없는 CPU 바운드 프로세스라고 판단하여 FCFS로 넘김.
  FCFS로 넘어왔는데 I/O burst로 빠지면서 자꾸 웨이팅큐로 넘어가면 다시 첫번째 큐로 돌아감.
  => CPU 바운드인줄알고 넣었는데 시간이 지나고 interactive한 프로세스로 바뀌었구나!