CPU 스케줄링

<다중 프로그래밍과 스케줄링>
- CPU 유후 시간을 줄이기 위한 다중 프로그래밍
  - 작업 스케줄링(job scheduling)
    - 보조저장장치로부터 메모장에 올릴 작업 선택
    - 시작 시 혹은 한 프로세스 종료 때마다

  - CPU 스케줄링(CPU scheduling)
    - 메모리에 적재된 작업 중 CPU를 할당할 프로세스 선택



<스케줄링(Scheduling)>
- 자원에 대한 경쟁이 있을 때 경쟁자들 중 하나를 선택하는 과정

  - 작업(job) 스케줄링
    - 배치 시스템
    - 대기중인 배치 작업 중 메모리에 적재할 작업 선정

  - CPU 스케줄링
    - 프로세스/스레드 중 하나를 선택해 CPU 할당
 
  - 디스크 스케줄링
    - 디스크 입출력 요청 중 하나를 선택하여 장치를 사용하도록 

  - 입출력 장치 스케줄링
    - 프린팅 작업 중 하나를 선택해 프린터 장치 할당




<CPU burst와 I/O burst>
- 프로세스들은 실행(CPU 버스트)과 입출력 대기(I/O 버스트)의 순환으로 구성
  - CPU burst : CPU 연산이 집중적으로 처리되는 상황 -> I/O burst보다 CPU busrt처리가 많을 때 -> CPU 집중 프로세스
  - I/O burst : I/O 장치의 입출력이 집중적으로 처리되는 상황 -> CPU burst 타임보다 I/O burst 타임이 더 많을 때 -> I/O 집중 프로세스




<CPU 스케줄링(Scheduling)>
- 시스템의 목표를 달성할 수 있도록 준비 상태의 스레드 중 하나에 프로세서를 할당하는 일련의 과정
  - 프로세서의 이용률을 높임
  - 시스템의 작업 처리율을 높임
  - 사용자 응답시간을 줄임



<CPU 스케줄링의 목표와 평가 기준(1)>
- CPU 이용률(Utilization) 
  - 가능한 CPU를 busy하게 유지(40~90%)

- 처리률(Throughput)
  - 단위 시간 동안 완료된 프로세스/스레드들의 개수

- 대기 시간(Waiting time) 
  - 프로세스/스레드가 ready 큐에 대기한 시간
  - 스케줄링 알고리즘에 따라 크게 차이난다




<CPU 스케줄링의 목표와 평가 기준(2)>
- 응답 시간(Response time)
  - 요청 후 첫 응답(not 화면 출력)이 나오는 데까지 걸린 시간
  - 이 시간을 줄이기 위해선 충분한 자원 확보 필요
    - 반면, 자원 활용도가 낮아지는 원인이 될 수도 있다
  - 평균 응답 시간의 최소보다는 응답 시간 사이의 변동 폭 최소가 중요하기도

- 총처리 시간(Turnaround time)
  - 한 프로세스를 처리(도착~완료)하는 데 걸린 시간
    - CPU + I/O + waiting + ready
  - 배치 처리 시스템에서 주된 스케줄링 기준




<CPU 스케줄링의 목표와 평가 기준(3)>
- 공정성(fairness)
  - 어느 프로세스도 무한정 실행이 연기되어서는 안됨

- 시스템 정책(policy enforcement)
  - 컴퓨터 시스템의 특별한 목적 달성을 위한 스케줄링
  
- 자원 활용률(resource efficiency)
  - 가능한 사용률을 높일 수 있도록 스케줄링

- 예측 가능성
  - 시스템 부하에 무관하게 거의 같은 시간 내에 비슷한 비용으로 실행 가능해야 한다




<시분할 시스템의 CPU 스케줄링>
- 한 스레드가 너무 오래 CPU를 점유하지 않도록 해야 한다
  - 타임 슬라이스(time slice)
    - 스케줄 된 스레드에게 한 번에 할당되는 CPU 시간
    - 커널이 스케줄을 실행하는 주기 시간
      - 타이머 인터럽트의 도움을 받아
      - 현재 실행중인 스레드를 강제 중단한 후 준비 리스트로 보냄
    - 타임 퀀턴(time quantum), 타임 슬록(time slot)이라고도 한다




<CPU 스케줄링이 일어나는 상황>
- ready 큐에 있는 스레드들 중에 하나를 선택하여 CPU를 할당
  - 스레드가 블록될 때 : CPU 이용률 향상 위해
  - 스레드가 자발적으로 CPU를 반환할 때
  - 스레드에게 할당된 타임 슬라이스가 만료될 때 : 균등한 CPU 사용 위해
  - 더 높은 우선순위의 스레드가 요청한 입출력 작업이 완료될 때 : 시스템의 목적(우선순위) 위해




<선점형 vs 비선점형>
- 비선점형(Non-preemption scheduling)
  - 프로세스가 스스로 CPU를 반납(비 강제적)
    - 상황 1 & 2에서만 스케줄링이 발생하는 경우

- 선점형(Preemptive scheduling)
  - 강제적으로 CPU 할당을 반납 받음
    - 상황 1~4에서 모두 스케줄링이 발생
  - 공유 자료에 대한 접근 조정이 필요
  - 컨텍스트 전환 전에 시스템 호출 처리를 완료하거나 I/O 요청을 blocking 한다
    - 실시간 컴퓨팅이나 멀티 프로세서 지원에 악영향
  - 오늘날 범용 OS에서 채택




<CPU 스케줄링과 CPU 디스패치>
- CPU 스케줄링은 커널에 의해 처리됨
  - 단, 스케줄링을 담당하는 스레드가 존재하진 않음

  - 시스템 호출/ISR이 끝나는 마지막 단계에서 처리
  - 시스템 호출/ISR에 의해 호출되는 함수 형태로 존재
    - 스케줄러 : ready 리스트에서 다음에 수행할 스레드 선택하는 코드
    - 디스패처(dispatcher) : 스케줄러에 의해 선택된 스레드를 CPU가 실행되도록 처리
      - 컨텍스트 스위칭을 처리하는 커널 코드




<기아와 에이징>
- 기아(Starvation) 
  - 스레드가 스케줄링에서 선택되지 못한 채 오랜 동안 ready 리스트에 있는 상황
    - 우선순위 기반의 시스템에서 더 높은 우선순위의 스레드가 계속 시스템에 들어 오는 경우
    - 짧은 스레드를 먼저 실행하는 시스템에서, 짧은 스레드가 계속 실행되는 경우

- 에이징(Aging)
  - 스레드가 ready 리스트에 머무는 시간에 비례해서 스케줄링 순위를 높이는 방법
    - 오래 기다릴 수 있지만, 언젠가는 스케줄링 되는 것을 보장




<CPU 스케줄링 알고리즘>
- First-Come, First-Served(FCFS)
- Shortest-Job-First(SJF)

- Shortest-Remaining-Time-First(SRTF)
- Round Robin(RR)

- Priority
- Multilevel Queue
- Multilevel Feedback Queue




<선입 선처리 스케줄링(First-Come, First-Served Scheduling, FCFS)>
- CPU를 먼저 요청하는 프로세스/스레드가 CPU를 먼저 할당 받음
  - 비선점형 스케줄링(자발적으로 CPU를 내줄 때까지 기다리는 것)

- 가장 간단한 알고리즘
- ready 큐를 FIFO 큐로 쉽게 구현
*ready 큐 : CPU를 할당받기 위해 대기하고 있는 프로세스들의 목록

- 일반적으로 기아는 발생되지 않는다
- 처리율이 낮다 : 평균 대기 시간이 길어질 수는 있다




<호위 효과(Convoy Effect)>
- 긴 CPU bust를 가진 프로세스/스레드에게 CPU가 할당되길 다른 프로세스/스레드들이 기다림
  - 하나의 CPU-bound 프로세스/스레드 A와 다수의 I/O-bound 프로세스/스레드들 B를 가정
    - A가 CPU 사용 시 B들은 I/O를 마치고 CPU 대기
    - A가 I/O 처리 시 B들은 CPU 사용을 마치고 I/O 대기

- CPU와 I/O 장치들은 idle 시간이 커진다
  - 빨리 끝날 수 있는 프로세스/스레드부터 처리하자 : Shortest Job First Scheduling




<최소 작업 우선 스케줄링(Shortest-Job-First Scheduling, SJF)>
- Shortest-next-CPU-burst scheduling
  - 다음에 수행할 프로세스/스레드들 중 가장 짧은 CPU burst를 갖는 프로세스/스레드를 우선 선택
  - 동일한 수행시간을 갖는다면 FCFS로 처리

- 특징
  - 평균 대기 시간이 작음(최적)
  - 다음 CPU burst의 길이 파악이 어려움 : 현실에서는 사용되지 못한다
  - 기아 발생이 가능
  



<최소 잔여시간 우선 스케줄링(Shortest-Remaining-Time-First Scheduling, SRTF)>
- 선점형 SJF
  - ready 큐에 현재 실행중인 프로세스 A의 잔여 CPU burst보다
  - 더 짧은 CPU burst를 가진 프로세스 B가 ready 큐에 도착하면
  - A는 B에 선점된다

- 특징
  - 기아 발생 가능
  - 평균 대기 시간 최소화




<우선 순위 스케줄링(Priority Scheduling)>
- 각 프로세스/스레드에 우선순위 지정
- 가장 높은 우선순위를 가진 프로세스/스레드에게 CPU 할당
  - 선점형 vs 비선점형

- 기준
  - 내부/외부적 요인들
  - FCFS : ready 큐에 들어온 순서
  - SJF : (추정된) CPU burst의 길이 -> 가장 짧은 것
  - SRTF : (추정된) 잔여 CPU burst의 길이 -> 남은 CPU burst time이 가장 짧은 것




<우선순위 스케줄링의 문제점>
- 기아(Starvation) / 무한봉쇄(Indefinite Blocking)
  - 낮은 우선순위의 프로세스들이 무한히 대기
    - 실행 준비는 되어 있으나 CPU를 할당받지 못함

- 해결책 : 에이징(Aging)
  - 오래도록 처리되지 못하고 남아있는 프로세스에 대해 점진적으로 우선순위를 올려주는 기법




<순환 할당 스케줄링(Round Robin Scheduling)>
- 시분할 시스템을 위해 설계됨
- 규정 시간량(Time quantum)/시간 할당량(Time slice)
  - 각 프로세스에게 한 번에 할당되는 CPU 시간 : 보통 10~100msec
  - 이 시간이 만료되어 설정된 타이머에서 완료 인터럽트 발생 시 디스패치
- 선점형 FCFS
  - FCFS와 유사하나 프로세스들 사이를 강제로 옮기기 위한 선점이 추가
  - 순환 FIFO ready 큐
- 일반적으로 평균 대기 시간이 길다





<RR 스케줄링의 성능>
- 시간 할당량의 크기와 성능 
  - 잦은 스케줄링으로 전체 스케줄링 오버헤드가 큼
    - time quantum이 무한(infinite)이면, <=> FCFS(선입선처리 스케줄링)
    - time quantum이 너무 짧으면(too short) <=> 프로세서 공유
      - n개의 프로세스는 각각 1/n 속도로 실행되는 자신만큼의 프로세서를 가지고 있는 것처럼 보여진다

- 기아가 발생하지는 않는다




<다단계 큐 스케줄링(Multilevel Queue Scheduling)>
- 프로세스/스레드를 n개의 우선순위 레벨로 구분, 높은 레벨을 먼저 처리할 경우에 유용
  - 15950년대 후반

- ready 큐를 다수의 독리벅인 큐로 분류하여 구성
  - 각 프로세스/스레드는 특성에 따라 영구적으로 특정 큐에 할당 
    - 다른 레벨의 큐로 이동 불가
  - 각 큐는 자신만의 스케줄링 알고리즘을 가지고 스케줄 가능




<MLQ 스케줄링 특징>
- 각 큐는 낮은 우선순위의 큐보다 절대적인 우선 순위를 가진다
  - 비선점 : 스레드 종료 시 스케줄링
  - 선점 : 높은 레벨의 큐에 도착 시 스케줄링
    - 기아상태 발생 가능

- 스레드별로 고정 우선순위를 두고 높은 우선순위의 스레드를 먼저 실행시키고자 할 때 유용
  - 포그라운드 > 백그라운드
  - 시스템 스레드 > 대화식 스레드 > 배치 스레드
  - 교수자 스레드 > 대학원생 스레드 > 학부생 스레드




<다단계 피드백 큐 스케줄링(Multi-Level Feedback Queue)>
- MLQ의 큐 사이에 프로세스들의 이동을 허용
  - 평균대기시간과 응답시간을 줄이고 기아 방지
    - CPU burst가 짧은 스레드, I/O 작업이 많은 스레드, 대화식 스레드를 우선 실행
      - CPU 시간을 많이 사용하는 스레드는 lower-priority 큐로 이동
    - lower-priority 큐에서 너무 오래 대기하는 프로세스/스레드는 higher-priority 큐로 이동

- 가장 일반적인 CPU 스케줄링 알고리즘
- 성능에 영향을 미치는 매개변수들이 많아 복잡
  - 큐 개수, 각 큐의 스케줄링 알고리즘
  - 프로세스의 큐 이동(L<->H) 시기 결정 방법
  - 프로세스 생성 시 진입할 큐 결정 방법




<멀티 코어 시스템에서의 CPU 스케줄링 이슈>
- 단일 코어 시스템의 CPU 스케줄링 적용시(1)
  - 컨텍스트 스위칭 오버헤드 증가
    - 이전에 실행된 적 없는 코어에 스레드 배치 시 캐시에 새로운 스레드 코드/데이터 적재 오버헤드

- CPU 친화성(CPU affinity)적용
  - 스레드를 동일한 코어에만 실행하도록 제한
  - =코어 친화성(core affinity), CPU 피닝(pinning), 캐시 친화성

- 코어 당 스레드 큐 사용





<멀티코어 시스템에서의 CPU 스케줄링 이슈>
- 단일 코어 시스템의 CPU 스케줄링 적용시(2)
  - os가 스레드를 무작위로 스케줄링하면 코어별 부하 불균형 발생
    - 각 코어마다 처리할 스레드 수의 불균형 발생

- 부하 균등화(load balancing) 기법으로 해결
  - 푸시 마이그레이션(push migration)
  - 풀 마이그레이션(pull migration)