CPU scheduler

CPU 스케줄러는 컴퓨터 시스템에서 프로세스의 실행 순서를 결정하고 관리하는 역할을 한다. 

시스템의 전체 성능을 최적화하고, 응답 시간을 최소화하며, 자원 사용률을 극대화하는 것이 목표이다

 

CPU스케줄러는 다음 상황들에서 사용된다

• running에서 waiting상태로 스위칭할 때 
• running에서 ready 상태로 스위칭할 때
• waiting에서 ready상태로 스위칭할 때 (선점형인 경우)
• terminate 시

스케줄러는 선점형/비선점형으로 나눌 수 있다.

---

Dispatcher

 

디스패쳐는 스케줄러가 선택한 프로세스를 실행하기 위해 CPU를 할당한다.

또한, 다음 프로세스가 실행되기 전에 현재 실행중인 프로세스의 상태를 저장하고, 새로운 프로세스가 이전에 중단한 지점부터 실행될 수 있도록 환경을 설정한다.

 

디스패쳐는 다음 작업들과 관련이 있다

• switching process context: 문맥교환
• Mode change into user mode : 사용자 모드로 모드 변경
• jumping to the proper location in the user program to restart that program: 사용자 프로그램을 재시작할 올바른 위치로 이동

---

Scheduling Criteria

 

• CPU utiliztion: CPU활용도
• Throughput: 처리량. 단위시간당 처리하는 일의 양
• Turnaround time: 특정 프로세스가 작업을 시작해서 끝날때까지 걸린 시간. (대기시간, 서비스시간, I/O시간을 포함함)
• Waiting time: 대기시간. 프로세스가 레디큐에서 기다리고 있는 시간(계산시간 제외)
• Response time: 응답시간. 사용자가 요청을 보낸 시점부터 그 요청에 대한 응답을 제공하기 시작한 시점까지의 시간.

 

 

프로세스가 완료되는 데 걸리는 시간이 짧을수록 더 빠른 응답 시간을 경험할 수 있으므로, 스케줄링 알고리즘은 턴어라운드 시간을 줄이는 것이 중요하다.

프로세스 간의 우선순위를 조절하여 중요한 작업이 빠르게 처리될 수 있도록 하면 응답 시간을 개선할 수 있다.

 

interactive system에서는 응답시간이 중요하다.

응답시간을 강화하기 위해서 문맥교환을 많이 발생시키게 되는데, 이로 인해 처리량이 감소되기도 한다.

(Trade-off 관계)

 

---

First-Come,First-Served(FCFS) scheduling

FIFO scheduling

• 간단하다
• 도착시간(arrival time)에 따라 프로세스가 실행된다
• 비선점형이다(Non-preemption)
• 공평하다

FIFO스케줄링에는 몇 가지 단점이 있다.

• 콘보이 효과(Convoy Effect): 긴 작업이 먼저 도착하면 뒤이어 도착한 짧은 작업들이 긴 대기 시간을 감수해야 한다.
• 평균 대기 시간이 길어질 수 있다.
• 중요한 작업이 지연될 수 있다

---

Shortedst-Job-First(SJF) Scheduling

실행시간이 가장 짧은 프로세스부터 먼저 실행하는 방식이다.

비선점 방식과 선점 방식 두 가지로 구분된다.

 

1. 비선점 SJF:

프로세스가 한 번 CPU를 할당받으면 작업을 완료할 때까지 CPU를 유지한다. 이 방식은 새로 도착한 더 짧은 작업이 대기해야 할 수 있다.

 

2. 선점 SJF: 

현재 실행 중인 프로세스보다 짧은 작업이 도착하면, 현재 실행 중인 프로세스를 중단하고 새로 도착한 짧은 작업을 먼저 실행한다. 이 방식은 Shortest Remaining Time First(SRTF)로도 불린다.

 

SJF스케줄링의 주요 특징

• 평균 대기 시간을 최소화함
• Starvation 문제: 실행 시간이 긴 프로세스의 경우, 더 짧은 작업이 계속해서 도착하면 실행되지 못하는 상황이 발생할 수 있음

SJF의 가장 큰 단점은 프로세스의 실행 시간을 사전에 알 수 없다는 것이다. 따라서, 다음 프로세스의 실행 시간을 예측하여 사용해야 한다. (하지만 최적의 평균대기시간을 알 수 있어 지표로 사용되기도 한다)

 

다음 CPU 버스트를 예측하기 위해서 Exponential Averaging방법을 사용하기도 한다.

τ(n+1) = α * T(n) + (1 - α) * τ(n)

위 식을 해석해보면,

n+1번째 CPU버스트 예측값 = 가중치 * n번째CPU버스트 실제값 + (1-가중치) * (n번째 CPU버스트 시간 예측값)

 

가중치 알파값에 따라 past history에 더 많은 가중치가 부여될 수도, past predict에 더 많은 가중치가 부여될 수 있다.

 

---

Priority Scheduling

각 프로세스에 우선순위를 부여하고, 이를 기반으로 CPU를 할당하는 방식이다.

높은 우선순위를 가진 프로세스가 먼저 실행되며, 우선순위가 동일한 프로세스는 도착순서나 다른 방식을 사용해 스케줄링된다.

 

우선순위 스케줄링은 비선점과 선점방식 두가지로 나뉜다.

1. 비선점 우선순위 스케줄링:

프로세스가 CPU를 할당받으면 작업을 완료할 때까지 CPU를 유지한다. 새로 도착한 프로세스가 더 높은 우선순위를 가지더라도 기다려야 한다.

 

2. 선점 우선순위 스케줄링: 현재 실행중인 프로세스보다 높은 우선순위를 가진 프로세스가 도착하면, 현재 실행 중인 프로세스를 중단하고 새로 도착한 프로세스를 먼저 실행한다.

 

우선순위 스케줄링에도 몇 가지 단점이 있다.

• Starvation: 낮은 우선순위를 가진 프로세스는 계속해서 높은 우선순위의 프로세스가 도착하는 경우 실행되지 못할 수 있다.
• 우선순위 결정 어려움.
• 비선점형 우선순위 스케줄링은 우선순위 역전현상이 발생.

여기서 Starvation 문제를 해결하기 위한 Aging기법이 사용되기도 한다.

- 시간이 지날수록 process 우선순위를 서서히 증가시킴.

 

---

HRRN(Highest Response Ratio Next)

프로세스의 대기 시간과 실행 시간의 비율을 고려하여 스케줄링을 결하

프로세스의 응답 비율이 가장 높은 것부터 먼저 실행함.

응답 비율 = (대기 시간 + 실행 시간) / 실행 시간

 

HRRN 스케줄링은 

1. 대기 시간 고려: 오래 기다린 프로세스에 대한 공정성을 향상시킴

2. 실행 시간 고려: 짧은 작업이 먼저 실행될 수 있도록 함

3. Starvation 방지: 오래 대기한 프로세스의 응답 비율이 점차 증가하기 때문에 starvation을 방지할 수 있음.

 

---

RoundRobin (RR)

각 프로세스에 고정된 시간 단위(타임 퀀텀)의 CPU자원을 순환하며 할당하는 방식으로 작동.

 

• Based on FIFO
• 타임 퀀텀 만큼씩만 실행하며 순회함.
• 여러 프로세스들이 메모리에 올라와있어야 함
• 복잡한 스케줄링 알고리즘으로 사용됨

 

타임퀀텀이 q, 프로세스가 n개 일 때 프로세스는 (n-1)q 시간 이상 기다릴 일이 없다.

 

타임퀀텀q가 커지면 FIFO가 되고

q가 작아지면 문맥교환이 많이 일어나게 되어 비효율적이다. q는 최소한 문맥교환하는 시간보다는 커야 한다.

processor sharing 이라고도 부른다.

 

또, 평균 Turnaround time과 타임퀀텀은 관계가 없다.

 

 

---

RR in MS-Windows

 

라운드로빈에서,

우선순위에 따라 선점될 수 있다.

실행하고 있던 프로세스가 우선순위15보다 높다면, 중단한 후 재시작할 때 새로운 풀 퀀텀타임 만큼 할당해준다.

우선순위가 15보다 낮다면, 실행하다 남은 만큼만 다시 재개한다.

 

---

Multilevel Queue

 

멀티레벨 큐는 여러개의 큐를 이용해 프로세스를 분리하여 관리하는 방식이다.

각각의 큐는 다른 알고리즘 정책을 사용할 수 있다.

각 큐마다 우선순위기 부여되어 우선순위가 높은 큐에서 먼저 프로세스를 선택한다.

starvation문제가 발생할 수 있다.

각 큐마다 타임슬라이스를 적용할 수 있다.

 

Multilevel feedback queue

 

멀티레벨 피드백 큐는 멀티레벨 큐 스케줄링의 단점을 해결하기 위해 도입되었다.

멀티레벨 피드백 큐는 여러 개의 큐를 사용하며, 각 큐에는 서로 다른 우선순위와 알고리즘이 적용된다.

이 방식은 프로세스의 우선순위를 동적으로 조정하여, 시스템의 성능과 처리 공정성을 개선한다.

 

ㅇ프로세스는 여러 큐들 사이를 움직일 수 있다.

 

---

Fair Share Scheduling(FSS)

 

사용자 또는 그룹의 자원 사용을 고려하여 CPU시간을 할당하는 방식.

사용자 또는 그룹에게 공정한 자원 사용을 보장하기 위해 프로세스가 아닌 사용자 또는 그룹을 기준으로 스케줄링을 수행한다.

 

 

---

Thread Scheduling

 

실행중인 스레드들 사이에서 CPU시간을 할당하고 관리한다.

user-level 스케줄링과 kernel-level 스케줄링으로 구분된다.

kernel-level 스케줄링: OS가 스레드를 관리

user-level 스케줄링: 프로그램이 스레드 실행순서와 우선순위를 관리

 

user thread: 유저가 만드는 스레드

kernel thread: 운영체제가 만든 스레드

lightweight process

 

LWP는 스레드를 일컫는 말이기도 하지만

솔라리스 운영체제에서 사용되는것이기도 한데,

이것은 user thread와 kernel thread사이에서 정보교환을 하는 역할을 한다.

 

 

스레드의 상태 전이도

 

---

Multiple-Processor scheduling

다중 프로세서 스케줄링.

 

다중 프로세서의 아키텍처 스타일은 

-Asymmetric multiprocessing: 비대칭적 다중처리: 기능,성능이 다른 CPU들이 있음

-Symmetric multiprocessing: 대칭 다중 처리: 프로세서들이 동등한 역할을 수행.

 

다중프로세서 스케줄링은 다음 이슈들이 있음

-Processor affinity

-Load balancing

 

Processor affinity

:프로세서 친화도. 특정 프로세스 또는 스레드를 특정 프로세서에 고정시키는 기술.

이를 통해 캐시 지역성을 개선하고, 캐시 일관성 유지에 소요되는 오버헤드를 줄일 수 있음

 

Load balancing

:부하 균형. 여러 프로세서에 작업을 고르게 분산시켜 처리량을 극대화하고 전반적인 성능을 개선.

-push migration: load만 지켜보는 특정 프로세스가 idle한 프로세서에게 작업 push

-pull migration: idle한 프로세서가 바쁜 프로세서의 일을 가져옴.

 

Multicore Processors

여러개의 처리코어를 하나의 칩에 통합한 프로세서.

병렬처리를 통해 시스템 성능을 향상시키고, 작업 처리량을 증가시킬 수 있음.

 

Simultaneous milti-threading(a.k.a. hyper threading)

Coarse MT: stall날 때마다 스위칭

Fine MT: RR느낌

SMT: 빢빢빡 요즘 트렌드

 

---

Real-Time Scheduling

시간제약 조건이 있음.

 

-Hard real-time system: 시간제약이 엄격함. 시간제한을 초과하면 심각한 결과가 발생(미사일격추, 항공 등..)

 

-Soft real-time system: 시간제한을 초과해도 시스템은 작동하나, 퀄리티 하락이 발생(날씨예보, 실시간 스트리밍..)

 

real-time system은 선점형이어야 함.(우선순위 역전 방지, 빠른 응답 지원). 심지어 운영체제를 선점할 수도 있음

 

Deadline based Scheduling(실시간 스케줄링 기법)

-RMS(Rate Monotonic scheduling): 사이클(주기)이  짧은것 먼저

-EDF(Earliest Deadline First): 데드라인이 빠른것부터.

 

---

Algorithm Evaluation

Deterministic Modeling(결정론적 모델링):

주어진 입력에 대해 항상 동일한 결과를 생성하는 모델 사용

 

평가방법

1. simulation: 시뮬레이션. cherry picking에 주의.

2. queueing models: 대기열 모델

3. implementation