4장 CPU 스케줄링 B200512046 양희수

4.1 개 요 4.1 개요 모든 컴퓨터 자원은 사용되기 전에 스케줄 되어야 하므로 스케줄링은 운영체제기능의 기초가 된다. CPU는 컴퓨터에서 주요 자원의 하나이므로 CPU 스케줄링은 운영체제 설계의 중심이다. 4.1.1 기본요소 CPU가 주로 수행하는 것은 사용자의 작업과 프로그램이지만 그 외 다른 시스템 활동도 수행해야 한다. CPU는 오류, 프로그램의 요구 사항, 입출력 인터럽트 등에 대해서 대응 조치를 취해야 한다. 인터럽트는 시분할 단말기 키보드에서의 개별적 특성일 수도 있고, 채널 프로그램의 결과일 수도 있다. 일괄처리 시스템은 “작업(jobs)”을 수행하는 반면, 시분할 시스템은 “사용자 프로그램”을 가지고 있다

4.1 개 요 기본요소 단일 사용자 시스템에서도 대화형 작업과 여러 개의 일괄처리 프로그램들을 수행하는 식으로 하여 여러 프로그램을 동시에 수행할 수 있다. 사용자는 어느 순간 한 프로그램 밖에 수행할 수 없지만, 운영체제는 자신의 내부 활동(예: 스풀링(spooling))들을 지원할 필요가 있다. 프로세스 실행 상태에 있는 프로그램을 말하며 일괄처리 작업(batch job)이 그 전형적인 예이다. 시분할 시스템에 있는 사용자 프로그램도 프로세스이며 스풀링과 같은 시스템도 프로세스이다.

4.1 개 요 CPU 입출력 버스트 주기(CPU I/O burst cycle) 시프로세스 실행은 CPU버스트(burst)로부터 시작되며 입출력 버스트가 뒤따르고, 그 후 또 다른 CPU 버스트가 뒤따르는 과정을 반복한다. LOAD STORE ADD READ from file I/O의 대기 INCREMENT INDEX WRITE to file CPU 버스트 I/O 버스트 실행은 CPU와 입출력 버스트의 교대순 CPU 버스트 I/O 버스트 CPU 버스트 I/O 버스트

4.1 개 요 프로세스의 상태 프로세스란 실행 상태에 있는 프로그램을 말하는데 프로그램이 실행되면서 프로세스는 상태 변환을 하게 된다. 프로세스의 상태는 현재 상테에 의해서 정의되는데 프로세스의 실행은 CPU 버스트와 입출력 버스트의 혼합된 연속이며, CPU 버스트로 시작되고 끝난다. 160 140 120 빈 도 CPU 버스트(burst) 타임의 히스토그램 40 20 8 16 24 32 40 버스트(burst) 지속시간

4.1 개 요 프로세스의 상태 생성 활동 정지 대기 생성 준비 실행 정지 대기 모든 프로세스는 생성(new), 활동(active), 대기(waiting), 중단(halted) 중의 한 상태에 있게 된다. 생성 활동 정지 프로세스 상태 전이도 대기 전자를 준비(ready)라 하고, 후자를 실행(running)이라 한다. 생성 준비 실행 정지 자세한 프로세스 상태 전이도 대기

4.1 개 요 프로세스 제어 블록(process control block) 포인터 프로세스 상태 프로세스 번호 프로그램 계수기 각 프로세스는 프로세스 제어 블록(타스크 제어블록, 작업 제어 블록이라 부르기도 함)에 의해 운영 체제 내에 표현된다. 포인터 프로세스 상태 프로세스 번호 프로그램 계수기 레지스터들 기억장치 사용 가능 범위 : 프로세스 제어 블록

4.1 개 요 프로세스 제어 블록(process control block) 프로세스 상태 생성(new), 준비(ready), 실행(running), 유휴(idle), 중단(halted) 등의 상태를 표시 프로그램 계수기(Program counter) 프로세스를 수행하기 위한 다음 명령의 주소를 표시 CPU 레지스터 누산기(accumulator), 색인 레지스터(index register), 범용 레지스터(general purpose register), 조건코드(condition code) 등에 관한 정보를 말하며 컴퓨터 구조에 따라 수나 형태(type)가 변화한다. 인터럽트가 발생하면 PC와 함께 저장되어 뒤에 다시 수행이 될 때 원상 복구 할 수 있도록 한다. 주기억 장소 관리 정보 기준 레지스터(base register), 한계 레지스터(bound register), 페이지 표(page table)를 포함한다. 계정 정보(accounting information) CPU 사용 시간, 실제 사용 시간, 한정된 시간, 계정 번호, 작업이나 프로세스 번호 등을 포함한다.

4.1 개 요 프로세스 제어 블록(process control block) 입출력 상태 정보(I/O status information) 특별한 입출력 요구 프로세스에 할당된 입출력 장치, 개방된(opened) 파일의 목록 등을 가지고 있다. CPU 스케줄링 정보 프로세스의 우선 순위, 스케줄링 큐에 대한 포인터, 그외 다른 스케줄 매개 변수를 가지고 있다. PCB는 프로세스마다 다른 여러 정보에 관한 저장소의 역할만 한다. PCB는 모니터 기억 장소에 있어야 하며 여러 방법으로 관리되는데, 가장 쉬운 방법은 최대 프로세스의 수를 미리 선언하고 모든 PCB에 충분한 공간을 미리 할당하는 것이다.

4.1 개 요 레지스터 상태 저장 레지스터 상태 원상 복구 레지스터 상태 저장 레지스터 상태 원상 복구 사용자 프로그램 A 운영체제 사용자 프로그램 B 실행 레지스터 상태 저장 유휴 : 레지스터 상태 원상 복구 유휴 실행 레지스터 상태 저장 : 레지스터 상태 원상 복구 유휴 실행 사용자 간에 전환되는 CPU사용

4.1 개 요 4.1.2 성능의 기준(Performance Criteria) Cpu 사용률 처리율(throughput) : 단위 시간당 완료되는 작업수 변환 시간(turnaround time) 작업이 시스템에 맡겨져서 주기억장치에 들어가기까지의 시간, 준비 상태 큐에 있는시간, 실행시간, 입출력 하는 시간 등 모든 일을 마치고 시스템에서 빠져나올때까지의 소요시간. 대기 시간(waiting time) CPU 스케줄링 알고리즘은 작업의 실행 시간이나 입출력 시간에 대해서는 실질적인 영향을 못미치고 단지 준비 상태 큐에서 기다리는 시간에만 영향을 미친다. 반응 시간(response time) 대화형 시스템에서 중요한 인자이다. 어떤 요구를 의뢰한 시간으로부터 반응이 시작되는 시간(완료되는 시간이 아닌)까지의 간격을 말한다.

4.1 개 요 4.1.3 스케줄링 큐(Scheduling Queues) Head Tail Head Tail Head Tail Queue Header PCB #7 PCB #2 Head Tail 준비 상태 큐 레지스터들 레지스터들 자기 테이프 유니트 0 Head Tail PCB #3 PCB #4 PCB #6 자기 테이프 유니트 1 Head Tail Head Tail 디스크 유니트 0 PCB #5 Head Tail 터미널 유니트 0 준비상태 큐와 다양한 입출력 장치 큐

4.1 개 요 4.1.4 스케줄러(Scheduler) 장기 스케줄러(작업 스케줄러) 단기 스케줄러(CPU 스케줄러) 어떤 작업이 시스템에 들어 와서 처리될 것인가를 결정함. 일괄처리 시스템에서는 대개 즉시 처리 될 수 있는 양보다 많은양이 들어옴. 단기 스케줄러(CPU 스케줄러) 주기억 장치 내의 준비 상태에 있는 작업들 중에서 실행할 작업을 선택하고 CPU를 배당하는 일을 한다. 두 스케줄러간의 가장 근본적인 차이 : 실행빈도 단기 스케줄러 : 실행해야 될 프로세스 수시 선택 CPU에서 실행시간은 100만분의 수초 정도이므로 최소한 100만분의 10초 단위로 단기 스케줄러가 실행됨. 단기 스케줄러가 프로세스를 선택하는데 100만분의 1초가 걸린다면 1/(10+1)은 약 9%정도의 CPU가 스케줄링이 소비되므로 단기스케줄러가 빨라야함. 장기 스케줄러 : 드물게 수행됨, 시스템에 새로운작업이 들어오는것은 분단위 다중 프로그래밍의 정도(주기억 장치에 있는 프로세스 수)를 결정, 일정하다면 시스템에 들어오는 작업의 도착률과 작업을 끝내고 시스템을 빠져나가는 정도는 같게 됨.

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

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

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

4.4 스케줄링의 종류 4.4.1 FIFO 스케줄링 중앙처리 장치 C B A 프로세스들은 대기큐(Queue)에서 그들의 도착시간에 따라 디스패치 된다. 외관상으로는 공정, 긴 작업이 짧은작업을 오래 기다릴수있고 중요하지 않은 작업이 중요한 작업을 기다리게 하므로 어느정도는 불합리함. 예) 다음 3개의 작업 평균 반환 시간 작업 시행시간 1 24 2 3 3 3 준비완료리스트(ready list) 중앙처리 장치 완성 C B A FIFO 스케줄링 작업 1 작업 2 작업 3 24 27 30 평균 반환시간 = ( 24 + 27 + 30 ) / 3 = 27 간트 도표(Gantt chart)

4.4 스케줄링의 종류 4.4.1 FIFO 스케줄링 4.4.2 Round-Robin (RR) 스케줄링 예) 다음 3개의 작업 평균 반환 시간(작업순서 2,3,1) 작업 시행시간 1 24 2 3 3 3 작업 2 작업 3 작업 1 3 6 30 평균 반환시간 = ( 3 + 6 + 30 ) / 3 = 13 작업 순서에 따라 평균 반환시간의 차이를 알수있다. 여러 프로세스들이 하나의 큰 프로세스가 CPU 사용을 끝내기를 기다리고 있는 것을 호위 효과(convoy effect)라 부른다. 4.4.2 Round-Robin (RR) 스케줄링 시스템이 대화식 사용자들에게 적절한 응답시간을 보장해 주어야 하는 시분할 시스템에 효과적

4.4 스케줄링의 종류 4.4.2 Round-Robin (RR) 스케줄링 시간 량이 지나면 인터럽트 발생되도록 해놓고 프로세스에 CPU를 할당함. RR 사용 예) 규정 시간량 : 4 작업 시행시간 1 24 2 3 3 3 작업 1 작업 2 작업 3 작업 1 작업 1 작업 1 작업 1 작업 1 4 7 10 14 18 22 26 30 평균 반환시간 = ( 7 + 10 + 30 ) / 3 = 16 시간 규정량이 적을수록 문맥 교환 회수는 많아짐 4.4.3 SJF(Shortest-Job-First) 스케줄링 작업이 끝나기까지의 실행시간의 추정치가 가장 작은 작업을 먼저 실행 SJF 사용 예) 작업 시행시간 1 24 2 3 3 3 작업 2 작업 1 작업 4 작업 3 3 9 16 24 평균 반환시간 = ( 3 + 9 + 16 + 24 ) / 3 = 13

4.4 스케줄링의 종류 4.4.4 SRT (Shortest-Remaining-Time) 스케줄링 남아있는 실행시간의 추정치가 가장작은 프로세스를 먼저 실행 4.4.5 HRN(Highest Response-ratio Next) 스케줄링 가변적 우선순위에 의한 방법 4.4.6 다단계 피드백 큐(Multi-level Feedback Queue) 스케줄링 스케줄링 기법 짧은 작업에 우선권을 주어야 함. 입출력 장치를 효과적으로 활용하기 위해서 입출력위주의 작업들에게 우선권을 주어야 함 가능한 한 빨리 작업의 성격을 파악하여 그 성격에 맞게 스케줄링을 해야 한다. 다단계 피드백 큐 예) 큐(queue)의 수, 각 큐에 대한 스케줄링 알고리즘 작업을 보다 높은 우선순위의 큐로 격상시키는 시기를 결정하는 방법 작업을 보다 낮은 우선순위의 큐로 격하시키는 프로세스들이 어느 큐에 들어갈 것인가를 결정하는 방법 알 고 리 즘 규정시간량 = 16 FCFS 규정시간량 = 8