[OS] CPU Scheduling

CPU Scheduling

CPU burst 가 긴 것도 있고 짧은 것도 있기에

CPU 스케쥴링이 필요하다.

여러종류의 job(=process) 가 섞여 있기 때문에 CPU 스케쥴링이 필요하다.

ready queue(CPU 를 얻고자하는 프로세스) 에서 어떤 프로세스에게 CPU를 할당할 것인지를 정하는 것이 CPU 스케쥴링이다.

I/O burst(I/O 요청을 하고 기다리는 시간)가 끝나면 CPU burst(CPU 명령을 실행하는 것) 상태에 들어간다.

두 가지 중요한 이슈

1. CPU burst에 들어온 프로그램들이 여럿이 있는데 누구한테 당장 cpu를 주는 가?
2. cpu burst 가 너무 길면 중간에 cpu를 뺏어서 다른 프로세스한테 주는 가?

사람과 직접적으로 연관있는 I/O bound job 들이 지나치게 오래기다리지 않게하는 방향으로 해야한다.

1. Non-preemptive Scheduling (비선점형) - 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다.(강제로 뺏지 않음)

2. Preemptive Scheduling (선점형)- 어떤 프로세스가 CPU를 할당받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지하고 CPU를 강제로 점유할 수 있는 것(강제로 뺏음)

CPU 스케쥴링의 성능 척도

• 시스템 입장의 성능척도

1. CPU Utilization(이용률) - 전체 시간 중에서 CPU 가 놀지 않는 시간 (최대한 놀게하지 마라)
2. Throughput(처리량) - 주어진 시간 동안 몇 개의 작업을 완료했는가?

• 프로그램 입장(고객 입장)에서의 성능척도

1. Turnaround Time (소요시간, 반환시간) - CPU를 사용하러 들어와서 다 사용할 때까지 걸린 시간
2. Waiting Time (대기 시간) - CPU 를 사용하고자 기다리는 시간
3. Response Time (응답 시간) - Ready Queue 에 들어와서 처음으로 CPU를 얻기까지 걸린 시간
   • Waiting Time 과 Response Time 과의 차이점
     • 선점형 스케쥴링 인 경우 CPU를 끝까지 사용하는 것은 아니다. 뺏겼다 얻었다(Waiting time 경우에는 뺏겼다 받았다 왔다갔다 할 수 있다.)
     • Response Time 최초로 CPU를 얻기까지 기다리는 시간을 말하는 것이다.

스케쥴링 알고리즘

1. FCFS(First-Come First-Served) - 먼저 온 고객을 먼저 서비스해주는 스케쥴링

   • FCFS 알고리즘은 앞의 프로세스가 얼마나 오랫동안 처리되는 지에 따라 평균 처리 시간이 달라진다는 단점이 있다. 먼저 온 프로세스의 처리 시간이 짧을수록 상당한 영향을 미친다.

   • Convoy Effect - 짧은 프로세스가 긴 프로세스 뒤에 나와 뒤에 있는 작업이 매우 늦어지는 현상

     • 제 1차 세계 대전에서 물자를 나르는데 뒤에서 호송하는 것과 관련 된 개념

2. SJF(Shortest-Job-First) - CPU burst 시간이 가장 짧은 작업에 먼저 스케쥴링 시켜주는 알고리즘

   • mininum average waiting time 을 보장한다.
   • 전체적으로 행복한 알고리즘

   1. Non Preemptive version - 지금 기다리고 있는 프로세스 중 가장 짧게 CPU 를 사용하는 작업에 CPU를 할당하면 더 짧은 CPU를 사용하는 작업이 들어오더라도 이 작업이 끝날 때까지 CPU 사용을 보장해주는 방식

   2. Preemptive version - CPU 를 주었다고 하더라도 더 짧은 프로세스가 도착하면 CPU를 뺏어서 그 프로세스에 CPU를 할당하는 방식 ( 이 방식을 Shortest-Remaining-time-First(SRTF) 라고도 부름 )

• SJF 의 문제점
  1. Long Process 는 Starvation(기아 상태)에 빠질 수 가있다. (영원히 CPU 자원을 받을 수 없다.)
  2. 다음번 CPU Burst Time을 알 수 가 없다. - CPU 사용시간을 알 수는 없지만 추정할 수는 있다. (과거에 이 작업이 프로세스를 얼마나 사용했었는가? 로 예측 할 수 있다) (=exponential averaging)

3. Priority Scheduling - 우선순위 스케쥴링 (우선 순위가 가장 높은 프로세스에게 CPU를 주겠다)

   • SJF 도 일종의 priority scheduling 이다.
   1. Preemptive - 우선순위가 높은 프로세스를 처리하고 있다가 더 높은 우선순위의 프로세스가 도착했을 때 CPU를 뺏을 수 있는 경우
   2. NonPreemptive - 일단 CPU를 할당 받으면 더 높은 우선순위의 프로세스가 도착하더라도 다 사용할 때 까지 보장해주는 것
   • 문제점 - 우선순위가 낮은 프로세스는 영원히 실행되지 않을 수가 있다.(Starvation)
   • 해결법 - Aging : 노화 : 우선 순위가 낮더라도 오래기다리면 우선순위를 높혀주자.

4. RR (Round Robin) - 현대적인 CPU Scheduling 은 Round Robin 방식을 사용하고 있다.

   • 할당시간이 지나면 프로세스는 Preempted 당하고 ready queue 의 제일 뒤에 가서 다시 줄을 선다.

   • N개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU의 1/N 을 얻는다 -> 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다. (n-1)q 시간을 기다리면 내 차례가 온다. q-time unit 을 짧게 잡아주면 빨리 돌아오게 된다.

• 장점 - 응답시간이 빨라진다. CPU를 최초로 얻기까지 걸리는 시간이 빨라진다. (줬다 뻇었다 그러기 떄문에) 그렇기에 짧은 처리 작업은 빨리 처리된 다음 최종 반환하기 떄문에 다 처리된 후 다른 프로세스에 더 오랜시간 할당 할 수있다.

• 단점

  1. 할당시간이 짧아지면 Context Switch 오버헤드가 커진다.
  2. 할당시간이 커지면 FCFS 와 같은 알고리즘이 된다.

5. Multilevel Queue

   • Ready Queue를 여러개로 나누어 분할 한다, 각 큐는 독립적인 스케쥴링 알고리즘을 가징
     • foreground(interactive) - RR - 사람과 교감을 하기 떄문에 응답시간을 짧게 가는 것이 좋다.
     • background ( batch - no human interaction) - 사람과 교감 없이 CPU 만 오랫동안 쓰는 Job - FCFS 알고리즘 사용 - 사람과 교감이 없다보니 먼저 온 순서대로 처리하는 것이 효율이 좋기때문에
   • 큐에 대한 스케쥴링이 필요하다.
     • 우선순위가 높은 대로 받다보면 우선 순위가 낮은 Job 들은 starvation 이 발생한다.
     • Stavation을 방지하기 위해서 우선순위가 높은(foreground RR) 방식의 Job 에 80%의 CPU time을 할당하고 나머지 20% 시간에는 FCFS 방식의 Background 에 할당한다.
   • 프로세스가 어느 위치에 주어야 하는가?

순서 highest priority -> lowest priority

• System Processes
• interactive processes
• interactive editing processes
• batch processes
• student processes

6. Multilevel Feedback Queue

• 출신이 낮아도 승격이 되고 출신이 높아도 낮아질 수 있는 스케쥴링

• 프로세스가 다른 큐로 이동 가능

• 에이징을 이와 같은 방식으로 구현 가능

• Multilevel Feedback Queue 를 정의하는 파라미터

  • Queue의 수
  • 각 큐의 scheduling algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 내쫓는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

• 위로 갈 수록 RR의 할당시간이 짧아지고 밑으로 갈수록 할당시간이 길어진다.

• 제일 하단의 Queue는 FCFS 방식을 사용한다.

• 할당 시간이 끝나도 처리가 안되게 되면 그 아래 Queue로 강등이 되는 방식

• 이 방식은 CPU 사용시간이 짧은 프로세스에게 우선순위를 많이 주는 스케쥴링 방식이다.

• CPU 사용량의 예측이 필요없다는 장점 (처음에 들어온 것은 무조건 짧은 시간을 할당 받기 때문에)

여기까지 CPU가 한 개인 경우의 스케쥴링 방식

---

Multiple-Processor Scheduling

• CPU가 여러개인 경우 스케쥴링은 더욱 복잡하다
• Homogenous Processor인 경우
  • Queue에 한 줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다.
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
• Load Sharing
  • 일부 프로세서에 Job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
• Symmetric Multiprocessing (SMP) - 모든 CPU들이 대등하다
  • 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric Multiprocessing - CPU가 여러개 있는데 그 중 하나가 전체적인 제어를 담당한다
  • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따른다.

Real-Time Scheduling

• Hard real-time systems
  • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케쥴링해야 함
• Soft real-time computing
  • Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함

Thread Scheduling

• Local Scheduling - 사용자 프로세스가 직접 어느 쓰레드에 CPU를 줄지 결정하는 것이다
  • User Level thread 의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케쥴할지 결정
• Global Scheduling - 운영체제가 쓰레드의 존재를 알고 있기 때문에 프로세스 스케쥴링 하듯이 운영체제가 어떤 알고리즘을 통하여 어떤 쓰레드에게 CPU를 줄지 결정하는 것
  • Kernel level Thread의 경우 일방 프로세스와 마찬 가지로 커널의 단기 스케쥴러가 어떤 thread를 스케줄할지 결정

Algorithm Evaluation (알고리즘 평가)

1. Queueing models
   • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 perfomance index 값을 계산
2. Implemetation(구현) & Measurement (성능 측정)
   • 실제 시스템에 알고리즘을 구현하여 실제 작업에 대해서 성능을 측정 비교
3. Simulation (모의 실험)
   • 알고리즘을 모의 프로그램으로 작성후 trace를 입력으로 하여 결과 비교

• 사진 자료 출처 : https://core.ewha.ac.kr/publicview/C0101020140401134252676046?vmode=f