7.0 개요
컨텍스트 교환과 같은 저수준 기술에 대해 명확하게 알아야합니다.
(OSTEP) 6. 제한된 직접 실행 원리(Limited Direct Execution)
6.0 개요 CPU 시간을 나누어 가상화를 실현할 수 있다.
그러나 몇 가지 문제를 해결해야합니다.
성능 저하 시스템에 과도한 오버헤드 없이 가상화를 구현할 수 있습니까?제어 문제
junqueue.
지금 높은 수준 정책에 대한 이해가 필요합니다.
스케줄링 정책소개합니다.
중요한 질문: 스케줄링 정책은 어떻게 개발하는가?
스케줄링 정책을 생각하기 위한 기본 프레임워크를 어떻게 만들 수 있습니까?
어떤 것을 가정해야 합니까? 어떤 기준으로 정책을 평가해야 합니까?
처음에는 어떤 기술이 사용되었습니까?
7.1 워크로드에 대한 가정
프로세스가 작동하는 일련의 행위 워크로드라고 한다.
적절한 워크로드 선택은 스케줄링 정책 개발에 매우 중요합니다.
이 장에서는 비현실적인 워크로드를 가정하여 스케줄링 정책을 개발합니다.
우리가 사용하는 비현실적인 워크로드는 다음과 같습니다.
1. 모든 작업은 같은 시간에 실행됩니다.
2. 모든 일은 동시에 도착한다.
3. 작업은 한 번 시작하면 마지막으로 끝날 때까지 실행됩니다.
4. 모든 작업은 CPU만 사용합니다(즉, 입출력을 사용하지 않음)
5. 각 작업의 실행 시간은 사전에 알려져 있습니다.
매우 이상적인 가정이라고 할 수 있다.
7.2 스케줄링 평가 항목
스케줄링이 성공했는지 여부를 평가하기 위해 스케줄링 평가 항목결정해야합니다.
스케줄링에는 다양한 평가 기준이 있습니다.
반환 시간(turnaround time)
반환 시간 표현식은 다음과 같이 나타낼 수 있습니다.
모든 작업이 동시에 도착한다고 가정했기 때문에 ‘반환 시간 ==완료 시간’이라고 부를 수 있습니다.
성능면의 평가 기준이다.
공정성
반환 시간과 모순되는 평가 기준.
성능을 극대화하려는 일부 작업에 실행 기회를 주지 않으면 공정성이 악화됩니다.
7.3 선입 선출
가장 기본적인 알고리즘으로 선입선출(First In First Out, FIFO) 또는 선도 착선 처리(First Come First Served, FCFS)라고도 합니다.
간단하고 구현하기 쉽습니다.
세 작업의 평균 리턴 시간은 (10+20+30)/3=20입니다.
하지만 여기서 1번 가정을 제거해 보면 다음과 같은 문제가 생겨 버린다.
평균 반환 시간이 (100+110+120)/3=110으로 증가
이 현상 콤보 효과라고 불린다.
7.4 최단 작업 우선
최단 작업 우선(Shortest Job First, SJF)는 실행 시간이 가장 짧은 작업을 먼저 실행합니다.
이렇게하면 convoy 효과의 문제를 쉽게 해결할 수 있습니다.
아까 평균 반환 시간이 110이었던 예를 (10+20+120)/3=50으로 2배 이상 향상한 모습을 볼 수 있다.
모든 작업이 동시에 도착하면 SJF 최적(optimal) 스케줄링 알고리즘입니다.
하지만 2번 가정을 없애면 다음과 같은 문제가 발생한다.
B와 C가 A 바로 뒤에 도착하더라도 A가 끝날 때까지 기다려야합니다.
평균 반환 시간은 ((100+(110-10)+(120-10))/3=103.33입니다.
7.5 최단 잔여 시간 우선
위의 문제를 해결하려면 세 번의 가정을 삭제해야 합니다.
그러면 작업이 실행 중에 중단될 수 있습니다.
SJF는 비 선점형 스케줄러따라서 실행중인 작업을 중지하고 다른 작업을 실행할 수 없었지만, 최단 잔여 시간 우선 (Shortest Time-to-Completion First, STCF)는 선점형 스케줄러그래서 가능.
지금까지의 가정에서의 평균 반환 시간은 ((120 – 0) + (20 – 10) + (30 – 10)) / 3 = 50이므로 STCF가 최적의 스케줄링이 된다.
7.6 새로운 평가 기준: 응답 시간
STCF는 초기 배치 컴퓨터 시간에 매우 효과적인 정책이었습니다.
그러나 시분할 컴퓨터의 등장이 모든 것을 바꿨다.
사용자는 터미널에서 작업하고 상호 작용을 원하는 성능이 필요합니다.
그렇게 나온 것은 응답 시간(response time)라는 평가 기준이다.
위의 예에서 응답 시간을 보면 A = 0, B = 0, C = 10, 평균 3.33입니다.
STCF와 유사한 정책은 응답 시간이 짧지 않습니다.
단지 늦게 스케줄되면 응답을 10초 기다릴 수 있을지도 모른다.
7.7 라운드 로빈
응답 시간 문제를 해결하기 위해 라운드 로빈 (Round-Robin, RR) 또는 타임 슬라이싱라는 알고리즘을 도입한다.
단순히 일정 시간 실행 후 실행 큐의 다음 작업으로 전환하는 것입니다.
작업이 실행되는 일정 시간 타임 슬라이스 또는 스케줄링 양자라고 부른다.
인터럽트가 10msec마다 인터럽트를 발생시키는 경우 타임 슬라이스는 10msec의 배수가 될 수 있습니다.
당연히 타임 슬라이스가 짧을수록 RR의 응답 시간은 빨라진다.
그러나 너무 짧으면 컨텍스트 교환 비용이 커지고 성능이 떨어집니다.
RR은 프로세스어떤 정책이므로 응답 시간은 좋지만 반환 시간은 나쁘다.
STCF는 응답 시간이 좋지 않지만 반환 시간은 좋다.
이 두 가지를 절충하는 것이 중요하다.
7.8 입출력 연산 고려
모든 프로그램은 입출력 조작을 수행하므로 가정 4를 제거합니다.
STCF에서 A를 처리하려고 하면 5개의 10msec 작업으로 나뉩니다.
A를 5개의 10msec 독립 조작으로 간주하면 STCF는 다음과 같이 처리합니다.
CPU를 A와 B가 나누어 시스템 사용률이 향상된 것을 확인할 수 있다.
7.9만병 치약 없음(No More Oracle)
그러나 지금까지는 실행 시간을 알고 있다는 가정하에 행해졌다.
일반적인 운영 체제에서 작업의 길이를 미리 알 수 있는 방법은 없습니다.
이제 사전 지식 없이 SJF/STCF처럼 동작하는 알고리즘과 응답 시간을 개선하기 위한 RR 아이디어를 도입하는 방법을 찾고 싶습니다.
7.10 요약
두 가지 접근법을 보았습니다.
첫 번째는 실행 시간이 가장 짧은 시간을 실행하고 평균 반환 시간을 최소화하는 방법입니다.
두 번째는 모든 작업을 번갈아 실행하고 응답 시간을 최소화하는 방법입니다.
정확한 스케줄링을 위해서는 프로세스의 미래 동작을 예측해야 합니다.
과거의 프로세스 동작 이력을 통해 예측하고 해결하면 됩니다만, 이 스케줄러를 다중 레벨 피드백 대기열(multi-level feedback queue)그리고 다음 장에서 배울 것입니다.