스케줄링의 단계
고수준 스케줄링
- 가장 큰 틀에서 이루어지는 스케줄링
- 시스템 내의 전체 작업(1개 또는 여러 개의 프로세스) 수를 조절하는 것
- 어떤 작업을 시스템이 받아들일지 또는 거부할지 결정
- 작업이 시작되면 시스템 자원을 사용하기에 기존 작업에 영향을 미치기 떄문이다.
저수준 스케줄링
- 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정
- 준비상태 프로세스 -> 실행상태, 실행상태 프로세스 -> 대기상태, 등 프로세스 상태에 관한 내용
중간 수준 스케줄링
- 고수준 스케줄링과 저수준 스케줄링 사이에 일어난 스케줄링
- 중지와 활성화를 하여 전체 시스템의 활성화된 프로세스 수를 조절하여 과부화를 막는다.
- 일부 프로세스를 중지(보류)상태로 옮김으로써 나머지 프로세스가 원만하게 작동하도록 지원한다.
스케줄링의 단계정리
스케줄링의 목적
- 공평성
- 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되어서는 안된다.
- 효율성
- 시스템 자원이 유휴 시간없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
- 안정성
- 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야한다.
- 확장성
- 프로세스가 중가해도 시스템이 안정적으로 작동하도록 조치해야한다.
- 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.
- 반응 시간 보장
- 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
- 무한 연기 방지
- 특정 프로세스의 작업이 무한히 연기되어서는 안된다.
스케줄링
선점형 스케줄링
- 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다.
선점형 스케줄링의 구조
- cpu가 인터럽트를 받으면 현재 실행 중인 작업을 중단한다.
- 커널을 깨워 인터럽트 처리시키며, 인터럽트 처리가 완료되면 원래의 작업으로 돌아간다.
비선점형 스케줄링
- 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다.
비선점형 스케줄링의 구조
- 어떤 프로세스가 실행 상태에 들어가 cpu를 사용하면 그 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지 계속 실행된다.
프로세스 우선순위
커널 프로세스
- 우선순위가 일반 프로세스보다 높다
- 우선순위가 높아 더 빨리 자주 실행되며, 같은 프로세스라 하더라도 더 중요한 커널 프로레스는 우선순위가 높다.
일반 프로세스
- 시스템에 따라 높은 숫자가 높은 우선순위를 나타내기도 하고, 낮은 숫자가 높은 우선순위를나타내기도 한다.
CPU 집중 프로세스와 입출력 집중 프로세스
CPU 버스트
- CPU 집중 프로세스가 CPU를 할당받아 실행하는 작업
- 수학 연산과 같은 CPU를 많이 사용하는 프로세스이다.
입출력 버스트
- 입출력 집중 프로세스가 하는 입출력 작업
- 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스
CPU 집중 프로세스
- 수학 연산과 같이 CPU를 많이 사용하는 프로세스
입출력 집중 프로세스
- 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스
각 프로세스의 배정
- 입출력 집중 프로세스를 먼저 실행 상태로 옮기는 것이 효율적이다.
- CPU 집중 프로세스와 입출력 집중 프로세스 중 어떤 것을 먼저 배정했느냐에 따른 결과 차이로
- 입출력 집중 프로세스가 실행 상태로 가면 입출력 요구에 의해 대기상태로 옮겨지기 때문에
- 다른 프로세스가 CPU를 사용할 수 있다.
- 입출력 프로세스가 CPU 집중 프로세스보다 실행 상태에 먼저 들어가는 경우를 사이클 훔치기 라고한다.
전면 프로세스와 후면 프로세스
전면 프로세스
- GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스
- 현재 입출력을 사용하는 프로세스이며, 사용자와 상호작용이 가능하다.
후면 프로세스
- 사용자와 상호작용이 없는 프로세스로 입력 없이 작동하는 일괄 작업프로세스 라고도 한다.
- 압축 프로그램 등이 있다.
다중 큐
준비 상태의 다중 큐
- 프로세스 우선순위 별로 여러개의 큐를 만들어 일의 효율성을 높인다.
고정 우선순위 방식
- 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식이다.
- 장점
- 프로세스가 작업하는 동안 우선순위가 변하지 않기 때문에 구현하기 쉽다.
- 단점
- 시스템의 상황이 시시각각 변하는데 우선순위를 고정하면 시스템의 변화에 대응하기 어려워 작업 효율이 떨어짐
변동 우선순위 방식
- 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식이다.
- 장점
- 단점
대기 상태의 다중 큐
- 시스템의 효율을 높이기 위해 대기상태 에서는 같은 입출력을 요구한 프로세스끼리 모아놓는다.
준비 상태의 다중 큐와 대기 상태
- 차이점
- 준비 큐는 한번에 하나의 프로세스를 거내어 CPU를 할당하는 반면, 대기 큐는 여러 개의 프로세스 제어 블록을 동시에 꺼내어 준비 상태로 옮긴다.
- 대기 상태의 다중 큐에 있는 프로세스 제어블록은 큐에 삽입된 순서대로 처리되지만, 일부는 나중에 들어온 프로세스 제어블록이 먼저 준비 상태로 옮겨 가기도 한다.
스케줄링 알고리즘
비선점형 스케줄링
- FCFS 스케줄링 ( First Come First Served ) = 선입선출 스케줄링
- 준비 큐에 도착한 순서대로 CPU를 할당하는 방식
- 프로세스가 큐에 도착한 순서대로 실행되며 한번 실행되면 종료될때까지 실행
- 콘보이 효과: FCFS 스케줄링은 단순하고 공평하지만 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들이 하염없이 기다려 시스템의 효율성이 떨어지는 문제
- SJF 스케줄링 ( Shortest Job First )
- 준비 큐에 있는 프로세스 중에 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 방식
- SJF 스케줄링은 작은 작업을 먼저 실행하므로 시스템의 효율성이 좋음
- 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 힘듬
- 사용자와의 상호작용이 빈번히 발생하는 현대의 프로세스는 프로그램의 종료 시간을 파악하기 어려움.
- 아사 현상: 만약 작업 시간이 작은 프로세스가 계속 큐에 들어오면, 작업 시간이 긴 프로세스가 무한히 연기
- HRN 스케줄링 ( Highest Response Ratio Next ) = 최고 응답률 우선 스케줄링
- 아사 현상을 해결
- 서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 우선순위를 결정
- 우선순위 = (대기시간 + CPU 사용시간) / CPU 사용시간 으로 계산되어 아사 현상을 완화
선점형 스케줄링
- RR 스케줄링
- Round Robin 스케줄링은 한 프로세스가 할당받은 시간 동안 작업 -> 작업을 실패 -> 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식 -> 가장 단순하고 대표적인 방식
- FCFS와 유사하지만 일정 타임 슬라이스 내에 작업이 끝나지 않으면 다시 큐에 삽입되는 것이 차이
- 타임 슬라이스 크기가 매우 크다면 FCFS와 같아지고, 작은 경우 Context Switching 이 자주 발생하므로 시스템의 전반적인 성능이 떨어진다.
- SRT 스케줄링 ( Shortest Remaining Time ) = 최소 잔류 시간 우선 스케줄링
- CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택
- 그러나 남은 시간을 주기적으로 계산하고 Context Switching이 자주 발생하기 때문에 잘 사용하지 않는다.
- 우선순위 스케줄링
- 중요도에 따라 부여받은 우선순위를 반영
- 시스템의 효율성은 떨어질 수 있으나, 커널 프로세스와 같은 중요한 프로세스를 위해 효율성보다 프로세스의 중요도를 생각해서 구현한다.
- 다단계 큐 스케줄링 ( Multilevel Queue )
- 우선순위에 따라 준비 큐를 여러개 사용하는 방식
- 우선순위가 높은 큐에 있는 프로세스가 모두 끝나야 다음 우선순위의 작업이 시작된다.
- 선점형 방식으로 고정형 우선순위를 사용
- 우선순위가 높은 프로세스의 작업이 끝나기 전엔 낮은 프로세스의 작업을 할 수 없다는 단점
- 다단계 피드백 큐 스케줄링 ( Multilevel Feedback Queue )
- CPU를 사용하고 난 프로세스의 우선순위가 낮아진다.
- CPU를 사용한 뒤 원래 큐가 아닌 우선순위가 하나 낮은 큐의 끝으로 들어간다.
- 우선순위마다 타임 슬라이스의 크기가 다르므로, 우선순위가 낮은 프로세스들이 어렵게 얻은 CPU를 좀 더 오래동안 사용할 수 있도록 조정한다.
