들어가기
CPU는 프로그램의 기계어 명령을 실제로 수행하는 컴퓨터 내의 중앙 처리장치이다. 프로그램이 시작되어 메모리에 올라가면 프로그램 카운터라는 이름의 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가지고 있게 된다. 그러면 CPU는 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행하게 된다. 한편 CPU는 일반적으로 한 시스템 내에 하나씩밖에 없으므로 여러 프로그램이 동시에 수행되는 시분할 환경에서 매우 효율적으로 관리되어야 하는 자원이다.
프로그램 실행과 관련된 몇가지 기계어 명령
-
CPU 내에서 수행되는 명령
Add 명령 : 레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령
-
메모리 접근을 필요로 하는 명령
Load 명령 : 메모리에 있는 데이터를 CPU로 읽어들이는 명령
Store 명령 : CPU에서 계산된 결괏값을 메모리에 저장하는 명령
-
입출력을 동반하는 명령
키보드 입출력, 컴퓨터에서 처리된 결과를 화면에 출력
-
차이점
입출력을 수반하는 명령은 CPU나 메모리 접근 명령에 비해 대단히 오랜 시간이 소요된다.
또한 컴퓨터 시스템에서는 모든 입출력 명령을 특권 명령으로 규정해 사용자 프로그램이 직접 수행할 수 없도록 하고 운영체제를 통해 서비스를 대행하도록 한다.
즉, 프로그램의 수행은 서로 다른 두 단계의 조합으로 이루어진다.
- 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계 ⇒ CPU 버스트(burst)
- I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계 ⇒ I/O 버스트(burst)
각 프로그램마다 CPU 버스트와 I/O 버스트가 차지하는 비율은 다르다.
I/O 바운드 프로세스
I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스
- 주로 사용자로부터 인터랙션을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램
- 짧은 CPU 버스트
CPU 바운드 프로세스
I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스
- 계산 위주의 프로그램
- 소수의 긴 CPU 버스트
CPU 스케줄링이 필요한 이유
CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 함께 실행되기 때문에 필요한 것이다. 프로세스의 CPU 버스트가 모두 균일한 경우에는 CPU 스케줄링을 하는 것이 큰 의미가 없지만, 우리가 사용하는 시분할 시스템에서는 이와 같이 CPU버스트가 큰 의미가 없지만, 우리가 사용하는 시분할 시스템에서는 이와 같이 CPU 버스트가 균일하지 않은 다양한 프로그램들이 공존하므로 효율적인 CPU 스케줄링 기법이 필요하다.
현대에는 사용자에게 바로 응답해줘야하는 대화영 작업이 많기 때문에 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 사용할 수 있도록 하는 스케줄링이 필요하다.
CPU 스케줄러
준비 상태에 있는 프로세스들 중 어떠한 프로세스에서 CPU를 할당할지 결정하는 운영체제의 코드
CPU 스케줄링이 필요한 경우
- 실행상태에 있는 프로세서가 I/O 요청 등에 의해 봉쇄 상태로 바뀌는 경우
- 실행상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
- I/O 요청으로 봉쇄 상태에 있던 프로세스의 I/O 작업이 완료되어 인터럽트가 발생하고 그 결과 이 프로세스의 상태가 준비 상태로 바뀌는 경우
- CPU에서 실행 상태에 있는 프로세스가 종료되는 경우
비선점형(nonpreemptive)
CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지는 CPU를 빼앗기지는 않는 방법을 말한다.
- 1번과 4번
선점형(preemptive)
CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법
- 2번과 3번
디스패처
새롭게 선택된 프로세스가 CPU를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드를 디스패처라고 부른다.
CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하고 나면 선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요하다(디스패치)
- 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장
- 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.
- 새로운 프로세스의 문맥을 복원시킨 후에는 시스템의 상태를 사용자 모드로 전환해 사용자 프로그램에게 CP의 제어권을 넘긴다.
- 그러면 사용자 프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 주소를 찾을 수 있게 된다.
디스패치 지연시간
디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간
- 문맥교환 오버헤드에 의해 발생
스케줄링의 성능 평가
스케줄링 기법의 성넝을 평가하기 위해 여러 지표들이 사용되는데 크게 시스템 관점, 사용자 관점의 지표 두가지로 나뉜다.
시스템 관점의 지표
- CPU 이용률 : CPU가 일을 한 시간의 비율
- CPU 처리량 : 프로세스를 몇 개를 끝마쳤는지
사용자 관점의 지표
- 소요시간 : 프로세스가 준비큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합
- 대기시간 : 프로세스가 준비큐에서 CPU를 얻기 위해 기다린 시간의 합
- 응답시간 : 프로세스가 준비큐에 들어온 후 첫번째 CPU를 획득하기까지 기다린 시간
스케줄링 알고리즘
선입선출 스케일링(first come first served: FCFS)
프로세스가 준비큐에 도착한 시간 순서대로 CPU를 할당하는 방식
- 프로세스가 자발적으로 CPU를 반남할 때 까지 빼앗지 않는다.
- 단점도 존재. CPU 버스트가 긴 프로세스 하나가 CPU 버스트가 짧은 여러 개보다 먼저 도착했다고 했을 때 CPU를 잠깐만 사용하면 준비 큐를 떠나 I/O 작업을 수행할 수 있는 다수의 프로세스들이 앞의 긴 작업 하나 때문에 계속 기다려야 하는 상황이 생겨 평균 대기시간이 길어지게 된다.
- CPU 버스트가 짧은 프로세스가 오랜시간동안 기다리는 현상 ⇒ 콘보이 현상(가장 큰 단점)
최단작업 우선 스케줄링(short job first: SJF)
CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
- 평균 대기시간을 가장 짧게 하는 최적 알고리즘
- 가장 짧은 프로세스에게 CPU를 할당했다 하더라도, CPU 버스트가 더 짧은 프로세스가 도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여하는 방식을 말한다.
- SJF의 선점형 구현 방식을 SRTF(shortest Remaining Time First)
프로세스들이 준비큐에 도착하는 시간이 불규칙한 환경에서는 선점형 방식이 프로세스들의 평균 대기시간을 최소화하는 최적의 알고리즘이 되지만, 프로세스들이 준비큐에 한거번에 도착하고 그 후에는 따로 도착하지 않는 환경에서는 비선점형 방식과 선점형 방식이 같은 결과를 내기도 한다. 하지만 시분할 시스템이기 때문에.!
우선순위 스케줄링
준비큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
- 이때 우선순위는 우선순위값을 통해 표시
- 우선순위 값을 결정하는 방식에는 여러가지가 있다 ( CPU 버스트 시간 등)
- 현재 CPU에서 프로세스가 수행중이더라도 우선순위가 높은 프로세스가 도착하여 CPU를 선점할 수 있다. 이와 달리 CPU를 얻었으면 비록우선순위가 더 높은 프로세스가 도착하더라고 CPU를 자진 반납하기 전까지 선점하지 않는 비선점 방식이 존재
- 기아현상 발생 : 우선순위가 높은 프로세스가 계속 도착하는 상황에서 우선순위가 낮은 프로세스는 CPU를 얻지 못한 채 계속 기다려야 할 수 있다.
- 이러한 문제점을 해결하기 위해 노화(aging)기법을 사용할 수 있다.
- aging : 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은순위가 되어 CPU를 할당받을 수 있게 해주는 방법
라운드 로빈 스케줄링
각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비큐에 줄 서 있는 프로스세스에게 CPU를 할당
- 시분할 시스템의 성질을 가장 잘 활용한 스케줄링
- 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 할당시간 이라고 부른다.
- 할당시간이 너무 길면 라운드 로빈 스케줄링은 FCRS와 같은 결과를 낸다.
- 반면 할당시간이 너무 작으면 문맥교환의 오버헤드가 커진다.
멀티레벨 큐
준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법을 말한다.
- CPU를 기다리기 위해 한 줄로 서는 것이 아니라 여러 줄로 서는 것이다.
- CPU는 하나밖에 없으므로 이 경우 어떤 줄에 서 있는 프로세스를 우선적으로 스케줄링 할 것인가 하는 문제가 발생한다.
- 성격이 다른 프로세스들을 별도로 관리하고 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 두게 된다.
ex) 빠른 응답을 필요로 하는 대화형 작업과 그렇지 않은 작업을 별도의 큐에 줄 세우도록 함.
전위 큐
멀티레벨 큐에서 대화형 작업을 담기 위한 큐
- 라운드 로빈 기법 사용
후위 큐
계산 위주의 작업을 위한 큐
- FCFS 스케줄링 기법
어느 큐에 먼저 CPU를 할당할 것인지 결정하는 스케줄링이 필요하다
고정 우선순위 방식
전위 큐가 먼저, 후위 큐가 나중에
타임 슬라이스 방식
각 큐에 대한 CPU 시간 할당
- 전위 큐 80%, 후위큐 20%를 CPU 시간을 적절한 비율로 할당
멀티레벨 피드백 큐
CPU를 기다리는 프로세스를 여러 큐에 줄 세운다는 측면에서 멀티 레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동 가능하다는 점이 다르다.
- 우선순위 스케줄링에서 기아 현상을 해결하기 위해 등장했던 노화 기법을 멀티레벨 피드백 큐 방식으로 규현할 수 있다. 오래 기다렸으면 우선순위가 높은 준비큐로 승격시킴
