Basic Concepts
다중프로그래밍(Multiprogramming) 및 최대 CPU 활용
- 다중프로그래밍은 여러 프로세스가 동시에 메모리에 적재되어 CPU를 사용할 수 있는 시스템 기법이다. 이것은 CPU가 놀거나 유휴 상태를 최소화하여 최대한 활용할 수 있는 방법 중 하나이다.
CPU-I/O Burst Cycle
- 프로세스 실행은 CPU 실행과 I/O 대기의 주기로 이루어진다.
- 프로세스는 CPU에서 실행되다가 I/O 작업을 위해 기다린다.
CPU Burst와 I/O Burst
- CPU Burst는 CPU에서의 연속적인 실행 시간이다.
- 반면에 I/O Burst는 해당 프로세스가 I/O 작업을 위해 기다리는 시간을 나타낸다.
CPU Burst 분포
- CPU Burst의 길이와 간격은 프로세스 동작의 특성을 결정짓는 요소이다.
- 이러한 분포를 이해하고 관리함으로써 시스템의 성능을 최적화한다.
- 작은 burst size가 많은 경우는 프로세스나 데이터 패킷의 작은 크기가 많이 발생한다는 것이다.
- ex) 마트 계산대: 소량의 물건을 사는 손님들은 전체 고객 중 소수이지만 많은 거래가 발생한다.
시스템 자원 사용량 관리
- CPU나 메모리 등 시스템 자원의 사용량을 과다하게 사용하면 시스템이 불안정해질 수 있다. 예를 들어, CPU 100% 사용하거나 메모리가 가득 차면 시스템이 느려지거나 비정상적으로 동작할 수 있다. 이를 방지하기 위해 시스템은 자원을 적절히 관리하고, 너무 많은 자원 사용을 막기 위해 시스템을 종종 제한하거나 조정한다.
CPU Scheduler
: 준비큐에 있는 프로세스들 중에서 어떤 프로세스가 CPU를 사용할지 선택하는 역할
선입선출 큐(FIFO-First-In-First-Out)
- 가장 오래 기다린 프로세스가 CPU를 먼저 사용하는 방식, 먼저 도착한 프로세스 먼저 실행
우선순위 큐(Priority Queue)
- 각 프로세스에 우선순위를 할당하고, 우선순위가 높은 프로세스가 CPU를 먼저 사용하는 방식
트리(Tree)
- 우선순위나 다른 속성에 따라 트리 구조로 프로세스를 정렬
- ex) 트리 구조를 사용하여 우선 순위가 높은 프로세스를 빠르게 찾음
순서가 없는 연결 리스트(Unordered Linked List)
- 특정한 순서 없이, 프로세스가 준비 큐에 추가되고 제거된다.
- 프로세스의 도착 순서나 특정한 속성을 고려하지 않음
선점 스케줄링
- 실행 중인 프로세스가 다른 프로세스에 의해 중단될 수 있는 방식
- CPU를 가진 프로세스가 실행 중에 중단되어 다른 프로세스가 CPU를 차지할 수 있음
- Running to Waiting State: 실행 중인 프로세스가 입출력 요청 등으로 인해 대기 상태로 전환될 때 스케줄링 결정이 이루어진다.
- Running to Ready State: 실행 중인 프로세스가 다른 프로세스가 실행되기 위해 준비 상태로 전환할 때 스케줄링 결정이 이루어짐
- Waiting to Ready State: 대기 중인 프로세스가 대기에서 준비 상태로 전환될 때 스케줄링 결정이 이루어짐
- New to Ready State: 새로운 프로세스가 시스템 도착하여 준비 상태로 전환될 때 스케줄링 결정이 이루어짐
- Termination: 프로세스가 종료될 때 스케줄링 결정이 이루어짐
1번과 5번 상황은 비선점 스케줄링으로 프로세스가 CPU를 할당받은 후 종료할 때까지 or 대기 상태로 들어갈 때까지 CPU를 갖고 있는다.
공유 자원을 업데이트하거나 운영체제의 핵심적인 작업을 하는 중에 선점될 경우 문제가 발생한다. 이를 방지하기 위해서 운영체제가 중요한 작업을 수행할 때는 인터럽트를 금지시키는 방법 등을 사용하여 스케줄러가 중요한 작업 중에는 선점되지 않도록 방지한다.
Scheduling Criteria
- CPU 이용률: CPU를 최대한 활용하여 시스템을 빈번히 작동시킨다. (CPU 놀지 말고 일해라)
- 처리량: 단위 시간당 완료된 프로세스의 수이다. 빠른 처리량은 시스템의 효율성을 나타내고, 많은 프로세스가 짧은 시간 안에 완료되어야 한다.
- 총 처리 시간: 특정 프로세스가 실행되기 위해 소요된 전체 시간이다. 프로세스의 제출 시간부터 완료시간까지 걸린 시간으로, 준비 큐 대기 시간, CPU 실행시간, I/O 시간 등의 합으로 구성된다.
- 대기 시간: 프로세스가 준비 큐에서 대기하는 동안 보낸 시간의 총합이다.
- 응답 시간: 요청이 제출된 시간부터 첫 응답이 생성될 때까지 걸린 시간이다. 이는 대화형 시스템에서 사용자가 명령을 입력한 후 첫 응답을 받는 데까지 걸린 시간이다.
Scheduling Algorithms
Fist-Come, First-Served(FCFS)
프로세스가 도착한 순서대로 CPU를 할당한다.
| Process | Burst Time |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
- P1의 대기시간 : 0 (처음 도착하므로 대기 시간 없음)
- P2의 대기시간 : 24 (P1의 프로세스 연속 사용 시간)
- P3의 대기시간 : 27 (P1과 P2의 프로세스 연속 사용 시간 합)
평균 대기 시간 : (0 + 24 + 27) / 3 = 17
Convoy effect(호위효과) : 긴 프로세스가 CPU를 점유하고 있을 때, 그 뒤에 있는 작은 프로세스들이 오랫동안 기다려야 한다. 예를 들어 맥도날드에서 단체 주문이 들어와 앞에 300개를 주문하면, 이후에 오는 손님들은 단체 주문이 완료될 대까지 기다려야 한다.
이번에는 P2, P3, P1 순서로 도착한다고 가정하면
|----|----|-----------|
0 3 6 30
| P2 | P3 | P1 |- P1의 대기시간 : 6 (P2와 P3의 프로세스 연속 사용 시간 합)
- P2의 대기시간 : 0 (처음 도착하므로 대기 시간 없음)
- P3의 대기시간 : 3 (P2의 프로세스 연속 사용 시간)
평균 대기 시간 : (6 + 0 + 3) / 3 = 3
Shortest-Job-First(SJF) Scheduling
개별 프로세스의 다음 CPU burst 시간이 가장 짧은 프로세스를 우선적으로 스케줄링한다. 주어진 프로세스 집합에 대해 평균 대기 시간을 최소로 하는 최적의 스케줄링이다. 그러나 CPU 요청의 길이를 알아내는 것이 어렵다.
| Process | Burst Time |
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
|----|----|------------|-----------------------|
0 3 9 16 24
| P4 | P1 | P3 | P2 |
- P1의 대기시간 : 3
- P2의 대기시간 : 16
- P3의 대기시간 : 9
- P4의 대기시간 : 0 (Burst Time이 가장 짦음)
평균 대기 시간 : (3 + 16 + 9 + 0) / 4 = 7
Determining Length of Next CPU Burst
이전 CPU Burst길이와 비슷하다고 가정한 후 가장 짧은 프로세스를 선택한다. 이전 CPU Busrt의 길이를 사용하여 지수 평균화를 통해 수행된다. 지수 평균화에서 사용하는 가중치 α는 ½로 설정한다.
Shortest-Remaining-Time-First, SRTF
이 방식의 선점형 버전은 Shortest-Remaining-Time-First, SRTF 라고 부른다. 현재 실행 중인 프로세스의 남은 실행 시간과 새로 도착한 프로세스의 예상 실행 시간을 비교하여, 더 짧은 실행 시간을 가진 프로세스에게 CPU를 할당한다.
| Process | Arrival Time | Burst Time |
| P1 | 0 | 8 |
| P2 | 1 | 4 |
| P3 | 2 | 9 |
| P4 | 3 | 5 |
|----|---------|------------|----------------|--------------------|
0 1 5 10 17 26
| P1 | P2 | P4 | P1 | P3 |도착 시간이 다르고, 선점이 가능한 상황에서의 스케줄링을 고려해보고자 한다.
- P1이 처음에 도착하고 Burst Time이 8이므로, 처음에 스케줄링되며, 대기시간은 0이다.
- P2가 도착하고 Burst Time이 4로 더 짧으므로, P1을 선점하고 스케줄링되며, 대기 시간은 1이다.
- P3이 도착하고 Burst Time이 9이지만, 현재 실쟁 중인 P2의 남은 Burst Time보다 길으므로 대기한다.
- P4가 도착하고 Burst Time이 5로, 현재 실행 중인 P2의 남은 Burst Time보다 길지만, 대기 중인 P3의 Burst Time보다는 짧으므로 P2가 종료된 뒤 스케줄링되며, 대기 시간은 5이다.
- 마지막으로 P1과 P3이 남아 있고, P1의 Burst Time이 더 짧으므로 P1이 먼저 스케줄링 되고 그 후 P3이 스케줄링된다. P1의 대기 시간은 10, P3의 대기 시간은 17이다.
평균 대기 시간 : (9+0+15+2) / 4 =26/4 =6.5msec
*(17-0-8) + (5-1-4) + (26-2-9) +(10-3-5)
https://mycareerwise.com/content/srtf-process-and-examples/content/exam/gate/computer-science
Priority Scheduling(우선순위 스케줄링)
각 프로세스에 우선순위 숫자가 부여되며, CPU는 가장 높은 우선순위(숫자가 작은 것)를 가진 프로세스에게 할당된다
1. 선점형(Preemptive) : 새로 도착한 프로세스의 우선순위가 현재 실행되는 우선순위보다 높으면 CPU를 선점한다.
2. 비선점형(NonPreemptive) : 가장 높은 우선순위의 프로세스가 준비 상태의 가장 앞에 위치한다.
SJF(Shortest Job First)스케줄링은 우선순위 스케줄링이다. 우선순위는 예측된 다음 CPU Burst 시간의 역수로 결정된다. 즉, 버스트 시간이 짧은 프로세스가 높은 우선 순위를 갖는다. 예를 들어 P1의 다음 CPU Burst 시간이 10이라면 이 프로세스의 우선 순위는 낮고, P2 다음의 CPU Burst 시간이 5라면 이 프로세스의 우선 순위는 높다.
이러한 방식이 기아 상태(Starvation)를 가질 수도 있다. 즉 낮은 우선 순위를 가진 프로세스는 높은 우선순위를 가진 프로세스들에게 CPU를 계속 선점당하므로 실행되지 못하는 상태가 될 수 있다. 기아 상태를 해결하기 위해 Aging이라는 기법을 사용할 수 있다. 시간이 지남에 따라 프로세스의 우선 순위를 점진적으로 높여서, 모든 프로세스가 결국에는 실행될 수 있도록 하는 것이다. 이렇게 하면, 낮은 우선 순위를 가진 프로세스도 일정 시간이 지나면, 높은 우선 순위를 가지게 된다.
| Process | Burst Time | Priority |
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |
|----|----------|--------------------|----|----|
0 1 6 16 18 19
| P2 | P5 | P1 | P3 | P4 |- P2의 우선순위가 1로 가장 높으므로 처음에 스케줄링되며, 대기 시간은 0이다.
- 그 다음을 P5의 우선순위가 2로 두번째로 높으므로 스케줄링되며, 대기 시간은 1이다.
- P1의 우선순위가 3으로 세번째로 높고, 대기 시간은 6이다.
- P3의 우선순위가 4로 네번째로 높고, 대기 시간은 16이다.
- P4의 우선순위가 가장 낮고, 대기 시간은 18이다.
평균 대기 시간 : (6 + 0 + 16 + 18 + 1) / 5 = 8.2 msec
| Process | Burst Time | Priority |
| P1 | 2 | 2 |
| P2 | 1 | 1 |
| P3 | 8 | 4 |
| P4 | 4 | 2 |
| P5 | 5 | 3 |
|----|----|-------|---------|--------------|
0 1 3 7 12 20
| P2 | P1 | P4 | P5 | P3 |P2의 우선 순위가 1로 가장 높으므로 처음에 스케줄링되며, 대기 시간은 0이다.
P1과 P4의 우선순위가 2로 두번째로 높지만, P1이 먼저 도착했으므로 P1이 먼저 스케줄링된다. P1의 대기 시간은 1, P4의 대기 시간은 3이다.
P5의 우선순위가 3으로 세번째로 높으므로, P4 다음에 스케줄링되며 대기 시간은 7이다.
P3의 우선순위가 가장 낮으므로 마지막에 스케줄링되며 대기 시간은 12이다.
평균 대기 시간 : (1 + 0 + 12 + 3 + 7) / 5= 4.6msec
Round Robin(RR)
시분할 시스템을 위해 설계된 방식이다. 각 프로세스가 일정시간 시간할당량(q)동안 CPU를 사용하게 된다. 시간 할당량은 일반적으로 10-100밀리초이다. 시간이 지나면, 해당 프로세스는 선점되어 준비완료 큐의 끝에 추가된다. 예를 들어, 준비완료 큐에 5개의 프로세스가 있고 시간 할당량이 20밀리초이면, 각 프로세스는 매 100밀리초마다 최대 20밀리초 동안 CPU를 사용하게 된다.
타이머는 매 시간 할당량마다 인터럽트를 발생시켜 다음 프로세스를 스케줄링한다. 성능 측면에서 시간할당량 q가 크면 FCFS와 유사한 성능을 보인다. 반면, 시간 할당량 q가 작으면 문맥 교환 시간에 비해 크게 설정되어야 한다. 그렇지 않으면 오버헤드가 너무 크게 잘생한다. 일반적으로 시간 할당량 q는 10ms에서 100ms사이로 설정되며 문맥 교환시간은 10마이크로초 미만이다.
Example of RR with Time Quantum = 4
| Process | Burst Time |
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
|----|----|----|----|----|----|----|----|
0 4 7 10 14 18 22 26 30
| P1 | P2 | P3 | P1 | P1 | P1 | P1 | P1 |일반적으로 SJF보다 높은 평균 처리 시간이지만, 각 프로세스에게 공정한 CPU를 할당하기에 응답 시간 측면에서는 더 공정하다.
Multilevel Queue(다단계 큐)
Ready queue를 여러 개의 독립된 큐로 분할하는 스케줄링이다.
대화형(foreground) - RR
배치(background) - FCFS
1. 고정 우선순위 스케줄링 : 예를 들어, 먼저 모든 대화형 프로세스를 처리하고 나서 배치 프로세스를 처리하는 방식이다. 그러나 기아 상태 발생 가능성이 있다
2. 시간 분할 : 각 큐는 일정량의 CPU 시간을 할당받아 그 안에서 자신의 프로세스를 스케줄링한다. CPU시간의 80%를 RR을 사용하는 대화형 큐에 나머지 20%는 FCFS를 사용하는 배치 큐에 할당할 수 있다.
Multilevel Feedback Queue(다단계 피드백 큐)
다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링은 프로세스가 여러 큐 사이를 이동할 수 있는 방식이다. 이 방식은 프로세스의 우선순위를 동적으로 변경하여 Aging를 구현할 수 있습니다.
다단계 피드백 큐 스케줄러는 다음과 같은 파라미터로 정의됩니다:
- 큐의 개수
- 각 큐에 대한 스케줄링 알고리즘
- 프로세스를 업그레이드할 때 사용하는 방법
- 프로세스를 강등할 때 사용하는 방법
- 프로세스가 서비스가 필요할 때 어느 큐에 들어갈지 결정하는 방법
다단계 피드백 큐의 예
Q0 - 타임 퀀텀이 8밀리초인 RR(Round Robin)
Q1 - 타임 퀀텀이 16밀리초인 RR
Q2 - FCFS(First Come First Serve)
- 새로운 작업이 Q0 큐에 들어가며, 이 큐는 FCFS 방식으로 서비스된다.
- 작업이 CPU를 획득하면, 8밀리초 동안 실행된다.
- 만약 8밀리초 내에 완료되지 않으면, 작업은 Q1 큐로 이동한다.
- Q1에서는 작업이 다시 FCFS 방식으로 서비스되며, 추가로 16밀리초 동안 실행된다.
- 만약 이 시간 내에도 완료되지 않으면, 작업은 선점되어 Q2 큐로 이동한다.
Thread Scheduling
스레드 스케줄링은 프로세스 내의 스레드들 사이에서 CPU를 할당하는 방법이다. 스레드 스케줄링에서는 유저 레벨 스레드와 커널 레벨 스레드를 구분된다.
- 유저 레벨 스레드: 운영체제가 인식하지 못하며, 사용자 애플리케이션에 의해 관리된다. 이 스레드는 프로세스 내에서 자체적으로 스케줄링되며, 이러한 스케줄링 경쟁 범위를 프로세스-경쟁 범위(Process-Contention Scope, PCS)라고 한다. many-to-one 모델과 many-to-many 모델에서는 스레드 라이브러리가 유저 레벨 스레드를 Lightweight Process(LWP)에 스케줄링한다. 이때 유저 레벨 스레드의 우선순위는 일반적으로 프로그래머에 의해 설정된다.
- 커널 레벨 스레드: 운영체제가 직접 관리하며, 시스템 전체의 스레드들 사이에서 스케줄링 경쟁이 발생한다. 이러한 스케줄링 경쟁 범위를 시스템-경쟁 범위(System-Contention Scope, SCS)라고 한다. 커널 스레드는 사용 가능한 CPU에 스케줄링되며, 이는 시스템의 모든 스레드들 사이에서 경쟁이 발생하게 된다.
Multiple-Processor Scheduling
| 비대칭 다중 처리 | 대칭 다중 처리(SMP) | |
| 프로세서의 역할 | 하나의 프로세서가 주로 시스템 자료 구조를 관리하고, 나머지 프로세서는 특정 작업 담당 | 모든 프로세서가 동등하게 작업을 수행하고, 모든 자원과 메모리에 접근 가능 |
| 병목 현상 | 발생 가능성 있음, 하나의 프로세서가 과부하 상태가 됨 | 없음, 모든 프로세서가 균등하게 작업 분산 |
| 관리 복잡성 | 상대적으로 낮음, 하나의 프로세서가 시스템 자료 구조를 관리 | 상대적으로 높음, 프로세서 간의 데이터 공유와 동기화 관리 |
| 확장성 | 제한적, 시스템이 복잡해질수록 관리 프로세서에 부하가 증가 | 우수, 프로세서 추가에 따른 성능 향상 가능 |
| 현재 사용 상황 | 주로 오래된 시스템에서 사용 | 현재 대부분의 다중 프로세서 시스템 |
SMP Queue 구조
공유 큐(shared Queue): 모든 프로세서가 하나의 공유 큐에 접근한다. 구현이 간단하고 작어블 공정하게 분산할 수 있지만 특정 경우에 따라 캐시 미스와 메모리 스틸이 일어난다.
Per-core Queue : 각 코어마다 따로 Queue가 있다. 프로세서는 자신의 큐에만 접근하여 다른 프로세서가 동시에 접근하려고 할 때 발생하는 메모리 스틸을 피할 수 있다. 또한, 프로세서가 자신의 큐에서 작업을 가져가기에 캐시 미스도 줄일 수 있다. 그러나 작업을 공정하게 분산시키는 데 어려움이 있을 수 있다.
Processor affinity
특정 프로세스가 특정 프로세서에 대한 선호도를 의미한다. 이는 프로세스가 현재 실행 중인 프로세서에 대한 친화성을 가지며 이를 통해 성능을 향상시킬 수 있다.
1 연성 친화성(Soft Affinity): 특정 프로세서에 대한 선호도를 가지지만, 필요에 따라 다른 프로세서에서 실행될 수 있다
2. 강성 친화성(Hard Affinity): 특정 프로세서에서만 실행되어야 한다. 프로세서는 그 프로세서의 캐시에 저장된 데이터를 재사용할 수 있으므로 성능을 향상시킬 수 있다.
NUMA and CPU Scheduling
NUMA 아키텍처는 여러 개의 프로세서가 각자의 로컬 메모리를 가지고 있으며 필요에 따라 다른 프로세서의 메모리에 접근할 수 있다. 프
메모리 배치 알고리즘은 친화성을 고려하여 프로세스를 해당 프로세서의 로컬 메모리에 가까운 위치에 배치할 수 있다. 그러나 자신의 로컬 메모리에서 사용 가능한 공간보다 더 많은 메모리를 필요로 하는 경우, 이 프로세스는 여전히 다른 프로세서의 메모리야 접근해야 할 수 있다. 그런 경우 메모리 배치 알고리즘은 도움이 되지 않는다.
부하 균등(Load Balancing)
SMP 시스템에서 모든 CPU가 효율적으로 작동하려면 각 CPU의 부하가 균등하게 유지되어야 한다. 이는 특정 CPU가 과부하 상태가 되거나 특정 CPU가 놀게 된느 상황을 방지하기 위해서이다.
부하 균등은 작업량을 모든 CPU에 고르게 분산시키려는 시도이다. 이를 위해 푸시 이주(Push Migration)와 풀 이주(Pull Migration)을 사용한다.
1. 푸시 이주(Push Migration) : 주기적으로 각 프로세서의 부하를 확인한다. 만약 특정 CPU에 부하가 많이 걸려 있으면, 해당 CPU의 작업을 다른 CPU로 이동한다. 이를 통해 과부하 상태의 CPU의 부하를 줄이고, 전체 시스템의 부하를 균등하게 분산시킨다.
2. 풀 이주(Pull Migration): 놀고 있는 CPU가 바쁜 프로세서의 대기 중인 작업을 가지고 온다.
Multicore Processors
하나의 물리적 칩에 여러 개의 프로세서 코어를 배치하는 방식이다. 이 방식은 더 빠르고, 더 적은 전력을 소비한다. 또한 각 코어에서 여러 스레드를 실행하는 것이 가능해지면서 이 방식이 일반화되고 있다.
멀티코어 프로세서는 메모리 스탈(memory stall)을 이용하여 효율성을 높인다. 특히, 한 스레드가 메모리를 탐색하는 동안 스탈 상태에 놓이면, 다른 스레드는 그 시간 동안 작업을 계속 진행할 수 있다.
Real-Time CPU Scheduling
1. Soft real-time(연성 실시간) 시스템 : 중요한 실시간 프로세스가 언제 스케줄될지에 대한 보장이 없다. 이러한 시스템은 실시간 제약이 중요하지만, 명확한 마감 시간을 놓치는 것이 시스템 실패를 초래하지 않는 애플리케이션에 적합하다.
2. Hard real-time(강성 실시간) 시스템 : 작업이 그것의 마감 시간 내에 서비스되어야 한다. 항공 제어, 심장 박동기 등과 같이 정확한 타이밍이 중요한 애플리 케이션에 사용된다.
실시간 시스템 성능에는 두 가지 유형의 지연 시간이 영향을 미친다.
1. 인터럽트 지연 시간 : 인터럽트의 도착부터 인터럽트를 서비스하는 루틴의 시작까지의 시간이다. 이는 CPU가 인터럽트를 인지하고 처리하는 데 걸리는 시간이다.
2. 디스패치 지연 시간 : 스케줄러가 현재 프로세스를 CPU에서 제거하고 다른 프로세스로 전환하는 데 걸리는 시간이다. 이는 프로세스 컨텍스트 전환에 필요한 시간을 나타낸다.
디스패치 지연 시간에는 충돌 단계가 존재한다.
1. 커널 모드에서 실행 중인 프로세스의 선점 : 실시간 시스템에서 높은 우선순위의 프로세스가 더 빨리 실행되어야 한다. 그러나 커널 모드에서 실행 중인 프로세스는 일반적으로 선점되지 않는다. 즉, 해당 프로세스가 작업을 완료하거나 대기 상태로 전환하기 전까지는 CPU를 계속 사용한다. 이로 인해 높은 우선순위의 프로세스가 대기해야 하는 상황이 발생할 수 있다.
2. 낮은 우선순위의 프로세스가 높은 우선순위의 프로세스가 필요로 하는 자원을 해제하지 않음 : 낮은 우선순위의 프로세스가 시스템 자원을 사용하고 있는 경우, 높은 우선순위의 프로세스가 해당 자원을 필요로 할 때 문제가 발생한다.
Priority-based Scheduling
실시간 스케줄링을 위해서는 스케줄러가 선점 가능하며 우선 순위 기반의 스케줄링을 지원해야 한다. 하지만 이것은 연성 실시간 시스템에 대해서만 보장된다. 강성 실시간 시스템을 위해서는 또한 마감 시간을 준수할 수 있는 능력을 제공해야 한다. 이는 프로세스가 지정된 시간 내에 반드시 완료되어야 함을 의미한다.
프로세스는 새로운 특성을 가지게 된다 .주기적인 프로세스들은 일정한 간격으로 CPU를 요구한다. 이러한 프로세스는 처리시간 t, 마감시간 d, 기간 p와 같은 특성을 갖는다. (0 ≤ t ≤ d ≤ p )주기적인 작업의 비율은 1/p로 계산된다
Operating Systems Examples
Algorithm Evaluation
Deterministic Evaluation(결정론적 평가)
운영 체제의 CPU 스케줄링 알고리즘 선택은 결정 기준을 설정하고, 이를 바탕으로 알고리즘을 평가하는 과정을 거친다. 이 평가에는 결정론적 모델링이라는 방법이 종종 사용된다. 결정론적 모델링은 특정한 미리 결정된 작업 부하에 대해 각 알고리즘의 성능을 분석하는 방법이다. 이는 미리 정해진 매개변수를 사용해 성능을 평가하므로 결과를 정확히 알 수 있다. 그러나 실시간 스케줄링의 경우 매개변수를 모두 미리 알 수 없어 결정론적 모델링으로 평가하는데 어려움이 있다. 실제 작업 부하는 동적으로 변하기 때문에 미리 예측하는 것이 어렵다. 이에 따라 실시간 스케줄링 알고리즘의 성능을 평가하기 위해서는 다른 방법이 필요하다.
결정론적 평가는 알고리즘의 성능을 평가하는 방법 중 하나로 최소 평균 대기 시간을 계산한다. 이는 간단하고 빠르지만, 입력헤 대한 정확한 숫자가 필요하며, 그 입력에만 적용된다.
Queueing Models
프로세스의 도착, CPU와 I/O 버스트를 확률적으로 설명한다. 지수 분포를 따르며 평균으로 설명된다. 큐잉 모델은 평균 처리량(throughput), 사용률(utilization), 대기 시간(waiting time) 등을 계산한다.
컴퓨터 시스템은 서버의 네트워크로 설명되며, 각 서버는 대기 중인 프로세스의 큐를 가지고 있다. 도착률과 서비스률을 알고 있다면, 큐잉 모델을 사용하여 사용률, 평균 큐 기링, 평균 대기 시간 등을 계산할 수 있다.
https://os.ecci.ucr.ac.cr/slides/Abraham-Silberschatz-Operating-System-Concepts-10th-2018.pdf
'사망년 > 운영체제' 카테고리의 다른 글
| Synchronization Toole(동기화 도구들) (0) | 2023.12.12 |
|---|---|
| chapter 1: Introduction (2) (0) | 2023.09.18 |
| chapter 1: Introduction (1) (0) | 2023.09.10 |