[운영체제와 정보기술의 원리] 06장. CPU 스케줄링

CPU는 프로그램의 기계어 명령을 처리하는 장치이다. 프로그램이 메모리에 올라가면 PC에 수행할 코드의 메모리 주소값을 가지게 되고, CPU는 PC가 가리키는 주소의 기계어 명령을 하니씩 수행한다. 기계어 명령은 CPU 내에서 수행되는 명령, 메모리 접근을 필요로 하는 명령, 입출력을 동반하는 명령으로 나누어 볼 수 있다.

CPU 내에서 수행되는 명령은 Add같은 것이 있다. 메모리 접근을 수행하는 명령은 Load, Store 명령이 있다. 입출력을 동반하는 명령은 디스크 읽기, 키보드 입력등이 있다. 다만 입출력 명령을 특권명령으로 규정하여 사용자 프로그램이 직접 수행할 수 없도록 하고, 운영체제를 통해 서비스를 대행하도록 한다. 

CPU 버스트와 I/O 버스트의 모습

사용자 프로그램은 CPU 작업과 I/O 작업의 반복으로 구성된다. 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계인 CPU 버스트와 I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계인 I/O 버스트로 구성된다. 

 

CPU 스케줄러

CPU 스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제의 코드이다. CPU 스케줄링은 다음과 같은 경우에 필요하게 된다.

• 실행 상태에 있던 프로세스가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우(비선점)
• 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우(선점)
• I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우(선점)
• CPU에서 실행 상태에 있는 프로세스가 종료되는 경우(비선점)

  CPU 스케줄링에는 CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지 않는 비선점과 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 선점이 있다. 

 

디스패처

CPU 스케줄러가 어떤 프로세스에게 CPU를 할당할지 경정하고나면 CPU를 실제로 이양하는 작업이 필요하다. 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정하는 운영체제의 코드를 디스패처라고 부른다. 디스패처는 현재 수행중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고, 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그프로세스에게 CPU를 넘기는 과정을 수행한다. 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패치 지연시간이라고 하며, 디스패치 지연시간의 대부분은 문맥교환 오버헤드에 해당된다.

 

스케줄링의 성능 평가

스케줄링 기법의 성능을 평가하기 위해 시스템 관점으로 CPU 이용률, 처리량이 있고, 사용자 관점으로 소요시간, 대기시간, 응답시간 등이 있다. 

 

스케줄링 알고리즘

CPU 스케줄링 알고리즘

선입선출 스케줄링 (First Come First Served, FCFS)

선입선출 스케줄링은 프로세스가 준비 큐에 도착한 시간 순서대로 CPU를 할당하는 방식이다. CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고 그 프로세스가 자발적으로 CPU를 반납할 때까지 빼았지 않는 비선점방식의 스케줄링이다. 그렇기에 긴 프로세스를 오랜 시간 기다려야하는 콘보이 현상이 단점이다.

 

최단작업 우선 스케줄링 (Shrotest Job First, SJF)

최단작업 우선 스케줄링은 CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. CPU 버스트가 짧은 프로세스가 CPU를 먼저 사용하고 준비 큐를 빠져나가게 되면 프로세스들이 준비 큐에서 기다리는 전체적인 시간이 줄어드는 방식이다. SJF 스케줄링에서는 예측을 통해 CPU 버스트 시간을 구한후 예측치가 가장짧은 것을 선택한다. SJF는 평균 대기시간을 초쇠하는 알고리즘이다. 다만 CPU 버스트가 긴 프로세스는 영원히 CPU를 할당 받을 수 없는 기아 현상이 발생할 수 있다.

SJF는 비선점과 선점 두가지 방식이 있다. 비선점 방식의 경우 CPU를 획득하면 프로세스가 CPU를 자진반납전까지 CPU를 빼앗기지 않는 방식이다. 선점 방식의 경우 CPU 버스트가 가장 짧은 프로세스에게 CPU를 할당했더라도 더 짧은 CPU 버스트를 가진 프로세스가 들어오면 그 프로세스에게 CPU를 부여하는 방식이다.

 

우선순위 스케줄링 (Priority Scheduling)

우선순위 스케줄링이란 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 우선순위값을 결정하는 방식에는 CPU 버스트 시간, 시스템 관련 중요도 등 다양하게 있다. 우선순위 스케줄링도 비선점과 선점방식 두가지 모두 구현이 가능하다. 다만 우선순위 스케줄링 또한 기아현상이 발생할 수 있다. 따라서 이것을 해결하기 위해 기다리면 우선순위가 올라가는 노화(Aging) 기법을 사용할 수 있다.

 

라운도 로빈 스케줄링 (Round Robin)

라운드 로빈 스케줄링은 시분할 시스템의 성질을 활용한 스케줄링 기법으로 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당하는 기법이다. 할당시간이 길면 FCFS와 같은 결과값을 초래하고, 너무 짧으면 프로세스의 문맥교환의 오버헤드가 커지게 된다. 

할당시간이 만료되면 CPU를 회수하는 방법으로 타이머 인터럽트를 발생시키는 방식으로 선점방식이다. CPU 버스트 시간이 짧은 프로세스는 CPU 버서트를 빨리 끝마치고, CPU 버스트가 긴 프로세느는 오래 기다리게 되는 합리적인 스케줄링이다.

 

멀티레벨 큐 (Multi Level Queue)

멀티레벨 큐의 모습

멀티레벨 큐는 준비 큐를 여러개로 분할해 관리하는 스케줄링 기법이다. 프로세스들이 CPU를 기다리기 위해 한줄로 서는 것이 아니라 여러줄로 서게 된다. 프로세스의 성격이 다른 프로세스들을 별도로 관리하고, 성격에 맞는 스케줄링을 적용하기 위해 별도로 준비 큐를 두게 된다. 따라서 일반적으로 멀티레벨 큐에서 준비 큐는 빠른응답을 필요로 하는 대화형 작업을 담기 위한 전위 큐와 계산 위주의 작업을 담기 위한 후위 큐로 분할하여 운영한다. 전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용하고, 계산 위주의 작업을 위한 후위 큐에서는 응답시간이 큰 의미를 가지지 않기때문에 FCFS 스케줄링을 사용한다.

멀티레벨 큐에서는 여러개의 준비 큐에 대해서 어느 큐에 먼저 CPU를 할당할지 결정하는 스케줄링 또한 필요하게 된다. 따라서 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어 있을 때에만 서비스하는 우선순위 방식 스케줄링을 보통 사용한다. 그 외에는 고정 우선순위 방식도 사용한다.

 

멀티레벨 피드백 큐 (Multilevel Feedback Queue)

멀티레벨 피드백 큐의 모습

멀티레벨 피드백 큐는 CPU를 기다리는 프로세스를 여러 큐에 줄 세우는 것은 멀티레벨 큐와 같지만 프로세스가 하나의 큐에서 다른 큐로 이동가능하다는 점이 다르다. 즉 우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시키는 것이 가능한 스케줄링 기법이다. 최상위 큐가 우선적으로 CPU를 배당받고, 상위 큐가 비었을 때에만 하위 큐에있는 프로세스들이 CPU를 할당받는 방식이다.

 

다중처리기 스케줄링 (Multi Processor System)

CPU가 여러 개인 시스템을 다중처리기 시스템이라고 한다. 이 환경에서는 프로세스를 준비 큐에 한 줄로 세워서 각 CPU가 알아서 다음 프로세스를 꺼내가도록 하는 방식을 사용할 수 있다.

다만 여러 줄로 줄 세우기를 하는 경우에는 CPU에 작업이 편중되는 현상이 있을 수 있어서, 다중처리기 스케줄링을 할 때 CPU별 부하가 적당히 분산되도록 부하균형(Load Balancing) 매커니즘이 필요하다. 다중 처리기 스케줄링은 각 CPU가 알아서 스케줄링을 하는 대칭형 다중처리와 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지는 비대칭형 다중처리가 있다.

 

실시간 스케줄링

실시간 시스템은 각 작업마다 데드라인이 있어 정해진 데드라인 안에 작업을 끝내야하는 방식이다. 시간을 정확히 지켜야 하는 경성 실시간 시스템이 있고, 데드라인이 존재하지만 딱히 안지켜도되는 연성 실시간 시스템이 있다. 실시간 환경에서는 먼저 요청을 먼저 처리하기보다는 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 EDF(Earlist Deadline First) 스케줄링을 사용한다.

 

 

출처
http://blog.skby.net/cpu-%EC%84%A0%EC%A0%90-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-%EA%B8%B0%EB%B2%95/
운영체제와 정보기술의 원리 - 이화여자대학교출판문화원 출판, 반효경 저

운영체제와 정보기술의 원리 - 교보문고