9 장단일처리기스케줄링 9 장의강의목표 처리기스케줄링의유형을이해한다. 단일처리기시스템에서여러단기 - 스케줄링방식들의동작원리를이해한다. 단일처리기시스템에서여러단기 - 스케줄링방식들의장단점을이해한다. 제 9 장단일처리기스케줄링 2
목차 9.1 처리기스케줄링의유형 9.2 스케줄링알고리즘들 9.3 전통적인유닉스시스템에서의스케줄링 제 9 장단일처리기스케줄링 3 9.1 처리기스케줄링의유형 처리기스케줄링의정의 응답시간이나처리량, 효율성을증대시키기위해처리기가다음에실행할프로세스를선택하는것! 선후관계에따른스케줄링의유형 3 가지 장기스케줄링 : degree of multiprogramming i 을결정 중기스케줄링 : swapper 의역할 단기스케줄링 : CPU 스케줄링에해당 제 9 장단일처리기스케줄링 4
9.1 처리기스케줄링의유형 - 개요 ( 계속 ) 프로세스상태와스케줄링유형과의관계 스케줄링단계와프로세스상태와의관계 제 9 장단일처리기스케줄링 5 9.1 처리기스케줄링의유형 - 개요 ( 계속 ) 프로세스가일생동안거치는스케줄링큐다이어그램 스케줄러의성능 프로세스들이일생동안각종큐에서대기하는시간을얼마나줄일수있을것이냐하는문제 제 9 장단일처리기스케줄링 6
9.1 처리기스케줄링의유형 장기스케줄링 새프로세스의시스템진입허용여부를결정 다중프로그래밍의정도를결정함 새로운프로세스의진입허용시점은? 시스템내의부하조절과관련 시스템포화상태여부 어떤규정으로작업들을골라프로세스로만들어줄것인가? FCFS (First-Come-First-Served) Priority-based CPU-burst 길이 입출력-중심 (I/O-bound) 프로세스우대 여유입출력자원사용예정프로세스우대 제 9 장단일처리기스케줄링 7 9.1 처리기스케줄링의유형 중기스케줄링 스와핑 (swapping) 기능의일부 스왑공간으로쫓겨나간 (swap-out) 프로세스전체또는일부중어느것을다시주메모리로스왑인 (swap-in) 할것인가? 제 9 장단일처리기스케줄링 8
9.1 처리기스케줄링의유형 단기스케줄링 디스패쳐 (dispatcher) 라고도함 장기 / 중기스케줄러보다매우자주실행 세밀한기준으로다음번에실행시킬프로세스를선정 단기스케줄러실행시점 클럭 ( 타이머 ) 인터럽트 ( 시간할당량만료시 ) 입출력인터럽트 운영체제시스템호출 ( 커널내 preemption point 또는사용자모드로복귀하기직전 ) 신호 (signal)( 예를들면, 세마포어 ) 제 9 장단일처리기스케줄링 9 9.2 스케줄링알고리즘 : 단기스케줄링평가기준 기준 1 : 사용자중심관점 vs. 시스템중심관점 사용자중심관점 개별사용자또는개별프로세스의입장에서자신들에게긍정적인영향을미치는스케줄러와그렇지못한스케줄러를평가 예 : 응답시간 (Response Time) 프로세스가요구한작업요청에대해시스템이최초로출력을내주기시작할때까지걸린시간 시스템중심관점 스케줄러가처리기를얼마나효율적으로활용했느냐? 예 : 처리량 (Throughput) 단위시간안에실행을완료시킬수있는프로세스의수 어느한관점만을중시하면다른관점이안좋아짐! 모든시스템에서중시해야할관점 사용자중심 시스템유형별로중시해야할관점이다를수있음 예 ) 단일처리기시스템 시스템중심관점이상대적으로덜중요! 제 9 장단일처리기스케줄링 10
9.2 스케줄링알고리즘 단기스케줄링평가기준들 ( 계속 ) 기준 2 : 성능중심관점 vs. 성능외적관점 성능중심관점 대부분정량적인척도 측정이용이함. 성능외적 ( 기타 ) 관점 대부분정성적인척도 측정이어려움 예 : 예측가능성 (Predictability) 제 9 장단일처리기스케줄링 11 9.2 스케줄링알고리즘단기스케줄링평가기준들 스케줄링평가척도 제 9 장단일처리기스케줄링 12
9.2 스케줄링알고리즘단기스케줄링평가기준들 스케줄링평가척도 ( 계속 ) 제 9 장단일처리기스케줄링 13 9.2 스케줄링알고리즘 우선순위기반스케줄링 우선순위가높은프로세스를먼저실행! 우선순위별대기큐를별도로두고, 높은우선순위의대기큐에있는프로세스를먼저실행 우선순위 [RQi] > 우선순위 [RQj] for i < j 같은우선순위큐내에서는어떤정책을쓸것인가? 순수우선순위기반스케줄링의문제점 : Starvation! 제 9 장단일처리기스케줄링 14
9.2 스케줄링알고리즘 다양한스케줄링정책들 비교기준 1 : Selection Function 다음번실행을위해준비큐에서대기중인프로세스중하나를고를때사용하는알고리즘 Function Factors w = 대기한시간과실행한시간을모두합쳐시스템에들어온후지금까지경과한시간 e = 지금까지실행하는데에만걸린시간 s = 프로세스가시작해서종료하기까지걸릴총서비스시간 선택함수의예 max[w] : 시스템에진입한지가장오랜시간을보낸프로세스를선택하라는것 FCFS 를의미! 제 9 장단일처리기스케줄링 15 9.2 스케줄링알고리즘다양한스케줄링정책들 비교기준 2 : Decision Mode 선택함수가호출되는시점이언제인가? 비선점 (nonpreemptive) 프로세스가일단실행상태 (Running state) 에진입하면종료되거나자발적으로 CPU 를놓을때까지는 CPU 를빼앗기지않는다. 선점 (preemptive) 현재실행중인프로세스라할지라도운영체제에의해인터럽트가걸려비자발적으로준비큐로이동될수있다. nonpreemptive 모드보다문맥교환횟수가많아지긴하지만, 한프로세스가처리기시간을독점하는것을방지할수있어효율적인스케줄링이가능함! 제 9 장단일처리기스케줄링 16
9.2 스케줄링알고리즘다양한스케줄링정책들 스케줄링기법들의동작방식비교 스케줄링기법비교를위한프로세스들 First-Come-First-Served FIFO(First-In-First-Out) 라고도함 프로세스는준비상태가되면준비큐에들어간다. 현재실행중인프로세스가실행을종료 준비큐에서대기중이던프로세스중가장오랫동안기다렸던프로세스가다음번실행프로세스로선정됨 제 9 장단일처리기스케줄링 17 9.2 스케줄링알고리즘다양한스케줄링정책들 FCFS ( 계속 ) First-Come-First-Served( 계속 ) FCFS는짧은프로세스보다는긴프로세스에게유리 Nonpreemptive 모드로동작하기때문! 입출력중심의프로세스보다처리기중심프로세스를우대하는경향이나타남 FCFS 는결국비효율적스케줄링기법이지만 우선순위기법과결합하면성능이많이나아짐! 제 9 장단일처리기스케줄링 18
9.2 스케줄링알고리즘다양한스케줄링정책들 라운드-로빈 (Round-Robin) FCFS 에서짧은프로세스가피해보는현상완화방법 시간을측정하고있다가어떤긴프로세스가일정시간이상을넘어가는순간실행을강제로중단시키는 (preemption) 것 프로세스실행시간측정방법 클럭 (clock) 인터럽트 ( 또는타이머인터럽트 ) 클럭인터럽트는일정간격으로주기적으로발생 라운드 - 로빈스케줄링기법동작방식 클럭인터럽트가발생하면클럭인터럽트서비스루틴이실행되고, 클럭인터럽트서비스루틴은현재실행중이던프로세스를준비큐로이동시키고, 준비큐에서 FCFS 방식으로다음번프로세스를골라실행시킴 시간할당량 (time slicing, 또는 time quantum) 기법이라고도함 제 9 장단일처리기스케줄링 19 9.2 스케줄링알고리즘다양한스케줄링정책들 라운드 - 로빈 (Round-Robin) ( 계속 ) 시간할당량의크기 (q) 가라운드 - 로빈성능에미치는영향 시간할당량이너무작다면? 문맥교환오버헤드가증가 시간할당량이너무크다면? FCFS 와비슷해짐 시간할당량의권장길이 프로세스가사용자와최소한한번이상대화하기에충분하거나 프로세스내의어떤한함수정도는실행을마칠수있는충분한길이 제 9 장단일처리기스케줄링 20
9.2 스케줄링알고리즘다양한스케줄링정책들 라운드 - 로빈 (Round-Robin) ( 계속 ) 시간할당량의크기가스케줄링에미치는영향 제 9 장단일처리기스케줄링 21 9.2 스케줄링알고리즘다양한스케줄링정책들 라운드 - 로빈 (Round-Robin) ( 계속 ) 단점 : 입출력중심프로세스보다처리기중심프로세스를우대할수밖에없는현상이여전히발생함! 해소방법 : 가상라운드로빈 (VRR) 스케줄링방식 입출력중심프로세스와처리기중심프로세스를분리하여준비큐를둠. 계산하던중시간할당량을다썼다면그냥준비큐로들어감. 입출력요청으로 CPU를반납했다면입출력대기큐로들어감. 스케줄러는입출력대기큐에있는프로세스를먼저스케줄링함! 제 9 장단일처리기스케줄링 22
9.2 스케줄링알고리즘다양한스케줄링정책들 Shortest Process Next(SPN) FCFS의긴프로세스우대편향성완화방법 2: 가장짧은프로세스를먼저실행시키는정책 종료시까지남아있는실행시간이가장짧은프로세스를다음번프로세스로선택 비중단 (Nonpreemptive) 모드로동작 실행시간이짧은프로세스가 ( 비록늦게도착했더라도 ) 긴프로세스들보다먼저스케줄링될수있음! 단점 : 짧은프로세스들이지속적으로시스템에진입한다면이들보다상대적으로긴프로세스가기아상태에빠질수있다 제 9 장단일처리기스케줄링 23 9.2 스케줄링알고리즘다양한스케줄링정책들 Shortest Process Next(SPN) ( 계속 ) SPN 구현상의문제점 각프로세스가요구하는총실행시간을미리알아야한다는점 미리알기어렵기때문에시스템은이를유추할수있어야함 프로세스의예상실행시간을유추하는방법 단순평균 : n Ti S 1 + = n 1 1 n 1 Sn + 1 = Tn + S n 1 n n i= n 지수적평균 (exponential averaging) S S n + 1 n + 1 = α T n = αt n + (1 α ) S n + (1 α ) αt n 1 i +... + (1 α ) αt n i n +... + (1 α ) S 1 과거에측정된실행시간일수록다음실행시간예측에미치는영향이작아짐 α = 0.8일경우를가정해보면 S 1 = 0.8T n + 0.16T + 0.032 T + 0.0064 T 3 +... n + n 1 n 2 n α : 가중치요소 (weighting factor) 제 9 장단일처리기스케줄링 24
9.2 스케줄링알고리즘다양한스케줄링정책들 Shortest-Process-Next(SPN) ( 계속 ) 특정 α 값이주어졌을때 T n-i 앞에붙는계수값들의변화 단점 : 최근에갑자기비정상적으로처리기를많이사용한경우향후에도그럴것으로예측해버리므로잠시후정상구간으로진입했을때잘못된예측을할가능성이있다. 제 9 장단일처리기스케줄링 25 9.2 스케줄링알고리즘다양한스케줄링정책들 Shortest-Process-Next(SPN) ( 계속 ) 지수적평균기법과단순평균기법의예상실행시간값비교 지수적평균기법이좀더현실과부합하는예상을하고있음 제 9 장단일처리기스케줄링 26
9.2 스케줄링알고리즘다양한스케줄링정책들 SRT (Shortest Remaining Time) SPN 의중단 (preemptive) 모드버전에해당 예상되는남아있는실행시간이가장짧은프로세스가다음번프로세스로선택됨 if ( 새로도착한프로세스의예상되는남아있는실행시간 < 현재실행중인프로세스의예상실행시간 ) 늦게도착했더라도현재실행중인프로세스를중단하고곧장선택됨. 단점 매스케줄링때마다프로세스들의남아있는실행시간을평가해야하는부담 긴프로세스가기아상태에빠질가능성 제 9 장단일처리기스케줄링 27 9.2 스케줄링알고리즘다양한스케줄링정책들 Highest Response Ratio Next (HRRN) 준비큐에있는프로세스중 R 값 ( 응답비율 ) 이가장큰프로세스를다음번프로세스로선택 프로세스가시스템내에머문시간 ( 즉, 프로세스의나이 ) 을고려 서비스시간이짧은프로세스의 R 값이상대적으로크기때문에짧은프로세스를우대하는면도있고, 대기시간때문에시스템에오래머문긴프로세스도오래머물면머물수록 R 값이커지기때문에홀대받지는않는다. 응답비율의정의 w + s R = R = 응답비율 s w = 처리기를기다리며대기한시간 s = 예상되는서비스시간 제 9 장단일처리기스케줄링 28
9.2 스케줄링알고리즘 피드백 (Feedback) 스케줄링 다양한스케줄링정책들 프로세스들의예상되는서비스시간을미리알아낼필요가없다 중단점을만날때마다프로세스는한단계낮은우선순위의준비큐로강등되어진입 새로도착한프로세스일수록, 그리고짧은프로세스일수록오래된프로세스나긴프로세스보다우대받는정책 Multilevel Feedback Queue 의구조를갖게됨 큐 RQ 0 ~ RQ n-1 1 : FCFS 방식 큐 RQ n : 라운드 - 로빈방식 제 9 장단일처리기스케줄링 29 9.2 스케줄링알고리즘 피드백 (Feedback) 스케줄링 ( 계속 ) 다양한스케줄링정책들 피드백의변형 1 : 모든큐에서고정된시간할당량이있는라운드로빈방식으로스케줄링 짧은프로세스가계속진입하는경우긴프로세스가불이익을받음 피드백의변형 2: 시간할당량의크기를큐별로다르게함 제 9 장단일처리기스케줄링 30
9.2 스케줄링알고리즘 스케줄링정책들의특징 제 9 장단일처리기스케줄링 31 9.2 스케줄링알고리즘스케줄링정책들의특징 ( 계속 ) 제 9 장단일처리기스케줄링 32
9.2 스케줄링알고리즘스케줄링정책들의비교분석결과 제 9 장단일처리기스케줄링 33 9.2 스케줄링알고리즘스케줄링정책들의비교분석결과 ( 계속 ) 제 9 장단일처리기스케줄링 34
9.2 스케줄링알고리즘 스케줄링정책들의성능비교 2 가지비교분석방법을사용 큐잉분석 (Queuing Analysis) 시뮬레이션모델링 (Simulation Modeling) 큐잉분석 관찰에의하면프로세스의서비스시간에관계없이다음프로세스를선택하는스케줄러는다음과같은관계를따른다. Normalized Turnaround Time = T T r 1 = 1 ρ T r = 턴어라운드시간또는시스템에머문시간 ; 시스템내에총머문시간 ( 대기시간 + 실행시간 ) T s = 평균서비스시간 ; 실행상태에머물렀던평균시간 ρ = 처리기이용율 Ts 제 9 장단일처리기스케줄링 35 9.2 스케줄링알고리즘스케줄링정책들의성능비교 큐잉분석 ( 계속 ) 제 9 장단일처리기스케줄링 36
9.2 스케줄링알고리즘스케줄링정책들의성능비교 큐잉분석 ( 계속 ) 전체적인정규화된턴어라운드시간비교 짧은작업을우대 처리기이용율이높아짐에따라평균정규화된턴어라운드시간개선 preemptive 스케줄링기법을사용한경우에평균정규화된턴어라운드시간이최대로개선됨을확인 하지만전체적으로성능향성의정도가그리확연하지는않다는것도알수있다. 제 9 장단일처리기스케줄링 37 9.2 스케줄링알고리즘 큐잉분석 ( 계속 ) 스케줄링정책들의성능비교 짧은프로세스들이모여있는높은우선순위등급에대한결과 시스템이비중단모드의우선순위기반스케줄링기법을사용했을때큰성능향상을보인다는것을알수있다. 제 9 장단일처리기스케줄링 38
9.2 스케줄링알고리즘 큐잉분석 ( 계속 ) 스케줄링정책들의성능비교 긴프로세스들이모여있는낮은우선순위등급에대한결과 우선순위를사용한경우더안좋은성능을보인다는것을알수있다. 제 9 장단일처리기스케줄링 39 9.2 스케줄링알고리즘스케줄링정책들의성능비교 가정 50,000 개의프로세스를대상 시뮬레이션모델링 각프로세스의도착률은 λ = 0.8, 평균서비스시간은 T s = 1, 따라서처리기이용율은 ρ = λt s = 08 0.8 이라고가정 처리기이용율은변하지않고 0.8로고정되어있는어떤한시점에대한실험이라고봐도무방함! 프로세스분류 서비스시간백분율별로 100 개의그룹으로나누어짐 500 개의프로세스는서비스시간으로 1 을요구하는그룹으로, 또다른 500 개의프로세스는서비스시간으로 2 를요구하는그룹으로나누어지는식 마지막 500개의프로세스는가장긴서비스시간인 100을요구하는그룹으로분류될것임 제 9 장단일처리기스케줄링 40
9.2 스케줄링알고리즘스케줄링정책들의성능비교 시뮬레이션모델링 ( 계속 ) 정규화된턴어라운드시간에대한시뮬레이션결과 제 9 장단일처리기스케줄링 41 9.2 스케줄링알고리즘스케줄링정책들의성능비교 시뮬레이션모델링 ( 계속 ) 대기시간에대한시뮬레이션결과 제 9 장단일처리기스케줄링 42
9.2 스케줄링알고리즘 Fair-Share 스케줄링 Background 하나의사용자응용프로그램이여러개의프로세스 ( 또는스레드 ) 들로구성된경우도많음 사용자의관점에서는개별프로세스보다는자신의프로세스집합 ( 즉, 응용전체 ) 이어떻게동작하는지에관심을더갖게됨. 스케줄링의단위를개별프로세스가아닌프로세스집합단위로하는것이더공정하지않을까? Fair-Share 스케줄링 프로세스집합단위의스케줄링방식 공정함을나누어갖는다 라는 공정 - 공유 의의미가함축 제 9 장단일처리기스케줄링 43 9.2 스케줄링알고리즘 Fair-Share 스케줄링 ( 계속 ) Fair-Share 스케줄링의동작방식개요 각사용자에게는일종의가중치가부여됨 가중치는시스템전체자원중에이사용자가사용할수있는지분을의미 사용자 A 가사용자 B 에비해 2 배큰가중치를가지고있다고가정 목표 : 한참수행한후에평가해봤더니사용자 A 가사용자 B 에비해 2배에달하는작업량을소화해냈더라. 라는결론이도출되도록 자원사용율을지분에맞게통제하는것 복합우선순위활용을통한 Fair-Share 통제방법 복합우선순위 순수한의미의프로세스별우선순위 + 최근처리기사용시간 + 프로세스가소속된그룹이최근소비한처리기시간 제 9 장단일처리기스케줄링 44
9.2 스케줄링알고리즘 Fair-Share 스케줄러의동작예 스케줄링정책들의성능비교 세개의프로세스가두개의그룹을구성 그룹 1: A, 그룹 2: B, C 각그룹의가중치는 0.5 스케줄링순서 A, B, A, C, A, B, 그룹별가중치 0.5 를유지하게됨. 제 9 장단일처리기스케줄링 45 9.3 전통적인유닉스시스템에서의스케줄링 동작방식 다중- 레벨피드백큐 방식 우선순위등급별로하나씩큐가존재 각큐내에서는라운드로빈방식으로스케줄링 스케줄링은 1초마다한번씩실시 실행중인프로세스가 1초이내에자발적으로 CPU를놓거나종료되지않으면스케줄러가강제로 CPU 를뺏어다른프로세스에게할당 각프로세스의우선순위는기본적으로 1 초마다한번씩재계산된다 기본우선순위큐의순위 ( 내림차순 ) 스와퍼 (swapper) 블록입출력장치제어 파일처리 문자입출력장치제어 사용자프로세스 제 9 장단일처리기스케줄링 46
9.3 전통적인유닉스시스템에서의스케줄링 제 9 장단일처리기스케줄링 47 9.3 전통적인유닉스시스템에서의스케줄링 동작예 제 9 장단일처리기스케줄링 48
요약 처리기스케줄링의 3 가지유형 장기, 중기, 단기스케줄링 단기스케줄링알고리즘 FCFS, 라운드로빈, SPN, SRT, HRRN, 피드백, 공정공유스케줄링 스케줄링정책성능비교 큐잉분석, 시뮬레이션모델링 전통적인 UNIX 시스템에서의스케줄링기법 제 9 장단일처리기스케줄링 49