[운영체제] CPU Scheduling(2)

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

프로그램에는 CPU를 연속적으로 사용하는 경우가 많은 패턴의 프로그램도, 또는 키보드 입출력 혹은 하드디스크에서 정보를 읽어오는 I/O burst가 잦아 CPU의 사용 시간이 짧은 패턴의 프로그램도 존재합니다.

 

I/O burst가 끝나고 CPU burst 구간이 되었다고 무조건 CPU를 바로 넘겨받는 건 아닙니다. 위의 그림과 같은 프로그램 여러 개가 동시에 돌아가는 것이 일반적으로 우리가 컴퓨터를 사용하는 방식이기 때문입니다.

때문에 위와 같이 여러 개의 프로그램들이 CPU를 기다리고 있을 때 어떤 프로그램에게 먼저 CPU를 할당할지 결정하는 CPU Scheduling이 필요합니다.

 

CPU bound job은 한 번 CPU를 잡으면 지속기간이 길게 이어집니다. 반면 I/O bound job은 CPU를 금방 사용하고 금방 반납합니다. 때문에 스케쥴러는 한 번 CPU를 주면 금방 작업을 끝내는 I/O bound job이 오래 기다리지 않도록 적당한 스케쥴링을 해줘야 합니다.

---

CPU의 스케쥴링 메커니즘을 두 가지로 나눠보자면,

1) 프로세스가 할당된 작업을 모두 끝낼 때까지 CPU를 강제로 빼앗지 않는 비선점형(nonpreemtive)과

2) 프로세스의 CPU를 언제든지 강제로 빼앗을 수 있는 선점형(preemtive) 알고리즘으로 나뉩니다.

 

그렇다면 어떤 스케쥴링 알고리즘이 효율적인 알고리즘이냐를 판단할 수 있는 척도가 필요한데, 그 척도는 Scheduling Criteria라고 합니다. 이 척도 역시 두 가지 기준으로 나눠볼 수 있습니다.

 

1) 시스템 입장에서의 성능 척도: CPU 하나를 가지고 최대한 일을 많이 시키는 게 좋음

- CPU Utilization(이용률): 전체 시간 중 CPU가 놀지 않고 일한 시간[중국집 주방장이 놀지 않고 일한 시간]

- Throughput(처리량): 주어진 시간 동안 몇 개의 작업을 완료했는가[중국집 주방장이 시간당 만들 수 있는 음식 양]

 

2) 프로그램(프로세스) 입장에서의 성능 척도: 가능한 빨리 CPU를 얻어서 빨리 끝내는 게 좋음

- Turn-around time(소요시간, 반환시간): CPU를 사용하러(대기상태) 들어와서 다 처리하고 나갈 때(다른 IO작업을 처리하러)까지 걸린 시간(wating time까지 포함)[중국집에 와서 음식을 먹고 나가기까지 걸린 시간]

- Waiting time(대기 시간): 순수하게 ready que에서 CPU를 기다린 시간[중간중간 음식이 나올 때까지 걸린 시간]

- Response time(응답 시간): ready que에 들어와서 처음으로 CPU를 얻기까지 걸린 시간[중국집에 와서 첫 음식이 나오기까지 걸린 시간]

* 선점형 알고리즘 -> 한 번 cpu burst에 와서도 CPU를 빼앗겨 ready que에서 줄을 기다리다가 다시 cpu를 얻는 과정을 반복하게 됨. 그렇게 되면 ready que에서 줄을 기다리는 경우가 많은데, 그렇게 여러 번 줄을 서서 기다린 시간을 합친 게 waiting time. response time은 cpu burst에 진입해서 최초로 cpu를 얻게 될 때까지 기다린 시간을 말함

 

이 scheduling criteria는 프로세스가 시작되어 끝날 때까지의 전체 과정을 보는 게 아니라, 각 burst 건마다의 시간을 체크하는 것임

---

1. FCFS(First-Come First-Served): 먼저 온 순서대로 처리. 비선점형 알고리즘에 속함. 그다지 효율적이지는 못함. CPU bound job이 처음에 자리하면 뒤에 I/O bound job들이 금방 끝나는 작업임에도 불구하고 속절없이 기다려야 함.

앞부분에 어떤 프로세스가 위치하느냐에 따라 평균 waiting 시간이 결정됨

앞 단에 위치한 긴 프로세스 때문에 짧은 프로세스들이 오래 기다려야 하는 상황을 Convoy effect라고 함

---

2. SJF(Shortest-Job-First): 사용시간이 짧은 프로세스에게 더 높은 우선순위를 제공. Average waiting time이 가장 짧음.

- Nonpreemtive: 일단 CPU를 잡으면 더 짧은 프로세스가 오더라도 일단 일을 처리. 7초에 이미 도착한 P1~P3 중에서 작업 시간이 짧은 순서대로.

- Preemtive: 일단 CPU를 잡더라도 더 짧은 프로세스가 도착하면 CPU를 넘겨줌. 이 Preemtive 방식이 평균 시간을 optimal 하게 만들어줌. 시간마다 가장 짧은 프로세스를 계산하여 CPU를 제공

Non-preemtive는 CPU를 다 사용하는 시점에 스케쥴링을 고려하는 반면, preemtive는 새로운 프로세스가 도착할 때마다 스케쥴링을 고려함.

 

하지만 SJF에도 문제가 존재

1) Starvation: SJF는 극단적으로 CPU 사용시간이 짧은 작업을 선호. 극단적인 예에서 CPU 시간이 긴 프로세스는 영원히 CPU를 할당받지 못할 수도 있음

2) CPU 사용시간 예측의 어려움 -> 과거의 기록, 패턴을 가지고 예측

---

t: 실제 CPU 사용 시간

타우: CPU 예측 시간

CPU 사용 시간을 예측할 때, 최근의 과거는 가중치를 높게 반영하고 먼 과거는 가중치를 낮게 반영해서 예측.

과거의 값을 토대로 CPU 사용시간을 예측해볼 수 있음

---

우선순위가 가장 높은 프로세스에게 CPU를 할당.

우선순위를 나타내는 숫자가 주어짐. 정수 중 낮은 순서대로 높은 우선순위를 가짐.

Starvation과 같은 문제를 해결하기 위해 Aging 같은 기법이 등장.

Aging: 아무리 우선순위가 낮더라도 대기 시간이 오래되면 높은 우선순위를 부여

---

CPU를 줄 때 할당시간을 세팅해서 줌. 할당 시간이 끝나면 타이머 인터럽트로 인해 CPU를 빼앗기고 ready que에 가서 기다림.

장점: CPU를 처음으로 얻기까지의 응답 시간이 짧음. 누가 CPU를 오래 사용할지 모르는 상황에서 굳이 예측할 필요가 없음.

모든 프로세스가 적어도 한 번은 CPU를 사용할 수 있음. 

할당 시간이 지나치게 길어지면 -> FCFS

할당 시간이 지나치게 짧아지면 -> 계속 CPU를 얻었다 뺏기는데 여기서 context switch가 자주 발생해 오버헤드가 커지고 시스템 전체의 성능이 나빠질 수 있음. CPU 사용시간이 모두 동일한 프로그램이 여러 개 있을 때에는 모두 동시에 빠져나가기 때문에 마지막까지 웨이팅 타임이 길어짐. 반면 이 경우 FCFS에서는 프로그램이 차례로 자기 작업이 끝나면 빠져나갈 수 있음

RR은 turn-around time보다는 response time이 빨라짐