CPU 스케줄링  200812065 이성연

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

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

CPU 입출력 버스트 주기(CPU I/O burst cycle)

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

프로세스 제어 블록(process control block) 프로세스 상태 : 생성(new), 준비(ready), 실행(running), 유휴(idle), 중단(halted) 프로그램 계수기(program counter) : 프로세스를 수행하기 위한 다음 명령의 주소를 표시 CPU 레지스터 : 누산기, 색인 레지스터, 범용 레지스터, 조검코드 등에 관한 정보를 말함 컴퓨터 구조에 따라 수나 형태가 변화함 인터럽트가 발생하면 PC와 함께 저장되어 뒤에 다시 수행이 될 때 원상 복구할 수 있도록 함 주기억 장소 관리 정보 : 기준 레지스터, 한계 레지스터, 페이지 표를 포함 계정 정보(accounting information) : CPU 사용 시간, 실제 사용 시간, 한정된 시간, 계정 번호, 작업이나 프로세스 번호 등을 포함 입출력 상태 정보(I/O status information) : 특별한 입출력 요구 프로세스에 할당된 입출력 장치, 개방된 화일의 목록 등을 가지고 있음 CPU 스케줄링 정보 : PCB는 프로세스마다 다른 여러 정보에 관한 저장소의 역할만 함

성능의 기준 CPU 사용률 : 실제 시스템에서 이값은 40%, 90% 정도 처리율 : 단위 시간당 완료되는 작업 수 반환시간 : 작업이 시스템에 맡겨져서 주기억장치에 들어 가기까지의 시간 대기시간 : 단지 준비 상태 큐에서 기다리는 시간에만 영향을 미침 반응시간 : 대화형 시스템에서 중요한 인자

스케줄러 장기 스케줄러 단기 스케줄러 두 스케줄러의 차이 : 실행 빈도 어떤 작업이 시스템에 들어 와서 처리 될 것인가를 결정 실행될 작업을 꺼내서 주기억 장치에 적재함 단기 스케줄러 주기억 장치 내의 준비 상태에 있는 작업들 중에서 실행할 작업을 선택하고 CPU를 배당하는 일을 함 실행해야 될 프로세스를 수시로 선택 두 스케줄러의 차이 : 실행 빈도

스케줄링 단계 1단계 스케줄링 : 작업스케줄링 어느 작업부터 시스템내의 자원들을 실제로 사용할 수 있도록 할 것인지를 결정 2단계 스케줄링 : 어느 프로세스부터 중앙처리장치를 차지할 수 있도록 할지를 결정 3단계 스케줄링 : 1초에도 여러 번 작동하는 디스패처에 의해 이루어짐 항상 주기억 장치 내에 적재되어 있어야 함

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

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

방법별 스케줄링 선점 운영체제가 프로세서 등의 자원을 할당 받고 있는 프로세스로부터 그 자원을 선점하여 다른 프로세스에 할당 할 수 있도록 허용하는 정책 우선순위가 높은 프로세서들의 빠른처리 요구하는 시스템 바른 응답시간이 요구되는 시분할 시스템 비선점 한 프로세스가 프로세서 등의 자원을 할당 받았을 때 그 자원을 스스솔 반납할때까지 계속 그 자원을 사용하도록 허용하는 정책 모든 프로세서들에 대한 요구가 공정히 처리 CPU 할당시간이 짧은 작업이 CPU할당시간이 많이 필요로 하는 작업의 수행을 기다림

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

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

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

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

감사합니다 