CPU 스케줄링
운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것
프로세스마다 우선순위가 존재하고 우선순위에 따라 CPU를 사용한다. 각 프로세스의 우선순위는 PCB에 명시 된다.
스케줄링 큐
CPU나 입출력 장치를 사용하고 싶어하는 프로세스들이 준비중인 대기열
CPU가 프로세스 실행을 위해 PCB를 탐색하며 우선순위가 가장 높은 프로세스를 찾아 실행시키는 방법이 있지만 비효율적이다. 따라서 프로세스를 줄을 세워놓고 차례대로 실행시키는 방법을 사용한다.
준비 큐
CPU를 이용하기 위해 대기중인 프로세스들이 있는 큐
대기 큐
입출력 장치를 이용하기 위해 대기 중인 프로세스들이 있는 큐
스케줄링 기법
스케줄링 기법에 영향을 주는 정책으로는 1.선점/비선점 정책 2.우선순위 가 있다.
이미 CPU를 사용중인 프로세스보다 더 급한 프로세스가 있을 경우 운영체제가 자원을 선점하여 급한 프로세스에게 주는 상황
비선점 스케줄링
이미 프로세스가 CPU를 사용하고 있다면 다른 어떤 프로세스는 끼어들 수 없는 방법
선점형 스케줄링
이미 프로세스가 CPU를 사용하고 있더라도 자원을 강제로 빼앗아 다른 프로세스에게 할당하는 방법
우선순위
프로세스의 중요도를 숫자로 표현
•
정적 우선 순위
우선순위를 정적으로 부여해주고, 불변한다.
구현이 단순하고 오버헤드가 적지만 시스템 환경 변화에 적절히 대응하기 어렵다.
•
동적 우선 순위
우선순위를 동적으로 변경 가능하다.
구현이 복잡하고 우선순위 계산으로 인한 오버헤드가 발생하지만 변화하는 상황에 유연하게 대응 가능하다.
CPU 스케줄링 알고리즘
1. FCFS 선입 선처리 스케줄링
준비 큐에 삽입된 순서대로 프로세스들을 처리하는 비선점형 스케줄링 방식
•
비선점
•
호위효과 발생
호위효과 Convoy Effect
실행시간 작은 프로세스가 실행시간이 긴 프로세스를 기다리는 현상
2. SJF 최단 작업 우선 스케줄링
실행 시간이 가장 짧은 프로세스부터 실행하는 방식
비선점, 선점 둘다 구현 가능한 스케줄링 방식이다.
•
비선점(선점도 가능)
3. RR 라운드 로빈 스케줄링
프로세스들이 돌아가며 정해진 타임 슬라이스만큼 CPU를 사용하는 선점형 스케줄링 방식
삽입 순서대로 CPU를 사용하되 정해진 시간만큼만 사용하고 자원을 반납한다.
타임 슬라이스의 크기가 너무 작다면 문맥교환에서 발생하는 비용이 커져 비효율적이다.
•
선점
타임슬라이스
프로세스가 CPU를 사용할 수 있는 정해진 시간
4. SRT 최소 잔여 시간 우선 스케줄링
프로세스들이 정해진 타임 슬라이스만큼 CPU를 점유하되, CPU를 사용할 다음 프로세스로 남아있는 시간 중 작업 시간이 가장 적은 프로세스를 선택하는 스케줄링 방법
최단작업 우선 스케줄링 + 라운드 로빈
•
선점
5. 우선순위 스케줄링
가장 높은 우선순위를 가지는 프로세스부터 실행하는 스케줄링
SJF 최단 작업 우선 스케줄링, SRT 최소 잔여 시간 우선 스케줄링 둘다 이 우선순위 스케줄링에 해당된다.
기아 현상을 위해 에이징 기법을 사용한다.
기아 현상
우선순위가 낮은 프로세스가 실행이 계속 연기되는 상황
에이징
오랫동안 대기한 프로세스의 우선순위를 높이는 방식
6. HRRN 최상 응답 비율 순서 스케줄링
응답률이 가장 높은 프로세스에게 우선권을 주는 방식
응답률 : 서비스 시간에 대한 대기 시간 비율
응답률(우선순위) = (대기시간 + 서비스시간) / 서비스 시간
대기하는 시간이 길어지는 프로세스의 우선순위가 올라가는 효과
응답률 계산을 위한 오버헤드 발생
7. 다단계 큐 스케줄링
우선순위별로 준비 큐를 여러 개 사용하는 스케줄링 방식
우선순위가 가장 높은 큐를 먼저 처리하고, 큐가 비어있다면 그다음 우선순위 큐에 있는 프로세스를 처리
큐가 여러개 있으면 프로세스 유형별로 우선순위를 구분할 수 있다.
큐 별로 타임 슬라이스를 다르게 지정할 수 있다.
8. 다단계 피드백 큐 스케줄링
다단계 큐 에서 프로세스들이 우선순위에 의해 큐를 이동할 수 있는 방식
기존의 다단계 큐에서 기아현상을 방지할 수 있다.
큐의 우선순위 단계가 높으면 CPU의 시간 할당량이 적고, 우선순위 단계가 낮으면 CPU의 시간 할당량이 높다.
프로세스가 처음 생성되면 가장 우선순위가 높은 큐에 배정된다.
CPU 점유 시간이 긴 프로세스는 우선순위가 낮은 큐, I/O 점유 시간이 긴 프로세스는 우선순위가 높은 큐에 배정된다.
출처 : 혼자 공부하는 컴퓨터 구조+운영체제
