학습목표 ü 01_ 소개 ü 02_ 스케줄링수준 ü 03_ 선점형 / 비선점형스케줄링 ü 04_ 우선순위 ü 05_ 스케줄링목적 ü 06_ 스케줄링기준 ü 07_ 스케줄링알고리즘 ü 08_ 데드라인스케줄링 ü 09_ 실시간스케줄링 ü 10_ 자바스레드스케줄링 2/23

Ch08_ 프로세서스케줄링 운영체제론

학습목표 ü 01_ 소개 ü 02_ 스케줄링수준 ü 03_ 선점형 / 비선점형스케줄링 ü 04_ 우선순위 ü 05_ 스케줄링목적 ü 06_ 스케줄링기준 ü 07_ 스케줄링알고리즘 ü 08_ 데드라인스케줄링 ü 09_ 실시간스케줄링 ü 10_ 자바스레드스케줄링 2/23

01_ 소개 o 프로세서스케줄링정책 주어진시간에시스템이실행할프로세스를선택하는작업 여러성능요건의충족이필요 처리량최대화 지연시간최소화 무기한연기방지 명시된데드라인전에작업완료 프로세서활용도극대화 3/23

02_ 스케줄링수준 o 고수준스케줄링 시스템이어떤작업에자원을얻으려고경쟁하게해줄지결정 임의의시간에시스템에존재하는프로세스의총수를지정 o 중간수준스케줄링 어떤프로세스가프로세서를얻으려고경쟁할수있는지결정 단기적인시스템부하의높낮이에따라결정 o 저수준스케줄링 활성화된프로세스중어떤프로세스에프로세서를할당할지결정 우선순위부여 4/23

02_ 스케줄링수준 5/23

03_ 선점형 / 비선점형스케줄링 o 선점형스케줄링 프로세서에서프로세스가실행중일때시스템이프로세서의쟁취가가능 우선순위가높은프로세스에대한응답시간향상 대화식시분할시스템에서반응시간보장 여러프로세스를메인메모리에유지하는것이필요 o 비선점형스케줄링 프로세스가프로세서를할당받으면작업을완료하거나자발적으로프로세서를반납할때까지프로세서에서실행가능 중요한프로세스라도앞의프로세스가완료될때까지대기 6/23

04_ 우선순위 o 정적우선순위 처음에정해진우선순위가고정 쉬운구현 낮은오버헤드 환경변화에대한반응이불가능 지연시간감소의어려움 o 동적우선순위 상황에따라우선순위의변화 복잡한구현 높은오버헤드 시스템의반응성향상 7/23

05_ 스케줄링목적 o 시스템유형에따라다른목적 처리량최대화 수용할만한 시간안에반응을보이는대화식프로세스의수최대화 자원활용도최대화 무기환연기회피 우선순위강화 오버헤드최소화 예측가능성보장 o 대부분의스케줄러가가지는공통된목적 공평성 예측가능성 규모확장성 8/23

06_ 스케줄링기준 o 프로세서중심프로세스 시스템이할당하는프로세서시간을모두사용하는경향 o 입출력중심프로세스 입출력요청을하기전에프로세서를잠시사용하고곧반납하는경향 o 배치프로세스 사용자와상호작용없이수행할수있는작업을포함 o 대화식프로세스 빈번한사용자입력을요구 9/23

07_ 스케줄링알고리즘 o 스케줄링알고리즘 각프로세스가언제, 얼마동안실행할지결정 여러요인에대한고려 선점 / 비선점여부 우선순위 실행시간 완료시까지남은시간 공평성 기타프로세스특성 10/23

07_ 스케줄링알고리즘 o 선입선출스케줄링 (First-In-First-Out(FIFO) Scheduling) 가장간단한스케줄링알고리즘 준비큐에도착한순서에의해프로세서할당 비선점형 현대시스템에서주요스케줄링정책으로사용하는일은거의없음 11/23

07_ 스케줄링알고리즘 o 라운드로빈스케줄링 (Round-Robin(RR) Scheduling) 프로세스를 FIFO 순서로디스패치 타임슬라이스 ( 퀀텀 ) 라는제한된프로세서시간안에서만수행 선점형 대기프로세스를메인메모리에유지해선점에의해발생하는오버헤드최소화 주로복잡한스케줄링알고리즘내부에서사용 12/23

07_ 스케줄링알고리즘 o 라운드로빈스케줄링 (Round-Robin(RR) Scheduling) 이기적인라운드로빈스케줄링 (Selfish Round-Robin(SRR) Scheduling) 시간이지남에따라프로세스의우선순위를높이는에이징기법사용 먼저온오래된프로세스를선호 2개의큐 ü 보류큐 ü 활성큐 퀀텀크기 매우큰퀀텀크기 ü 프로세스가작업을마칠정도의크기 ü FIFO 방식처럼동작 매우작은퀀텀크기 ü 프로세서사이클의대부분을문맥전환오버헤드에사용 13/23

07_ 스케줄링알고리즘 o 최단프로세스우선스케줄링 (Shortest-Process-First(SPF) Scheduling) 완료시까지실행시간이가장짧을것으로예상하는프로세스를선택 FIFO 보다는평균대기시간감소 대기하는프로세스의수를줄임 긴프로세스뒤에대기하는프로세스수를최소화 변량이큰대기시간 비선점형 부정확한예상실행시간 적절한반응시간을보장해야하는환경에서는부적합 14/23

07_ 스케줄링알고리즘 o 최고응답률우선스케줄링 (Highest-Response-Ratio- Next(HRRN) Scheduling) SPF 의약점을보강 비선점형 대기시간고려 무기한연기방지 15/23

07_ 스케줄링알고리즘 o 최소잔여시간스케줄링 (Shortest-Remaining-Time(SRT) Scheduling) SPF 의선점형버전 실행시간이짧은프로세스가프로세서를선점 실행중인프로세스의경과시간에관한정보의유지가필요 실행시간이긴프로세스는 SPF 보다대기시간이길어질수있으며, 대기시간의변량이큼 선점오버헤드에의한성능저하 실행중인프로세스가거의완료되어갈때예상서비스시간이아주짧은프로세스가도착하는경우 실행중인프로세스보다실행예상시간이짧되차이가아주작은경우 16/23

07_ 스케줄링알고리즘 o 다수준피드백큐 서로다른특징의프로세스는다른스케줄링방법을요구 프로세스가행동양식을확립할기회를얻지못한경우, 정확한프로세서시간을결정하지못함 일반적으로짧은프로세스, 입출력중심프로세스가프로세스중심프로세스이전에실행되는것을선호함 다수준피드백큐 새로운프로세스는가장높은큐에들어가며, 낮은큐의프로세스보다높은우선순위를획득 ü 실행중인프로세스도더높은큐에도착하는프로세스에의해선점당함 퀀텀을모두소비하면, 한수준낮은큐로이동 ü 짧은프로세스와입출력중심프로세스에게높은우선순위할당 ü 실행시간이긴프로세스는짧은프로세스나입출력중심프로세스의종료후에실행 가장낮은수준의큐는라운드로빈방식, 나머지수준의큐는 FIFO 방식 프로세스의변화에대해적절한반응이필요 적응메커니즘의본보기 ü 시스템의변화에민감하게적응해, 시스템의반응성향상 17/23

07_ 스케줄링알고리즘 o 다수준피드백큐 18/23

07_ 스케줄링알고리즘 o 공평분배스케줄링 (Fair Share Scheduling(FSS)) 어떤사용자그룹은다른그룹보다중요함 ex) 수석연구원그룹 vs. 보조연구원그룹 낮은중요도의그룹이자원을독점하는것을방지 자원을다양한공평분배그룹별로배치 상대적인필요에따라한공평분배그룹이사용하지않는자원을다른공평분배그룹에할당 19/23

07_ 스케줄링알고리즘 o 공평분배스케줄링 (Fair Share Scheduling(FSS)) 20/23

07_ 스케줄링알고리즘 o 공평분배스케줄링 (Fair Share Scheduling(FSS)) 21/23

08_ 데드라인스케줄링 o 데드라인스케줄링 프로세스들이특정시간안에마치도록스케줄링 데드라인을놓치면프로세스는가치가낮아지거나아예없어질수있음 복잡한스케줄링 정확한자원요구량을미리제시하는것이필요 다른사용자들에대한서비스에심각한악영향을미치는것을방지 데드라인이될때까지자원요구량을철저하게계획 상당한오버헤드초래 22/23

09_ 실시간스케줄링 o 실시간스케줄링 타이밍제약 주기적인실행 o 소프트실시간스케줄링 시간적제약을지킨다고보장하지못함 ex) 멀티미디어재생 o 하드실시간스케줄링 항상시간적제약의충족을보장 데드라인을지키지못할경우큰재난을초래할수있음 ex) 항공제어시스템 23/23

09_ 실시간스케줄링 o 정적실시간스케줄링알고리즘 프로세스우선순위를시간에따라조절하지않음 낮은오버헤드 하드실시간시스템은정적스케줄링알고리즘을주로사용 프로세스가제한시간안에완료함을쉽게증명가능 비율단조 (RM, Rate-Monotonic) 알고리즘 선점형, 우선순위기반라운드로빈알고리즘 주기적인프로세스선호 데드라인비율단조알고리즘 주기적인프로세스들이주기와같지않은데드라인을지정할때사용 24/23

09_ 실시간스케줄링 o 동적실시간스케줄링알고리즘 프로세스실행중에도우선순위조절 큰오버헤드발생 최단데드라인우선 (EDF, Earliest-Deadline-First) 데드라인이가장임박한프로세스를디스패치하는선점형스케줄링알고리즘 최소여유시간우선 (Minimum-laxity-first) EDF와유사하지만프로세스의여유시간에근거해우선순위를결정 여유시간 ü L = D (T + C) ü L: 여유시간, D: 프로세스의데드라인, T: 현재시간, C: 프로세스의남은실행시간 25/23

10_ 자바스레드스케줄링 o 운영체제는다양한수준에서스레드를지원 사용자수준스레드 운영체제는프로세스가멀티스레드라는것을인식못함 프로세스를한단위로디스패치 커널수준스레드 커널수준에서구현 각스레드를개별적으로스케줄링가능 o 자바스레드스케줄러 사용자영역에서스레드를구현하는경우, 타임슬라이싱에의존 타임슬라이싱이없는경우우선순위가같은스레드집합이완료할때까지실행 타임슬라이싱이있는경우각스레드가해당기한안에실행할퀀텀을부여받음 26/23

10_ 자바스레드스케줄링 27/23

운영체제론