[운영체제] 3. Scheduling

Scheduling

한 시점에서 여러 프로세스가 제한된 물리적 자원인 CPU를 접근할 경우 프로세스 별로 접근에 대한 순서를 정해주어야 된다.

 

Scheduling Metrics

• Turnaround time = 수행완료시간 - 도착시간
• Response time = 첫 서비스 시간 - 도착시간
• Fairness: 프로세스간 걸리는 시간이 비슷한 정도
• Throughput: 단위 시간 동안 얼마나 많은 작업을 처리했는지
• Deadline: Turnaround time < deadline

---

FIFO(First In First Out)

도착 시간이 빠른 프로세스를 먼저 수행하는 스케쥴링 기법. 장점으로는 간단하고 구현이 쉽지만, 단점으로는 convey effect에 의해 긴 대기 시간이 유발될 수 있다.

 

SJF(Shotest Job First)

대기 중인 프로세스 중 빨리 끝나게 될 작업을 먼저 처리하는 스케쥴링 정책이다. Turnaround time은 좋지만, 긴 작업이 조금이라도 일찍 도착할 경우 문제가 된다.

 

STCF(Shorted Time-to Completion First)

프로세스가 수행되던 도중에 service time이 짧은 프로세스가 도착한다면, 수행 중인 프로세스를 선점하고 도착한 프로세스를 수행한다.

 

RR(Round Robin)

프로세스를 일정한 시간을 나누어 할당된 시간만큼한 처리하는 스케쥴링 정책이다.

Time quantum이 증가할 수록 response time은 짧지만 문맥 교환에 의한 부하가 증가한다.

 

MLFQ

Turnaround time과 response time이 모두 적절히 최적화된 스케쥴링 정책으로 우선순위 별로 큐가 있고 각 큐에는 ready 상태인 프로세스들이 각 큐에 존재한다. 과거를 통해 미래를 예측하는 스케쥴링 정책이다.

 

 MLFQ 스케쥴링 규칙

1. 우선순위가 높은 프로세스를 먼저 스케쥴링한다.
2. 우선순위가 같으면 RR 방식으로 스케쥴링한다.
3. 새로 도착한 프로세스는 우선순위가 가장 높은 큐에 삽입된다.
4. 특정 우선순위에서 총 사용된 시간으로 우선순위의 하락을 판단한다.
5. 장기간 스케쥴링 되지 못한 프로세스를 주기적으로 우선순위를 높여준다.

---

Workload에 따른 스케쥴링 정책 별 수행 다이어그램.

Process	Arrival Time	Service Time
A	0	3
B	2	6
C	4	4
D	6	5
E	8	2

FIFO, SJF, STCF

 

RR

MLFQ

 

HRRN

프로세스의 서비스시간과 대기시간 모두 고려하는 스케쥴링 정책이다. SJF의 문제점을 해결한 스케쥴링 정책이다.

 

---

Proportional Share

프로세스르 turnaround, response time의 고려 대신 CPU를 비율대로 할당해주는 스케쥴링 정책.

 

 

Lottery Scheduling

프로세스 별로 티켓을 할당하여 비율을 설정하고, 랜덤 추출하여 선택된 티켓을 가진 프로세스를 스케쥴링한다.

 

장점

1. Ticket transfer, ticket inflation으로 인해 유연성이 좋다.
2. 구현이 간단하다.
3. 사용자들마다 구분이 가능하다.

단점

   Not deterministic

 

Stride Scheduling

Pass value가 가장 작은 프로세스를 스케쥴링하는 정책이다. 스케쥴링 된 프로세스는 stride 만큼 pass value를 증가시킨다. Lottery scheduling과 달리 deterministic하다.

 

예시. 3개의 프로세스: A(100), B(50), C(250)

---

Mulitporcessor Scheduling

프로세서(코어)가 여러개인 컴퓨터에서 각 프로세스를 어떻게 스케쥴링 해야할 지 결정해야 한다.

 

CPU cache: CPU 내부에 존해하는 빠르게 접근이 가능한 메모리이다. Cache hit가 발생할 경우 메모리 접근이 없어 성능이 매우 향상되며, 지연쓰기를 통해 성능을 향상시키는 것이 가능하다.

• Spatial locality: 특정 데이터를 접근하면 주변 데이터도 접근할 확률이 높다.
• Temporal locality: 한번 접근한 데이터는 다음에도 다시 접근할 확률이 높다.

 

Cache affinity: 멀티 프로세서 컴퓨터에서 특정 프로세스를 실행할 때 가능하면 이전 CPU와 같은 CPU에서 실행하는게 좋다. 해당 프로세스를 실행했던 CPU는 해당 프로세스의 데이터를 캐시에 저장하고 있을 확률이 높아 메모리 접근이 적어진다.

 

 

SQMS(Single Queue Multiprocessor Scheduling)

한개의 큐를 사용하여 여러 프로세스를 관리하는 멀티프로세서 스케쥴링 정책.

 

- 장점과 단점

• 장점: 단순하다.
• 단점: 캐시 친화도가 낮다. Lock contention이 높아 확장성이 낮다.

MQMS(Multi Queue Multiprocessor Scheduling)

여러 큐를 활용하여 프로세스 별로 큐에 배정하는 멀티프로세서 스케쥴링 정책이다. 각 큐는 CPU와 연관되어 있다.

 

- 장점과 단점

• 장점: 캐시 친화도가 높다. Lock contention이 줄어 확장성이 좋다.
• 단점: Load balancing의 처리가 필요하다. → Migration