5. CPU Scheduling

CPU Scheduling이 필요한 이유

: 사람과 interaction하는 Job과 CPU만 사용하려는 Job이 섞여있기 때문에 적절한 스케줄링이 필요.

 

- CPU and I/O Bursts in Program Execution

위의 그림과 같이 컴퓨터의 모든 프로그은 다음 프로세스를 진행(프로그램마다 실행하는 방법은 다를 수 있음)

EX) running -> I/O -> ready -> I/O ...

즉, CPU만 연속으로 실행하거나 I/O만 실행하는 컴퓨터는 없으며, 실행하는 단계는 burst라고 부른다.

 

- 프로세스의 특성 분류

• I/O bound process
  • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
  • many short CPU bursts
• CPU bound process
  • 계산 위주의 job (과학 계산 응용에 많이 사용)
  • few very long CPU bursts

- CPU Scheduler & Dispatcher

• CPU Scheduler  :  Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고르는 과정
• Dispatcher : CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘기는 과정(=context switch : 문맥 교환)
• CPU 스케줄링이 필요한 경우 ( = 프로세스에게 다음과 같은 상태 변화가 일어나는 경우)
  1. Running -> Blocked (EX : I/O 요청하는 시스템콜)
  2. Running -> Ready (EX : 할당시간만료로 인한 timer interrupt)
  3. Blocked -> Ready (EX : I/O 완료 후 interrupt)
  4. Terminate

비선점형 nonpreemptive( =강제로 빼앗지 않음)

선점형 preemptive(=강제로 빼앗음)

 

- Scheduling Criteria

Performance Index (=Performance Measure, 성능 척도)

• 시스템 입장에서의 성능 척도
  1. CPU utilization(이용률) : CPU가 사용된 전체 시간 중에서 놀지 않고 일한 시간
  2. Throughput(처리량) : 주어진 시간동안 완료한 프로세스 개수
• 프로세스 입장에서의 성능 척도
  1. Turnaround time(소요시간, 반환시간) : 프로세스가 CPU를 사용한 시간(대기시간 포함)
  2. Waiting time(대기 시간) : CPU를 사용하기 위해 기다린 시간의 총 합
  3. Response time(응답시간) : Ready Queue에 들어와서 처음으로 CPU를 사용할 때까지 기다린 시간
     - 응답시간이 별도로 있는 이유 : 사용자 입장에서 첫 사용시 반응이 빨라야 하기 때문

- Scheduling Algorithms

1. FCFS(First-Come First-Served) : 먼저 들어온 프로세스를 먼저 처리하는 알고리즘 (비선점형 스케줄링)

* Convoy Effect: 하나의 큰 프로세스가 자원을 오랫동안 독점 하는 동안 작은 프로세스들이 자원을 할당받지 못하는 현상. 

 

2. SJF(Shortest-Job-First) : CPU를 사용하는 시간이 짧은 프로세스부터 처리하는 알고리즘

*주어진 프로세스들에 대해 minimum average waiting time을 보장

- Nonpreemptive : 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음

- Preemptive(=Shortest-Remaining-Time-First[SRTF]) : 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김

SJF의 단점 : 다음 CPU Burst Time 예측 불가능(추정만 가능) -> 과거의 CPU burst time을 이용해서 추정

 

3. Priority Scheduling : 우선순위가 제일 높은 프로세스먼저 처리하는 알고리즘(가장 높은 우선순위 = 가장 작은 정수)

- Nonpreemptive : 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점 당하지 않음

- Preemptive : 현재 수행중인 프로세스의 우선순위보다 더 높은 우선순위를 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김

 

4. Round Robin(RR) : 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가지며 각 프로세스를 할당 시간만큼 처리하는 알고리즘(선점형), 현대 컴퓨터는 거의 이 알고리즘을 따름

- Multilevel Queue

고려 사항

1. 프로세스를 어느 줄에 넣을 것인가?

2. 프로세스가 들어가 있을 때 무조건 우선순위에 따라 CPU를 부여할 것인가?

 

• Ready Queue를 여러 개로 분할
  • foreground queue - interactive한 job 
  • background queue - 사람과 interaction이 일어나지 않는 batch형 job
• 각 큐는 독립적인 스케줄링 알고리즘을 가짐
  • foreground queue - RR(사람과 interaction이 일어나는 job이기 때문에)
  • background queue - FCFS(응답시간이 빨라서 좋을게 없는 job들만 모여있음)
• 큐에 대한 스케줄링이 필요
  • Fixed priority scheduling(우선순위를 강하게 적용하는 방식)
    - starvation이 발생할 가능성이 높음.
  • Time slice(starvation이 일어나는 것을 방지하는 방식)
    - 각 큐에 CPU time을 적절한 비율로 할당
    - Eg., 80% to foreground in RR, 20% to background in FCFS

- Multilevel Feedback Queue

• 프로세스가 다른 큐로 이동 가능
• 에이징(aging)을 이와 같은 방식으로 구현할 수 있음
• Multilevel-feedback-queue scheduler를 정의하는 파라미터
  • Queue의 수
  • 각 큐의 scheduling algorithm
  • Process를 상위 큐로 보내는 기준
  • Process를 하위 큐로 내쫒는 기준
  • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

보통은 처음 들어오는 process는 우선순위가 가장 높은 queue(rr-time quantum이 굉장히 짧음)에 입력

"CPU 사용시간이 짧은 프로세스에게 유리한 방법"

 

- Multiple-Processor Scheduling

CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐

• Homogeneous processor인 경우
  • queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있음
  • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에 문제가 복잡해짐
• Load sharing
  • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘이 필요
  • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
• Symmetric Multiprocessing(SMP)
  • 각 프로세서가 각자 알아서 스케줄링 결정
• Asymmetric multiprocessing
  • 하나의 CPU(master)가 시스템 데이터의 접근과 공유를 책임지고 나머지 CPU는 master의 명령에 따름

 

- Real-Time Scheduling

real-time job : deadline이 정해진 job, 정해진 시간안에 끝내야 하는 일

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

 

- Thread Scheduling

thread : 하나의 process안에 CPU 수행 단위가 여러 개 있는 것

• Local Sechduling
  : User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄할지 결정
  (OS는 Thread의 존재를 모르기 때문에 프로세스 내부에서 결정)
• Global Sechduling
  : Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정
  (OS는 Thread의 존재를 알기 때문에 OS에서 결정)

 

- Algorithm Evaluation

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