[운영체제] CPU 스케줄링

기본 개념

• 코어가 하나인 시스템에서는 한순간에 오직 하나의 프로세스만 실행 가능
• 나머지 프로세스는 CPU의 코어가 가용 상태가 되어 다시 스케줄 될 수 있을 때까지 기다려야 함
• 멀티프로그래밍의 목적은 CPU 이용률을 최대화하기위해 항상 실행중인 프로세스를 가지게 하는 것

CPU I/O 버스트 사이클

• 프로그램이 실행되면 CPU가 일을 수행하고, I/O 요청에 대한 응답을 기다리는 일을 반복한다
• Cpu Burst Time : CPU가 일을 수행하는 시간
• I/O Burst Time : I/O 요청에 대한 응답을 기다리는 시간

CPU 스케줄러

• CPU가 사용 가능한 상태가 될 때마다 운영체제는 준비 큐에 있는 프로세스 중 하나를 선택해 실행
• 준비 큐는 선입선출큐, 우선순위큐, 트리, 연결리스트 등 다양하게 구현 가능
• 큐에 있는 레코드들은 일반적으로 PCB이다

선점 및 비선점 스케줄링

• CPU 스케줄링 결정은 다음 네가지 상황에서 발생
  • 프로세스가 실행 상태에서 대기 상태로 전환 (I/O 요청)
  • 프로세스가 실행 상태에서 준비 완료 상태로 전환 (인터럽트 발생)
  • 프로세스가 대기 상태에서 준비 완료 상태로 전환 (I/O 종료)
  • 프로세스가 종료
• 1,4번 상황은 반드시 새로운 프로세스를 선택해야 한다. 이러한 스케줄링 방법을 비선점(nonpreemptive) 협조적(cooperative) 스케줄링이라 함
• 2,3 번상황은 선점(preemptive) 스케줄링 이라고 함

디스패처

• 디스패처 : CPU 코어의 제어를 CPU 스케줄러에 주는 모듈 한 프로세스에서 다른 프로세스로 문맥 교환 사용자 모드로 전환 프로그램을 다시 시작하기 위해 사용자 프로그램을 적절한 위치로 이동
  
• 디스패치 지연 : 디스패처가 한 프로세스를 정지하고 다른 프로세스의 수행을 시작하는데까지 소요되는 시간

스케줄링 기준

• CPU 이용률 : CPU를 최대한 바쁘게 유지
• 처리량 : 단위 시간 당 처리되는 프로세스의 개수
• 총처리 시간 : 특정 프로세스를 처리하는데 걸리는 총 시간(준비큐에서 대기 한 시간 + CPU에서 실행한 시간 + I/O 시간)
• 대기 시간 : 준비큐에서 대기한 시간
• 응답 시간 : 하나의 요구를 제출한 후 첫 번째 응답이 나올 때까지의 시간
• CPU 이용률과 처리량을 최대화하고 총처리 시간, 대기 시간, 응답 시간을 최소화 해야 함

스케줄링 알고리즘

선입 선처리 스케줄링(First-Come First-Served)

• CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받음
• 프로세스가 준비큐에 진입하면 이 프로세스의 PCB를 큐의 끝에 연결
• CPU가 가용 상태가 되면, 준비 큐의 앞부분에 있는 프로세스에 할당
• 실행 상태의 프로세스는 준비 큐에서 제거

• 호위 효과 : 처리 시간이 짧은 프로세스들이 긴 프로세스가 CPU를 양도하기 기다리는 것
• CPU와 장치 이용률이 저하
• 비선점형 알고리즘으로 CPU가 프로세스에 할당되면 그 프로세스가 종료하거나 I/O 처리를 요구할 때 까지 CPU를 점유
• 대화형 시스템에서는 각 프로세스가 규칙적으로 CPU에 할당되도록 하는것이 중요하므로 선입 선처리 스케줄링을 사용할 수 없음

최단 작업 우선 스케줄링(Shortest Job First)

• 각 프로세스에 다음 CPU 버스트 길이를 연관
• 가장 작은 CPU 버스트를 가진 프로세스에 CPU 할당
• 동일한 CPU 버스트를 지니면 선입선처리 스케줄링 사용
• 선점형 또는 비선점형 스케줄링으로 작동
• 선점형 : 새로운 프로세스가 이용 가능 할 때 그 프로세스의 CPU 버스트가 현재 실행되는 프로세스의 CPU 버스트보다 짧으면 새로운 프로세스에 CPU 할당
• SRTF(Shortest-Remaining-Time-Friest) 스케줄링이라고 불림
• 프로세스들의 평균 대기 시간을 줄여줌

• 프로세스의 CPU 버스트 시간을 예측
• 이전 CPU 버스트 시간을 측정하여 지수 평균한것으로 예측

우선순위스케줄링

• 우선순위가 가장 높은 프로세스에 CPU 할당
• SJF는 CPU 버스트 시간이 우선순위인 우선순위스케줄링
• 기아(Starvation) 문제점을 노화(Aging) 방법으로 해결
• 기아 : 낮은 우선순위를 지닌 프로세스가 평생 실행되지 못함
• 노화 : 시간이 흐르면 해당 프로세스의 우선순위를 높임

라운드로빈(RR)

• 각 프로세스들은 시간 할당량(time quantum)이라는 작은 단위의 시간을 지님
• 일반적으로 10-100밀리초로 해당 시간이 지나면 다른 프로세스에 CPU를 넘기고 준비큐에 끝에 다시 삽입
• 준비 큐는 선입선출 큐로 동작하며 새로운 프로세스들은 큐의 꼬리에 추가
• 프로세스의 CPU 버스트가 시간 할당량보다 작을 때 해당 프로세스는 CPU를 자발적으로 방출
• 프로세스의 CPU 버스트가 시간 할당량보다 클 때 타이머가 끝나면 운영체제에 인터럽트 발생
• 이 후 문맥교환이 발생하고 프로세스는 준비큐의 끝으로 삽입
• 준비큐에 n개의 프로세스가 있고 q의 시간 할당량을 지니면 모든 프로세스는 (n-1)q 이상의 시간을 대기하지 않음
• RR 알고리즘의 성능은 시간 할당량에 영향을 받음
• 시간 할당량이 크다면 선입선처리 스케줄링과 똑같음
• 시간 할당량이 매우 적다면 많은 문맥교환을 발생시켜 성능 악화
• 시간 할당량이 문맥 교환 시간과 비교하여 더 크게 만들어야 함

다단계 큐 (Multileve Queue)

• 포그라운드(대화형) 프로세스와 백그라운드(배치) 프로세스를 구분
• 포그라운 프로세는 백그라운드 프로세스보다 우선순위를 가질 수 있음
• 포그라운드 큐 - RR 사용
• 백그라운드 큐 - FCFS 사용
• 큐와 큐 사이에 스케줄링 구현 - 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현
• Ex) 실시간 큐는 대화형 큐보다 높은 우선순위를 지님
• 큐 사이에 시간을 나누어 사용 - 각 큐는 CPU 시간의 일정량을 받아 자기 큐에 있는 프로세스를 스케줄링
• Ex) 포그라운드 큐는 CPU의 80% 시간이 할당되고 백그라운드 큐는 CPU의 20% 시간이 할당

다단계 피드백 큐 (Multilevel Feedback Queue)

• 다단계 큐 스케줄링 알고리즘에서는 프로세스들이 시스템 진입 시점에 영구적으로 하나의 큐에 할당
• 오버헤드의 장점이 있으나 융통성이 적음
• 다단계 피드백 큐에서는 프로세스 큐들 사이를 이동하는것을 허용
• 다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의
  • 큐의 개수
  • 각 큐의 스케줄링 알고리즘
  • 한 프로세스를 높은 우선 순위 큐로 올려주는 시기를 결정하는 방법
  • 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
  • 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법

• 새로 진입하는 프로세스는 첫번째 큐에 넣어진다
• 8밀리초동안 프로세스가 완료되지 않으면 다음 큐로 이동
• 16밀리초동안 프로세스가 완료되지 않으면 다음 큐로 이동
• 첫번째 큐와 두번째 큐가 비었을때만 세번째 큐는 FCFS 방식으로 실행
• 기아를 방지하기 위해 우선순위가 낮은 큐에서 오래 대기하는 프로세스는 우선 순위가 높은 큐로 이동 가능