정보처리

<p>프로세스가 생성되여 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미한다.<br>프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거치게 된다.</p><div data-type="horizontalRule"><hr></div><h3 id="561c1e9a-5928-4ad8-803b-4be73e1f7770" data-toc-id="561c1e9a-5928-4ad8-803b-4be73e1f7770">스케줄링 종류</h3><h4 id="1fb53c1d-6b5c-42ed-a3e7-10a6209159bd" data-toc-id="1fb53c1d-6b5c-42ed-a3e7-10a6209159bd">장기 스케줄링</h4><p>- 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업을 의미한다.<br>- 작업 스케줄링 (Job Scheduling), 상위 스케줄링이라고도 하며, 작업 스케줄러에 의해 수행된다.</p><h4 id="93ca4580-18a3-4881-b71f-b2369aee5a6b" data-toc-id="93ca4580-18a3-4881-b71f-b2369aee5a6b">중기 스케줄링</h4><p>- 어떤 프로세스들이 CPU를 할당받을 것인지 결정하는 작업을 의미한다.<br>- CPU를 할당받으려는 프로세스가 많을 경우 프로세스를 일시 보류시킨 후 활성화해서 일시적으로 부하를 조절한다.</p><h4 id="a3b59582-c1c5-4dc3-bd12-c033a33d3ed2" data-toc-id="a3b59582-c1c5-4dc3-bd12-c033a33d3ed2">단기 스케줄링</h4><p>- 프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업을 의미한다.<br>- 프로세서 스케줄링 (Processor Scheduling), 하위 스케줄링이라고도 한다.<br>- 프로세서 스케줄링 및 문맥 교환은 프로세서 스케줄러에 의해 수행된다.</p><div data-type="horizontalRule"><hr></div><h3 id="f8ba0f46-6e19-467b-8274-23d3edf9eb7d" data-toc-id="f8ba0f46-6e19-467b-8274-23d3edf9eb7d">프로세서(스) 스케줄링의 기법</h3><h4 id="b0f275fc-0e28-474a-a68d-b58a353423af" data-toc-id="b0f275fc-0e28-474a-a68d-b58a353423af">비선점 (Non-Preemptive) 스케줄링</h4><p>이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법이다.</p><ul><li><p>프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다.</p></li><li><p>모든 프로세스에 대한 요구를 공정하게 처리할 수 있다.</p></li><li><p>프로세스 응답 시간의 예측이 용이하며, 일괄 처리방식에 적합하다.</p></li><li><p>중요한 작업 (짧은 작업)이 중요하지 않은 작업 (긴 작업)을 기다리는 경우가 발생할 수 있다.</p></li></ul><blockquote><p>비선점 스케줄링의 종류에는 <code spellcheck="false">FCFS</code>, <code spellcheck="false">SJF</code>, 우선순위, <code spellcheck="false">HRN</code>, 기한부 등의 알고리즘이 있다.</p></blockquote><h4 id="de57d335-cc61-4fe1-bf35-07aee24dc929" data-toc-id="de57d335-cc61-4fe1-bf35-07aee24dc929">선점 (Preemptive) 스케줄링</h4><p>하나의 프로세스가 CPU를 할당받아 실행하고 있을 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케줄링 기법이다.</p><ul><li><p>우선순위가 높은 프로세스를 빠르게 처리할 수 있다.</p></li><li><p>주로 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 사용된다.</p></li><li><p>많은 오버헤드(Overhead)를 초래한다.</p></li><li><p>선점이 가능하도록 일정 시간 배당에 대한 인터럽트용 타이머 클록(Clock)이 필요하다.</p></li></ul><blockquote><p>선점 스케줄링의 종류에는 <code spellcheck="false">Round Robin</code>, <code spellcheck="false">SRT</code>, 선점 우선순위, 다단계 큐, 다단계 피드백 큐 등의 알고리즘이 있다.</p></blockquote><div data-type="horizontalRule"><hr></div><h3 id="99ea2c53-5728-4de7-8083-43457e8a016e" data-toc-id="99ea2c53-5728-4de7-8083-43457e8a016e">주요 스케줄링 기법</h3><h4 id="c7066876-3d7f-4aa1-ac08-08aacacdaf86" data-toc-id="c7066876-3d7f-4aa1-ac08-08aacacdaf86">FCFS <strong>(First Come First Service, 선입 선출) = FIFO (First In First Out)</strong></h4><p>준비상태 큐 (대기 큐, 준비 완료 리스트, 작업준비 큐, 스케줄링 큐)에 도착한 순서에 따라 차례로 CPU를 할당하는 기법으로, 가장 간단한 알고리즘이다.</p><p>- 먼저 도착한 것이 먼저 처리되어 공평성은 유지되지만 짧은 작업이 긴 작업을 기다리게 된다.<br>또한, 중요한 작업이 중요하지 않은 작업을 기다리게 된다.</p><blockquote><p>문제 1. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, <code spellcheck="false">FCFS</code> 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오.<br>(제출시간은 없으며 시간의 단위는 초이다.)</p><table style="min-width: 100px"><colgroup><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p>프로세스 번호</p></td><td colspan="1" rowspan="1"><p>P1</p></td><td colspan="1" rowspan="1"><p>P2</p></td><td colspan="1" rowspan="1"><p>P3</p></td></tr><tr><td colspan="1" rowspan="1"><p>실행 시간</p></td><td colspan="1" rowspan="1"><p>20</p></td><td colspan="1" rowspan="1"><p>4</p></td><td colspan="1" rowspan="1"><p>6</p></td></tr></tbody></table><p>1. 실행 시간을 이용하여 다음과 같이 각 프로세스의 대기 시간과 반환 시간을 구한다.<br>1.1. 대기 시간 : 프로세스가 대기한 시간으로, 바로 앞 프로세스까지의 진행 시간으로 계산<br>1.2. 반환 시간 : 프로세스의 대기 시간과 실행 시간의 합<br>2. 실행 시간, 대기 시간, 반환 시간의 평균은 <code spellcheck="false">각 프로세스 시간의 합 / 프로세스의 개수</code>를 이용한다.</p><img src="https://image.until.blog/jsw9330/article/1744609237862.png" data-width="75%" data-align="left" alt="5137"><p><strong>평균 실행 = (20 + 4 + 6) / 3 = 10<br>평균 대기 = (0 + 20 + 24) / 3 = 14.6<br>평균 반환 = (20 + 24 + 30) / 3 = 24.6</strong></p></blockquote><div data-type="horizontalRule"><hr></div><h4 id="7e2c718f-d0e9-4eff-a013-f039d61ca64c" data-toc-id="7e2c718f-d0e9-4eff-a013-f039d61ca64c">SJF<strong> (Shortest Job First, 단기 작업 우선)</strong></h4><p>SJF는 준비상태 큐에서 기다리고 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법이다.</p><blockquote><p><strong>문제 1. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, SJF 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오.<br>(제출 시간이 없을 경우)</strong></p><table style="min-width: 100px"><colgroup><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p>프로세스 번호</p></td><td colspan="1" rowspan="1"><p>P1</p></td><td colspan="1" rowspan="1"><p>P2</p></td><td colspan="1" rowspan="1"><p>P3</p></td></tr><tr><td colspan="1" rowspan="1"><p>실행 시간</p></td><td colspan="1" rowspan="1"><p>20</p></td><td colspan="1" rowspan="1"><p>4</p></td><td colspan="1" rowspan="1"><p>6</p></td></tr></tbody></table><p>1. 실행 시간이 짧은 프로세스를 먼저 처리하도록 이동시킨 후 각 프로세스의 대기시간과 반환 시간을 구한다.<br>2. 실행 시간, 대기 시간, 반환 시간, 각 시간의 평균은 FCFS의 방법과 동일하게 구한다.</p><img src="https://image.until.blog/jsw9330/article/1744609251897.png" data-width="75%" data-align="left" alt="5138"><p><strong>평균 실행 = (20 + 4 + 6) / 3 = 10<br>평균 대기 = (0 + 4 + 10) / 3 = 4.6<br>평균 반환 = (4 + 10 + 30) / 3 = 14.6</strong></p><div data-type="horizontalRule"><hr></div><p><strong>문제 2. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, SJF 기법을 이용하여 평균 실행 시간, 평균 대기 시간, 평균 반환 시간을 구하시오.<br>(제출 시간이 있을 경우)</strong></p><table style="min-width: 100px"><colgroup><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p>프로세스 번호</p></td><td colspan="1" rowspan="1"><p>P1</p></td><td colspan="1" rowspan="1"><p>P2</p></td><td colspan="1" rowspan="1"><p>P3</p></td></tr><tr><td colspan="1" rowspan="1"><p>실행 시간</p></td><td colspan="1" rowspan="1"><p>20</p></td><td colspan="1" rowspan="1"><p>7</p></td><td colspan="1" rowspan="1"><p>4</p></td></tr><tr><td colspan="1" rowspan="1"><p>도착 시간</p></td><td colspan="1" rowspan="1"><p>0</p></td><td colspan="1" rowspan="1"><p>1</p></td><td colspan="1" rowspan="1"><p>2</p></td></tr></tbody></table><p>1. 가장 먼저 도착한 P1을 실행한 후 요구된 실행 시간이 적은 P3, P2 순으로 수행한다.<br>2. 대기 시간은 현재 프로세스가 수행되기 전까지의 진행 시간에서 도착 시간을 차감하고, 반환시간은 실행 시간과 대기 시간의 합으로 구한다.</p><img src="https://image.until.blog/jsw9330/article/1744689912878.png" data-width="75%" data-align="left" alt="5165"><p><strong>평균 실행 = (20 + 4 + 7) / 3 = 10.3<br>평균 대기 = (0 + 18 + 23) / 3 = 13.6<br>평균 반환 = (20 + 22 + 30) / 3 = 24</strong></p></blockquote><div data-type="horizontalRule"><hr></div><h4 id="40267d15-f71b-46e7-9e0a-24c3a04bbb85" data-toc-id="40267d15-f71b-46e7-9e0a-24c3a04bbb85">HRN (Highest Response-ratio Next)</h4><p>HRN은 실행 시간이 킨 프로세스에 불리한 SJF 기법을 보완하기 위한 것으로,<br>대기 시간과 서비스 (실행) 시간을 이용하는 기법이다.</p><p>우선순위를 계산하여 그 숫자가 가장 높은 것부터 낮은 순으로 우선순위가 부여된다.</p><img src="https://image.until.blog/jsw9330/article/1744609486453.png" data-width="75%" data-align="left" alt="5139"><blockquote><p>문제 1. 다음과 같은 프로세스가 HRN 기법으로 스케줄링될 때 우선순위를 계산하시오.</p><table style="min-width: 100px"><colgroup><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p>프로세스 번호</p></td><td colspan="1" rowspan="1"><p>P1</p></td><td colspan="1" rowspan="1"><p>P2</p></td><td colspan="1" rowspan="1"><p>P3</p></td></tr><tr><td colspan="1" rowspan="1"><p>실행 시간</p></td><td colspan="1" rowspan="1"><p>20</p></td><td colspan="1" rowspan="1"><p>4</p></td><td colspan="1" rowspan="1"><p>6</p></td></tr><tr><td colspan="1" rowspan="1"><p>대기 시간</p></td><td colspan="1" rowspan="1"><p>10</p></td><td colspan="1" rowspan="1"><p>20</p></td><td colspan="1" rowspan="1"><p>10</p></td></tr><tr><td colspan="1" rowspan="1"><p>우선순위 계산</p></td><td colspan="1" rowspan="1"><p>(10 + 20) / 20 = 1.5</p></td><td colspan="1" rowspan="1"><p>(20 + 4) / 4 = 6</p></td><td colspan="1" rowspan="1"><p>(10 + 6) / 6 = 2.6</p></td></tr></tbody></table><p><strong>우선순위 : P2 &gt; P3 &gt; P1</strong></p></blockquote><div data-type="horizontalRule"><hr></div><h4 id="5f32efb7-227b-4bc9-98d5-4f7290a8013b" data-toc-id="5f32efb7-227b-4bc9-98d5-4f7290a8013b">RR (Round Robin)</h4><p>RR (Round Robin)은 시분할 시스템 (Time Sharing System)을 위해 고안된 방식으로, FCFS 알고리즘을 선점 (Preemptive) 형태로 변형한 기법이다.</p><p>할당되는 시간이 클 경우 FCFS 기법과 같아지고, 할당되는 시간이 작을 경우 문맥 교환 및 오버헤드가 자주 발생된다.</p><blockquote><p>문제 1. 다음과 같은 프로세스들이 차례로 준비상태 큐에 들어왔다고 가정할 때, 평균 대기 시간, 평균 반환 시간을 구하시오.<br>(단, Time Slice는 4초이다.)</p><table style="min-width: 100px"><colgroup><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p>프로세스 번호</p></td><td colspan="1" rowspan="1"><p>P1</p></td><td colspan="1" rowspan="1"><p>P2</p></td><td colspan="1" rowspan="1"><p>P3</p></td></tr><tr><td colspan="1" rowspan="1"><p>실행 시간</p></td><td colspan="1" rowspan="1"><p>20</p></td><td colspan="1" rowspan="1"><p>4</p></td><td colspan="1" rowspan="1"><p>6</p></td></tr></tbody></table><p>1. 주어진 시간 할당량 (Time Slice) 동안 실행되지 못할 경우 준비상태 큐의 가장 마지막으로 재배치하여 차례를 기다리므로 다음과 같이 표시할 수 있다.</p><img src="https://image.until.blog/jsw9330/article/1744690737014.png" data-width="75%" data-align="left" alt="5167"><p>2. 반환 시간 : 각 프로세스가 완료되는 시간을 이용하여 구한다.<br>3. 대기 시간 : 대기 시간을 구하고자 하는 프로세스의 가장 마지막 실행이 시작되기 전까지의 진행 시간을 이용하여 구하되, 해당 프로세스가 앞에서 여러 번 실행되었을 경우 실행된 시간은 제외한다.</p><table style="min-width: 125px"><colgroup><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"><col style="min-width: 25px"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p>프로세스 번호</p></td><td colspan="1" rowspan="1"><p>P1</p></td><td colspan="1" rowspan="1"><p>P2</p></td><td colspan="1" rowspan="1"><p>P3</p></td><td colspan="1" rowspan="1"><p>평균</p></td></tr><tr><td colspan="1" rowspan="1"><p>반환 시간</p></td><td colspan="1" rowspan="1"><p>30</p></td><td colspan="1" rowspan="1"><p>8</p></td><td colspan="1" rowspan="1"><p>18</p></td><td colspan="1" rowspan="1"><p>56 / 3 = 18.6</p></td></tr><tr><td colspan="1" rowspan="1"><p>대기 시간</p></td><td colspan="1" rowspan="1"><p>26 - 16 = 10</p></td><td colspan="1" rowspan="1"><p>4</p></td><td colspan="1" rowspan="1"><p>16 - 4 = 12</p></td><td colspan="1" rowspan="1"><p>26 / 3 = 8.6</p></td></tr></tbody></table></blockquote>

프로세스가 생성되여 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업을 의미한다.프로세스가 생성되어 완료될 때까지 프로세스는 여러 종류의 스케줄링 과정을 거치게 된다.스케줄링 종류장기 스케줄링- 어떤 프로세스가 시스템의 자원을 차지할 수 있도록 할 것인가를 결정하여 준비상태 큐로 보내는 작업을 의미한다.- 작업 스케줄링 (Job Sch