OS - CPU Scheduling

CPU Scheduling

• Ready 상태인 프로세스 중 수행시킬 프로세스를 선택하는 과정

Process Execution

• CPU Burst : CPU 명령어를 수행하는 구간
• I/O Burst : I/O 작업이 끝나기를 기다리는 구간
• A CPU-bound process : CPU Burst가 길고 I/O Bound가 짧은 process
  • 연산이 많이 필요하고 사용자가 개입하지 않는 process
  • ex) 딥러닝, 데이터 마이닝, 슈퍼컴퓨터 계산
• An I/O-bound process : CPU burst가 짧고, I/O Bound가 길고 많은 process
  • 사용자와 interactive하게 동작하는 process
  • ex) web-browser, hwp파일, mp3파일, 웹 크롤링

Dispatch

• Scheduling으로 선택한 process를 CPU로 올리는 작업이 dispatch
• Context Switching, Switching to user mode

Sceduling

Non-Preemptive Scheduling (실생활)

• 이미 할당된 CPU를 다른 프로세스가 빼앗을 수 없는 기법
• Process가 waiting state가 되거나 끝났을 때만 context switching이 발생

Preemptive Scheduling

• scheduler가 job을 interrupt하여 context switching이 가능한 scheduling
• 실행 중인 프로세스를 중단시키고 우선 순위가 높은 프로세스에게 CPU할당이 가능한 기법

Scheduling Criteria

CPU Utilization

• CPU를 최대한으로 사용한다.

Throughput

• 단위 시간당 처리량
• CPU Throughput 단위 : 초당 실행 명령어의 양 MIPS
• Network Throughput 단위 : 초당 전송 속도 Mega bps

Turnaround time

• 프로세스의 실행부터 종료까지의 시간
• Finish time – arrival time

Waiting Time

• Ready queue에서 기다리는 시간
• Finish time – arrival time – burst time

Response time

• 사용자가 작업을 요청하고 첫번째 결과를 확인할 때까지 걸리는 시간

Scheduling goals

All systems

• Fairness : 각각의 프로세스가 공평하게 CPU를 사용해야 한다.
• Balance : 시스템의 모든 부분을 사용한다.

Batch systems : 프로그램 하나만을 실행시키는 시스템

• Throughput : 시간당 처리하는 job을 최대화한다.
• Turnaround time : 요청과 종료 사이의 시간을 최소화한다.
• CPU utilization : CPU 사용을 최대화한다.

Interactive systems

• Response time : ready queue에서 기다리는 시간을 최소화한다.
• Waiting time : wait queue에서 기다리는 시간을 최소화한다.
• Proportionality : 사용자의 기대를 충족시킨다 (지불 비용에 따른 다른 성능/서비스 등)

Real-time systems

• meeting deadlines : avoid losing data
• Predictability : avoid quality degradation in multimedia systems
  • kernel과 application에서 소요되는 bound 시간을 예측가능해야한다.

Starvation

• 특정 프로세스가 사용해야할 자원을 다른 프로세스가 사용하거나 우선 순위에서 밀려 동작하지 못하는 상황을 말하며, Ready queue에 계속 대기하며 CPU에서 동작하지 못하는 상황을 지칭한다.

Scheduling Algorithms

FCFS(first come first served)

• 도착한 순서대로 처리되므로 공정성이 보장된다.
• Non-preemptive 방식이며 공정성이 보장되어 starvation이 발생되지 않는다.
  문제점
• 긴 작업이 먼저 오면 짧은 작업이 뒤에서 대기하여 평균 waiting time이 늘어난다.
• Convoy effect : short process behind long process
• 우선 순위를 고려하지 못한다.
  

SJF(Shortest Job First)

• FCFS의 긴 Waiting time을 보완한 Non-preemptive 방식, 고객을 만족시킨다.
• 가장 작은 CPU Burst를 가질 것으로 예상되는 job을 고른다.
• 평균 waiting time이 optimal(동일한 성능은 있지만, 더 좋은 성능은 없다) min하다.
  문제점
• 미래의 CPU Burst 크기를 예측할 수 없다. (컴퓨터에 적용할 수 없다)
• starvation을 발생시킬 수 있다.
  

SRTF(Shortest Remaining Time First)

• preemptive SJF
  

Priority

• 우선 순위를 고려하여 작업을 처리한다.
• 우선순위 별로 queue를 만들며 우선순위가 같다면 RR방식으로 처리한다.
• Starvation을 발생시킬 수 있으며 Aging방식(시간이 지날수록 프로세스의 우선순위를 높여준다)으로 해결할 수 있다.

Round-Robin(RR)

• preemptive 방식
• Time quantum 단위 만큼 CPU에서 실행되며 시간이 지나면 Ready queue의 마지막으로 간다.
• Time quantum large -> FIFO / Time quantum Small : 너무 작으면 overhead가 커진다.
• SJF 보다 Turnaround가 크지만 response면에서 더 좋다
• Rule of Thumb : CPU burst의 80%가 time quantum보다 작을 때 좋다

Multi-Level Queue

• 각 level별로 queue를 달고 그에 알맞은 기법을 사용한다.
• ex) foreground(interactive) – RR / background(batch) – non-preemptive
• Fixed priority scheduling : Queue별로 우선순위를 부여하며 각각 알맞은 기법을 적용한다.
• Time Slice : 각 queue별로 동작하는 time quantum을 설정한다.

Multi-Level Feedback Queue(MLFQ)

• 실행하기 전까지 Interactive/batch 등 프로세스의 종류를 알 수 없기에 queue를 이동하면 작업을 수행한다.
• 전통적인 UNIX에서 사용한 기법
• Interactive process에게 높은 우선 순위를 주기 위하여 고안되었다.
  

현재 운영체제가 채택한 방법

• Queue에 Priority두고, 우선 순위가 같은 작업에 대해 RR을 적용한다(Fixed priority scheduling)

Multiple processor scheduling

Load balancing (가장 중요)

• push/pull migration : 코어의 가용성에 따라 작업할 코어를 이동시킨다.

Processor affinity

• 프로세스를 하나의 core에서 처리하는 방법과 여러 core에 migration되며 처리되는 방식이 있다. 하나의 core에서 처리될 때 core의 cache메모리를 활용할 수 있기 때문에 성능이 더 좋아진다. affinity는 프로세스와 core간의 결합성을 나타낸다.
• hard affinity는 성능이 중요하여 결합력을 강하게 한다는 뜻이다
  

Real-time scheduling

• real-time은 embedded에 많이 사용되며 embedded는 전원이 켜지면 이미 만들어진 프로세스를 전원이 꺼질 때까지 반복 수행된다. >> 프로세스가 주기적으로 실행된다.

Static priority scheduling (현재 사용 방법)

• 프로세스의 우선 순위가 바뀌지 않는다.
• 1/rate = period, rate에 비례하여 우선 순위를 부여한다.
• deadline을 지키지 못한다는 문제점이 발생할 수도 있다.

dynamic priority scheduling

• 실행될 때마다 프로세스의 우선 순위가 바뀐다.
• deadline이 가까운 프로세스에게 높은 우선 순위를 부여한다.
• deadline을 넘기지 않으며 optimal방법이지만 overhead가 너무 커서 사용하지 않는다.
  

Linux scheduling

• 0이 우선순위가 가장 높다
  

• normal 우선 순위 중에서 모든 프로세스를 100번으로 할당 후 time quantum을 다 쓰거나(무한루프) CPU사용량이 많으면 우선 순위를 낮추는 방법을 선택할 수 있다.

Nice value

• 사용자가 지정할 수 있는 우선 순위 변수로 -20 ~ 19의 값을 할당할 수 있으며 -20을 할당할 경우 100번의 우선순위를 가져 높은 우선순위로 처리될 수 있다.

CFS

• Virtual run time을 관리하는 변수 vruntime을 통해 우선 순위를 관리한다 (Normal 우선순위에)
• task의 우선 순위를 balanced binary tree형태로 관리한다.

Windows scheduling

• 숫자가 클수록 우선순위가 높다

  

알고리즘 증명방법

Implementation

• 직접 구현하여 적절한 benchmarks와 함께 테스트를 진행한다.

Simulation

• statical input을 이용하여 특정한 환경을 가정하거나 단순화된 알고리즘 버전에 입력하여 성능을 테스트해본다. 구현이 어려울 때 사용하는 방법
• 실제의 상황을 대략적으로 구현한다.
• trace tape(or trace data) : 실세계의 실제 데이터를 input으로 사용한다.

cf) Emulation

• 하드웨어의 동작을 100% 소프트웨어적으로 구현한다.

Deterministic modeling / Queueing models

• 수학적인 방법을 사용하여 알고리즘의 성능을 테스트 한다.
• 명확하고 틀림없는 방법으로 증명할 수 있다.
• 실세계의 실제 데이터를 테스트에 사용할 수 없다는 단점이 있다.
• 통신 알고리즘 테스트에 많이 사용된다.