[OS] Chapter 5: CPU Scheduling

CPU Scheduling Basic Concepts 

프로세스 실행은 다음으로 구성된다

CPU 실행( CPU brust)

I/O 대기 (I/O brust)

 

Histogram of CPU-burst Times

CPU Brust가 짧은 것이 많다

 

CPU Scheduler 

 

메모리 안에 있는 프로세스에서 실행 시킬 프로세스를 고르고 CPU를 할당한다.

CPU 스케줄링은 다음과 같은 경우에 이루어질 수 있다

 

프로세스:

1. 실행 중인 상태에서 대기 상태로 전환 될 때  (I/O Brust)

2. 실행 중인 상태에서 준비 상태로 전환 될 때

3. 대기 중인 상태에서 준비로 전환될 때  

4. 종료 

 

 

1,2은 반드시 CPU 스케줄러가 호출되어야 하지만 3,4는 호출할 수도 있고 안 할 수도 있다. 

 

1,4는 nonpreemptive이고 나머지는 preemptive다.

 

preemptive Scheduling(선점형):  하나의 프로세스가 다른 프로세스 대신에 프로세서(CPU)를 차지할 수 있다. 

nonpreemptive Scheduling)(비선점형) : 하나의 프로세스가 작업을 마치고 자발적으로 대기 상태로 들어가거나 종료되는 경우 다른 프로세스가 실행된다. 스스로 자원을 반납한다. 

 

 

Dispatcher

Disaptcher

디스패처 모듈은 CPU를 CPU 스케줄러에 의해 선택된 프로세스에 제어를 넘기는 역할을 한다.

 

• 컨텍스트 전환 (Context Switching): 
• 유저 모드로 전환
• 프로세스 전환이 발생할 때 새로운 프로세스를 시작하기 위해 유저 프로그램의 정확한 위치로 이동시킨다.
• (PC카운터를 변경하여 새로운 프로세스 실행을 시작)

Disapatch latency

디스패치 지연은 디스패치가 하나의 프로세스를 중지하고 다른 프로세스를 실행하기까지 걸리는 시간을 나타낸다. 

Scheduling Criteria

 

스케줄링 기준 

CPU 이용률 (CPU Utilization)

CPU를 가능한 한 바쁘게 유지하려고 노력하여 CPU 활용을 극대화한다.

처리량 (Throughput)

단위 시간 내에 완료된 프로세스의 수를 측정하여 처리량을 극대화한다.

턴어라운드 시간 (Turnaround Time) 

특정 프로세스의 실행을 완료하기 위해 걸리는 시간을 측정하여 턴어라운드 시간을 최소화한다. 


대기 시간 (Waiting Time)

프로세스가 준비 대기 큐에서 대기한 시간을 나타낸다. 대기 시간을 최소화한다.

 

응답 시간 (Response Time)

요청이 제출된 후 첫 번째 응답이 생성되는데 걸리는 시간을 나타낸다.

주로 Timed Sharing 환경에서 사용된다.

응답 시간을 최소화한다. 

 

Scheduling Algorithms

 

• 최단 작업 우선 스케줄링(SJF)
• 우선순위 스케줄링
• 라운드 로빈 스케줄링
• 멀티레벨 대기열 스케줄링
• 멀티레벨 피드백-큐 스케줄링

 

평균 대기 시간(Ready queue에서 대기하는 시간) 은 다양한 스케줄링 알고리즘을 비교하는 데 사용되는 측정 지표다.

 

 

First-Come First-Served (FCFS) Scheduling

 

 

First-Come First-Served (FCFS) Scheduling

 

먼저오면 먼저 선택하는 방식 즉 선착순 방식이다. 

 

 

 

 

첫번째 그림은 Conboy effect가 발생한 것, 두번째 그림은 아닌 것

 

Brust time: 프로세스가 CPU를 사용하여 실행하는데 걸리는 시간. (프로세스가 CPU를 사용하는 시간의 총합)

*CPU 버스트의 길이는 각 프로세스가 CPU를 사용하는 시간을 나타낸다. 

 

Convoy effect 

 

스케줄링에서 발생하는 현상으로, 하나의 긴 실행 시간을 가진 프로세스 앞에 짧은 실행 시간을 가진 여러 프로세스가 뒤따라 실행될 때 발생한다. 이로 인해 모든 다른 프로세스는 하나의 큰 프로세스가 CPU에서 실행을 완료할 때까지 대기해야한다, 

 

Shortest-Job-First (SJF) Scheduling

 

Shortest-Job-First (SJF) Scheduling

각 프로세스에 해당 프로세스의 다음 CPU Brust (실행시간)의 길이를 이용하여 가장 짧은 실행 시간을 가진 프로세스를 스케줄링하는 스케줄링 알고리즘

 

가장 최적화된 방법으로 주어진 프로세스 집합에 대한 최소 평균 대기 시간을 제공한다. 

 

Nonpreemptive SJF Scheduling

• CPU가 한 번 할당되면 해당 프로세스는 CPU Brust를 완료할 때 까지 선점되지 않는다. 즉 실행 중인 프로세스는 누구에게도 CPU를 뺏기지 않고 자신이 스스로 반납하게 된다. 

 

Preemptive SJF Scheduling

현재 실행 중인 프로세스의 남은 실행시간보다  CPU Brust 길이가 더 짧은 새로운 프로세스가 도착하면 현재 프로세스로 선점한다. 즉 실행 중인 프로세스는 실행시간이 더 짧은 프로세스가 나타나면 CPU를 빼앗기게 된다.

nonpreemptive 일때

 

preemptive 일때

Determining Length of Next CPU Burst

다음 CPU Brust의 길이를 알 수있는 방법이 없기 때문에 최적의 방법임에도 불구하고 사용되지 않는다.

 

 

 

 

이전 길이를 사용해여 다음 길이를 예측할 수 있는 방법이 있다. 

n+1은 n번째 CPU 버스트 이후의 다음 CPU 버스트의 예측 값이며, 𝜶는 예측에 사용되는 상수

초기 예측값 𝜏0은 상수로 설정하거나 전체 시스템의 평균값으로 정의될 수 있다.

->   이를 통해 CPU 버스트의 예측값을 조정하고 대기 시간을 최소화할 수 있다.

 

Priority Scheduling

 

Priority Scheduling

우선순위 스케줄링 

 

각 프로세스에는 우선순위 번호가 할당된다. CPU는 가장 높은 우선순위를 가진 프로세스에 할당된다. 예를 들어 가장 작은 정수는 가장 높은 우선순위를 나타낸다. 이 스케줄링 방식은 선점형 및 비선점형 두 가지 버전으로 구현될 수 있습니다.

또한 SJF는 우선순위 스케줄링 중 하나로, 여기서 우선순위는 다음 CPU Brust 예측한 값.

문제:

굶주림 (무한 블로킹)

• ->지나치게 높은 우선순위를 가지거나 연속적으로 높은 우선순위를 가진 프로세스가 도착하는 경우, 낮은 우선순위를 가진 프로세스는 실행될 수 없는 상황이 발생할 수 있음
•  
• MIT의 IBM 7094 컴퓨터가 1973년에 종료될 때 1967년에 제출된 낮은 우선순위 프로세스가 발견되었던 사례

 

해결책:

노화(Aging)

• 시간이 지남에 따라 프로세스의 우선순위를 높이는 방법을 도입
• 이를 통해 오랫동안 낮은 우선순위로 기다려야 하는 문제를 완화함
• 낮은 우선순위 프로세스도 언젠가는 높은 우선순위를 얻을 기회가 주어짐

 

Round Robin (RR) Scheduling

 

Round Robin (RR) Scheduling 

• 다중 프로세스 스케줄링 알고리즘 중 하나.
• 각 프로세스가 동일한 time slice, time quantum 내에서 CPU를 할당받는 방식으로 동작한다. 단위는 일반적으로 10-100 밀리초.
• 이 시간이 경과하면 해당 프로세스는 선점(preempted)되고 준비 큐의 끝에 추가된다. 

 

만약 준비 큐에 N개의 프로세스가 있고 time quantime이 q라면,

• 각 프로세스는 최대 q 시간 단위로 CPU 시간의 1/n을 할당받는다. 이는 CPU 시간을 n개의 프로세스에 균등하게 분배하는 것을 의미한다. 
• 각 프로세스는 (n-1) x q 시간 단위보다 더 긴 대기를 경험하지 않는다. 즉, 다른 프로세스가 실행되기를 기다리는 시간이 (n-1) x q 이하다.
• 이것은 프로세스 공유를 의미한다. n개의 프로세스가 각각 자신의 프로세서를 가지고 있으며, 이 프로세서는 실제 프로세서 속도의 1/n로 동작한다.

다중 프로세스 간에 CPU 시간을 공평하게 분배하고, 각 프로세스가 너무 오랫동안 대기하지 않도록 하는 방법 중 하나. 이러한 프로세스 공유 방식은 시분할 시스템(Timed sharing) 에서 사용되며, 다중 사용자 환경에서 여러 프로세스가 공정하게 CPU 시간을 사용할 수 있도록 도와준다.

 

 

large q -> 라운드 로빈 스케줄링 = FCFS 스케줄링과 유사하게 동작한다. 이것은 각 프로세스에 대한 실행 시간 할당이 길어진다는 것을 의미하며 더 오래 실행된다는 것을 의미한다. 

 

small q-> 많은 컨텍스트 전환이 너무 많이 발생하지 않도록 충분히 크게 설정해야 합니다. 그렇지 않으면 시스템 성능 저하될 수 있다. 결국 q의 크기는 컨텍스트 전환에 비해 충분히 크도록 설정해야 한다. 

일반적으로 라운드 로빈 스케줄리은 최단 작업 우선(SJF) 스케줄링보다 높은 값을 가지는 경향이 있다. 이는 라운드 로빈 스케줄링이 각 프로세스에 대한 실행시간을 균일하게 나누는 방식으로 동작하기 때문이다. 

 

그러나 라운드 로빈 스케줄링은 빠른 응답시간을 제공하는데 더 효과적일 수 있다. 이는 각 프로세스가 시간 양자 내에서 실행되고 다른 프로세스에 CPU를 넘겨야하기 때문이다. 

 

 

 

 

Turnaround Time Varies With Time Quantum

 

 

평균 반환 시간이 time quantum 가 증가함에 따라서 반드시 향상 되는 것은 아님-> 향상 될 수는 있지만 이러한 개선은 모든 프로세스가 다음 CPU Brust를 단일 time quantum 내에서 완료하는 경우에 발생한다. 

 

Multilevel Queue Scheduling

 

Ready queue는 별도의 queue로 분활된다.

• Foreground
• Background

프로세스는 하나의 queue에 영구적으로 할당된다.

각 queue는 고유한 스케줄링 알고리즘을 가지고 있다. 

• Foreground - 라운드 로빈 스케줄링
• Background - FCFS(먼저 온 순서대로 처리) 스케줄링

 

 

 

한번 줄서면 자기 차례가 올때까지 바뀌지 않는다

queue 간 스케줄링 방법 

 

고정 우선순위 선점(preemptive) scheduling 사용 

 

• p(foreground processes) > p (background processes )
• 먼저 foreground  processes queue 에서 모두 처리한 다음에 background  processes queue에서 처리한다.
• 기아 현상(특정 프로세스나 작업이 충분한 CPU 자원을 얻지 못하여 계속해서 대기하는 상황)이 발생할 수 있다. 

 

queue 간 스케줄링 방법 

 

• CPU 시간을 각 queue에 일정한 비율로 할당한다.
• 예를 들어 CPU의 80%를 전경 프로세스에 할당하고 20%를 배경 프로세스에 할당
• 기아 현상이 없음 

 

Multilevel Feedback Queue Scheduling

• 새로운 작업이 큐 Q0에 들어오며, 이 큐는 Round Robin(RR) 방식으로 처리된다.
• CPU를 얻으면 작업은 8밀리초의 CPU 시간을 받는다.
• 8밀리초 안에 작업을 완료하지 못하면, 작업은 큐 Q1로 이동된다.
• 큐 Q1에서 작업은 다시 RR 방식으로 처리되며 추가로 16밀리초의 CPU 시간을 받는다.
• 이 시간 안에도 작업을 완료하지 못하면, 작업은 선점당하고 큐 Q2로 이동된다.

프로세는 CPU Brust 특성에 따라 다양한 큐 간에 이동할 수 있다.

 

• 준비 큐에 들어오는 프로세스는 큐 0에 배치된다.
• CPU 시간을 지나치게 사용하는 프로세스는 낮은 우선순위 큐로 이동될 수 있다.
• 낮은 우선순위 큐에서 너무 오랫동안 대기하는 프로세스는 높은 우선순위 큐로 이동할 수 있다(기아 상태 방지).

다음과 같은 매개변수로 정의된다.

 

• 큐의 수
• 각 큐를 위한 스케줄링 알고리즘
• 어떤 큐에 프로세스가 서비스를 필요로 할 때 해당 프로세스가 어떤 큐로 들어갈지 결정하는 방법
• 프로세스를 업그레이드할 때 언제 업그레이드할지 결정하는 방법
• 프로세스를 강등할 때 언제 강등할지 결정하는 방법

Multi-Processor System Scheduling

Asymmetric Multi-Processor System (AMP System):

각 프로세서가 별도의 역할을 가지며 서로 다른 작업을 수행한다.
예를 들어, 하나의 프로세서가 운영 체제(OS)를 실행하고 다른 프로세서는 응용 프로그램을 처리하는 역할을 할 수 있다.
AMP 시스템은 특정 업무에 중점을 둘 때 유용하다.

Symmetric Multi-Processor System (SMP System):

모든 프로세서가 동등한 지위를 가지며, 모든 프로세서가 동일한 메모리와 시스템 리소스에 접근할 수 있다.

운영 체제(OS)가 각 프로세서 사이에서 자유롭게 실행될 수 있는 시스템 구조
SMP 시스템은 프로세서 사이의 작업을 동등하게 분배하고, 프로세서 간에 협력하여 성능을 향상시킨다.
대부분의 현대적인 다중 프로세서 시스템은 SMP 아키텍처를 기반으로 하며, 멀티코어 프로세서가 이 유형에 속한다. 

 

 

 

 

 

 

Asymmetric Multi-Processor System은 단일 프로세서(마스터 프로세서라고 함)가 스케줄링, I/O 처리 등과 같은 모든 시스템 활동을 처리하는 시스템 구조를 나타냅니다. 이러한 시스템에서 스케줄링은 단순하며, 시스템 데이터 구조에 대한 접근을 하나의 프로세서만 처리하므로 데이터 공유의 필요성을 줄인다. 

 

공동 대기 큐일때

Symmetric Multi-Processor System (SMP System)에선 

 

Ready Queue: 모든 프로세스는 공통의 대기 큐(ready queue)에 있을 수 있다. 또는 각 프로세서마다 별도의 개인적인 대기 큐를 가질 수도 있다.

공통 데이터 구조: 여러 프로세서가 공통 데이터 구조(공통 대기 큐)에 액세스하고 업데이트할 수 있다. 따라서 스케줄러는 공통 데이터 구조를 손상시키지 않도록 조심스럽게 프로그래밍되어야 한다. 모든 CPU는 항상 일을 해야한다. 

개인 대기 큐: 일반적으로 공통 대기 큐보다는 개별 프로세서마다 개인 대기 큐를 가지는 것이 선호된다. 이렇게 하면 데이터 구조 충돌 및 경합을 피할 수 있으며 프로세서 간에 병렬로 작업을 수행할 수 있다. 

 

개인 대기 큐일때

작업 배정 가능

줄의 길이에 따라 일하는 CPU, 쉬는 CPU가 생긴다 -> Load balancing을 해야한다. 각 CPU 코어마다 개별 대기 큐를 사용하는 경우 로드 밸런싱이 중요해진다. 

 

Load Balancing

SMP에서 CPU 코어 간의 작업 부하를 균형있게 분배하는 것. 

• Push Migration : 여기서 특정 작업이 일정 간격으로 각 프로세서의 부하를 확인하고 프로세스를 균등하게 분산한다. 작업이 한 CPU코어에서 다른 CPU코어로 프로세스를 이동시킨다. (긴줄에서 짧은 줄로 이동시킨다)
• Pull Migration : 작업이 없는 프로세스가 부하가 있는 프로세서로 부터 대기중인 작업을 가져와 실행한다. 

Processor Affinity

프로세스가 현재 실행 중인 프로세서에 대한 선호도를 나타낸다. 프로세서 관련성은 프로세스가 특정 프로세서에 실행 중일 대 해당 프로세서에 대한 Affinity를 나타낸다.

• 캐시메모리의 유효성 유지: 프로세스가 다른 프로세서로 Migration하는 경우 첫 번째 프로세서의 캐시 메모리 내용은 무효화 되어야하며 , 두번째 프로세서의 캐시 메모리는 다시 채워져야한다.

캐시 메모리를 무효화하고 다시 채우는 과정이 비용이 많이 드는 작업이기 때문에 프로세스는 현재 실행중인 프로세서에 대한 애착을 가진다. 캐시 메모리의 무효화와 재로딩 작업은 시간과 리소스가 소모되는데, 이러한 과정을 최소하하기 위해 프로세스는 현재 실행 중인 프로세스를 선호하게 된다.