Chapter 04 CPU 스케줄링

1. 스케줄링 개요

 

1) CPU 스케줄링

- 스케줄러: 여러 프로세스 상황을 고려해 CPU와 시스템 자원을 어떻게 배정할지 결정

- 규모에 따라 고수준, 중간 수준, 저수준 스케줄링으로 구분된다.

 ✨ 스케줄링

 - 고수준: 시스템 내의 전체 작업 수를 조절한다. 이에 따라 시스템 내에서 동시에 실행 가능한 프로세스의 총개수가 정해진다.

 - 중간 수준: 시스템의 부하를 조절한다. 이미 활성화된 프로세스 중 일부를 보류 상태로 보내고, 여유가 생기면 다시 활성화된다.

 - 저수준: 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다.

 

 

2) 스케줄링의 목적

- 모든 프로세스가 공평하게 작업하도록 하는 것

- 공평성, 효율성, 안정성, 확장성, 반응 시간 보장, 무한 연기 방지

---

2. 스케줄링 시 고려 사항

 

1) CPU를 할당받은 프로세스가 일을 하고 있는데 인터럽트가 걸린다면 프로세스는 CPU 자원을 해제시킨다. 이처럼 선점형 스케줄링은 context switching 같은 부가적인 작업으로 인한 자원의 낭비가 있지만, 하나의 프로세스가 CPU를 독점할 수 없어 더 효율이 좋고 공평하다.

선점형 스케줄링	비선점형 스케줄링
어떤 프로세스가 CPU를 할당받아 실행중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 방식	어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 방식
문맥 교환 같은 부가적인 작업으로 낭비가 생긴다.	작업량이 적고 문맥 교환에 의한 낭비가 적다.
CPU를 독점할 수 없어 대화형, 시분할 시스템에 적합	CPU 사용시간이 긴 프로세스 때문에 다른 프로세스들이 오랫동안 기다리게 되어 처리율이 떨어진다.

 

 

2) 프로세스 운선순위

- 우선순위가 높다는 것은 더 빨리 자주 실행된다는 의미이다.

- 커널 프로세스와 일반 프로세스가 하나씩 있다면 커널 프로세스의 우선순위가 높아 먼저 실행되며 작업이 끝날 때까지 계속 CPU를 사용한다.

 

 

3) CPU 집중 프로세스와 입출력 집중 프로세스

- 프로세스는 CPU가 더 많은 처리를 해야하는지, 입출력 처리가 더 많이 처리되어야 하는지에 따라 CPU 집중 프로세스(CPU bound process), IO 집중 프로세스(IO bound process)로 나뉜다.

- 입출력 집중 프로세스 > CPU 집중 프로세스로 우선순위를 부여하면 시스템 효율이 향상된다. 입출력 집중 프로세스는 CPU를 잠깐 사용하고 대기상태로 이동하기 때문인데, 이를 '사이클 훔치기'라고 한다.

 

 

4) 전면, 후면 프로세스

- 전면 프로세스: GUI 를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스로 현재 입력과 출력을 사용하는 프로세스이다.(상호작용, 대화형 프로세스)

- 후면 프로세스 : 사용자와 상호작용 없이 백그라운드에서 동작하는 프로세스를 말한다.(일괄, 배치 프로세스)

 

> 이는 전면 프로세스가 IO 집중 프로세스이라는 것이므로 전면 프로세스가 우선순위가 더 높다는 것을 의미한다. 반면 후면 프로세스는 전면 프로세스보다 CPU 집중 프로세스에 더 가까우므로 우선순위가 더 낮다.

---

3. 다중 큐

1) 준비 상태의 다중 큐

- 고정 우선순위 방식: 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식

- 변동 우선순위 방식: 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식

 ✨ 우선순위는 PCB에 적혀있는데, 매번 PCB를 모두 순회하여 프로세스를 찾아내면 부하가 클 것이다. 그래서 스케줄러는 다중 큐(multi queue)를 우선순위 별로 두어 필요할 때마다 우선순위가 높은 순서로 pop해나간다.

 

 

2) 대기 상태의 다중 큐

- 대기 상태의 프로세스를 한 곳에 모아놓으면 관리가 불편

- 시스템의 효율을 높이기 위해 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아 놓는다.

- 준비 큐는 한 번에 하나의 프로세스를 꺼내 CPU에 할당/ 대기 큐는 여러 PCB를 동시에 꺼내 준비 상태로 옮긴다.

---

4. 스케줄링 알고리즘

 

1) 종류

1. 비선점형 알고리즘 : FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링
2. 선점형 알고리즘 : 라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링
3. 비선점형, 선점형 알고리즘 : 우선순위 스케줄링

 

2) 스케줄링 알고리즘의 선택 기준

- 효율성을 평가할 때 주로 대기 시간, 응답 시간, 반환 시간을 계산한다.

 

 

- 대기 시간: 프로세스가 생성된 후 실행되기 전까지 대기하는 시간

- 응답 시간: 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지 걸리는 시간

- 실행 시간: 프로세스 작업이 시작된 후 종료까지 걸리는 시간

- 반환 시간: 대기 시간을 포함해 실행이 종료될 때까지 걸리는 시간

 

 

- 평균 대기 시간은 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값이다. 즉, 위의 예시에서 평균 대기 시간은 (p1 대기시간 + p2 대기시간 + p3 대기시간) / 3이 된다. p1은 대기 시간 없이 바로 실행되므로 대기 시간이 0이다.

 

 

3) FCFS 스케줄링

- 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식으로, 선입선출 스케줄링이라고도 한다.

- 한 번 실행되면 그 프로세스가 끝나야 다음 프로세스를 실행할 수 있다.

- 큐가 하나라 모든 프로세스의 우선순위가 동일하다.

 

<평균 대기 시간 구하기>

1. p1는 도착하자마자 시작되므로 대기시간이 0이다.
2. p2는 3ms에 도착했지만 p1이 끝나기 전까지 시작하지 못한다. 따라서, 30ms까지 기다리게 되고 30-3=27ms 대기시간을 가지게 된다.
3. p3는 6ms에 도착했지만 p1, p2가 끝날 때까지 시작하지 못한다. 따라서 48ms에 시작하므로 48-6=42ms 대기시간을 갖게 된다.

따라서, 평균 대기 시간은 (0+27+42)/3 = 23ms가 된다.

 

 

4) SJF 스케줄링

- 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식, 최단  작업 우선 스케줄링이라고도 한다.

 

<평균 대기 시간 구하기>

1. 0ms에 프로세스 p1이 들어오고 바로 시작한다. 대기시간은 0ms이다.
2. 3ms에 p2가 들어오고 , 6ms에 p3가 들어온다. 비선점 방식이기 때문에 p1이 30ms까지 계속 작업을 진행한다.
3. 30ms에 p2, p3 중에 작업 시간이 짧은 프로세스를 먼저 작업시킨다. p2는 18ms, p3는 9ms이므로 p3를 먼저 실행시킨다.
4. p3가 30ms에 시작하므로 30-6 = 24ms 대기시간을 갖게 된다.
5. p3가 끝나게 되면 39ms가 되고, 39ms에 p2가 실행된다. p2는 3ms에 들어왔으므로 대기시간이 39-3= 36ms가 된다.
6. 따라서 평균 대기 시간은 (0 + 24 + 36) / 3 = 20ms이다.

<평가>

- 작은 작업을 먼저 실행하므로 시스템의 효율성이 좋아진다.

- 그러나 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다는 점, 공평성에 위배된다는 점 때문에 사용하기 힘들다.

- 만약 P3 같은 작업이 계속 준비 큐에 들어오면 P2 작업이 계속 연기되는데, 이를 '아사현상'이라고 한다. 아사현상은 프로세스가 양보할 수 있는 상한선을 정하는 에이징으로 완화할 수 있다.

 

5) HRN 스케줄링

- SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 알고리즘, 대기 시간과 CPU 사용 시간을 고려하여 스케줄링하는 방식이다.

<우선순위, 평균 대기 시간 구하기>

1. 먼저 p1이 30ms동안 실행된다. 이때 준비큐에 있는 p2와 p3의 우선순위를 계산한다.
2. p2는 3ms에 들어오고 30ms(p1이 끝나고 다음 process가 실행할 수 있는 시간)에 실행하면 대기시간 27ms이다. 따라서 (27ms+ 18ms)/ 18ms = 2.5ms이다.
3. p3는 6ms에 들어오고 30ms에 실행하면 30ms-6ms = 24ms가 대기시간이다. 실행 시간이 9ms이므로 (24 + 9) / 9 = 3.67ms이다.
4. HRN는 최고 응답률이 높을수록 우선순위가 높기 때문에 p3가 먼저 실행되고 p2가 실행된다.

대기 시간은 (0 + 24 + 36)/3 = 20ms가 된다.

// 반환 시간 = 대기 시간 + 실행 시간

 

<평가>

- HRN 스케줄링은 실행 시간이 짧은 프로세스의 우선순위를 높게 정하면서 대기 시간을 고려하기 때문에 아사 현상을 완화한다.

- SJF 스케줄링과 비교해 대기 시간이 긴 프로세스의 우선순위를 높여 CPU를 할당받을 확률을 높인다.

- 그러나 여전히 공평성에 위배되어 많이 사용되지 않는다.

 

 

6) 라운드 로빈 스케줄링

- 한 프로세스가 타임 슬라이스 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다. 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행된다.

- FCFS 스케줄링과 유사한데, 각 프로세스마다 사용할 수 있는 최대 시간이 있다는 차이가 있다.

- 프로세스가 CPU를 사용한 후 다른 프로세스에 넘겨줘야 하므로 콘보이 효과가 줄어든다.

 

<평가>

- 문맥 교환 시간을 고려하여 RR 스케줄링의 평균 대기시간을 산출하면 계산 값이 더 커진다.

- 그러므로 항상 FCFS 스케줄링보다 좋다고 할 순 없다.