OS - Scheduling

#CPU scheduling

- 레디 큐에서 돌아갈 프로세스를 고름

    - 모든 프로세스가 메모리에 있다고 가정

- 멀티프로그래밍 환경에서 필수정

    - CPU utilization을 최대화 하는것이 목표

- Non-preemptive scheduling - 다음 상황에서만 작동

    1. 프로세스가 종료

    2. 러닝에서 블락으로 프로세스 상태 전이

 

#Process Execution Behavior

- 가정:

    1. 1 유저당 1 프로세스

    2. 1 프로세스당 1 스레드

    3. 프로세스들은 독립적, 자원 확보 경쟁(CPU 포함)

- 프로세스는 CPU에서 런 - I/O burst cycle:

    1. 잠시 계산(CPU에서)

    2. I/O 진행

    3. 1, 2번 반복 - ★입출력을 해야 컴퓨팅이 가능하기 때문임★

ㅁ- Two types of processes:

    1. CPU-bound - 대부분의 컴퓨팅(long cpu burst)과 약간의 I/O

    2. I/O-bound - 대부분의 I/O, 약간의 컴퓨팅(short CPU burst)

 

#First-Come-First-Served(FCFS)

- 또는 FIFO, Run-Until-Done이라고도 함

- 정책:

    1. 도착한 순서대로 레디큐에서 프로세스 선택, non-preemptively(프로세스가 끝날 때 까지 자원을 뺏기지 않음) 실행

- FIFO queue를 사용해서 구현 (Nachos에서 사용됨)

-> Greedy와 비슷. 짧은 프로세스를 앞으로 보내면 평균 대기시간이 줄어듦

-> 그러나 프로세스 시간을 정확히 예측할 수 없는 점이 한계. SJF는 일종의 개념일 뿐임

 

#CPU Scheduling Goals

- CPU 스케줄러는 다음을 결정:

    1. 프로세스가얼마나 오래 실행할 것인가

    2. 어떤 순서로 실행되는가

 - User-oriented scheduling policy goals:

    1. 평균 응답 시간을 최소화, 적절한 응답을 받는 대화형 사용자 수를 최대화

    2. 처리 완료까지의 시간을 최소화

        - 실행 시간과 대기 시간을 포함

    3. 평균 응답 시간의 분산을 최소화

        - 예측 가능성이 중요

        - 시스템 부하에 따라 동일한 시간에 프로세스가 실행되어야 한다.

-> 가장 이상적인 스케줄링은, 미래를 내다 보고 CPU burst time만큼 자원을 모두 주는 것.

-> 그러나 얼마나 필요한지 정확히 알 수 없음

- System-oriented scheduling policy goals:

    - 처리량 최대화

    - cpu utilization 최대화

- Other system-oriented scheduling policy goals:

    - Fairness -> 모든 프로세스가 공평하게, starvation 방지(그러나 평균 응답시간을 줄이기 위해서는 덜 fair해도 됨)

    - Balace resources -> 모든 자원이 busy하게

 

#FCFS 평가

- Non-preemptive

- Response time - 실행 시간의 분산이 클수록 느림

    > 만약 짧은거 앞에 긴게 있다면 짧은거는 오래 기다려야 함

    > CPU-bound 프로세스가 I/O-bound 앞에 있다면 -> Low CPU, I/O utilizaion(Convoy effect)

*CPU utilizaion: CPU 활용

- 처리량: Not emphasized

*throughput(처리량): 단위시간 안에 처리되는 프로세스가 몇개냐

- 공정성: 짧은 프로세스, I/O bound에 불리

- Starvation: 불가능

- Overhead: 최소

 

#Preemptive vs Non-preemptive Scheduling

- Non-preemptive scheduling: 스케줄러가 다음에서만 실행됨

    1. 프로세스 종료

    2. 프로세스가 running -> blocked로 전이

- Preemptive scheduler: 거의 아무때나 실행 가능함

    1. 프로세스 생성

    2. 차단된 프로세스가 준비

    3. 타이머 인터럽트 발생

    > 오버헤드가 더 많이 들지만, 긴 프로세스가 CPU 독점하는것 방지

    > sys call을 처리하거나 일관성이 없는 상태에 있을 때 OS 커널을 선점해서는 안되고, 이런 경우 서비스 제공해야 함

    X: 유저 프로세스 간에 공유된 데이터를 일관되지 않은 상태로 남길 수 있음

 

#Round Robin

- 정책:

    1. time slice를 정한다(time quantum)

    2. 레디큐의 헤드에 있는 프로세스를 고른다

    3. 1 time slice만큼 실행하고, 완료되지 않았더라고 레디큐의 tail로 보낸다

    4. 그 프로세스가 time slice가 끝나기 전에 종료되거나 block되면, 다음 헤드에 있는 프로세스를 실행시킨다

- 구현:

    1. 하드웨어 타이머(주기적 간격으로 인터럽트)

    2. FIFO ready queue(add to tail, from head)

->ex 1에서 p1의 시간이 두번 계산됨.(0, 10-4)

->중간에 선점되어 빼앗긴 시간까지 계산된 것

->그러나 이는 계산하지 않아도 됨.

 

#Round Robin 평가

- Preemptive(타임 슬라이스 끝에서)

- Response time: good for short processes

     > 긴 프로세스는 n(다른 프로세스 수)*q(타임 슬라이스 길이) 만큼기다릴 수 있음

- Throughput: 타임 슬라이스에 따라 다름

     > 너무 작으면: 너무 많은 context swtich

     > 너무 크면: FCFS와 비슷해짐

- Fairness: I/O bound 프로세스에 페널티

- Starvation - 불가

- Overhead - 낮음(우선순위를 고려하지 않으므로 오버헤드가 낮다고 판단)

    > priority scheduler들은 우선순위를 고려하여 다음 프로세스를 선택하기 때문에 오버헤드가 높다.

 

#Shortest Job First(SJF)

- 또는 Shortest-Process-Next(SPN)

- 정책:

    > 가장 작은 CPU burst를가진 프로세스를 선택, non-preemptively 돌림

    > 같은 시간이 남았다면 FCFS로 처리

- Difficulty: 다음 CPU burst를 계산하는 것이 어려움

    > 접근- 길이를 추척, 과거 퍼포먼스, 과거 예측을 이용

-> 시간 계산은 CPU burst만 고려함. I/O는 고려하지 않음

-> SJF는 이론일 뿐임. 현실적으로 구현되지 않음

-> 기준을 설정하기 위해 존재. 최적 알고리즘의 기준. 이것과 비교하여 실제 스케줄러를 평가

#SJF 평가

- Non-preemptive

- Response time: 짧은 프로세스에게 좋음

    > 긴 프로세스는 많은 짧은 프로세스를 기다릴 수도 있음

    > 거의 최적 - 평균 대기시간 최소화

- Throughput: 높음

- Fairness: 긴 프로세스에게 불리

- Starvation: 긴 프로세스에게 가능

- Overhead: 높을수 있음(CPU burst time을 기록하고, 측정하는데에 가능)

 

#Shortest-Remaining-Time(SRT)

- SJF의 preemptive 버전

- 정책:

    1. 가장 짧은 CPU burst가 남은 프로세스를 선택. preemptive 하게 돌림

        > 종료, 블락, 레디큐 진입, 새 프로세스 도착, 블락된 프로세스 해제 될 때까지

    2. 스케줄러는 남은 CPU burst 시간이 가장 짧은 프로세스를 선택

#SRT 평가

- Preemptive(새 프로세스가 레디큐에 도착할 때마다)

- Response time: good

    > 거의 최적 - 평균 대기시간 최소화

- Throughput: high

- Fairness: 긴 프로세스에게 불리

    > 그러나 긴 프로세스도 결국 짧은 프로세스가 됨

- Starvation: 긴 프로세스에게 가능

- Overhead: 높음(잔여 CPU burst 시간을 계속 계산하기 때문임)

-> SRT도 이상적일 뿐 현실적이지 않음

 

#Priority Scheduling

- 정책: 각 프로세스에 우선순위를 부여

    > 외부적으로 정의됨 -> 가격, 중요도, 정책 등에 따라서

    > 내부적으로 정의됨 -> 요구 메모리, 요구 파일, 요구 CPU vs 요구 I/O

    > SJF는 priority scheduling임. 다음CPU burst순위에게 인버전 되기 때문

    > 가장 높은 우선순위를 가진 프로세스를 고르고 실행시킴

- 평가:

    > Starvation: 우선순위가 낮은 프로세스에게 가능

        > "Aging process"로 방지: 대기시간이 길어질수록 우선순위를 높여줌