4장 CPU 스케줄링 200512071 2B 정은태

개요 Cpu스케줄링은 다중 프로그래밍을 가능하게 하 는 운영체제의 기본이 된다. 또한 프로세스들 간의 cpu 배정을 원활히 함으로써 운영체제는 시스템의 출력을 더욱 개선할 수 있다. 모든 컴퓨터 자원은 사용되기 전에 스케줄 되어 야 하므로 스케줄링은 운영체제 기능의 기초가 된다. Cpu는 컴퓨터에서 주요 자원의 하나이므로 cpu 스케줄링은 운영 체제 설계의 중심이다.

1. 기본 요소 Cpu가 주로 수행하는 것은 사용자의 작업과 프 로그램이지만 그 외 다른 시스템 활동도 수행해 야 한다. 즉 , 컴퓨터의 모든 동작은 cpu에 의해 시작된다. Cpu는 오류, 프로그램의 요구 사항, 입출력 인터 럽트 등에 대해서 대응 조치를 취해야 한다.

(1) Cpu 입출력 버스트 주기 프로세스 실행은 cpu실행과 입출력 대기 상태의 순환인데, 프로세스는 이 두 상태를 오가며 실 행된다. 프로세스 실행은 cpu 버스트로부터 시작되며 입 출력 버스트가 뒤따르고, 그 후 또 다른 cpu 버 스트가 뒤따르는 과정을 반복한다.

Cpu 버스트 타임의 히스토그램 입출력 중심의 작업 --- CPU 버스트 시간은 아주 짧고, 회수는 많음

(2) 프로세스의 상태 프로세스란? 실행 상태에 있는 프로그램을 말하는데 프로그램 이 실행되면서 프로세스는 상태 변환을 하게 된다. 프로세스의 상태는 현재 상태에 의해서 정의 된다. 모든 프로세스는 생성, 활동,대기,중단 중의 한 상 태에 있게 된다. 또한 더욱 세분화 될 수 있다(그림 참조)

(2) 프로세스의 상태 생성 new 활동 active 정지 halted 대기 waiting 생성 new 준비 ready 정지 ① 프로세스 상태 천이도 ② 자세한 프로세스 상태 천이도 생성 new 활동 active 정지 halted 대기 waiting 생성 new 준비 ready 정지 halted 대기 waiting 실행 running

(3) 프로세스 제어 블록 포인터 프로세스 상태 프로세스 번호 프로그램 계수기 레지스터들 기억장치관리정보 사용가능 범위 … ① 프로세스 상태 : new, ready, running, idle, halted 등 ② 프로그램 계수기 : 다음 실행할 명령어의 주소 ③ CPU 레지스터 : 문맥전환 시 저장 필요 (그림 4.9) ④ 주기억 장소 관리 정보 : 기준 레지스터, 한계 레지스터, 페이지 표 등 ⑤ 계정 정보 : CPU사용시간, 실제사용시간, 한정된 시간, 프로세스 번호 등 ⑥ 입출력 상태 정보 : 입출력 상치 할당 정보, 개방된 파일 목록 등 ⑦ CPU 스케쥴링 정보 : 프로세스 우선 순위, 스케쥴링 큐에 대한 포인터 등 포인터 프로세스 상태 프로세스 번호 프로그램 계수기 레지스터들 기억장치관리정보 사용가능 범위 … PCB 운영체제 기억장소 내에서 관리

2. 성능의 기준 ① CPU 사용률 : 전체작업시간 중에서 CPU가 사용된 시간 ② 처리율(throughput) : 단위 시간당 완료되는 작업 수 ③ 반환시간(turnaround time): 작업이 맡겨진 시간부터 종료될때까지의 시간 ④ 대기시간(waiting time) : 준비상태 큐에서 대기하는 시간 ⑤ 반응시간(response time): 어떤 요구를 의뢰한 시간으로부터 반응이 시작될 때 까지의 시간 ▶ 성능을 높이려면  ①과 ②는 최대화하고, ③④⑤는 최소화 : 이상적인 시스템 ▶ 실제 시스템에서는 시스템의 특성에 맞도록 성능기준을 trade-off 예) 대화형 시스템  평균반응시간을 최소화하는 것보다는 반응시간의 편차를 감소

3. 스케줄링 큐 준비 상태 큐와 다양한 입출력 장치 큐

4. 스케줄러 (1) 장기 스케쥴러(long-term scheduler) = 작업 스케쥴러 : 어떤 작업이 시스템에 들어와서 처리될 것인지를 결정 (job pool) (2) 단기 스케쥴러(short-term scheduler) = CPU 스케쥴러 : 주기억 장치 내에 있는 작업들 중에서 실행할 작업을 선택하여 CPU 배당 (준비 상태 큐) process

(3) 두 스케쥴러의 근본적 차이 : 실행 빈도 ① 장기 스케쥴러 : 분 단위 (∵ 한 작업이 종료될 때마다 실행)  스케쥴링 시간이 조금 길어도 무관 . 다중 프로그래밍의 정도(즉, process의 수)를 결정 . 시분할 시스템에는 없음 ② 단기 스케쥴러 : 최소한 100만분의 10초 단위  스케쥴링 시간이 아주 빨라야 함 예) 스케쥴링 시간이 100만분의 1초라면  1 / (10+1) = 거의 9% 전체 CPU 시간 = 실행 + 프로세스 전환 (4) 장기 스케쥴러의 작업 선택 : 입출력 중심 작업과 CPU 중심 작업을 잘 혼합하여 선택해야 함 예) 입출력 중심 작업 >> CPU 중심 작업  준비상태큐 거의 비게 됨 입출력 중심 작업 << CPU 중심 작업  입출력대기큐 거의 비게 됨 (5) 중간 단계 스케쥴러 (midium-term scheduler) ① 가상 기억 체제나 시분할 기법을 사용하는 시스템에서 사용됨

스케줄링 단계 및 목적 1.단계 1단계 : 작업스케줄링이라고 불리며 어느 작업부터 시스템내의 자원들을 실제로 사용할 수 있도록 할 것인지를 결정한다. 이것은 작업들이 시스템에 들 어오는 것을 승인하는 것이기 때문에 때로는 승인 스케줄링이라고도 불린다. 2단계 : 어느 프로세스부터 cpu를 차지할 수 있도록 할지를 결정한다. 2단계 스케줄링은 프로세스들을 일시 보류시키고 또 다시 활성화시키는 기법을 사 용하여 시스템에 대한 단기적 부하를 조절한다.(적 절한 운영과 이상적인 성능 유지) 3단계 : cpu가 이용 가능할 때 어느 프로세스에게 배당될지를 결정한다. 이것은 디스패처에 의하여 이루어지며 따라서 이 디스패처는 항상 주기억 장 치 내에 적재되어 있어야 한다.

2. 목적 공정해야 한다 단위시간당 처리량을 최대화해야 한다. 대화식 사용자에게는 도리수록 응답을 빠르게 주어야 한다. 예측이 가능해야 한다. 오버헤드를 최소화 시켜야 한다. 자원의 사용에 있어서 균형을 이루어 주어야 한다. 응답시간과 자원의 활용간에 균형을 유지해야 한다. 무한정으로 실행이 연기되는 것을 피해야 한다. 우선 순위 제도를 실행하는 것이 좋다. 주요 자원을 차지하고 있는 프로세스에게 우선권을 주어야 한다. 바람직한 행동을 보이는 프로세스들에 서비스를 더 잘 주어야 한다. 시스템에 부하가 많이 걸린 경우에도 성능체증은 서서히 일어나야 한다. 입출력 위주의 프로세스인가? 연산위주의 프로세스인가? 프로세스 배치형인가 또는 대화형인가? 신속한 응답이 얼마나 긴급한가? 프로세스의 우선순위 프로세스가 얼마나 자주 페이지 부재를 발생시키는가? 각 프로세스들이 얼마나 자주 보다 높은 우선순위의 프로세스에 의하여 자 원을 빼앗겼는가? 프로세스가 얼마나 많은 실제의 실행시간을 얻었는가? 프로세스가 끝나려면 얼마나 더 많은 시간이 필요한가?

선점형 스케줄링과 비선점형 스케줄링 종류 방법 특징 비고 우선순위 스케줄링 우선순위를 할당해 우선순위가 높은 순서대로 처리하는 기법 1.고정적 우선순위 2.가변적 우선순위 3.구입된 우선순위 비선점 기한부 프로세스가 주어진 시간 내에 작업이 끝나도록 계획한다 마감 시간을 계산해야 하기 때문에 막대한 오버헤드와 복잡성이 발생 FIFO 작업이 컴퓨터에 들어온 순서대로 수행하는 방법 1.대화형에 부적합 2. 간단하고 공평하다 3. 반응속도를 예측 가능 라운드 로빈 FIFO 방식의 변형으로 일정 한 시간을 부여하는 방법 1. 시분할 방식에 효과적 2. 할당시간이 크면 FIFO와 같다 3. 할당 시간이 작으면 문맥 교환이 자주 발생 선점 SJF 수행 시간이 적은 작업을 우선적으로 처리하는 방법 작은 작업에 유리하고 큰 작업은 상당한 시간이 걸린다. SRT 수행 중 나머지 수행 시간이 적은 작업을 우선 처리하는 방법 작업처리는 SJF와 같으나 이론적으로 가장 작은 대기 시간이 걸린다. HRN SRT의 큰 작업이 시간이 많이 걸리는 점을 보완한 방법 우선순위=(대기시간+수행시간)/수행시간 MLQ 서로 다른 작업을 각각의 큐에서 시간 할당에 의해 처리 하는 방법 각각의 큐는 독자적인 스케줄링 알고리즘 사용 MFQ 하나의 준비 상태 큐를 통해 여러 개의 귀환 큐를 걸쳐 일을 처리하는 것 CPU와 I/O 장치의 효율을 높일 수 있다 FSS 서로 관련된 다양한 프로세스집합을 지원하는 알고리즘 UNIX 환경에 적합

스케줄링의 종류 작업 1 작업 2 작업 3 24 27 30 1.FIFO ① 할당방법 : CPU를 요구하는 순서대로 할당 ③ 특징 : 가장 간단하지만 성능은 좋지 않음 예) 작업 시행시간 1 24 2 3 3 3 I. 작업 순서가 1, 2, 3 순서라면 간트 도표 평균작업반환시간 = (24 + 27 + 30) / 3 = 27 작업 1 작업 2 작업 3 24 27 30

∴ I, II를 비교해 볼 때 성능의 폭이 상당히 크다. 예) 작업 시행시간 1 24 2 3 3 3 II. 작업 순서가 2, 3, 1 순서라면 간트 도표 평균작업반환시간 = (3 + 6 + 30) / 3 = 13 ∴ I, II를 비교해 볼 때 성능의 폭이 상당히 크다. 작업 1 작업 2 작업 3 3 6 30

2. Round-Robin ① 할당방법 : 시분할 시스템을 위해 고안된 것으로 각 작업에 동일한 시간량(시간 조각) 만큼씩 순환하며 CPU를 할당 예) 작업 시행시간 1 24 2 3 3 3 규정시간량 4 평균작업반환시간 = (7 + 10 + 30) / 3 = 16 ② 라운드로빈의 성능 I. 시간량의 크기에 영향 II. 상황(문맥) 교환(Context Switching) 오버헤드  작업 교환 시 현재 수행중인 프로세스의 상황(register, memory)을 보관해야 하는 오버헤드 ∴ I을 적절히 선택해서 성능을 높여야 함 작업 1 4 작업 2 7 작업 3 10 14 18 22 26 30

3.SJF ① 할당방법 : CPU 버스트 시간(CPU 사용기간)이 가장 적은 작업을 먼저 할당 예) 작업 시행시간 1 6 예) 작업 시행시간 1 6 2 3 3 8 4 7 간트 도표 평균작업반환시간 = (3 + 9 + 16 + 24) / 4 = 13 ② SJF의 어려운 점 : CPU 버스트 시간을 예측해야 함 ③ 특징 : 최적이지만, 구현이 어려움 (② 때문에) 작업 2 작업 1 작업 4 3 9 16 작업 3 24

규정시간량 8인 queue 규정시간량 16인 queue FCFS 6.다단계 피드백 큐 4.SRT스케줄링 : 실행시간 추정치(남은 시간)가 가장 적은 프로세스에게 먼저 CPU를 할당하는 방 법. 5.HRN스케줄링 : 우선 순위에 의한 방법. 6.다단계 피드백 큐 ① 구성 : 다단계 큐로 작성되며, 작업이 큐 사이를 이동할 수 있음 ② 예) ③ 알고리즘 정의 요소 . 큐의 개수 . 각 큐에 대한 스케쥴링 알고리즘 . 작업을 보다 높은 우선 순위의 큐로 격상시키는 시기를 결정하는 방법 . 작업을 보다 낮은 우선 순위의 큐로 격하시키는 시기를 결정하는 방법 . 작업들이 들어갈 큐를 결정하는 방법 규정시간량 8인 queue 규정시간량 16인 queue FCFS