CPU 스케줄링 200812077 장우영

1.CPU스케줄링의 개요 스케줄링 CPU 스케줄링 운영체제의 핵심기능으로 누구한테 먼저 자원을 할당해줄지 결정 다중 프로그래밍을 가능하게 하는 운영체제의 기본으로 CPU들을 대상으로 CPU 자원을 할당해 주는 순서를 정하는 일

2. 스케줄링의 개념 스케쥴되는 프로세스 스케쥴되지 않는 작업 사용자 프로세스 시스템 호출에 의해 발생되는 시스템 프로세스 인터럽트 처리 오류 처리 사용자의 시스템 호출에 있어서의 사전 처리

3.CPU스케줄링의 기본요소 컴퓨터의 모든 동작은 CPU에 의해 시작 실행교대 일괄 처리 시스템은 작업을 수행하는 반면, 시분할 시스템은 사용자 프로그램을 가지고 있음 프로세스란 실행상태에 있는 프로그램을 말함 CPU 버스트 입출력 버스트 실행교대

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

5.프로세스의 상태 프로세스란 실행 상태에 있는 프로그램 프로그램이 실행되면서 프로세스는 상태 변환을 하게 됨 프로세스의 상태는 현재 상태에 의해서 정의됨 프로세스의 실행은 CPU버스트 와 입출력 버스트의 혼합된 연속이며, CPU버스트 로 시작되고 끝남 모든 프로세스는 생성(new), 활동(active), 대기(waiting), 중단(halted) 중의 한 상태에 있게 됨

6.성능의 기준 CPU 사용률 : 전체작업시간 중에서 CPU가 사용된 시간 처리율(throughput) :단위 시간당 완료되는 작업 수 반환시간: 작업이 맡겨진 시간부터 종료될 때 까지의 시간 대기시간(waiting time) : 준비상태 큐에서 대기하는 시간 반응시간: 어떤 요구를 의뢰한 시간으로부터 반응 이 시작될 때 까지의 시간

7.스케줄링 단계 1단계 스케줄링(장기) = 승인스케줄링 2단계 스케줄링(중기) 3단계 스케줄링(단기) 시스템에 들어오는 것에 대한 승인여부 결정 2단계 스케줄링(중기) 프로세스의 CPU 할당 순서 결정 3단계 스케줄링(단기) 프로세스에 CPU 할당 결정

8.스케줄링 목적 시스템의 성능을 높이는데 있음 공정 해야함 단위시간당 처리량 최대화 대화식 사용자에게는 될수록 응답을 빠르게 주어야함 예측이 가능 해야함 오버헤드를 최소화 시켜야함 자원 사용에 있어서 균형을 이루어주어야 함 무한정으로 실행이 연기 되는것을 피해야 함 주요자원을 차지하고 있는 프로세스에게 우선권을 주어야 함 바람직한 행동을 보이는 프로세스들에 서비스를 더 잘 주어야함 성능체증은 서서히 일어나야함 (1) 사용자관점 : 응답시간의 단축 (2) 시스템 관전 : 작업 처리량, 자원 활용도

9.CPU 스케줄링 기법의 분류 단계별 방법별 알고리즘별 장기, 중기, 단기스케줄링 선점, 비선점 우선순위, 기한부,FIFO, RR,SPN,SRT,HRN,MLQ,MFQ

10.방법별 스케줄링 1. 선점스케쥴링 2. 비선점스케쥴링 한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 경우 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용 빠른 응답시간을 요구하는 시분할 시스템에 유용 높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래 2. 비선점스케쥴링 한 프로세스가 CPU를 할당받으면 다른 프로세스는 CPU를 점유 못함 짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때까지 기다려야 함 모든 프로세스들에게 공정하고 응답시간의 예측이 가능

11.알고리즘별 스케줄링 우선순위 스케줄링(비선점) : 우선순위를 할당해 우선순위가 높은 순서대로 처리하는 기법 기한부 스케줄링(비선점) : 프로세스가 주어진 시간 내에 작업이 끝나도록 계획함 FIFO 스케줄링(비선점) : 작업이 컴퓨터에 들어온 순서대로 수행하는 방법 HRN 스케줄링(비선점) : SRT의 큰 작업이 시간이 많이 걸리는 점을 보완한 방법 SJF 스케줄링(비선점) : 수행 시간이 적은 작업을 우선적으로 처리하는 방법 SRT 스케줄링(선점) : 수행 중 나머지 수행 시간이 적은 작업을 우선 처리하는 방법 MLQ 스케줄링(선점) : 서로 다른 작업을 각각의 큐에서 시간 할당에 의해 MFQ 스케줄링(선점) : 하나의 준비 상태 큐를 통해 여러 개의 귀환 큐를 걸쳐 일을 처리하는 것 FSS 스케줄링(선점) : 설 관련된 다양한 프로세스 집합을 지원하는 알고리즘 라운드 로빈 스케줄링(선점) : FIFO 방식의 변형으로 일정한 시간을 부여하 는 방법

12.스케줄링의 종류 FIFO 스케줄링 Round-Robin(RR) 스케줄링 가장 간단한 스케줄링 기법 대화식 사용자들을 스케줄링 하는 데에는 적합하지 않음 nonpreemtive기법 응답시간에 있어서 차이가 적게 나며 따라서 다른 기법들보다는 예측이 수월한 편 평균반환시간 = (작업1+작업2+작업3…작업n)/n FIFO에서의 평균 반환 시간은 일반적으로 최소치가 아니고 상당히 큰 폭으로 변할 수 있다. Round-Robin(RR) 스케줄링 프로세스들이 FIFO식으로 디스패치 되지만 타임슬라이스 또는 시간 할당량이라 불리는 중앙처리장치에서의 시간 량에 제한을 받음 시스템이 대화식 사용자들에게 적절한 응답시간을 보장해 주어야 하는 시분할 시스템에 효과적 preemption 오버헤드는 효과적인 문맥교환 기법을 쓰고 프로세스들이 동시에 주기억장치에 유지될 수 있도록 적당한 기억장치 용량을 제공하면 어느 정도 낮게 유지될 수 있음

13.스케줄링의 종류 SJF(Shortest-Job-First) 스케줄링 작업이 끝나기까지의 실행시간의 추정치가 가장 작은 작업을 먼저 실행시키는 nonpreemptive 스케줄링 기법 FIFO 기법보다 평균 대기시간이 작지만 대기시간의 분산은, 특히 긴 작업의 경우, FIFO 기법보다 더 크며 따라서 더욱 예측이 불가능함 긴 작업들을 어느 정도 희생시키면서 짧은 작업들에 우선적으로 서비스를 해줌 작업들이 시스템을 통과할 때 평균대기시간을 최소화시킬 수 있음 적절한 응답시간이 보장되어야 하는 시분할 시스템의 경우에는 적당하지 못함 SRT(Shortest-Remaining-Time) 스케줄링 SJF기법의 preemption 변형 시분할 시스템에 유용함 남아있는 실행시간의 추정치가 가장 작은 프로세스를 먼저 실행시킴 각 프로세스가 서비스를 받은 시간이 기록되어야 하며 이 때문에 오버헤드가 늘어남

13.스케줄링의 종류 HRN(Highest Response-ratio Next) 스케줄링 Brinch Hansen은 sjf기법의 약점, 특히 긴 작업과 짤은 작업간의 지나친 불평등을 어느정도 보완하는 기법개발 nonpreemptive 스케줄링 기법 우선순위= 대기한 시간+서비스를 받을 시간/서비스를 받을 시간 다단계 피드백 큐(Multi-level Feedback Queue) 프로세스가 낮은 단계로 내려 강수록 프로세스의 시간할당량이 커짐 프로세스가 큐잉 네트워크 내에 오래 머물러 있을수록 중앙처리장치를 차지할 때마다 더 큰 할당량을 얻게 됨 높은 단계큐의 우선순위가 낮은 단계 큐들보다 높기 때문에 낮은 단계로 내려 갈수록 중앙처리장치를 차지하는 빈도는 적어짐 어떤임의의 큐에 있는 프로세스는 그보다 높은 단계 큐들이 비어야만 실행할 수가 있으며 또 이미 실행중인 프로세스도 그보다 높은 단계 큐에 있는 프로세스들에 의하여 preemption됨 프로세스들을 중앙처리장치에 대한 요구량에 따라 분류하는 데 이상적 시스템이 경직되지 않고 유동적인 상태변화에 적응하도록 하는 적응기법을 사용토록 한 좋은 한 예

14.평가 기준 스케줄링 알고리즘은 다음과 같은 기준을 통해 평가할 수 있다. CPU 사용률 : 전체 시스템 시간 중 CPU가 작업을 처리 하는 시간의 비율. 처리량 : CPU가 단위 시간당 처리하는 프로세스의 개 수. 응답 시간 : 대화식 시스템에서 요청 후 응답이 오기 시 작할 때까지의 시간. 대기 시간 : 프로세스가 준비 큐 내에서 대기하는 시간 의 총합. 턴어라운드 시간 : 프로세스가 시작해서 끝날 때까지 걸리는 시간.