자료 및 개념의 출처 : https://www.os-book.com/OS10/slide-dir/index.html
이 글은 Operating System Concepts 10th edition 을 바탕으로 작성되었습니다.
개요
컴퓨터 전반적인 성능이 증가함에 따라, 특히 CPU 성능의 비약적 발전으로 인해 I/O 작업에 걸리는 시간과의 차이가 크게 벌어졌으며, 이로 인해 과거와 동일한 작업을 수행하더라도 CPU가 대기하는 시간이 증가했다.
사람들은 CPU가 대기하는 시간도 최대한 활용하고자 했다. 따라서 현재 놀고 있는 CPU를 다른 프로세스에 할당하기 위해 메모리 안에 다양한 프로그램을 동시에 적재하는 멀티 프로그래밍 방식이 도입되기도 했다.
이처럼 CPU의 성능을 최대한 활용하기 위해서는 현재 놀고 있는 CPU에 대한 사용권을 다른 CPU에게 넘겨 사용할 수 있도록 해야 한다. 그렇다면, 다음에 CPU를 사용할 프로세스는 어떻게 정할 수 있을까? 이런 문제를 해결하기 위해 현재 적재된 프로세스들에 대한 CPU의 실행 권한 및 순서를 부여하는 CPU 스케줄러가 등장한다.
- CPU burst : CPU 연산 작업을 수행하는 시간
- I/O burst : I/O 와 관련된 작업을 수행하는 시간
CPU Scheduler
CPU scheduler 은 ready queue 에 있는 프로세스들에 대해 CPU를 사용하는 순서를 정해 할당해주는 스케줄러이다. 이때 순서는 요구사항에 따라(우선 순위, FIFS, SJF, LJF 등) 다르게 정해질 수 있다.
- running -> waiting ( 인터럽트로 인한 경우 )
- running -> ready ( 프로세스에 부여된 시간 전부 사용 )
- waiting -> ready ( ready queue가 충분한 경우 )
- terminate ( 프로세스가 자신의 업무를 끝마친 경우 )
Preemptive & Nonpreemptive
- Preemptive
: 프로세스가 running queue에 할당된 이후, 외부의 영향 ( ex: interrupt ) 에 의해 CPU 사용권을 다른 프로세스에게 양도할 수 있는 스케줄링 방식.- 스케줄링에 의한 스위치가 발생할 때, 각 프로세스와 관련된 다양한 정보들도 저장 및 교환되어야 한다.
- Nonpreemptive
: 일단 프로세스가 running queue에 할당되면 외부 interrupt가 있더라도 자신의 작업을 끝까지 수행하도록 하는 스케줄링 방식.- teminate & waiting 으로 상태가 변경되지 않는 경우, 계속 실행된다.
- 프로세스는 다양한 정보(커널, 레지스터, PCB ... ) 를 기반으로 동작하며, 특정 상황에서는 작업을 중단하면 안 되는 경우가 존재한다. 이 경우 비선점 방식을 채택할 수 있다.
Dispatcher
CPU 스케줄러에 의해 선택된 프로세스에게 CPU 사용 권한을 부여한다.
CPU 사용 권한을 부여하기 위해서는 이전 프로세스의 작업을 PCB0에 저장(save)하고, 현재 실행될 프로세스의 정보를 PCB1로부터 가져와(load) 레지스터, 모드 플래그 등 다양한 정보를 교체해야 하는데, 이러한 작업을 수행한다.
Dispatch Latency : 실행중인 프로세스를 정지 및 저장하고, 새로운 프로세스를 로드 및 실행하는데 걸리는 시간
스케줄링을 위한 기준들
- CPU utilization -> MAX
: CPU 사용량. 높을 수록 CPU가 비는 시간 없이 잘 사용함을 의미한다. - Throughput -> MAX
: 단위시간 내 끝낼 수 있는 Job의 수 - Turnaround Time -> MIN
: 각 프로세스의 시작(큐에 도착)부터 실행을 마칠 때까지 걸리는 시간- T = Pf - Pa : 프로세스 종료 시간 - 프로세스 큐에 도착하는 시간
- Waiting Time -> MIN
: 프로세스가 ready queue에서 기다린 총 대기시간.- W = Ps - Pa (NonPreemptive) | Wa = (∑ Wi )/ n (Preemptive)
- Nonpreemptive 환경에서는 Response Time과 동일하다.
- Response Time -> MIN
: 프로세스가 ready queue에 도착해서 처음으로 실행될 때까지 대기한 시간.
모든 최적화를 한번에 달성하는 것은 사실상 불가능하다. 따라서 최적화는 각각의 단위에 대해 처리한다.
스케줄링 알고리즘
FCFS : First - Come First - Served
단순히 먼저 도착한 순서대로 프로세스를 실행하는 알고리즘. 가장 간단하게 구현할 수 있다.
P1, P2, P3 순으로 들어온 경우
| 프로세스 | Arrived | Start | Finished | Waiting | Turnaround |
| P1 | 0 | 0 | 24 | 0 | 24 |
| P2 | 0 | 24 | 27 | 24 | 27 |
| P3 | 0 | 27 | 30 | 27 | 30 |
| 평균 | - | - | - | 17 | 27 |
P2, P3, P1 순으로 들어온 경우
| 프로세스 | Arrived | Start | Finished | Waiting | Turnaround |
| P2 | 0 | 0 | 3 | 0 | 3 |
| P3 | 0 | 3 | 6 | 3 | 6 |
| P1 | 0 | 6 | 30 | 6 | 30 |
| 평균 | - | - | - | 3 | 13 |
동일한 프로세스가 처리되더라도 해당 프로세스들 간의 순서 차이에 의해서 Waiting Time 및 Turnaround Time 이 급격하게 차이날 수 있다.
일반적으로 프로세스들은 Burst Time이 긴 프로세스 뒤에 짧은 프로세스들이 연이어 나오는 방식으로 처리되는 경우가 많다 ( Convey effect ). 위 상황에서는 P2, P3, P1 순으로 프로세스가 오면 좋겠지만 현실에서는 P1, P2, P3 순으로 프로세스가 등장하는 경우가 많다. 따라서 FCFS 방식은 많은 상황에서 성능적으로 부족한 모습을 보인다.
SJF : Shortest Job First
각각의 프로세스들에 대해 다음 CPU burst 시간을 예측하고, 해당 시간이 짧은 순서대로 작업을 실행하는 방식.
Waiting Time을 최소화하기 때문에 많은 상황에서 최적의 선택이지만, 프로세스의 작업 실행시간을 어떻게 예측할 것인지에 대한 고려가 필요하며, 길이가 긴 작업의 우선순위가 계속 밀려 실행되지 않을 수 있다는 단점이 존재한다.
FJFS 방식으로 실행되는 경우
| 프로세스 | Arrived | Start | Finished | Waiting | Turnaround |
| P1 | 0 | 0 | 6 | 0 | 6 |
| P2 | 0 | 6 | 14 | 6 | 14 |
| P3 | 0 | 14 | 21 | 14 | 21 |
| P4 | 0 | 21 | 24 | 21 | 24 |
| 평균 | - | - | - | 10.25 | 16.25 |
SJF 방식으로 실행되는 경우
| 프로세스 | Arrived | 시작 순서 | Start | Finished | Waiting | Turnaround |
| P1 | 0 | 2 | 3 | 9 | 3 | 9 |
| P2 | 0 | 4 | 16 | 24 | 16 | 24 |
| P3 | 0 | 3 | 9 | 16 | 9 | 16 |
| P4 | 0 | 1 | 0 | 3 | 0 | 3 |
| 평균 | - | - | - | - | 7 | 13 |
SJF으로 프로세스를 처리하는 경우 평균 대기시간 및 Turnaround time이 모두 FJFS 방식에 비해 감소했다.
Next CPU Burst 시간 계산 방식
일반적으로 특정 프로세스가 얼마나 시간이 걸릴지는 맨 처음에는 알 수 없다. 그러나 특정 프로세스가 실행되면, 해당 프로세스가 실제로 실행될 때 걸린 시간은 확실히 알 수 있다. 따라서 과거 특정 프로세스가 보인 실행 시간 정보를 지수 평균 ( exponential averaging ) 을 이용하여 계산한다.
보통 네트워크 패킷의 예상 도착시간을 계산할 때도 유사한 수식이 사용된다.
- tn : 특정 프로세스의 n번째 CPU burst 에 대한 실제 길이
- τn : 특정 프로세스의 n번째 CPU burst 에 대한 예측치
- a : 비례 계수. 높을 수록 최근 값에 대한 영향이 크며, 보통 1/2로 설정.
τn + 1 = a tn + (1 - a) τn
Shortest remaining time first
SJF 의 preemptive 한 방식. 정해진 단위시간마다 남은 시간이 가장 짧은 작업을 수행한다.
t = 1
| 프로세스 | arrived | Start | Remaining | Finished | Waiting | Turnaround |
| P1 | 0 | 0 | 7 | - | - | - |
| P2 | 1 | - | 4 | - | - | - |
| P3 | - | - | - | - | - | - |
| P4 | - | - | - | - | - | - |
t = 5
| 프로세스 | arrived | Start | Remaining | Finished | Waiting | Turnaround |
| P1 | 0 | 0 | 7 | - | 4 | - |
| P2 | 1 | 1 | 0 | 5 | 0 | 4 |
| P3 | 2 | - | 9 | - | 3 | - |
| P4 | 3 | - | 5 | - | 2 | - |
t = 10
| 프로세스 | arrived | Start | Remaining | Finished | Waiting | Turnaround |
| P1 | 0 | 0 | 7 | - | 9 | - |
| P2 | 1 | 1 | 0 | 5 | 0 | 4 |
| P3 | 2 | - | 9 | - | 8 | - |
| P4 | 3 | 5 | 0 | 10 | 2 | 7 |
t = 17
| 프로세스 | arrived | Start | Remaining | Finished | Waiting | Turnaround |
| P1 | 0 | 0 | 0 | 17 | 9 | 17 |
| P2 | 1 | 1 | 0 | 5 | 0 | 4 |
| P3 | 2 | - | 9 | - | 15 | - |
| P4 | 3 | 5 | 0 | 10 | 2 | 7 |
t = 26
| 프로세스 | arrived | Start | Remaining | Finished | Waiting | Turnaround |
| P1 | 0 | 0 | 0 | 17 | 9 | 17 |
| P2 | 1 | 1 | 0 | 5 | 0 | 4 |
| P3 | 2 | 17 | 0 | 26 | 15 | 24 |
| P4 | 3 | 5 | 0 | 10 | 2 | 7 |
| 평균 | - | - | - | - | 6.5 | 13 |
( 계산이 정확하지 않을 수 있습니다. 대략 이런 느낌이구나, 하고 봐주세요. )
Round Robin ( RR )
CPU 실행시간을 작은 유닛 ( quantum ) 단위로 나누고, 각 시간을 프로세스에게 차례대로 할당하는 방식.
quantum은 보통 10 ~ 100 ms 사이에서 결정되며, 80% 이상의 프로세스가 단위 시간 안에 종료되는 것이 이상적이다.
- quantum이 지나치게 큰 경우 : FIFS 와 다를바가 없음.
- quantum이 지나치게 작은 경우 : 컨텍스트 스위칭이 지나치게 많이 발생, 오히려 오버헤드로 작용한다.
SJF 방식보다 Waiting time 및 Turnaround time이 짧지는 않지만, 모든 작업이 동등한 시간을 차례대로 사용하기 때문에 Response time 은 확실히 감소하며, Starvation 현상이 발생하지 않는다.
t = 4
| 프로세스 | Arrived | Start | Remain | Finished | Response | Waiting | Turnaround |
| P1 | 0 | 0 | 20 | - | 0 | 0 | - |
| P2 | 0 | 4 | 3 | - | 4 | 4 | - |
| P3 | 0 | - | 3 | - | - | 4 | - |
t = 7
| 프로세스 | Arrived | Start | Remain | Finished | Response | Waiting | Turnaround |
| P1 | 0 | 0 | 20 | - | 0 | 3 | - |
| P2 | 0 | 4 | 0 | 7 | 4 | 4 | 7 |
| P3 | 0 | 7 | 3 | - | 7 | 7 | - |
t = 10
| 프로세스 | Arrived | Start | Remain | Finished | Response | Waiting | Turnaround |
| P1 | 0 | 0 | 20 | - | 0 | 6 | - |
| P2 | 0 | 4 | 0 | 7 | 4 | 4 | 7 |
| P3 | 0 | 7 | 0 | 10 | 7 | 7 | 10 |
t = 30 ( 14, 18, 22, 26, 30 )
| 프로세스 | Arrived | Start | Remain | Finished | Response | Waiting | Turnaround |
| P1 | 0 | 0 | 20 | 30 | 0 | 6 | 30 |
| P2 | 0 | 4 | 0 | 7 | 4 | 4 | 7 |
| P3 | 0 | 7 | 0 | 10 | 7 | 7 | 10 |
| 평균 | - | - | - | - | 3.67 | 5.67 | 15.67 |
Turnaround Time과 Quantum 사이의 관계
quantum과 Turnaround time은 비례하게 증가하거나 감소하는 관계를 가지지는 않는다. 다만 지나치게 짧으면 overhead로 작용하고 너무 길면 FCFS 와 차이가 없어지므로, 각 상황에서 계산을 통해 적절하게 설정하는게 중요하다.
대부분의 상황에서 CPU burst의 80% 이상이 quantum 안에서 처리되는 것이 이상적이라고 한다.
Priority Scheduling
각각의 프로세스에 대해 우선순위를 지정해두고, 해당 우선순위에 따라 프로세스를 실행하는 방식의 스케줄링.
- Preemptive : 우선순위가 높은 프로세스가 등장하면, 현재 작업중인 프로세스 멈추고 CPU 사용권 넘김
- Nonpreemptive : 일단 running state 되면 높은 프로세스가 오건 말건 끝날때까지 수행
ex ) SJF 스케줄링은 다음 CPU burst가 가장 짧을 수록 우선순위를 높게 부여한 스케줄링 방식이다.
- Problem - Starvation ( 기아 문제 )
: 우선순위가 낮은 프로세스는 실행 순서가 계속 뒤로 밀려 실행되지 않을 수도 있다.
극단적인 예시로, 3년간 컴퓨터를 켜두더라도 우선순위로 인해 프로세스가 실행되지 않을 수 있다. - Solution - Aging ( 우선순위 증가 )
: 특정 프로세스가 일정 기간 이상 실행되지 않으면, 해당 프로세스의 우선순위를 높여 실행되도록 한다.
예시1 : 동시간에 도착한 프로세스들 사이의 우선순위 스케줄링
| 프로세스 | Arrived | Priority | Start | Finished | Waiting | Turnaround |
| P1 | 0 | 3 | 6 | 16 | 6 | 16 |
| P2 | 0 | 1 | 0 | 1 | 0 | 1 |
| P3 | 0 | 4 | 16 | 18 | 16 | 18 |
| P4 | 0 | 5 | 18 | 1 | 18 | 19 |
| P5 | 0 | 2 | 1 | 6 | 1 | 6 |
| 평균 | - | - | - | - | 8.2 | 12 |
예시 2 : 우선순위 스케줄링에 Round-Robin : quantum = 2 적용
Multi Level Queue
Priority Scheduling을 수행할 때 작업의 특성에 따라 다양한 종류의 큐를 만들 수 있다.
- foreground
: 외부 환경과 상호작용하는 프로세스들- 주로 Round Robin 으로 스케줄링
- background
: 내부적 처리를 수행하는 프로세스들- FCFS 으로 스케줄링
Round Robin을 통해 foreground : background 를 80 : 20 비율로 실행하는 식으로 시간을 분배할 수 있다.
MultiLevel Feedback Queue
각 큐에 대해 Aging 및 Time Slice을 적절히 지정하여 멀티 레이어 형태의 큐를 사용할 수도 있다.
MultiLevel Feedback Queue를 구현할 때 고려할 점
- 큐의 개수
- 각 큐에 적용할 스케줄러 알고리즘
- 프로세스를 upgrade 할지 결정하기 위한 메서드
- 프로세스를 demote 할지 결정하기 위한 메서드
- 프로세스가 서비스를 필요로 할 때 어떤 큐에 넣을지 결정하기 위한 메서드
예시
프로세스들을 1차적으로 quantum = 8인 큐에 넣어 실행한다. 만약 해당 큐에서 작업이 끝나지 않는 경우, quantum이 더 긴 큐로 해당 프로세스를 이동하는 작업을 반복한다.
스레드 스케줄링
스레드는 User Level 및 Kernel Level로 구분된다. 운영체제는 Kernel Level의 스레드를 스케줄링하며, User Level 스레드는 스레드 라이브러리에 의해 관리될 뿐 커널의 인식 하에 존재하지 않는다.
CPU에서 스레드가 동작하기 위해서는 반드시 커널 수준 스레드와 매핑되어야 하는데, 해당 과정은 LWP를 통해 스레드 라이브러리가 스케줄링을 진행함으로서 가능하다.
Contention Scope
스레드들은 CPU 작업을 수행하기 위해 다른 스레드들과 경쟁하게 된다. 이때 해당 경쟁 범위가 Contention Scope 이다.
PCS - Process Contention Scope
LWP 상에서 동작하는 유저레벨 스레드(many - to - one, many - to - many ) 에 대한 스레드 라이브러리 주도의 스케줄링. 동일 프로세스에 속한 스레드끼리 CPU를 두고 경쟁한다고 해서 이런 이름이 붙었다고 한다.
스케줄링이라는 이름이 붙기는 했지만, 실제 스케줄링에 의한 CPU 사용은 LWP에 대응되는 커널 스레드가 운영체제에 의해 CPU 코어를 할당받을 때 가능하다. 즉, 프로세스 내에서의 순서 정하기 정도의 위치에 있다.
일반적으로 PCS는 preemptive 하게 동작하며, 유저 수준에서 우선순위를 어느정도 지정할 수 있다. 단, 스레드들에 대해 time slicing 및 round robin이 항상 보장되는 것은 아니며, 운영체제에 따라 다를 수 있다.
SCS - System Contention Scope
시스템 상의 모든 스레드 사이에서 CPU를 할당받기 위해 발생하는 경쟁 관계. window 나 linux 운영체제에서는 통상 one - to - one 모델을 이용한다고 한다.
Pthread Scheduling
리눅스나 mac 환경에서는 Pthread 에 대한 스케줄링을 진행해준다. 단, SCOPE_SYSTEM에 대해서만 지원한다.
- PTHREAD_SCOPE_PROCESS : PCS 스케줄링 지원
- PTHREAD_SCOPE_SYSTEM : SCS 스케줄링 지원
Pthread는 구현이 아니라 specification 이므로, 운영체제마다 SCOPE 지원 범위가 다를 수 있다.
멀티 프로세서 스케줄링
CPU가 여러개인 경우, 스케줄링은 더 복잡해진다. 다음과 같은 상황을 고려할 수 있다.
Homogeneous processors
동일 프로세서가 여러개 존재하는 경우. 스케줄링을 통해 모든 프로세스가 동일한 수준의 작업을 빠짐없이 수행하도록 적절한 로드밸런싱 작업이 필요하다.
Asymmetric multiprocessing
하나의 프로세서가 주된 작업을 수행하고, 다른 프로세서들은 작업을 담당하는 경우. 메인 프로세서에서 모든 데이터를 처리하므로, 데이터의 교환이 다른 방식에 비해 덜 필요하다.
Symmetric multiprocessing
모든 프로세서가 메인 프로세서의 역할을 수행하는 경우. 각각의 프로세서에 대해 스케줄링을 진행할 수도, 하나의 큐에서 스케줄링을 진행하여 작업을 분배할 수도 있는 등 구현 자체는 다양하다.
로드 밸런싱
SMP ( Symmetric multiprocessing ) 방식에서는 각 CPU가 동등한 수준의 역할을 수행해야 하므로, 작업이 적절하게 분산될 수 있도록 조절해줘야 한다. 이 작업을 로드 밸런싱이라고 한다.
Ready Queue가 전체 프로세서에 대해 하나만 존재한다면 작업을 다 수행한 프로세서에게 업무를 맡기면 되겠지만, 각 프로세서마다 별개의 Queue를 가지는 경우 다음과 같은 동작을 고려할 필요가 있다.
- Push Migration : 특정 프로세서가 작업이 많은 경우, 다른 프로세서의 큐로 작업을 던진다.
- Pull Migration : 특정 프로세서가 작업이 없는 경우, 바쁜(busy) 프로세서 큐의 작업을 가져온다.
위와 같은 로드 밸런싱 작업에서는 스레드의 캐시 정보를 잃을 수 있으므로 전반적인 속도가 감소할 수 있다.
Processor affinity
특정 프로세스가 할당된 프로세서에서만 동작되도록 만드는 것.
프로세서1 과 프로세서2가 작업을 진행하는 경우를 생각해보자. 프로세서1 의 작업이 끝나 프로세서2의 작업을 양도받는 경우, 프로세서1에는 해당 작업에 대한 캐시 및 프로세스 정보가 존재하지 않는다. 따라서 해당 정보를 메모리를 통해 로드하기 위해서는 비교적 긴 시간을 투자해야 한다. 이렇듯 경우에 따라 프로세스는 할당된 프로세서에서만 동작되도록 하는 것이 성능적으로 우수할 수 있다.
- soft affinity : 가능한 한 프로세스를 할당된 프로세서에서 동작시키는 것
- hard affinity : 반드시 프로세스를 할당된 프로세서에서 동작시키는 것
멀티코어 프로세서
하나의 프로세서에 여러개의 코어를 두는 방식.
하나의 프로세서에서 모든 작업을 담당하게 만들기 위해서는 클럭 수를 증가시켜야 하는데, 이는 전력 소모의 증가 및 발열량 증가라는 문제점을 가져오게 된다. 따라서 프로세서 하나의 성능을 늘리는 대신 프로세서 내에 작은 단위를 여러개 두어 각각을 사용하는 방식을 채택하게 되었고, 최근에는 멀티코어 프로세서를 대중적으로 사용한다.
Memory Stall
현대 프로세서의 속도는 메모리의 속도보다 월등히 빠르다. 따라서 메모리로부터 정보를 읽어오는데 어느정도의 대기시간이 존재하게 된다. Memory Stall 은 해당 시간을 의미한다.
따라서 현대 프로세서에서는 Memory Stall Cycle 시간동안 CPU를 활용하기 위해 하나의 코어에 여러개의 물리적 스레드를 대응시킨다. 8코어 16 스레드 같은 문구는 하나의 코어에 2개의 물리적 스레드를 대응시켰다는 의미로, 앞서 언급한 CPU 효율 상승을 위한 아키텍처라고 볼 수 있다.
NUMA ( non uniform memory access ) & CPU Processing
각 CPU에 대응되는 메모리를 로컬 영역에 둬서 속도를 높이는 방식. 로컬 메모리 접근 속도는 빠르지만, 외부 메모리에 접근할 때는 속도가 상대적으로 느리다.
Real-Time CPU Scheduling
프로세스가 정해진 시간 내에 반드시 수행되어야 한다는 제약조건이 존재할 때 Real-Time 이라는 표현을 이용한다. 이러한 시스템들은 보통 실시간 동작을 포함하기에 real-time 이라는 말이 붙었다. 이때 Real-Time System은 해당 작업이 필수적으로 deadline을 지켜야 하는지에 따라 크게 두 부류로 나뉜다.
- Soft Real-Time System
: real-time 작업이 높은 우선도 ( high priority ) 를 가지기는 하지만, 반드시 스케줄링 된다는 보장은 없는 시스템.
ex ) 실시간 동영상 - Hard Real-Time System
: 작업이 정해진 deadline 내에 반드시 수행되어야 하는 시스템.
ex) 미사일 요격 시스템
이러한 작업들은 문제를 일관적이고 별 이슈 없이 처리할 수 있는지가 중요한 척도로 작용한다.
Event Latency
특정 이벤트가 발생한 후부터 해당 이벤트에 반응할 때까지 걸리는 시간을 Event Latency라고 한다.
- Interrupt latency
: 인터럽트가 생성된 시점부터 인터럽트 서비스 루틴이 시작될 때까지 걸리는 시간 - Dispatch latency
: CPU에서 현재 수행중인 프로세스를 인터럽트 프로세스와 스위칭하는데 걸리는 지연.
컨텍스트 스위칭은 작업을 의미하고, Dispatch latency는 해당 작업에 걸리는 시간이 된다.- 커널 모드에서 실행중인 프로세스를 선점
- low priority 프로세스를 ready 상태로 돌리고, 해당 자원을 high priority 작업에 넘긴다.
Priority-based Scheduling
리얼 타임 시스템에서 프로세스를 스케줄링 할 때, 스케줄러는 반드시 preemptive + priority 기반으로 동작해야 한다. 특히 Hard Real-time 시스템을 다루는 경우 deadline 까지도 고려해야 한다.
따라서 Priority-based Scheduling에서는 다음 세가지를 고려한다.
- t : 프로세스에 걸리는 시간
- d : 프로세스가 반드시 종료되어야 하는 시간 ( deadline )
- p : 프로세스가 실행되는 주기
위 요소들은 다음 조건을 만족한다.
- 0 ≤ t ≤ d ≤ p
- 단위시간당 작업 처리율 Rate = 1/p
Rate Monotonic Scheduling
프로세스가 실행되는 주기(period)가 짧을 수록 우선순위를 높게 두는 방식의 스케줄링. 각각의 시간마다 우선순위가 더 높은 프로세스를 실행하게 된다.
| P1 | P2 | t1 | t2 |
| 50 | 100 | 20 | 35 |
P1의 주기는 50, P2의 주기는 100초이다. 따라서 P1의 우선순위가 P2 보다 높다. 위 간트 차트에서는 P1의 작업을 다 완료한 후 P2의 작업을 수행하는 모습을 보여주고 있다.
그런데, 경우에 따라 이 방식은 문제가 발생할 수 있다.
| P1 | P2 | t1 | t2 |
| 50 | 80 | 25 | 35 |
위 그림은 P2의 주기가 감소하고, P1을 수행하는데 걸리는 시간 t1이 증가했을 때의 모습을 보여준다. 앞선 그림에서와는 달리 P2의 주기 감소로 인해 deadline 내에 모든 작업을 수행하지 못하는 모습을 볼 수 있다. 이처럼 Monotonic Scheduling은 단순히 각 시간에 존재하는 프로세스들의 우선순위만을 고려하여 스케줄링이 진행되므로 period의 분포에 따라 deadline을 넘기는 프로세스가 존재할 수 있다.
Earlist Deadline First Scheduling
현재 가장 deadline이 가까운 프로세스가 실행될 수 있도록 스케줄링을 진행하는 방식이다. 따라서 새로운 프로세스가 들어오더라도 해당 프로세스의 deadline이 기존 실행중이던 프로세스의 deadline보다 멀리 있다면 기존 프로세스를 계속 실행하게 된다.
Propotional Share Scheduling
각각의 프로세스들이 전체 프로세스의 업무 T에 대해 자신의 task에 걸리는 시간 N 에 대한 비율만큼의 시간을 할당받도록 하는 스케줄링 방식. 예를 들어 P1 은 25, P2는 35의 시간을 사용한다면, P1은 25/60 %, P2 는 35/60% 만큼의 시간을 할당받아 사용하게 된다.
Posix Real-Time Scheduling
SCHED_FIFO ( FIFS ) 및 SCHED_RR ( Round Robin ) 방식을 지원하며, 해당 설정은 다음 함수를 통해 가능하다.
스케줄링 알고리즘 평가 방법
크게 3가지 방법이 있다.
- Deterministic Evaluation
: 특정 상황을 가정하고, 각각의 알고리즘의 효율성을 평가한다. - Queueing Model을 이용한 시뮬레이션
: Queueing Model에 랜덤한 데이터를 전달하여 각 알고리즘을 평가한다. 수학적 계산 모델이라 실제 환경과는 큰 차이가 존재할 수 있다. - Implementation
: 실제로 알고리즘을 구현하고, 시스템에서 테스트해본다. 실제 기기에 대해 수행하는 것이므로 비용 및 리스크가 매우 크며, 환경마다도 크게 다를 수 있다.
'CS > 운영체제' 카테고리의 다른 글
| [운영체제] 데드락 (0) | 2022.04.30 |
|---|---|
| [운영체제] 동기화 문제 및 방법 (0) | 2022.04.22 |
| [운영체제] 스레드 & Concurrency (0) | 2022.04.06 |
| [운영체제] 프로세스 (0) | 2022.04.03 |
| [운영체제] 운영체제 (0) | 2022.03.17 |
