2.4 스케줄링 (1) 스케줄링의개요스케줄링은프로세스가생성되어실행될때필요한시스템의여러자원을해당프로세스에할당하는작업을의미 1) 작업스케줄링 (Job Scheduling) 1 어떤프로세스가시스템의자원을차지할수있는지를결정하여준비상태큐로보내는작업을의미 2 작업스케줄러 (Job Scheduler) 에의해수행 2) 프로세서스케줄링 (Processor Scheduling) 1 프로세스가실행되기위해 CPU를할당받는시기와특정프로세스를지정하는작업 2 프로세서스케줄러 (Processor Scheduler) 에의해프로세서스케줄링및문맥교환이수행됨 0010 프로세스스케줄러 : 하나의프로세스를준비 (ready) 상태에서실행 (run) 상태로전이시킴 9904 스케줄링목적오답 운영체제의오버헤드를최대화하기위함 모든프로세스에게공정하게적용되어야하기때문에우선순위제도는불필요 프로세서의처리량을최소화해야함 (2) 스케줄링의목적 9910 0303 0409 0503 0605 0005 0106 0308 0605 0709 1) 처리율증가 2) CPU 이용률증가 3) 오버헤드최소화 4) 응답시간최소화 5) 반환시간최소화 6) 대기시간최소화 비선점스케줄링오답 SRT (Shortest Remaining Time) RR(Round-Robin) 7) 모든작업에대해공평성을유지해야하며, 경과시간의예측이가능해야함 (3) 비선점스케줄링 9908 0003 0109 0209 0303 0007 0106 0109 0305 0503 0509 이미할당된 CPU 를다른프로세스가강제로빼앗아사용할수없는스케줄링기법 1) 모든프로세스에대한요구를공정하게처리할수있음 2) 프로세스응답시간예측이용이 3) 중요한작업이중요하지않은작업을기다리는경우가발생할수있음 4) 비선점스케줄링의종류에는 FIFO, SJF, 우선순위, HRN, 기한부등의알고리즘이있음 5) 대화형시스템에부적합 9910 0709 6) 비선점기법종류 1 FIFO(First In First Out)=FCFS 0703 가장간단한방식이고비선점방식의스케줄링 중요하지않은작업이작업을기다리게할수있음 198
대화식시스템에부적합 FIFO 기법예 아래와같이프로세스들이차례로준비상태큐에들어왔다고가정 프로세스번호 P1 P2 P3 실행시간 20 4 6 결과 프로세스번호 P1 P2 P3 평균 실행시간 20 4 6 30/3 대기시간 0 20 24 44/3 반환시간 20 24 30 74/3 2 SJF(Shortest Job First) 0209 0308 0709 9908 0205 0209 0303 0505 0509 0603 준비상태큐에서기다리고있는프로세스들중에서실행시간이가장짧은프로세스에게먼저 CPU를할당하는기법 가장적은평균대기시간을제공하는최적알고리즘 실행시간이긴프로세스는실행시간이짧은프로세스에게할당순위가밀려무한연기상태가발생가능 SJF 기법예 0505 0509 0503 0509 아래와같이프로세스들이차례로준비상태큐에들어왔다고가정프로세스번호 P1 P2 P3 실행시간 20 4 6 결과 프로세스진행 P2 P3 P1 평균 실행시간 4 6 20 30/3 대기시간 0 4 10 14/3 반환시간 4 10 30 44/3 www.gisa79.com SJF 스케줄링오답 SJF 스케줄링은남아있는실행시간의추정치가가장작은작업을먼저실행시키며, 언제라도실행중인작업이강제로실행을멈출수있는산정기법 각프로세서의프로세서요구시간을미리예측하기쉬움 선점스케줄링기법에해당 3 HRN(Highest Response-ratio Next) 0403 0609 0703 9906 0305 0603 0705 실행시간이긴프로세스에불리한 SJF 기법을보완하기위한것으로대기시간과서비스시간을이용하는기법 우선순위를계산하여그숫자가가장높은것부터낮은순으로우선순위가부여 우선순위계산식 9904 0203 0305 0503 0605 9908 0003 0106 0109 0205 0209 0308 0409 0503 0509 0609 0709 대기시간 + 서비스시간서비스시간 우선순위계산예 9904 0503 작업 대기시간 서비스시간 A 5 5 B 10 6 C 15 7 D 20 8 - A : (5 + 5) / 5 = 2 - B : (10 + 6) / 6 = 2.67 - C : (15 + 7) / 7 = 3.14 - D : (20 + 8) / 8 = 3.5 우선순위가가장높은것은 D 199
4 기한부 (Deadline) 9908 프로세스에게일정한시간을주어그시간안에프로세스를완료하도록하는기법 프로세스가제한된시간안에완료되지않을경우제거되거나처음부터다시실행 기한부스케줄링에필요한집약적자원관리는많은오버헤드를일으킬수있음 사용자는그작업에필요한자원에관한정확한정보를시스템에제시하여야함 5 우선순위 (Priority) 준비상태큐에서기다리는각프로세스마다우선순위를부여하여그중가장높은프로세스에게먼저 CPU를할당하는기법 우선순위가동일할경우 FCFS 기법으로 CPU를할당 가장낮은순위를부여받은프로세스는무한연기또는기아상태가발생할수있음 에이징 (Aging) 기법 0007 0010 0205 0403 0405 0003 0005 0010 0203 프로세스가자원을기다리고있는시간에비례하여우선순위를부여함으로써무한연기문제를방지 선점 (preemptive) 스케줄링의특징오답 모든프로세스에대한요구를공정히처리 일단 CPU 를할당받으면다른프로세스가 CPU 를강제적으로빼앗을수없는방식 시분할시스템은보통비선점 CPU 스케줄링기법을사용 (4) 선점기법 0003 0109 0605 0609 9910 0203 0205 0308 0405 0505 0605 0609 하나의프로세스가 CPU를할당받아실행하고있을때우선순위가높은다른프로세스가 CPU를강제로빼앗아사용할수있는스케줄링기법 1) 우선순위가높은프로세스를빠르게처리할수있음 2) 주로빠른응답시간을요구하는대화식시분할시스템에서사용 3) 선점스케줄링의종류에는 SRT, Round Robin, 선점우선순위, 다단계큐, 다단계피드백큐등의알고리즘이있음 SRT 스케줄링오답 SRT 에서는한작업이실행을시작하면강제로실행을멈출수없음 Round Robin 방식에대한오답 처리하여야할작업의양이가장작은프로세스에게 CPU 를할당하는기법 작업이끝나기까지의실행시간추정치가가장작은작업을먼저실행시키는기법 비선점형기법 프로세스들이배당시간내에작업을완료되지못하면폐기됨 할당된자원과처리기의소유권은수행중인프로세스의제어권한임 짧은대화식사용자에게는시간할당량을크게하는것이효율적임 시간할당량이작아질수록문맥교환과부하는상대적으로낮아짐 4) 선점기법종류 0703 1 SRT(Shortest Remaining Time) 0106 0203 0409 0709 비선점스케줄링인 SJF 기법을선점형태로변경한기법 현재실행중인프로세스의남은시간과준비상태큐에새로도착한프로세스의실행시간을비교하여가장짧은실행시간을요구하는프로세스에게 CPU를할당하는기법으로시분할시스템에유용 실행시간을추적해야하므로오버헤드가증가함 2 RR(Round Robin) 9910 0203 0305 0308 0405 0503 0605 9904 9908 0003 0005 0109 0209 0305 0403 0405 0503 0605 0609 0703 0705 0709 시분할시스템을위해고안된방식으로 FIFO 기법을선점형태로변형한기법 할당되는시간이클경우 FIFO 기법과같아짐 9908 할당되는시간이작은경우문맥교환및오버헤드가자주발생 프로세스들이배당시간내에작업되지못하면준비상태큐의맨뒤로이동 시스템이사용자에게적합한응답시간을제공해주는대화식시스템에유용 < 대기큐 (Ready Queue)> CPU C B A 할당시간 : 1초 200
3 선점우선순위준비상태큐의프로세스들중에서우선순위가가장높은프로세스에게먼저 CPU를할당하는기법 www.gisa79.com 4 다단계큐 (MQ, Multi-level Queue) 0010 0403 프로세스를특정그룹으로분류할수있을경우그룹에따라각기다른준비상태큐를사용하는기법 프로세스가특정그룹의준비상태큐에들어갈경우다른준비상태큐로이동할수없음 하위준비상태큐에있는프로세스를실행하는도중이라도상위준비상태큐에프로세스가들어오면상위프로세스에게 CPU를할당해야함 5 다단계피드백큐 (MFQ, Multi-level Feedback Queue) 0007 0103 특정그룹의준비상태큐에들어간프로세스가다른준비상태큐로이동할수없는다단계큐기법을준비상태큐사이를이동할수있도록개선한기법 CPU 스케줄링특성중대화형시스템에서가장중요한인자 0705 반응시간 (response time) CPU 스케줄링을평가하는기준 0705 처리량 (throughput) 대기시간 (waiting time) 균형있는자원이용 201
기 출 문 제 0106 0409 0709 8. 스케줄링기법중 SJF 기법과 SRT 기법에관한설명으로옳지않은것은? 9910 0409 0605 1. 가장바람직한스케줄링정책은? 가. CPU 이용률을줄이고반환신간을늘린다. 나. 응답시간을줄이고 CPU 이용률을늘린다. 다. 대기시간을늘리고반환시간을줄인다. 라. 반환시간과처리율을늘린다. 가. SJF 는비선점 (nonpreemptive) 기법이다. 나. SJF 는작업이끝나기까지의실행시간추정치가가장작은작업을먼저실행시킨다. 다. SRT 는시분할시스템에유용하다. 라. SRT 에서는한작업이실행을시작하면강제로실행을멈출수없다. 0303 2. 스케줄링의목적으로거리가먼것은? 가. 모든작업들에대해공평성을유지하기위하여나. 단위시간당처리량을최대화하기위하여다. 응답시간을빠르게하기위하여라. 운영체제의오버헤드를최대화하기위하여 0203 0605 0703 3. 선점 (preemptive) 방식을사용하는 CPU 스케줄링방식은? 가. SRT 스케줄링나. FIFO 스케줄링다. HRN 스케줄링라. SJF 스케줄링 9910 0203 0308 0505 0605 4. 디스크스케줄링방법중 Round-Robin 방식에대한설명중옳지않은것은? 가. FIFO 방식으로선점 (preemptive) 형기법이다. 나. 처리하여야할작업의양이가장작은프로세스에게 cpu 를할당하는기법이다. 다. 대화식사용자에게적당한응답시간을보장한다. 라. 시간할당량이작을경우문맥교환에따른오버헤드가커진다. 9908 0003 0103 0109 0209 0303 5. 비선점식스케줄링기법으로짝지어진것은? 가. FIFO - SJF 나. SRT - SJF 다. RR - SJF 라. HRN - RR 9904 0203 0503 0605 6. HRN(Highest Response Scheduling) 스케줄링기법에서우선순위결정방법은? 가. ( 대기시간 + 서비스시간 ) / 대기시간나. ( 대기시간 + 서비스시간 ) / 서비스시간다. 대기시간 / ( 대기시간 + 서비스시간 ) 라. 서비스시간 / ( 대기시간 + 서비스시간 ) 0305 7. HRN(Highest Response-ratio Next) 방식으로스케줄링할경우, 입력된작업이다음과같을때우선순위가가장높은작업은? 작업 대기시간 서비스시간 A 5 5 B 10 6 C 15 7 D 20 8 가.A 나.B 다.C 라.D 0209 0303 0308 9. SJF(Shortest-Job-First) 스케줄링방법에대한설명으로거리가먼것은? 가. 작업이끝나기까지의실행시간추정치가가장작은작업을먼저실행시킨다. 나. 작업시간이큰경우오랫동안대기하여야한다. 다. 각프로세서의프로세서요구시간을미리예측하기쉽다. 라. FIFO 기법보다평균대기시간이감소된다. 0403 0703 10. SJF 방식의단점을보완하기위해대기시간을고려한프로세스의응답률로프로세스의우선순위를결정하는프로세스스케줄링방법은? 가. 우선순위 (Priority) 스케줄링나. 다단계큐 (Multilevel Feedback Queue) 스케줄링다. HRN 스케줄링라. Round-Robin 스케줄링 9910 0103 0109 0203 0305 0308 0405 0505 0605 11. 라운드로빈 (round robin) 스케줄링방법에대한설명중적절하지않은것은? 가. 시간분할의크기가작으면작은프로세서들에게유리하다. 나. 시간분할의크기가너무작으면스래싱에소요되는시간의비중이커진다. 다. 시간분할의크기가커지면 FCFS(First Come First Serve) 방법과같게된다. 라. 비선점기법에해당한다. 0007 0209 12. 스케줄링기법에대한설명으로옳지않은것은? 가. RR 스케줄링은주어진시간할당량 (time slice) 안에작업을마치지않으면준비완료리스트 (ready list) 의가장뒤로배치되는기법이다. 나. SJF 스케줄링은남아있는실행시간의추정치가가장작은작업을먼저실행시키며, 언제라도실행중인작업이강제로실행을멈출수있는선점기법이다. 다. HRN 스케줄링은그작업이서비스받을시간과그작업이서비스를기다린시간으로결정되는우선순위에따라 CPU 를할당한다. 라. 기한부 (Deadline) 스케줄링은제한된시간내에반드시작업이완료되도록스케줄링하는기법이다. 202