[운영체제] CPU Scheduling(3)

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

---

RR: 시간을 정해놓고 CPU를 할당한 다음, 할당된 시간이 끝나면 강제로 다른 프로세스에게 CPU를 할당

CPU 사용 시간이 짧을 경우 한 번에 자신의 job을 처리하고 빠져나갈 수 있어서 효율적

결국 CPU를 기다리는 시간이, 자신이 CPU를 사용하려는 시간과 비슷함.

CPU를 뺏길 때 Process의 context를 save하고, 다시 CPU를 얻었을 때 context로부터 다시 일을 시작할 수 있는 메커니즘 덕분에 가능

---

지금까지의 ready que는 한 줄. 

반면 Multilevel Queue는 여러 줄에서 프로세스들이 기다림.

각 줄마다 우선순위가 존재. 위에 있는 줄일수록 우선순위가 높음.

1) System process

2) Interactive: 사람과 상호작용

4) Batch process: CPU만 오래 사용함

위의 줄이 비어있어야 다음 줄에 우선순위가 할당. 우선순위가 낮은 process는 starvation을 겪을 수 있음

foreground que와 background que 두 개의 큐를 운용

- foreground que: Interactive job(with human) -> 사람과 상호작용하기 때문에 Round Robin을 사용

- background que: batch(no human interactive) -> 어차피 CPU만 오래 사용하는 프로세스. 응답시간이 빠르다고 좋을 이유가 그다지 없기 때문에 context 오버헤드를 줄이기 위해 FCFS를 사용

 

각 줄은 독립적인 스케줄링 알고리즘을 가짐

1) 어떤 줄(que)을 사용할 것인지

2) 줄(que) 내에서 누구에게 우선권을 줄 것인지

 

우선순위가 높은 줄이 비어있을 때만 낮은 줄에게 우선순위를 주는 스케줄링 -> 우선순위 낮은 줄이 starvation

이를 막기 위해 각 줄별로 어느 정도는 CPU 이용 시간을 나눠서 줌

ex. 전체 시간의 80%는 우선순위가 높은 프로세스, 나머지 20%는 우선순위가 낮은 프로세스에게 CPU를 할당하는 스케줄링

---

여러 줄로 줄을 서면서, 줄 간에 이동을 할 수 있는 방법

보통은, 처음 들어오는 프로세스는 우선순위가 가장 높은 que에 주고, 우선순위가 높은 que는 Round Robin에서 quantum time을 짧게 할당. 그리고 우선순위가 낮은 que로 갈수록 RR의 시간을 많이 할당. 그리고 마지막에서는 FCFS.

프로세스가 맨 위의 que에서 할당시간이 끝나면 한 단계 낮은 que로 강등. 

CPU burst가 짧은 프로세스는 일찍 도착하여 바로 작업을 끝내고 나갈 수 있음.

CPU burst가 긴 프로세스는 점점 아래 que로 이동하면서 할당 시간을 더 받음.

CPU 사용 시간이 짧은 프로세스에게 빠른 순서 제공. CPU 사용 시간이 긴지 짧은지 예측할 필요도 없음

---

CPU가 여러 개인 시스템에서의 스케줄링

 어떤 job은 CPU가 반드시 실행해야 하는 작업.

Load sharing: CPU가 여러 개가 있으면 Load sharing이 잘 되어야 함. 작업을 잘 나눠줘야 함

Symetric: 모든 CPU들이 대등하기 때문에 각 프로세서가 알아서 결정

Asymmetric: 여러 cpu 중 하나의 CPU가 전체적인 컨트롤을 담당. 데이터의 접근, 공유 등. 나머지는 그 CPU를 따르는 방식

---

Real-Time job: 데드라인이 존재하는 job. 정해진 시간 안에 반드시 끝내야 함.

CPU 스케쥴링을 할 때에도 real-time job은 반드시 데드라인을 보장해줘야 함. Real-time job에 대해서는 데드라인 안에 꼭 끝낼 수 있도록 미리 스케줄링을 해주는 방식. 오프라인으로 먼저 스케줄링을 해줌

real-time job은 주기적으로 activate 해야하는 period한 경우가 많은데(몇 초에 한 번씩 CPU를 몇 초 씩 실행), 여기에 맞게 데드라인을 보장해줌

 

반드시 보장되어야 하는 real-time을 Hard real-time systems

데드라인이 존재하기는 하지만, 반드시 지켜야하는 건 아닌 Soft real-time systems

 

Thread: 하나의 프로세스 안에 여러 개의 수행 단위가 존재

- 쓰레드 구현 방식

1) Local(User level): 운영체제는 쓰레드의 존재를 모름 -> 운영체제는 그냥 프로세스에게 CPU를 줄지 말지

CPU를 주면 어떤 쓰레드가 CPU를 사용할지는 프로세스 내부에서 결정

 

2) Global(Kerner level): 운영체제가 쓰레드의 존재를 알고 있음 -> 프로세스 스케줄링을 하듯이 어떤 쓰레드에게 CPU를 줄 지 결정

---

CPU 스케줄링 알고리즘 평가 방법

1) Queueing model: 굉장히 이론적인 모델. 도착률과 처리률을 계산해서 계산

2) Implementation(구현) & Measurement(성능 측정): 실제 시스템에 알고리즘을 구현한 뒤 돌려보고 성능을 측정

3) Simulation(모의실험): 실제로 알고리즘을 만들어서 실행하지는 않음. 

Simulation에서 input으로 들어갈 데이터 -> trace(실제 프로그램에서 뽑을 수도, 임의로 만들 수도 있음)

 

단지 하나의 예를 가지고 알고리즘 성능을 판단하지 않음. 실제 시스템에서 CPU burst와 I/O burst의 패턴을 분석하고 이를 바탕으로 성능을 판단하는 게 더 신뢰도가 높음