CPU 스케줄링은 다중 프로그램 운영체제의 기본이다. 운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만든다. 최신 운영체제에서는 실질적으로 운영체제는 프로세스가 아니라 커널 수준의 스레드를 스케줄 한다. 그러나 “프로세스 스케줄링”과 “스레드 스케줄링” 용어는 상호 교환적으로 사용된다. 이 장에서는 프로세스 스케줄링 = 일반적인 스케줄링 개념/ 스레드 스케줄링 = 스레드에 국한된 개념인 경우 각 용어를 쓰도록 하겠다.
5.1 기본 개념
다중 프로그램의 목적은 CPU 이용률을 최대화 하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있다. 따라서 어떤 프로세스가 대기해야할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당하게 된다. 이러한 패턴은 계속된다. 하나의 프로세스가 대기해야 할 때마다 다른 프로세스가 CPU 사용을 양도 받을 수 있다. CPU는 중요한 컴퓨터 자원 중 하나이다. 따라서 CPU의 스케줄링은 운영체제 설계의 핵심이 된다.
5.1.1 CPU-I/O 버스트 사이클
CPU 스케줄링의 성공은 프로세스들의 다음과 같은 성질에 의해 좌우된다.
프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.
프로세스들은 이들 두 상태를 교대로 왔다갔다한다.
프로세스 실행은 CPU 버스트로 시작하여 I/O 버스트 → CPU 버스트 → 반복되며, 마지막 CPU버스트는 또 다른 I/O 버스트가 뒤따르는 대신 실행을 종료하기 위한 시스템 요청과 함께 끝난다.
5.1.2 CPU 스케줄러
CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중 하나를 선택해 실행해야한다. 선택 절차는 CPU 스케줄러에 의해 수행된다. 준비 큐에 있는 모든 프로세스는 CPU에서 실행될 기회를 기다리며 대기하고 있다. 큐에 있는 레코드들은 일반적으로 PCB들이다.
5.1.3 선점 및 비선점 스케줄링_Preemptive and Nonpreemptive Scheduling
CPU 스케줄링 결정은 다음의 네가지 상황에서 발생할 수 있다.
- 한 프로세스가 실행 상태에서 대기 상태로 전환될 때 (ex) I/O 요청이나 자식 프로세스를 기다리며 wait() 할 때)
- 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때(인터럽트가 발생할 때)
- 프로세스가 대기 상태에서 준비완료 상태로 전환될 때(I/O의 종료 시)
- 프로세스가 종료할 때
⇒ 1,4의 경우 실행을 위해 반드시 새로운 프로세스가 선택되어야한다. 반면 2,3은 선택의 여지가 있다.
만약 1,4의 상황에서만 스케줄링 발생하는 경우, 이런 스케줄링 방법을 비선점 또는 협조적이라고 한다. 그렇지 않으면 선점이라고 한다. (Window, macOS, Linux 및 UNIX를 포함한 거의 모든 최신 운영체제는 선점 스케줄링 알고리즘을 사용한다.)
선점 스케줄링은 데이터가 다수의 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있다. (한 프로세스가 자료를 갱신하고 있는 동안 선점되어 두번째 프로세스가 실행가능한 상황이 되면, 데이터의 일관성이 깨질 수 있다.) ⇒ 6장에서 상세히 논의할 예정이다.
5.1.4 디스패처_Dispatcher
디스패처는 CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에게 주는 모듈이다.
다음과 같은 작업을 한다.
- 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일
- 사용자 모드로 전환하는 일
- 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일
디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 최고로 빨리 수행되어야한다.
디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데 까지 소요되는 시간을 디스패처 지연이라고 한다.
자발적 문맥교환 vs 비자발적 문맥교환
자발적 문맥교환: 현재 사용 불가능한 자원을 요청했기 때문에 프로세스가 CPU 제어를 포기한 경우
비자발적 문맥교환: 타임 슬라이스가 만료되었거나, 우선순위가 더 높은 프로세스에 의해 선점된 경우와 같이 CPU를 빼앗긴 경우
5.2 스케줄링 기준
CPU 스케줄링 알고리즘을 비교하기 위한 여러 기준이 있다. 비교하는 데 사용되는 특성에 따라 최선의 알고리즘을 결정하는 데 큰 차이를 준다.
- CPU 이용률: 우리는 가능한 CPU를 최대한 바쁘게 유지하기를 원한다. 실제 시스템에서는 40%(부하가 적은 시스템)~ 90%까지의(부하가 큰 시스템의 경우) 범위를 가져야한다.
- 처리량: 작업량 측정의 한 방법은 시간 단위당 완료된 프로세스의 개수로 이것을 처리량이라고 한다.
- 총처리 시간(turnaround time): 특정 프로세스의 입장에서 보면, 중요한 기준은 그 프로세스를 실행하는 데 소요된 시간일 것이다. 프로세스의 제출과 완료 시간의 간격을 총 처리 시간이라고 한다.
- 대기시간: CPU 스케줄링은 프로세스가 실행하거나, I/O를 하는 시간의 양에는 영향을 주지 않는다. 단지 프로세스가 준비 큐에서 대기하는 시간의 양에만 영향을 주는데, 대기시간은 준비큐에서 대기하면서 보낸 시간의 합이다.
- 응답시간(response time): 하나의 요구를 제출한 후 첫번째 응답이 나올 때까지의 시간이다. 프로세스가 처음으로 CPU할당 받을때까지 걸리는 시간이다. 응답시간은 응답이 시작되는 데까지 걸리는 시간이지 응답을 출력하는데 걸리는 시간이 아니다.
⇒ CPU이용률과 처리량은 최대화하고, 총처리시간,대기시간,응답시간은 최소화하는 것이 바람직하다.
5.3 스케줄링 알고리즘
CPU 스케줄링은 준비 큐에 있는 어느 프로세스에 CPU 코어를 할당할 것인지를 결정하는 문제를 다룬다. 여러 다른 CPU 스케줄링 알고리즘을 보자
5.3.1 First-Come, First-Served Scheduling(FCFS)
가장 간단한 CPU 스케줄링 알고리즘이다. 이 방법에서는 CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당 받는다. FCFS의 구현은 FIFO 큐로 쉽게 관리할 수 있다.
부정적인 측면은 FCFS 하에서 평균 대기시간은 종종 대단히 길 수 있다.
예를 들어 각 프로세스와 수행 시간이 다음과 같다면, P1(24) P2(3) P3(3)
차이가 굉장히 큰 것을 알 수 있다. FCFS 하에서 평균 대기시간은 일반적으로 최소가 아니며, 프로세스 버스트 시간에 따라 평균 대기 시간도 상당히 변할 수 있다.
Convoy effect가 발생한다. 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것이다.(FCFS 알고리즘은 비선점형) ⇒ 짧은 프로세스들이 먼저 처리되도록 허용될 때 보다 CPU와 장치 이용률을 저하시킨다.
5.3.2 Shortest-Job-First Scheduling(SJF)
이 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연관시킨다. CPU가 이용가능해지면, 가장 작은 다음 CPU버스트를 가진 프로세스에 할당시킨다. 만약 동일한 길이를 가지면, 순위를 정하기 위해 FSFC알고리즘을 적용한다.
평균 대기시간은 (3+16+9+0)/4 =7밀리초이다.
비교를 위해, FCFS 스케줄링을 사용했다면, 평균 대기시간은 10.25 밀리초가 되었을꺼다. (직접해보기~><)
⇒ SJF 스케줄링 알고리즘은 주어진 프로세스 집합에 대해 최소의 평균 대기 시간을 가진다는 점에서 최적이다. 짧은 프로세스를 긴 프로세스의 앞으로 이동함으로서, 짧은 프로세스의 대기시간을 긴 프로세스의 대기시간이 증가하는 것보다 더 많이 줄일 수 있다. 결과적으로 평균 대기 시간이 줄어든다.
SJF 알고리즘이 최적이긴 하지만, 다음 CPU 버스트의 길이를 알 방법이 없어 CPU 스케줄링 수준에서 구현할 수 없다.
💡 한가지 접근 방식은 SJF 스케줄링과 근사한 방법을 사용하는 것이다. 다음 CPU 버스트의 길이를 알수는 없으나, 그 값을 예측할 수는 있을 것이다. 우리는 다음 CPU 버스트가 이전의 버스트와 길이가 비슷하다고 기대한다. 그러므로 다음 CPU 버스트 길이의 근삿값을 계산해 , 가장 짧은 CPU 버스트를 가진 프로세스를 선택한다. (아직 잘 모르겠다)
SJF 알고리즘은 선점형이거나 또는 비선점형일 수 있다. 앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 큐에 도착하면 선택이 발생한다. 비선점형 SJF알고리즘은 현재 실행되고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용한다.
선점형 SJF 스케줄의 평균 대기시간은 [(10-1)+(1-1)+(17-2)+(5-3)]/4 = 26/4 = 6.5 밀리초이다.
비선점형 SJF 스케줄링은 평균 대기시간이 7.75밀리초가 된다. (직접 해보깅 ><)
5.3.3 Round-Robin Scheduling (RR)
RR 스케줄링 알고리즘은 FCFS 스케줄링과 유사하지만 선점이 추가된다. 시간할당량(time quantum) 또는 타임슬라이스(time slice)라고 하는 작은 단위의 시간을 정의한다. 준비큐는 원형 큐(circular queue)로 동작한다. CPU 스케줄러는 준비 큐를 돌면서 한번에 한 프로세스에 한번의 시간 할당량동안 CPU를 할당한다.
라운드 로빈 스케줄링을 구현하기 위해, 다시 준비 큐가 선입선출 큐로 동작하게 만든다. 새로운 프로세스들은 준비 큐의 꼬리에 추가된다. CPU 스케줄러는 준비 큐에서 첫번째 프로세스를 선택해 한 번의 시간 할당량 이후에 인터럽트를 걸도록 타이머를 설정한 후, 프로세스를 디스패치한다.
두가지 경우가 있다
- 프로세스의 CPU 버스트가 한번의 시간 할당량 보다 작은 경우
- 자발적으로 CPU 방출, 스케줄러는 그 후 준비 큐에 있는 다음 프로세스로 진행
- 프로세스의 CPU 버스트가 한번의 시간 할당량 보다 큰 경우
- 문맥 교환이 일어나고 실행하던 프로세스는 준비 큐의 꼬리에 넣어진다. 그 후 스케줄러는 준비큐의 다음 프로세스를 선택
종종 RR정책 하에서 평균 대기 시간은 길다.
시간 할당량, time quantum이 4밀리초일때의 간트 차트는 위와 같다. p1,p2,p3는 시간 0에 도착한다.
이 스케줄에 따르는 평균 대기 시간을 계산해보면 p1은 6밀리초 (10-4)를 기다리고, p2는 4밀리초, p3는 7밀리초를 기다린다. 따라서 평균 대기 시간은 17/3 = 5.66밀리초다.
-
라운드로빈 스케줄링 알고리즘에서는, 유일하게 실행가능한 프로세스가 아니라면 연속적으로 두번 이상의 시간 할당량을 할당받는 프로세스는 없다.
-
만약 CPU 버스트가 한번의 시간 할당량을 초과한다면, 프로세스는 선점되고 준비 큐로 돌아간다.
-
RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. 극단적인 경우, 시간 할당량이 매우 크면 RR정책은 선입선처리 정책과 같다.
-
반대로 시간 할당량이 매우 적다면 RR 정책은 매우 많은 문맥 교환을 야기한다
⇒ 시간 할당량이 적을수록 문맥 교환 횟수가 늘어난다.
⇒ 우리는 시간 할당량이 문맥 교환 시간과 비교해 더 클 것을 원한다. 문맥 교환 시간이 시간 할당량의 10%에 근접한다면 CPU 시간의 10%는 문맥교환에 사용된다는 뜻이다. ( 문맥 교환을 하는 데 걸리는 시간은 보통 10 마이크로초 미만으로 적다!)
- 총 처리 시간 또한 시간 할당량의 크기에 좌우된다.
⇒ 그림 5.6에서 보는 바와 같이, 한 프로세스 집합은 평균 총 처리 시간은 시간 할당량의 크기가 증가하더라도 반드시 개선되지는 않는다.
- 시간 할당량이 문맥 교환 시간에 비해 커야하지만 너무 커서는 안된다. 앞서 지적한 것처럼 시간 할당량이 너무 크다면 RR 스케줄링은 선입 선처리 정책으로 퇴보한다. 경험으로 CPU 버스트의 80%는 시간 할당량 보다 짧아야한다.
5.3.4 우선순위 스케줄링 Priority Scheduling
SJF(Shortest Job First) 알고리즘은 일반적인 우선 순위 알고리즘의 특별한 경우이다. 우선순위가 각 프로세스들에 연관되어 있으며, cpu는 가장 높은 우선 순위를 가진 프로세스에게 할당된다. 우선 순위가 같다면 선입선출 순서로 스케줄된다.
- SJF는 우선순위가 예상되는 다음 CPU 버스트의 역인 단순한 우선 순위 알고리즘이다. (?) CPU 버스트가 클수록 우선순위가 낮다. ⇒ ?? 이해 안가
높은 우선순위? 낮은 우선순위?
우선순위는 일반적으로 일정 범위의 수가 사용된다. 그러나 0이 최상위 또는 최하위 순서인가에 대한 일반적인 합의가 없다. 이러한 차이는 혼란을 야기할 수 있다. ⇒ 여기서는 낮은 수가 높은 우선 순위를 나타낸다고 가정한다.
하나의 예
평균 대기 시간은 8.2밀리초이다.
- 우선 순위는 내부적 또는 외부적으로 정의될 수 있다.
- 내부적으로 정의된 우선순위는 어떤 측정 가능한 야들을 이용한다. (EX) 시간 제한, 메모리 요구, 열린 파일의 수, 평균 I/O 버스트의 평균 CPU 버스트에 대한 비율)
- 외부적 우선 순위는 프로세스의 중요성, 컴퓨터의 사용을 위해 지불되는 비용의 유형과 양, 그 작업을 후원하는 부서 그리고 정치적인 요인 등과 같은 기준에 의해 결정된다.
선점형? 비선점형?
우선순위 스케줄링은 선점형이거나 또는 비선점형이 될 수 있다. 프로세스가 준비 큐에 도착하면, 새로 도착한 프로세스의 우선순위를 현재 실행 중인 프로세스의 우선순위와 비교한다.
- 선점형 우선순위 스케줄링 알고리즘: 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선 순위보다 높다면 CPU를 선점한다.
- 비선점형 우선순위 스케줄링 알고리즘: 단순히 준비완료 큐의 머리부분에 새로운 프로세스를 넣는다.
우선순위 스케줄링 알고리즘의 주요문제
- 무한 봉쇄(indefinite blocking) 또는 기아 상태(starvation)
실행 준비는 되어있으나 cpu를 사용하지 못하는 프로세스는 cpu를 기다리면서 봉쇄된 것으로 간주할 수 있다.
우선순위 스케줄링 알고리즘을 사용할 경우 낮은 우선순위 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다.
EX) 부하가 과중한 컴퓨터 시스템에서는 높은 우선순위 프로세스들이 꾸준히 들어와서 낮은 우선 순위의 프로세스들이 CPU를 얻지 못할 수 있다.
⇒ 일반적으로 두가지 경우 중 하나가 발생한다.
- 그 프로세스가 결국 실행되거나(시스템의 부하가 적어진 시점에)
- 컴퓨터 시스템이 결국 크래시하여 아직 끝나지 않은 우선순위가 낮은 프로세스들을 잃어버린다.
낮은 우선 순위의 프로세스들이 무한 봉쇄되는 문제에 대한 한가지 해결 방법은 노화(aging)이다.
노화는 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
다른 옵션은 라운드 로빈과 우선순위 스케줄링을 결합하는 방식이다.
시스템이 우선순위가 가장 높은 프로세스를 실행하고 우선 순위가 같은 프로세스들은 라운드 로빈 스케줄링을 사용하여 스케줄링 하는 방식이다!
우선순위 p4 > p2,p3 > p1,p5
5.3.5 Multilevel Queue Scheduling
우선순위와 라운드 로빈 스케줄링을 사용할 때 모든 프로세스가 단일 큐에 배치되고 스케줄러는 우선순위가 가장 높은 프로세스를 선택하여 실행할 수 있다. 큐가 관리되는 방식에 따라 우선 순위가 가장 높은 프로세스를 결정하기 위해 O(n) 검색이 필요할 수 있다. 실제로 우선순위마다 별도의 큐를 갖는 것이 더 쉬울 때도 있으며 우선 순위 스케줄링은 우선순위가 가장 높은 큐에서 프로세스를 스케줄한다.
다단계 큐라고 하는 이 방법은 우선순위 스케줄링이 라운드로빈과 결합한 경우에도 효과적이다. 우선 순위가 가장 높은 큐에 여러 프로세스가 있는 경우 라운드로빈 순서로 실행된다. 이 방식의 가장 일반적인 형태에서 우선순위가 각 프로세스에 정적으로 할당되며 프로세스는 실행시간 동안 동일한 큐에 남아 있다.
프로세스 유형에 따라 프로세스를 여러개의 개별 큐로 분할하기 위해 다단계 큐 스케줄링 알고리즘을 사용할 수도 있다. 예를들어, 흔히 포그라운드(대화형) 프로세스와 백그라운드(배치) 프로세스를 구분한다. 포그라운드 및 백그라운드 프로세스에 별도의 큐가 사용될 수 있으며 각 큐에는 자체 스케줄링 알고리즘이 있을 수 있다. 예를 들어, 백그라운드 큐 FCFS 알고리즘에 의해 스케줄되는 반면, 포그라운드 큐는 RR 알고리즘에 의해 스케줄 될 수 있다.
5.3.6 다단계 피드백 큐 스케줄링 _ Multilevel Feedback Queue Scheduling
다단계 큐 스케줄링 알고리즘에서는 일반적으로 프로세스들이 시스템 집입시에 영구적으로 하나의 큐에 할당된다. 예를들어 포그라운드와 백그라운드 프로세스를 위해 별도의 큐가 있으면, 프로세스들은 한 큐에서 다른 큐로 이동하지 않는다. ⇒ 이러한 방식은 스케줄링 오버헤드가 장점이 있으나 융통성이 적다.
↔ 다단계 피드백 큐 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다.
아이디어: 프로세스들을 CPU 버스트 성격에 따라서 구분한다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동한다.
일반적으로, 다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의된다.
- 큐의 개수
- 각 큐를 위한 스케줄링 알고리즘
- 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
- 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결정하는 방법
- 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법
이 알고리즘은 설계중인 특정 시스템에 부합하도록 구성가능하다. 하지만 가장 좋은 스케줄러로 동작하기 위해서는 모든 매개변수들의 값을 선정하는 특정 방법이 필요하기 때문에 또한 가장 복잡한 알고리즘이기도 하다.
5.4 스레드 스케줄링
4장에서 프로세스 모델에 스레드를 도입하면서 사용자 수준과 커널 수준 스레드를 구별하였다. 대부분 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다!
사용자 수준 4장에서 프로세스 모델에 스레드를 도입하면서 사용자 수준과 커널 수준 스레드를 구별하였다. 대부분 최신 운영체제에서는 스케줄 되는 대상은 프로세스가 아니라 커널 수준 스레드이다!
사용자 수준 스레드는 라이브러리에 의해 관리되고 커널은 그들의 존재를 알지 못한다. CPU 상에서 실행되기 위해서 LWP를 통한 간접적인 방식이리지라도 사용자 수준 스레드는 궁극적으로 연관된 커널 수준 스레드에 사상되어야한다.
5.4.1 경쟁범위_Contention Scope
스레드: 프로세스-경쟁-범위
커널: 시스템-경쟁-범위
5.5 다중 처리기 스케줄링_Multiple-Processer Scheduling
지금까진 단일 처리기 코어를 가진 CPU를 스케줄하는 문제에 주안점을 두었다. 만일 여러개의 CPU가 사용가능해진다면, 여러 스레드가 병렬로 실행될 수 있으므로 부하 공유(load sharing)가 가능해진다. 그러나 스케줄링 문제는 그에 상응하여 더욱 복잡해진다.
다중처리기: 여러개의 물리적 프로세서를 제공하는 시스템. 각 프로세서에는 하나의 단일 코어 cpu가 포함되어 있다.
5.5.1 다중처리기 스케줄링에 대한 접근 방법
비대칭 다중 처리(asymmetric multiprocessing): 오직 하나의 코어만 시스템 자료 구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다. 하지만 단점은 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 것이다.
대칭 다중 처리(symmetric multiprocessing, SMP): 다중 처리기를 지원하기 위한 표준 접근 방식, 각 프로세서는 스스로 스케줄링 할 수 있다. 각 프로세서의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행된다.
이는 스케줄 대상이 되는 스레드를 관리하기 위한 두 가지 가능한 전략을 제공한다.
- 모든 스레드가 공통 준비 큐에 있을 수 있다.
- 각 프로세서는 자신만의 스레드 큐를 가질 수 있다.
(a)의 경우 공유 주비 큐에 경쟁 조건이 생길 수 있으므로 두개의 다른 프로세서가 동일한 스레드를 스케줄 하지 않도록 그리고 큐에서 스레드가 없어지지 않도록 보장해야한다.
(b)의 경우 각 프로세서가 자신만의 실행 큐를 가지므로 공유 실행 큐와 관련되어 발생할 수 있는 성능 문제를 겪지 않는다. 따라서 smp를 지원하는 시스템에서 가장 일반적인 접근 방식이다. 또한 캐시 메모리를 효율적으로 사용할 수 있다. 쟁점은 큐마다 부하의 양이 ㅏ를 수 있다는 것인데, 균형 알고리즘을 사용하여 프로세스간 부하를 균등하게 만들 수 있다.
5.5.2 다중 코어 프로세서_Multicore Processors
SMP 시스템은 다수의 물리 처리기를 제공함으로써 다수의 프로세스가 병렬적으로 실행되게 한다.그러나 현재 컴퓨터 하드웨어는 동일한 물리적인 칩안에 여러개의처리 코어를 장착하여 다중 코어 프로세서가 된다.
⇒ 각 코어는 구조적인 상태를 유지하고 있어서 운영체제 입장에서는 개별적인 논리적 CPU처럼 보이게 된다.
다중 코어 프로세서는 스케줄링 문제를 복잡하게 한다. 연구자들은 프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비한다는 것을 발견했다. 메모리 스톨(memory stall)이라고 하는 이 상황은 최신 프로세서가 메모리보다 훨씬 빠른 속도로 자동하기 때문에 주로 발생한다. 그러나 캐시 미스(캐스 메모리에없는 데이터를 엑서스)로 인해 메모리 스톨이 발생할 수도 있다.
이러한 상황을 해결하기 위해 최근의 많은 하드웨어 설계는 다중 스레드 처리 코어를 구현하였다.
⇒ 이러한 설계에서 하나의 코어에 2개 이상의 하드웨어 스레드가 할당된다. 이렇게 하면 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환할 수 있다.
운영체제 관점에서 각 하드웨어 스레드는 명령어 포인터 및 레지스터 집합과 같은 구조적 상태를 유지하므로 소프트웨어 스레드를 실행할 수 있는 논리적 cpu로 보인다. ⇒ 칩 다중 스레딩(chip multithreading, CMT)
5.5.3 부하 균등화_Load Balancing
SMP 시스템에서 처리기가 하나 이상이라는 것을 최대한 활용하려면, 부하를 모든 처리기에 균등하게 배분하는 것이 매우 중요하다.
부하 균등화는 SMP 시스템의 모든 처리기 사이에 부하가 고르게 배분되도록 시도한다. (부하 균등화는 통상 각 처리기가 실행할 스레드를 위한 자기 자신만의 준비큐를 가지고 있는 시스템에서만 필요한 기능이다. / 공통의 실행큐만 있는 시스템에서는 한 처리기가 쉬게 되면 곧바로 공통 큐에서 새로운 프로세스를 선택하여 실행하기 때문에 부하 균등화는 필요 없다.)
부하 균등화를 위해서는 push 이주(migration)과 pull이주 방식의 두가지 접근 방법이 있다.
push: 과부하인 처리기에서 덜 바쁜 처리기로 쓰레드를 push
pull: 쉬고 있는 처리기가 바쁜 처리기를 기다리고 있는 프로세스를 pull할 일어난다.
5.5.4 처리기 선호도_Processor Affinity
스레드가 특정 처리기에서 실행 중일 때 캐시 메모리에 어떤 일이 벌어지는가 고려해보자. 스레드에 의해 가장 최근에 접근된 데이터가 그 처리기의 캐시를 채우게 된다.
스레드가 다른 처리기로 이주한다면, 사용하고 있던 프로세서의 캐시 메모리의 내용은 무효화 되어야하며, 이동하는 프로세서의 캐시는 다시 채워져야한다. 캐시 무효화 및 다시 채우는 비용이 많이 들기 때문에 SMP를 지원하는 대부분의 운영체제는 스레드를 한 프로세서에서 다른 프로세서로 이주시키지 않고 대신 같은 프로세서에서 계속 실행시키면서 warm cache를 이용하려고한다. ⇒ 이를 프로세서 선호도라고 한다. ⇒ 즉, 프로세스는 현재 실행 중인 프로세서에 대한 선호도를 보인다.
5.6 실시간 CPU 스케줄링
5.6.1 지연시간 최소화_Minimizing Latency
이벤트 지연시간: 이벤트가 발생해서 그에 맞는 서비스가 수행될 때까지의 시간
다음 두 가지 유형의 지연시간이 실시간 시스템의 성능을 좌우한다.
-
인터럽트 지연시간
인터럽트 지연시간은 CPU 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴을 완료하기까지의 시간을 말한다.
-
디스패치 지연시간
디스패치 지연스간은 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 실행하는 데 까지 걸리는 시간을 의미한다.
5.6.2 우선순위 기반 스케줄링
연성 실시간 스케줄링은 비실시간 작업보다 실시간 작업에 우선순위를 둔다. 경성 실시간 스케줄링은 실시간 작업에 대한 타이밍 보장을 제공한다.
5.6.3 Rate-Monotonic 스케줄링
Rate-monotonic 실시간 스케줄링은 선점과 함께 정적 우선순위 정책을 사용하여 주기적 작업을 스케줄 한다.
5.6.4 Earliest-Deadline-First 스케줄링
EDF 스케줄링은 마감시한에 따라 우선순위를 지정한다. 마감시간이 빠를 수록 우선순위가 높고, 마감시한이 늦을 수록 우선순위가 낮다.
5.6.5 일정 비율의 몫 스케줄링
비례 공유 스케줄은 모든 응용프로그램이 몫 T를 공유한다. 응용 프로그램에 N몫 만큼의 시간이 배정되면 총 프로세서 시간의 N/T가 보장된다.
5.7. 운영체제 사례들
- Linux는 완벽한 공정 스케줄러(CFS)를 사용하여 각 작업에 일정 비율의 CPU 처리 시간을 할당한다. 비율은 각 잡업과 관련된 가상 실행시간(vruntime)값을 기준으로 한다.
- Windows 스케줄링은 선점적인 32-단계 우선순위 기법을 사용하여 스레드 스케줄링 순서를 정한다.
- Solaris는 전역 우선 순위에 매핑된 6개의 고유한 스케줄링 클래스를 식별한다. cpu를 많이 사용하는 스레드에는 일반적으로 낮은 우선 순위및 더 긴 시간 할당량이 할당되고, I/O 중심 스레드에는 일반적으로 높은 우선순위 및 더 짧은 시간 할당량이 할당된다.
5.8. 알고리즘의 평가
- 모델링 및 시뮬레이션을 사용하여 CPU스케줄링 알고리즘을 평가할 수 있다.
