11.1 CPU 스케쥴링 개요

CPU 스케쥴링: 운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분 하는 것

11.1.1 프로세스 우선순위

프로세스들에게 공정하게 CPU를 배분하려면 어떻게 해야 할까?
프로세스마다 우선순위가 다 다르다.
우선순위가 높은 프로세스: 빨리 처리해야 하는 프로세스
우선순위가 높은 프로세스에는 대표적은 I/O가 많은 프로세스
대부분의 프로세스는 CPU와 입출력장치를 모두 사용하며 실행
- running(실행) 상태와 대기(waiting) 상태를 반복하며 실행

프로세스 종류마다 입출력장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 존재
I/O bound process 입출력 집중 프로세스
- 비디오 재생이나 디스크 백업 작업을 담당하는 프로세스와 같이 입출력 작업이 많은 프로세스
- 실행 상태보다는 입출력을 위한 대기 상태에 더 많이 머무르게 됩니다.
- I/O burst가 많은 프로세스
  - I/O burst: 입출력장치를 기다리는 작업
CPU bound process CPU 집중 프로세스
- 복잡한 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스와 같이 CPU 작업이 많은 프로세스
- 반대로 CPU 집중 프로세스는 대기 상태보다는 실행 상태에 더 많이 머무름
- CPU burst가 많은 프로레스
  - CPU burst: CPU를 이용하는 작업을
CPU 집중 프로세스와 입출력 집중 프로세스가 모두 동일한 빈도로 CPU를 사용하는 것은 비합리적
CPU 집중 프로세스와 입출력 집중 프로세스가 동시에 CPU 자원을 요구했다고 가정
- 입출력 집중 프로세스를 가능한 한 빨리 실행시켜 입출력장치를 끊임없이 작동시키고
- 그 다음 CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 더 효율적
- 입출력장치가 입출력 작업을 완료하기 전까지는, 입출력 집중 프로세스는 어차피 대기 상태가 될 예정이기 때문에
- 입출력 집중 프로세스를 얼른 먼저 처리해 버리면 다른 프로세스가 CPU를 사용할 수 있기 때문입니다.
- I/O bound process의 대기 시간을 줄이자
모든 프로세스가 CPU를 차례대로 돌아가며 사용하는 것보다, 각각의 상황에 맞게 CPU를 배분하는 것이 더 효율적
상황에 맞게, 중요도에 맞게 CPU를 이용할 수 있도록 하기 위해 운영체제는 프로세스마다 우선순위 priority를 부여
운영체제는 각 프로세스의 PCB에 우선순위를 명시, PCB에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정
- 우선순위가 높은 프로세스는 더 빨리, 더 자주 실행

11.1.2 스케쥴링 큐

운영체제가 매번 일일이 모든 PCB를 검사하여, 먼저 자원을 이용할 프로세스를 결정하는일은 매우 비효율적
그래서 운영체제는 프로세스들에 ‘줄을 서서 기다릴 것‘을 요구
- CPU를 사용하고 싶은 프로세스들
- 메모리에 적재되고 싶은 프로세스들
- 특정 입출력장치를 사용하고 싶은 프로세스들
- 이 프로세스들을 모두 줄세움
운영체제는 이 줄을 스케줄링 큐; scheduing queue로 구현하고 관리, 큐에 삽입하여 줄을 세움

큐는 선입선출(First In First Out) 자료 구조이지만, 스케줄링에서 이야기하는 큐는 반드시 선입선출 방식일 필요는 없다.

운영체제가 관리하는 대부분의 자원은 이렇듯 큐로 관리
- 운영체제가 관리하는 줄(큐)에는 다양한 종류가 존재
준비 큐; ready queue는 CPU를 이용하고 싶은 프로세스들이 서는 줄을 의미
대기 큐; wating queue는 입출력장치를 이용하기 위해 대기 상태에 접어든 프로세스들이 서는 줄을 의미

운영체제는 PCB들이 큐에 삽입된 순서대로 프로세스를 하나씩 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행
우선순위가 낮은 프로세스들이 먼저 큐에 삽입되어도, 우선순위가 높은 프로세스는 그들보다 먼저 처리될 수 있다.
- 이런 점에서 봤을 때 높은 우선순위를 가진 프로세스는 마치 VIP와도 같다.
입출력이 완료되어, 완료 인터럽트가 발생하면 운영체제는 대기 큐에서 작업이 완료된 PCB를 찾고
이 PCB를 준비 상태로 변경한 뒤 대기 큐에서 제거합니다. 당연히 해당 PCB는 준비 큐로 이동합니다.

11.1.3 선점형과 비선점형 스케쥴링

선점형 preemptive 스케쥴링
- 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도, 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
- 어느 하나의 프로세스가 자원 사용을 ‘독점할 수 없는’ 스케줄링 방식
- 프로세스마다 정해진 시간만큼 CPU를 사용하고, 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면,
- 운영체제가 해당 프로세스로부터 CPU 자원을 빼앗아 다음 프로세스에 할당하는 방식
- 현재 대부분의 운영체제가 사용
- 장점: 더 급한 프로세스가 언제든 끼어들어 사용할 수 있는 방식이므로 자원 독점을 막고 프로세스들에 골고루 자원을 배분 가능
- 단점: 문맥 교환 과정에서 오버헤드가 발생
비선점형 non-prremptive 스케쥴링
- 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진, 다른 프로세스가 끼어들 수 없는 스케줄링 방식
- 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식
- 만약 비선점형 스케줄링 방식으로 자원을 이용하는 프로세스가 있다면 다른 프로세스들은 그 프로세스의 사용이 모두 끝날 때까지 기다려야 한다.
- 장점: 문맥 교환의 횟수가 선점형 스케줄링보다 적기 때문에 문맥 교환에서 발생 하는 오버헤드가 적다
- 단점: 하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황에서도 무작정 기다려야만 한다. (기아 현상)
  - 모든 프로세스가 골고루 자원을 사용할 수 없다

11.2 CPU 스케쥴링 알고리즘

11.2.1 스케쥴링 알고리즘의 종류

FCFS 스케쥴링
- FCFS; First Come First Served Scheduling, 선입 선처리
- 준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케쥴링
- 프로세스들이 기다리는 시간이 매우 길어질 수 있다
- 호위 효과 convoy effect 발생
  - 앞선 프로세스가 실행시간이 길다면 실행시간이 짧은 프로세스들이 실행되지 못해 마치 부하처럼 뒤따라서 기다리고 있다는 것을 가리키는 효과이다.
SJF 스케쥴링
- Shortest Job First, 최단 작업 우선
- 호위 효과 방지
- 준비 큐에 삽입된 프로세스들 중 CPU 이용 시간의 길이(CPU burst) 가 가장 짧은 프로세스부터 실행
- 비선점형 스케쥴링으로 분류 되지만, 선점형으로 구현될 수 도 있다.
  - 선점형 SJF가 ‘최소 잔여 시간 우선 스케쥴링(SRT)’ 이다.
- SJF가 가장 효율적인 CPU 스케줄링 방법 같지만, 비현실적이다.
  - 왜냐하면 프로세스의 CPU 점유 시간(Burst time) 을 알 수 없다.
  - 한 프로세스가 실행 중에는 많은 변수가 존재하기에, CPU 점유 시간을 알려면 실제로 수행하여 측정하는 수밖에 없다.
  - 실제 측정한 시간으로 예측하여 SJF를 사용할 수도 있지만, 이는 오버헤드가 매우 큰 작업으로 잘 사용되지 않는다.

Round Robin 스케쥴링
- FCFS에 타임 슬라이스(Time Quantum, Time Slice) 라는 개념이 더해진 방식
- 타임 슬라이스란 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미
- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 CPU를 이용하는 선점형 스케줄링
- 타임 슬라이스 크기가 매우 중요
  - 타임 슬라이스가 크면 사실상 선입 선처리 스케줄링과 다를 바 없어 호위 효과가 생길 여지가 있고,
  - 타임 슬라이스가 작으면 문맥 교환에 발생하는 비용이 커 CPU는 프로세스를 처리하는 일보다 프로세스를 전환하는 데에 온 힘을 다 쓸 여지가 있기 때문
- 시분할 시스템의 성질을 활용한 방법
SRT 스케쥴링
- 최소 잔여 시간 우선 스케쥴링
- 프로세스들은 정해진 타임 슬라이스만큼 CPU를 사용하되, 다음 프로세스로는 남아있는 작업 시간이 가장 적은 프로세스가 선택됨.
  - SJF, Round Robin 을 합친 방식
우선순위 스케쥴링
- 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행
- SJF, SRT 모두 우선순위 스케쥴링의 일종으로 볼 수 있다.
- 기아 현상, 근본적인 문제
  - 우선순위가 높은 프로세스들에 의해 실행이 계속되어 연기됨
- 이를 방지하기 위한 대표적인 기법으로 에이징; aging이 있다.
  - 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식입니다.
  - 말하자면 대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 방법
Multi-level Queue 스케쥴링
- 다단계 큐 스케쥴링
- 우선순위별로 준비 큐를 여러 개 사용하는 스케쥴링
- 프로세스들이 큐 사이를 이동할 수 없다.
  - 기아 현상이 발생 할 수 있다.
- 이렇게 큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해집니다.
  - 가령 어떤 큐에는 우선순위가 비교적 높아야 하는 I/O bound 프로세스가 삽입될 수 있고,
  - 어떤 큐에는 우선순위가 비교적 낮아도 상관없는 CPU bound 프로세스가 삽입될 수 있다.
  - 또 어떤 큐에는 (우선순위가 비교적 높아야 하는) 백그라운드 프로세스들을 삽입할 수 있고,
  - 어떤 큐에는 (우선순위가 비교적 낮아도 무방한) 사용자와의 상호작용이 잦은 프로세스들을 삽입할 수 있다.
  - 큐별로 타임 슬라이스를 여러 개 지정할 수도 있고, 큐마다 다른 스케줄링 알고리즘을 사용할수도 있다.
Multilevel Feedback Queue 스케쥴링
- 다단계 피드백 큐 스케줄링
- 다단계 큐 스케쥴링의 발전된 형태
- 구현 복잡하지만, 가장 일반적인 CPU 스케쥴링 알고리즘
- 동작 방식
  - 다단계 피드백 큐 스케줄링에서 새로 준비 상태가 된 프로세스가 있다면 우선순위가 가장 높은 우선순위 큐에 삽입되고 타임 슬라이스 동안 실행
  - 만약 새로운 프로세스가 해당 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐에 삽입되어 실행
  - 그리고 또 해당 큐에서 실행이 끝나지 않는다면 프로세스는 또 다음 우선순위 큐에 삽입되고, 결국 CPU를 오래 사용해야 하는 프로세스는 점차 우선순위가 낮아짐
- 프로세스들이 큐 사이를 이동할 수 있다
  - 낮은 우선순위 큐에서 너무 오래 기다리고 있는 프로세스가 있다면 에이징 기법을 적용하여 기아 현상을 예방