•
CPU 스케줄링 : 운영체제의 CPU 배분 방법
•
CPU 스케줄링 알고리즘 : CPU 스케쥴링의 절차
•
CPU 스케줄러 : CPU 스케쥴링 알고리즘을 결정하고 수행하는 운영체제의 일부분
개요
우선순위
•
모든 프로세스는 CPU 자원을 필요로 함
◦
따라서 운영체제는 공정하고 합리적인 방법으로 CPU 자원을 프로세스에 할당 필요
◦
운영체제는 프로세스별 우선순위를 판단해 PCB에 명시하고, 우선순위가 높은 프로세스에는 CPU의 자원을 더 빨리 더 많이 할당
•
운영체제가 프로세스들에게 높고 낮은 우선순위를 할당하는 다양한 기준
◦
CPU 활용률 : 전체 CPU 가동 시간 중 작업을 처리하는 시간의 비율
▪
운영체제는 CPU 활용률을 높게 유지할 수 있도록 우선순위를 할당
▪
높은 CPU 활용률을 유지하기 위해 입출력 작업이 많은 프로세스의 우선순위를 높게 유지
•
대부분의 프로세스는 CPU와 입출력장치를 모두 사용해 실행과 대기 상태를 오가며 실행
◦
CPU 버스트 : 프로세스가 CPU를 이용하는 작업
▪
CPU 집중 프로세스
•
EX : 복잡한 수학 연산, 그래픽 처리 작업 프로세스
•
대기 상태보다 실행 상태에 더 많이 머무름
◦
입출력 버스트 : 입출력장치를 기다리는 작업
▪
입출력 집중 프로세스
•
EX : 비디오 재생, 디스크 백업 작업 프로세스
•
실행 상태보다 입출력을 위한 대기 상태에 더 많이 머무름
◦
CPU 집중 프로세스와 입출력 집중 프로세스 각각 주로 머무르는 상태가 다르기 때문에 모든 프로세스가 동일한 시간의 빈도로 CPU를 사용하는 것은 합리적이지 않음
▪
입출력 집중 프로세스를 가능한 빨리 실행시켜 끊임없이 입출력 장치를 작동시킨 다음, CPU 집중 프로세스에 집중적으로 CPU를 할당하는 것이 합리적
▪
입출력장치가 입출력 작업을 완료하기 전까지 입출력 집중 프로세스는 어차피 대기 상태 → 입출력 집중 프로세스를 먼저 처리하고 이후에 다른 프로세스를 실행시켜 CPU 활용률을 높임
•
즉, 입출력 장치 프로세스는 일반적으로 CPU 집중 프로세스보다 우선순위가 높음
스케줄링 큐
•
운영체제는 프로세스들에게 ‘자원을 이용하고 싶다면 줄을 서서 기다릴 것’을 요구
◦
CPU 자원 요구 프로세스, 메모리에 적재되고 싶은 프로세스, 대기 상태로 특정 입출력장치를 이용하고 싶은 프로세스 모두에 해당 → 이 줄을 스케줄링 큐를 통해 구현
◦
프로세스들의 PCB를 큐에 삽입해 줄 세우는 것(스케줄링에 사용되는 큐는 반드시 선입선출일 필요 X)
•
운영체제가 관리하는 큐는 대표적으로 준비 큐와 대기 큐가 존재
◦
준비 큐 : CPU를 이용하고 싶은 프로세스의 PCB가 서는 줄
◦
대기 큐 : 대기 상태에 접어든 프로세스의 PCB가 서는 줄
▪
주로 입출력 작업을 수행 중인 경우, 대기 큐에서 대기 상태로 입출력 완료 인터럽트를 대기
CPU를 사용해야 입출력 작업이 가능한거 아닌가요?
▪
대기 큐에서, 같은 입출력 장치를 요구한 프로세스들은 같은 대기 큐에서 대기( EX : 프린터 대기 큐, CD-ROM 대기 큐, 하드 디스크 대기 큐 등) → 운영체제가 동시다발적으로 자원을 요구하는 여러 프로세스들을 효율적으로 관리 가능
◦
큐에 삽입된 순서대로 실행하되, 우선순위가 높은 프로세스부터 먼저 실행
선점형 스케쥴링 & 비선점형 스케쥴링
스케줄링은 기본적으로는 프로세스의 실행이 끝나면 이뤄짐. 그러나 프로세스가 종료되지 않은 상황임에도 실행 도중 스케줄링이 수행되는 대표적인 두 시점 존재
1.
실행 상태 → 대기 상태(입출력 작업) : 선점형, 비선점형
2.
실행 상태 → 준비 상태(타이머 인터럽트) : 선점형
선점형 스케줄링
현재 어떤 프로세스가 CPU를 할당받아 사용하고 있더라도 운영체제가 프로세스로부터 CPU 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식
•
타이머 인터럽트 기반 스케줄링
◦
프로세스마다 정해진 시간만큼만 CPU를 이용하고, 정해진 시간을 모두 소비하면 운영체제가 해당 프로세스로부터 CPU 자원을 뺏어 다음 프로세스에게 할당하는 방식이니까
장점•
한 프로세스의 CPU 독점을 막고 여러 프로세스에 골고루 CPU 자원을 배분 가능
단점•
문맥 교환 과정에서 오버헤드 발생 가능
문맥 교환(Context Switch)
오버헤드
비선점형 스케줄링
어떤 프로세스가 CPU를 사용하고 있을 때 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지는 다른 프로세스가 끼어들 수 없는 스케줄링 방식
장점•
문맥 교환 횟수가 적어 상대적으로 오버헤드 발생이 적음
단점•
어떤 프로세스가 CPU를 사용 중이라면 당장 CPU를 사용해야 하는 프로세스라도 무작정 기다려야함
CPU 스케줄링 알고리즘
CPU 스케줄링 알고리즘 : 운영체제가 프로세스에 CPU를 배분하는 방법
1. 선입 선처리 스케줄링(FCFS : First Come, First Served)
비선점형
•
준비 큐에 삽입된 순서대로 먼저 CPU를 요청한 프로세스부터 CPU를 할당하는 스케줄링 방식
◦
때로 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 부작용 존재
▪
호위효과(Convoy Effect) : 먼저 삽입된 프로세스의 오랜 실행 시간으로 인해 나중에 삽입된 프로세스의 실행이 지연되는 문제
2. 최단 작업 우선 스케줄링(SJF : Shortest Job First)
비선점형
•
준비 큐에 삽입된 프로세스 중 CPU를 이용하는 시간의 길이가 가장 짧은 프로세스부터 먼저 실행하는 스케줄링 방식
3. 라운드 로빈 스케줄링(RR : Round Robin)
선점형
•
선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식
◦
타임 슬라이스 : 프로세스가 CPU를 사용하도록 정해진 시간
•
큐에 삽입된 프로세스들이 순서대로 CPU를 이용하되, 정해진 타임 슬라이스만큼만 CPU를 이용
◦
프로세스가 정해진 시간을 모두 사용하고도 완료되지 않으면 문맥 교환이 발생해 다시 큐의 맨 뒤에 삽입
4. 최소 잔여 시간 우선 스케줄링(SRT : Shortest Remaining Time)
선점형
•
최단 작업 우선 스케줄링과 라운드 로빈 스케줄링을 합친 스케줄링 방식
•
정해진 타임 슬라이스만큼 CPU를 이용하되, 남아 있는 작업시간이 가장 적은 프로세스를 다음으로 CPU를 이용할 프로세스로 선택
5. 우선순위 스케줄링
비선점형
•
프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 방식
•
아사(Starvation) : SRT처럼 우선순위를 바탕으로 스케줄링하는 방식의 근본적인 문제
◦
우선순위가 낮은 프로세스는 우선순위 경쟁에서 계속 밀려 실행이 연기됨
◦
에이징(Aging) : 아사 현상을 방지하기 위한 기법
▪
오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식
6. 다단계 큐 스케줄링
선점형
•
우선순위 스케줄링의 발전된 형태로, 우선순위별로 여러 개의 준비 큐를 사용하는 스케줄링 방식
•
우선순위가 가장 높은 큐에 있는 프로세스를 먼저 처리, 해당 큐가 비면 그 다음으로 우선순위가 높은 큐에 있는 프로세스를 처리하는 형태
•
프로세스들이 큐 사이를 이동 할 수 없음 → 우선순위가 낮은 프로세스의 작업이 계속 연기되는 단점 존재(= 아사 현상)
7. 다단계 피드백 큐 스케줄링
선점형
•
다단계 큐 스케줄링과 비슷하게 동작하지만, 프로세스들이 큐 사이를 이동할 수 있는 차이 존재
•
새롭게 진입하는 프로세스는 먼저 우선순위가 가장 높은 우선순위 큐에 삽입되고, 타임 슬라이스 동안 실행
◦
해당 큐에서 프로세스의 실행이 끝나지 않으면 다음 우선순위 큐에 삽입되어 실행
◦
결국 오래 CPU를 사용해야 하는 프로세스의 우선순위는 점차 낮아짐
▪
CPU 집중 프로세스들의 우선순위는 낮아짐(CPU 사용시간이 길기 때문)
▪
입출력 집중 프로세스들의 우선순위는 높아짐
◦
아사 현상 예방을 위해 우선순위 큐에서 오래 기다리고 있는 프로세스들을 높은 우선순위 큐로 이동시키는 에이징 기법을 적용 가능
참고자료
