[CS - OS] 스케줄링

링딩·2023년 12월 5일

다시 공부하는 CS

목록 보기

2/4

1. 스케줄러

스케줄링

운영체제에서 여러 프로세스들 사이에 CPU 사용의 우선순위를 부여하고, 어떤 프로세스에게 CPU를 할당할 것인지를 결정하는 작업
=> 즉, CPU를 잘 사용하기 위해 '프로세스'들을 어떻게 배정할 것인지를 결정하는 작업이다

< 프로세스를 스케줄링 하기 위한 Queue 종류>

Job Queue : 현재 시스템 내에 있는 모든 프로세스의 집합

Ready Queue : 현재 메모리 내에 있으면서 CPU 를 잡아서 실행되기를 기다리는 프로세스의 집합

Device Queue : Device I/O 작업을 대기하고 있는 프로세스의 집합

스케줄링의 목표

CPU를 잘 사용하려면 프로세스를 어떤 식의 규칙으로 배정해야 할까?🤔

조건 : 오버헤드 ↓ / 사용률 ↑ / 기아 현상 ↓

목표

Batch System: 가능하면 많은 일을 수행. 시간(time) 보단 처리량(throughout)이 중요
Interactive System: 빠른 응답 시간. 적은 대기 시간.
Real-time System: 기한(deadline) 맞추기.

1-1. 스케줄러

스케줄링을 수행해주는 컴포넌트를 '스케줄러'라고 한다.

프로세스에게 공정한 CPU 접근 기회를 제공하며, 시스템의 전반적인 성능과 효율성을 향상

1-1-1. 프로세스 상태

⭐ 프로세스의 상태 전이

승인 (Admitted)
프로세스 생성이 가능하여 승인됨.

스케줄러 디스패치 (Scheduler Dispatch)
준비 상태에 있는 프로세스 중 하나를 선택하여 실행시키는 것.

인터럽트 (Interrupt)
예외, 입출력, 이벤트 등이 발생하여 현재 실행 중인 프로세스를 준비 상태로 바꾸고, 해당 작업을 먼저 처리하는 것.

입출력 또는 이벤트 대기 (I/O or Event wait)
실행 중인 프로세스가 입출력이나 이벤트를 처리해야 하는 경우, 입출력/이벤트가 모두 끝날 때까지 대기 상태로 만드는 것.

입출력 또는 이벤트 완료 (I/O or Event Completion)
입출력/이벤트가 끝난 프로세스를 준비 상태로 전환하여 스케줄러에 의해 선택될 수 있도록 만드는 것

1-1-2. 스케줄러 종류

◽ 장기 스케줄러

어떤 프로세스를 메모리를 할당해 Ready Queue로 적재할지 결정하는 역할을 합니다. 이를 통해 동시에 실행될 프로세스의 수를 제어합니다.

메모리와 - 디스크 사이의 스케줄링 담당

프로세스의 상태 (new -> ready(in memory))

◽ 단기 스케줄러

CPU가 할당될 프로세스를 선택합니다. 이는 매우 빠른 주기로 실행되며, 컨텍스트 스위칭을 수행합니다.

Ready Queue 에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정.

CPU - 메모리 사이의 스케줄링 담당

ready -> running -> waiting -> ready

◽ 중기 스케줄러

현재 실행 중인 프로세스를 일시 중단(swap out)하고 메모리를 확보하기 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄

ready -> stopped

2. 선점 / 비선점 스케줄링

* 선점

현재 CPU를 사용하고 있는 프로세스를 중단시키고, 다른 프로세스에게 CPU를 할당할 수 있는 스케줄링 방식

(장점) 작업을 빠르게 처리
(단점) '컨텍스트 스위칭 오버헤드' 발생이 생길 수 있다.

* 비선점

한 번 CPU를 할당받은 프로세스가 자발적으로 CPU를 반납하거나 작업을 완료할 때까지 CPU를 계속 사용하는 스케줄링 방식

(장점) 강제로 프로세스를 중단하지 않아-> '컨텍스트 스위칭 오버헤드'가 적다
(단점) '기아 상태' 발생 위험이 있다.
->(오랫동안 cpu에 점유하는 작업에 의해서)

3. CPU 스케줄링의 종류

🚦 비선점 스케줄링

FCFS (First Come First Served)
큐에 도착한 순서대로 CPU 할당
실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
- ( 문제점 ) : '콘보이 효과(Convoy effect)'
  -> 작은 작업이 큰 작업 뒤에 대기=> 평균 대기시간 증가
SJF (Shortest Job First)
- 수행시간(Cpu burst time)이 가장 짧다고 판단되는 작업을 먼저 수행
- 짧은 작업에 유리
- ( 문제점 ) : '기아 현상'
HRN (Hightest Response-ratio Next)
우선순위를 계산하여 점유 불평등을 보완한 방법(SJF의 단점 보완)
우선순위 = (대기시간 + 실행시간) / (실행시간)

🚦 선점 스케줄링

우선순위 스케줄링
- 정적/동적으로 우선순위를 부여하여 우선순위가 높은 순서대로 처리
- (문제점)
  무한정 기다리는 '기아현상' 이 생길 수 있음
- (해결법) : Aging 방법
  -> 너무 ~~오래 기다리면 우선순위를 올려줌~~

Round Robin (현대적인 스케줄링)
- FCFS에 의해 각 프로세스에게 일정 시간을 할당하고, 그 시간이 지나면 다음 프로세스에게 CPU를 넘김
- (단점)
  if 할당 시간이 크면? FCFS와 같게 되고,
  if 작으면, 문맥 교환 (Context Switching) 잦아져서 '오버헤드' 증가
  => 동등한 기회를 주어, 실시간 시스템 등에서 이용
SRTF
- 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
  - (문제점) : '기아현상'
다단계 큐(Multilevel Queue)
- 여러 개의 큐를 사용하여 각 큐마다 다른 스케줄링 알고리즘을 적용
  -> 그 안에서 ~~우선순위를 부여~~하여 높은 우선순위의 큐에 있는 프로세스를 먼저 처리* 다단계 큐
- 여러 개의 큐를 사용하여 각 큐마다 다른 스케줄링 알고리즘을 적용
  -> 그 안에서 ~~우선순위를 부여~~하여 높은 우선순위의 큐에 있는 프로세스를 먼저 처리
다단계 피드백 큐(Multilevel Feedback Queue)
- 다단계 큐에서 자신의 '실행 최소 단위시간(Time Quantum)'을 다 채운 프로세스는 밑으로 내려가고,
  자신의 Time Quantum을 다 채우지 못한 프로세스는 원래 큐 그대로
  -> Time Quantum을 다 채운 프로세스는 CPU burst 프로세스로 판단하기 때문
- 짧은 작업에 유리, 입출력 위주(Interrupt가 잦은) 작업에 우선권을 줌
- 처리 시간이 짧은 프로세스를 먼저 처리하기 때문에 작업이 완료될 때까지 걸리는 평균 시간을 줄여준다