Process Scheduling 2 (미완)

CS/OS

Process Scheduling 2 (미완)

느리님 2021. 5. 10. 16:11

Burst (time)

Burst 용어의 뜻부터 알아봅시다.

Burst란 어떤 operation을 수행하는데 걸린시간을 의미합니다.

스케줄링에서는 크게 두가지로 나누어서 구분하게 됩니다.

CPU Burst : CPU를 실행하는데 걸리는 시간
I/O Burst : CPU가 I/O가 실행하기 까지 기다리는 시간

이 두가지의 Burst가 번갈아 나타나는 것을 CPU-I/O burst cycle 이라고 합니다.

CPU-I/O burst cycle

Bound

프로세스의 타입이나 특징을 위에서 배운 Burst를 통해서 구분할 수 있습니다.

I/O bound : 짧은 CPU Burst, 긴 I/O Burst
CPU bound ( CPU intensive ) : 긴 CPU Burst, 짧은 I/O Burst

Scheduling Metrics

스케줄링의 성능을 평가하는 지표에는 여러가지 방법이 있습니다.

Optimization Criteria 최적화 기준
1. CPU utilization CPU 사용률
  - CPU를 가능한 바쁘게 유지
2. Throughput 처리량
  - 시간 단위당 실행을 완료한 프로세스 수
3. Turnaround time 프로세스 처리시간
  - 특정 프로세스를 실행하는 데 걸리는 시간
4. Response time 응답시간
  - 첫번째 응답을 받을 때까지 걸리는 시간
5. Deadline 마감시간
  - Deadline meet ratio: the percentage of deadlines met
6. Fairness 공평성
  - Service time error: 할당 시간과 실제 실행 시간의 차이

+ 스케줄링의 오버헤드도 고려해야 합니다.

Which metrics are important ?

어떤 지표가 중요할까요 ? 여러 장치에서 살펴봅시다.

Super computer
- Long CPU bound process, 적은 I/O bound process
Personal Computer
- I/O bound process가 많다.
Embeded system
- 긴급한 task가 많다. -> deadline이 중요하다.
Server Computer for Cloud Server
- 각 task가 점유율에 비례하여 CPU 리소스를 받도록 합니다.

⭐️결론 : 모든 장치를 만족시키는 스케줄러는 존재하지 않습니다.

FIFO vs SPN/RR

SPN, SRT 은 turnaround time 의 성능이 뛰어납니다. (짧은 프로세스를 많이 사용하는 것이 좋습니다.)
FCFS 는 짧은 프로세스보다 긴 프로세스에서 훨씬 더 잘 수행됩니다.
RR 에서 time slice가 작을수록 response time은 더 좋지만 turnaround time은 더 나빠질 수 있습니다.
수행시간이 동일하다고 할 때, overhead를 비교하면 FIFO가 더 좋을 수 있습니다.

Round Robin = RR

Response time을 위한 스케줄러

time slice 가 높아지면 response time은 줄어들고 turnaround time은 줄어들거나 높아질 수 있습니다.
time slice 가 작을수록 response time은 좋아지지만, turnaround time은 더 나빠질 수 있습니다.
-> 동시에 만족시킬 수 없습니다.
turnaround time 과 response time 은 Trade-off 관계입니다.

time slice 가 짧을 때
- response time에 좋습니다.
- clock 인터럽트, 스케줄링 및 dispatching 함수 처리가 기능에 영향을 미칩니다.
- SPN 과 비슷합니다. ( 많은 context switch overhead )
time slice 가 길 때
- response time에 좋지 않습니다.
- context switch overhead가 줄어듭니다.
- FCFS 와 비슷합니다.

Scheduling Incorporating I/O

I/O 통합 스케줄링 : 실제 CPU에서는 I/O burst도 함께 고려해야 합니다.

예시를 살펴봅시다.

두 개의 프로세스가 존재합니다.

process A : Run for 10 ms then wait for I/O for 50ms

process B : No waiting (CPU-intensive)

process A 는 I/O bound process, B는 CPU bound process 라고 생각합시다.

time slice가 길 때와 짧을 때의 utilization 을 계산해봅시다.

	CPU utilization	I/O utilization
time slice : 100ms	100 %	50 / 110
time slice: 10ms	100 %	50 / 60

완벽하게 계산된 값은 아니지만, I/O bound process의 효율은 time slice가 작을 때 고려하는 것이 좋다는 결론이 나왔습니다.

Time quantum

일반적인 유용한 가이드 중 하나는 time slice 가 일반적인 interaction 이나 프로세스 함수에 필요한 시간보다 약간 커야한다는 것입니다.

이 말은 time slice의 시간을 결정할 때 interaction 즉, I/O 수행시간이나 프로세스 처리 시간에 필요한 시간보다 약간 커야한다는 말로 볼 수 있습니다.

Virtual Round Robin

이 스케줄링이 등장하게 된 이유를 살펴보자면 먼저 RR을 살펴봐야합니다.

RR의 문제점은 긴 프로세스가 유리하다! 는 것입니다. 왜 긴 프로세스가 유리할까요 ?

RR은 time slice 가 정해져있는데 이 time slice 보다 짧은 프로세스는 time slice를 다 채우지 못한채 종료됩니다.

반면에 긴 프로세스들은 time slice를 모두 다 채우고 종료하여 효율이 좋을 수 밖에 없습니다.

여기서 잠시 대부분의 컴퓨터에서 긴 프로세스들은 CPU bound process 이고, 짧은 프로세스들은 I/O bound process 입니다.

이걸 적용하면 RR 의 문제점은 'CPU bound process 에 편향되어 있다'고 볼 수 있겠네요.

그래서 이러한 문제를 해결하기 위해 등장한 것이 Virtual Round Robin 입니다.

I/O bound process 와 CPU bound process 의 공평성을 위한 스케줄링인 것이죠

OS 에서 우선 time slice를 다 사용했는지 구분합니다.

다 사용했다면 CPU bound process,

다 사용하지 않았다면 I/O bound process.

time slice를 다 사용한 CPU bound process는 즉시 Ready queue로 돌아갑니다.

time slice를 다 사용하지 못한 I/O bound process는 보조 queue를 두어 보조 queue로 들어가게 됩니다.

그리고 다음 Dispatching decision 이 생길 때, 즉 다음 프로세스를 결정할 때

보조 queue의 프로세스들을 Ready queue에 있는 프로세스보다 우선시 하여 결정하게 됩니다.

이렇게 길고 짧은 프로세스들의 편향을 줄이게 되는 것입니다.

⭐️ Multi-Level Feedback Queues

이제 Multi-level feedback queue를 살펴봅시다.

우선 처음으로 들어온 task 는 우선순위가 가장 높은 priority queue 에서 실행을 시작합니다.

그리고 만약 프로세스가 blocking 되지 않고 time slice를 모두 사용했다면 우선순위를 한단계 낮춥니다.

우선순위가 낮아질 때, time slice는 증가하게 됩니다. (2배 증가)

장시간 실행되는 프로세스들은 우선순위가 계속 낮아져 starvation이 될 수 있습니다.

스케줄링의 특징을 보면서 더 살펴보면 기본 베이스는 Round Robin 입니다.

우선 순위가 가장 높은 Round Robin을 보면 time slice가 매우 작은데 이는 SPN 과 같다고 볼 수 있습니다.

이 사진에서 FIFO 라고 적혀있는 부분은 Round Robin 인데 time slice가 매우 길어서 FIFO 와 같다고 볼 수 있습니다.

특징을 더 살펴봅시다.

Ready queue는 여러개의 queue로 분리 됩니다.
- Foreground (interactive) : 앞 쪽의 queue는 time slice가 짧으므로 I/O bound process가 우선시 됩니다.
- Background (batch) : 뒤 쪽의 queue는 time slice가 길기 때문에 CPU bound process 처리에 좋습니다.
각 큐에는 자신만의 스케줄링 알고리즘이 존재합니다.
- Foreground : RR (SPN과 유사)
- Background : FIFO (time slice 가 긴 RR)
프로세스들은 다양한 큐를 이동할 수 있습니다.
다음과 같은 매개변수를 통해 Multi-level feedback queue의 스케줄러가 정의됩니다.
- Number of queue
- Scheduling algorithms for each queue
- Method used to determine when to promote a process
- Method used to determine when to demote a process
- Aging to avoid starvation

Multiprocessor Scheduling

멀티프로세서 스케줄링을 알아보기위해 유니프로세서 스케줄링과 비교해 봅시다.

Uniprocessor scheduling
- 언제 어떤 job 이 실행될지 결정합니다. (time domain)

Multiprocessor scheduling
- 언제 어떤 job이 실행될지 뿐만아니라 어디서 job 이 실행될지도 결정합니다. (time domain + space domain)
- Uniprocessor scheduling 의 목표와 거의 동일하지만 새로운 문제가 발생합니다.
  - Ready queue를 유지하는 방법
  - affinity (선호도) 를 정의하고 활용하는 방법
  - 여러 프로세서에 응용 프로그램을 할당하는 방법
  - 프로세서 heterogeneity (이질성) 을 어떻게 관리합니까?
  - 프로세서 간의 워크로드 균형을 어떻게 잡습니까?