[운영체제/OS] CPU 스케줄링

한국어

<h1 id="cpu-스케줄링">CPU 스케줄링</h1> <p>다중 프로그래밍 방식의 운영체제는 하나의 주기억 장소에 여러 개의 프로세스가 실행된다. 여러 개의 프로세스가 실행되지만, 컴퓨터 시스템에서 보유하고 있는 자원들은 극히 <strong>제한적</strong>이다.</p> <p>　 이러한 제한된 환경 아래서 최적의 효과를 보기 위해서는 <strong>프로세스의 계획적인 실행 순서</strong>가 필요하다. 이러한 계획적인 실행 순서를 CPU 스케줄링 혹은 프로세스 스케줄링이라고 한다.</p> <h2 id="스케줄링-목적">스케줄링 목적</h2> <p>CPU나 자원을 효과적이며 생산성 있게 사용하기 위한 소프트웨어적 계획을 의미. 이러한 프로세스 스케줄링은 필요한 하드웨어 레지스터를 설정함으로써 프로세스에게 CPU를 할당하고 <a href="/study/os-interrupt/#문맥-교환context-switching">문맥 교환</a>을 하는 프로세스 관리 기능이다</p> <ul> <li>모든 프로세스들에게 공정하게 배정해야 한다(<strong>공정성</strong>)</li> <li>단위 시간당 가능한 <strong>최대한 많은 양이 처리</strong>될 수 있도록 해야 한다</li> <li>응답 시간이 <strong>신속</strong>해야 한다</li> <li>같은 종류의 작업은 거의 같은 시간과 비용으로 실행될 수 있어야 한다</li> <li><strong>오버헤드를 최소화</strong>해야 한다</li> <li>시스템 내 <strong>자원을 사용하지 않는 시간이 없도록 유지</strong>해야 한다</li> <li>응답 시간과 자원의 활용 간 적절한 균형이 유지되도록 해야 한다</li> <li>프로세스가 무한정 기다리게 하는 것을 피해야 한다</li> <li>프로세스의 상태를 파악하여 우선순위를 부여하는 것이 좋다</li> <li>중요 자원을 차지하고 있는 프로세스에 우선권을 부여해야 한다</li> <li>문제로 인해 불안하지 않은 프로세스에 서비스를 많이 제공하도록 한다</li> <li>부하가 많은 경우 갑자기 체증이 발생하지 않도록 조절해야 한다</li> </ul> <h2 id="스케줄링-평가-기준">스케줄링 평가 기준</h2> <ul> <li>시스템 관점 <ul> <li>CPU 이용률 : <i class="fas fa-search-plus"></i><strong>최대화</strong></li> <li>처리 능력(Throughput) : 단위 시간당 처리할 수 있는 CPU의 작업량 <i class="fas fa-search-plus"></i><strong>최대화</strong></li> </ul> </li> <li>프로세스 관점 <ul> <li>대기(Waiting) 시간 : 준비 상태에서 대기하는 시간 <i class="fas fa-search-minus"></i><strong>최소화</strong></li> <li>응답(Response) 시간 : 입력에 대해 처음 반응하는 시간 <i class="fas fa-search-minus"></i><strong>최소화</strong></li> <li>반환(Turn-around) 시간 : 작업을 지시하고 결과가 되돌아오는 시간 <i class="fas fa-search-minus"></i><strong>최소화</strong></li> </ul> </li> </ul> <h2 id="스케줄링-알고리즘">스케줄링 알고리즘</h2> <p>다중 프로그래밍 방식은 메모리에 여러 개의 프로그램을 적재함으로써 CPU와 I/O 장치들의 유휴 시간을 줄여 사용 효율을 높이는 방식이다. 이러한 다중 프로그래밍 방식에서 <strong>CPU의 사용률과 처리율을 최대화 하기 위한 방법</strong>들을 프로세스 스케줄링 알고리즘이라고 한다</p> <h3 id="비선점형-방식non-preemptive">비선점형 방식(Non-Preemptive)</h3> <p>현재 실행 중인 프로세스가 자발적으로 CPU를 중단하는 경우에만 CPU 스케줄링을 수행하는 방법</p> <ul> <li>일괄처리 방식에 적당</li> <li>대화형/시간 분할/실시간 시스템 부적합</li> <li>응답 시간 예측이 어렵다</li> <li>문맥 교환이 적어 오버헤드가 적다</li> </ul> <h4 id="fcfsfirst-come-first-served-fifo-first-input-first-out">FCFS(First Come First Served, FIFO: First Input First Out)</h4> <p>먼저 입력된 작업을 먼저 처리하는 방식</p> <ul> <li>가장 대표적인 비선점형 방식</li> <li>공평하고 구현이 간단하나, 평균 반환 시간이 길다</li> <li>짧은 작업이나 중요한 작업이 지연될 수 있다</li> </ul> <h4 id="sjfshortest-job-first-최단-작업-우선">SJF(Shortest Job First, 최단 작업 우선)</h4> <p>작업이 끝나기까지의 실행 시간 추정치가 가장 작은 작업을 먼저 실행시키는 방식. 비선점형이기 때문에 긴 작업일지라도 이미 CPU를 점유하고 있다면 뒤로 밀려나지 않고 처리되고 다음 작업들을 대상으로 재정리를 수행한다</p> <ul> <li>평균 대기 시간을 최소화한다</li> <li>프로세스의 다음 CPU 사용시간을 예측해야하는 어려움이 있다</li> <li>긴 작업의 경우 계속해서 입력되는 짧은 작업들 때문에 우선순위가 계속 밀려나게 되고 <strong>무한 연기 상태</strong>가 발생하기도 한다</li> <li>위 무한 연기 현상을 방지하기 위해 <strong>에이징(Aging)</strong>^{<i class="fa fa-info-circle" aria-hidden="true"></i>} 기법을 사용하여 해결</li> </ul> <p class="notice--warning"><strong>에이징 기법</strong> : 자원이 할당되기를 오랜 시간 동안 기다린 프로세스는 기다린 시간에 비례하는 높은 우선순위를 부여하여 가까운 시간 안에 자원이 할당되도록 하는 기법</p> <h4 id="hrnhighest-response-ratio-next">HRN(Highest Response-ratio Next)</h4> <p>실행 시간 추정과 선점 기능 때문에 스케줄러가 복잡해지고 남은 계산 시간들을 저장해 놓아야 한다는 단점을 보완, 서비스 시간(실행 시간 추정치)과 대기 시간의 비율을 고려한 스케줄링 방식</p> <blockquote> <p>우선순위 = $\frac{대기 시간 + 서비스 시간}{서비스 시간}$</p> </blockquote> <ul> <li>SJF를 개선한 방식</li> <li>우선 순위 계산 공식을 이용하며, 계산된 값이 가장 큰 작업에게 우선권을 부여</li> </ul> <h4 id="우선순위priority">우선순위(Priority)</h4> <p>대기 리스트에 있는 프로세스들에게 작업의 우선순위를 부여하여 CPU를 할당하는 방법</p> <ul> <li>고정적 우선순위와 동적 우선순위 방식이 존재</li> <li>기아 현상, 무한 봉쇄 현상 발생 가능</li> </ul> <h4 id="기한부deadline">기한부(Deadline)</h4> <p>제한된 시간 내에 반드시 작업이 완료되도록 스케줄링하는 방식. 제한된 시간을 정확히 추정하여 그 시간 만큼에 CPU 사용 시간을 제한한다. 작업이 제한 시간 내에 처리되지 않으면 다시는 해당 작업이 CPU 사용 시간을 합당받을 수 없다</p> <ul> <li>프로세스들이 마감 시간 내에 처리되지 않으면 폐기되거나 처음부터 다시 실행 필요</li> <li>기한부 스케줄링에 필요한 집약적 자원 관리는 많은 오버헤드를 일으킬 수 있다</li> <li>동시에 다수의 기한부 작업이 수행되면 스케줄링은 매우 어려워질 수 있다</li> <li>사용자는 작업에 필요한 자원의 정확한 정보를 시스템에 제시하여야 한다</li> </ul> <h3 id="선점형-방식preemtive">선점형 방식(Preemtive)</h3> <p>하나의 프로세스가 다른 프로세스 대신에 CPU를 차지할수 있다</p> <ul> <li>대화형, 시간 분할, 실시간 시스템에 적합</li> <li>응답 시간 예측이 용이하다</li> <li>문맥 교환이 많아 오버헤드가 많다</li> </ul> <h4 id="라운드-로빈rr-round-robin">라운드 로빈(RR, Round-Robin)</h4> <p><a href="/study/os-development-process/#시분할-처리time-sharing-processing-시스템">시분할 시스템</a>을 위해 고안되었으며 여러 개의 프로세스가 10 ~ 100msec 정도의 시간 할당량(Quantum, Time Slice)이라는 작은 단위 시간이 정의되어 시간 할당량만큼씩 CPU를 사용하는 방식</p> <ul> <li>FIFO 스케줄링을 선점형으로 변환한 방식</li> <li>적절한 응답 시간을 보장해주는 대화식 사용자에게 효과적</li> </ul> <p><br /></p> <ul> <li>시간 할당량이 클 때, <i class="fas fa-search-plus"></i> <ul> <li>FIFO 방식과 거의 같은 형태가 된다</li> </ul> </li> <li>시간 할당량이 작을 때, <i class="fas fa-search-minus"></i> <ul> <li>프로세스 간의 전이가 많아지므로 프로세스가 전이되는 과정에서 필요한 문맥 교환 수 증가</li> <li>실행 시간보다 문맥 교환의 교체에 사용되는 부가적인 시간이 증가하게 되므로 오버헤드가 증가</li> <li>프로세서의 교환에서 시간을 소비하고 실제 사용자들의 연산은 거의 못하는 결과를 초래</li> </ul> </li> </ul> <h4 id="srtshortest-remaining-time">SRT(Shortest Remaining Time)</h4> <p>작업이 끝나기까지 <strong>남아 있는</strong> 실행 시간의 추정치가 가장 작은 프로세스를 먼저 실행하는 방식으로 <strong>새로 입력되는 작업까지도 포함</strong>된다.</p> <ul> <li>실행 시간 추적과 서비스 받은 시간을 기록해야 하므로 오버헤드가 증가</li> <li>임계치(Threshold Value)^{<i class="fa fa-info-circle" aria-hidden="true"></i>}를 사용</li> </ul> <p class="notice--warning"><strong>임계치</strong> : CPU를 사용 중인 프로세스가 거의 마지막에 이르렀을 때 남아 있는 시간보다 조금 작은 프로세스가 입력된다면 <strong>순수 SRT는 조금 작은 프로세스에게 CPU 사용 권한을 넘겨주어야</strong> 한다. 하지만 이럴 경우 <strong>문맥 교환 횟수나 전체 정황으로 보았을 때</strong> 현재 현재 작업 중인 프로세스를 모두 마치고 조금 <strong>작은 프로세스를 다음에 처리하는 것이 더 효율적</strong>일 것이다. 이러한 경우를 <strong>추정해서 공식에 적용시켜 얻어진 수치</strong>를 의미한다</p> <h4 id="다단계-큐mq-multi-level-queue">다단계 큐(MQ, Multi-level Queue)</h4> <p><a href="../../assets/images/os/mulitlevel-queue.png" title="https://www.includehelp.com/operating-systems/multilevel-queue-scheduling-in-operating-system.aspx"><img src="../../assets/images/os/mulitlevel-queue.png" alt="" title="다단계(멀티레벨) 큐" class="align-center" /></a></p> <p>준비 큐를 여러 종류의 그룹으로 나누고 여러 개의 큐에 다양한 알고리즘을 적용하는 스케줄링 기법. 일반적으로 멀티레벨 큐에서 준비 큐는 대화형 작업을 담기 위한 <strong>전위 큐(Foreground Queue)</strong>와 계산 위주의 작업을 담기 위한 <strong>후위 큐(Background Queue)</strong>로 분할되어 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어가며 우선순위가 낮은 하위 단계 큐의 작업은 실행중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏기는 선점 방식이다</p> <ul> <li>선점, 비선점 방식</li> <li>정적 우선순위를 사용하는 스케줄링을 구현 할 때 가장 적합</li> <li>서로 다른 우선순위의 프로세스들을 구별하고 관리하기 위해 우선순위의 개수만큼 큐가 필요</li> <li>큐를 특성별로 여러 개 가지며, 각 독립적인 스케줄링을 가진다</li> <li>큐 간에 <strong>프로세스가 이동이 안된다</strong></li> <li>우선순위가 가장 높은 큐에서는 비선점형으로 사용</li> </ul> <h4 id="다단계-피드백-큐mfq-multi-level-feedback-queue">다단계 피드백 큐(MFQ, Multi level Feedback Queue)</h4> <p><a href="../../assets/images/os/multilevel-feedback-queue.png"><img src="../../assets/images/os/multilevel-feedback-queue.png" alt="" title="다단계(멀티레벨) 피드백 큐" class="align-center" /></a></p> <p>짧은 작업이나 입출력 위주의 작업에 우선권을 부여하기 위해 개발된 방식으로 적응 기법의 개념을 적용. 큐 간에 프로세스가 이동이 불가한 다단계 큐(MQ)의 단점을 보완</p> <ul> <li>큐마다 시간 할당량이 존재하며 <strong>낮은 큐일수록 시간 할당량은 커진다</strong></li> <li>각각의 큐들은 종속적으로 연결되어 있다</li> <li>CPU를 시간 할당량만큼 사용한 프로세스는 낮은 큐로 이동</li> <li>맨 위에 큐는 <strong>RR방식</strong>을 사용, 맨 마지막 큐는 <strong>FCFS방식</strong> 사용</li> <li>우선순위가 낮은 프로세스는 계속 지연되는 <strong>기아(Starvation) 현상</strong>이 발생할 수 있다 <i class="far fa-hand-point-right"></i> <strong>Aging 기법</strong> 사용으로 해결</li> </ul>

CPU 스케줄링

다중 프로그래밍 방식의 운영체제는 하나의 주기억 장소에 여러 개의 프로세스가 실행된다. 여러 개의 프로세스가 실행되지만, 컴퓨터 시스템에서 보유하고 있는 자원들은 극히 제한적이다.

　 이러한 제한된 환경 아래서 최적의 효과를 보기 위해서는 프로세스의 계획적인 실행 순서가 필요하다. 이러한 계획적인 실행 순서를 CPU 스케줄링 혹은 프로세스 스케줄링이라고 한다.

스케줄링 목적

CPU나 자원을 효과적이며 생산성 있게 사용하기 위한 소프트웨어적 계획을 의미. 이러한 프로세스 스케줄링은 필요한 하드웨어 레지스터를 설정함으로써 프로세스에게 CPU를 할당하고 문맥 교환을 하는 프로세스 관리 기능이다

• 모든 프로세스들에게 공정하게 배정해야 한다(공정성)
• 단위 시간당 가능한 최대한 많은 양이 처리될 수 있도록 해야 한다
• 응답 시간이 신속해야 한다
• 같은 종류의 작업은 거의 같은 시간과 비용으로 실행될 수 있어야 한다
• 오버헤드를 최소화해야 한다
• 시스템 내 자원을 사용하지 않는 시간이 없도록 유지해야 한다
• 응답 시간과 자원의 활용 간 적절한 균형이 유지되도록 해야 한다
• 프로세스가 무한정 기다리게 하는 것을 피해야 한다
• 프로세스의 상태를 파악하여 우선순위를 부여하는 것이 좋다
• 중요 자원을 차지하고 있는 프로세스에 우선권을 부여해야 한다
• 문제로 인해 불안하지 않은 프로세스에 서비스를 많이 제공하도록 한다
• 부하가 많은 경우 갑자기 체증이 발생하지 않도록 조절해야 한다

스케줄링 평가 기준

• 시스템 관점
  • CPU 이용률 : 최대화
  • 처리 능력(Throughput) : 단위 시간당 처리할 수 있는 CPU의 작업량 최대화
• 프로세스 관점
  • 대기(Waiting) 시간 : 준비 상태에서 대기하는 시간 최소화
  • 응답(Response) 시간 : 입력에 대해 처음 반응하는 시간 최소화
  • 반환(Turn-around) 시간 : 작업을 지시하고 결과가 되돌아오는 시간 최소화

스케줄링 알고리즘

다중 프로그래밍 방식은 메모리에 여러 개의 프로그램을 적재함으로써 CPU와 I/O 장치들의 유휴 시간을 줄여 사용 효율을 높이는 방식이다. 이러한 다중 프로그래밍 방식에서 CPU의 사용률과 처리율을 최대화 하기 위한 방법들을 프로세스 스케줄링 알고리즘이라고 한다

비선점형 방식(Non-Preemptive)

현재 실행 중인 프로세스가 자발적으로 CPU를 중단하는 경우에만 CPU 스케줄링을 수행하는 방법

• 일괄처리 방식에 적당
• 대화형/시간 분할/실시간 시스템 부적합
• 응답 시간 예측이 어렵다
• 문맥 교환이 적어 오버헤드가 적다

FCFS(First Come First Served, FIFO: First Input First Out)

먼저 입력된 작업을 먼저 처리하는 방식

• 가장 대표적인 비선점형 방식
• 공평하고 구현이 간단하나, 평균 반환 시간이 길다
• 짧은 작업이나 중요한 작업이 지연될 수 있다

SJF(Shortest Job First, 최단 작업 우선)

작업이 끝나기까지의 실행 시간 추정치가 가장 작은 작업을 먼저 실행시키는 방식. 비선점형이기 때문에 긴 작업일지라도 이미 CPU를 점유하고 있다면 뒤로 밀려나지 않고 처리되고 다음 작업들을 대상으로 재정리를 수행한다

• 평균 대기 시간을 최소화한다
• 프로세스의 다음 CPU 사용시간을 예측해야하는 어려움이 있다
• 긴 작업의 경우 계속해서 입력되는 짧은 작업들 때문에 우선순위가 계속 밀려나게 되고 무한 연기 상태가 발생하기도 한다
• 위 무한 연기 현상을 방지하기 위해 에이징(Aging) 기법을 사용하여 해결

에이징 기법 : 자원이 할당되기를 오랜 시간 동안 기다린 프로세스는 기다린 시간에 비례하는 높은 우선순위를 부여하여 가까운 시간 안에 자원이 할당되도록 하는 기법

HRN(Highest Response-ratio Next)

실행 시간 추정과 선점 기능 때문에 스케줄러가 복잡해지고 남은 계산 시간들을 저장해 놓아야 한다는 단점을 보완, 서비스 시간(실행 시간 추정치)과 대기 시간의 비율을 고려한 스케줄링 방식

우선순위 = $\frac{대기 시간 + 서비스 시간}{서비스 시간}$

• SJF를 개선한 방식
• 우선 순위 계산 공식을 이용하며, 계산된 값이 가장 큰 작업에게 우선권을 부여

우선순위(Priority)

대기 리스트에 있는 프로세스들에게 작업의 우선순위를 부여하여 CPU를 할당하는 방법

• 고정적 우선순위와 동적 우선순위 방식이 존재
• 기아 현상, 무한 봉쇄 현상 발생 가능

기한부(Deadline)

제한된 시간 내에 반드시 작업이 완료되도록 스케줄링하는 방식. 제한된 시간을 정확히 추정하여 그 시간 만큼에 CPU 사용 시간을 제한한다. 작업이 제한 시간 내에 처리되지 않으면 다시는 해당 작업이 CPU 사용 시간을 합당받을 수 없다

• 프로세스들이 마감 시간 내에 처리되지 않으면 폐기되거나 처음부터 다시 실행 필요
• 기한부 스케줄링에 필요한 집약적 자원 관리는 많은 오버헤드를 일으킬 수 있다
• 동시에 다수의 기한부 작업이 수행되면 스케줄링은 매우 어려워질 수 있다
• 사용자는 작업에 필요한 자원의 정확한 정보를 시스템에 제시하여야 한다

선점형 방식(Preemtive)

하나의 프로세스가 다른 프로세스 대신에 CPU를 차지할수 있다

• 대화형, 시간 분할, 실시간 시스템에 적합
• 응답 시간 예측이 용이하다
• 문맥 교환이 많아 오버헤드가 많다

라운드 로빈(RR, Round-Robin)

시분할 시스템을 위해 고안되었으며 여러 개의 프로세스가 10 ~ 100msec 정도의 시간 할당량(Quantum, Time Slice)이라는 작은 단위 시간이 정의되어 시간 할당량만큼씩 CPU를 사용하는 방식

• FIFO 스케줄링을 선점형으로 변환한 방식
• 적절한 응답 시간을 보장해주는 대화식 사용자에게 효과적

• 시간 할당량이 클 때,
  • FIFO 방식과 거의 같은 형태가 된다
• 시간 할당량이 작을 때,
  • 프로세스 간의 전이가 많아지므로 프로세스가 전이되는 과정에서 필요한 문맥 교환 수 증가
  • 실행 시간보다 문맥 교환의 교체에 사용되는 부가적인 시간이 증가하게 되므로 오버헤드가 증가
  • 프로세서의 교환에서 시간을 소비하고 실제 사용자들의 연산은 거의 못하는 결과를 초래

SRT(Shortest Remaining Time)

작업이 끝나기까지 남아 있는 실행 시간의 추정치가 가장 작은 프로세스를 먼저 실행하는 방식으로 새로 입력되는 작업까지도 포함된다.

• 실행 시간 추적과 서비스 받은 시간을 기록해야 하므로 오버헤드가 증가
• 임계치(Threshold Value)를 사용

임계치 : CPU를 사용 중인 프로세스가 거의 마지막에 이르렀을 때 남아 있는 시간보다 조금 작은 프로세스가 입력된다면 순수 SRT는 조금 작은 프로세스에게 CPU 사용 권한을 넘겨주어야 한다. 하지만 이럴 경우 문맥 교환 횟수나 전체 정황으로 보았을 때 현재 현재 작업 중인 프로세스를 모두 마치고 조금 작은 프로세스를 다음에 처리하는 것이 더 효율적일 것이다. 이러한 경우를 추정해서 공식에 적용시켜 얻어진 수치를 의미한다

다단계 큐(MQ, Multi-level Queue)

준비 큐를 여러 종류의 그룹으로 나누고 여러 개의 큐에 다양한 알고리즘을 적용하는 스케줄링 기법. 일반적으로 멀티레벨 큐에서 준비 큐는 대화형 작업을 담기 위한 전위 큐(Foreground Queue)와 계산 위주의 작업을 담기 위한 후위 큐(Background Queue)로 분할되어 프로세스들은 자신의 우선순위 값에 해당하는 큐에 들어가며 우선순위가 낮은 하위 단계 큐의 작업은 실행중이더라도 상위 단계 큐에 프로세스가 도착하면 CPU를 뺏기는 선점 방식이다

• 선점, 비선점 방식
• 정적 우선순위를 사용하는 스케줄링을 구현 할 때 가장 적합
• 서로 다른 우선순위의 프로세스들을 구별하고 관리하기 위해 우선순위의 개수만큼 큐가 필요
• 큐를 특성별로 여러 개 가지며, 각 독립적인 스케줄링을 가진다
• 큐 간에 프로세스가 이동이 안된다
• 우선순위가 가장 높은 큐에서는 비선점형으로 사용

다단계 피드백 큐(MFQ, Multi level Feedback Queue)

짧은 작업이나 입출력 위주의 작업에 우선권을 부여하기 위해 개발된 방식으로 적응 기법의 개념을 적용. 큐 간에 프로세스가 이동이 불가한 다단계 큐(MQ)의 단점을 보완

• 큐마다 시간 할당량이 존재하며 낮은 큐일수록 시간 할당량은 커진다
• 각각의 큐들은 종속적으로 연결되어 있다
• CPU를 시간 할당량만큼 사용한 프로세스는 낮은 큐로 이동
• 맨 위에 큐는 RR방식을 사용, 맨 마지막 큐는 FCFS방식 사용
• 우선순위가 낮은 프로세스는 계속 지연되는 기아(Starvation) 현상이 발생할 수 있다 Aging 기법 사용으로 해결