4. CPU 스케줄링

4. CPU 스케줄링

2023. 4. 14. 18:09ㆍ운영체제

728x90

1. 스케줄링의 개요

CPU 스케줄러

: 여러 프로세스의 상황을 고려하여 CPU와 시스템 자원의 배정을 결정

고수준 스케줄링

전체 시스템의 부하를 고려하여 작업의 개수를 조절

저수준 스케줄링

어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 결정

중간 수준 스케줄링

중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막음

2. 스케줄링 시 고려 사항

2-1 선점형 스케줄링과 비선점형 스케줄링

선점형 스케줄링

실행 상태에 있는 프로세스의 작업을 중단시키고 새로운 작업을 시작할 수 있는 방식
문맥 교환의 오버헤드가 많다.

비선점형 스케줄링

그 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지는 계속 실행되는 방식
과거의 일괄 작업 시스템에서 사용하던 방식
전체 시스템의 처리율이 떨어짐
문맥 교환의 오버헤드가 적다.

2-2 프로세스 우선순위

* 우선순위가 높은 프로세스가 CPU 를 먼저 더 오래 차지한다.

CPU 집중 프로세스

CPU를 많이 사용하는 프로세스

입출력 집중 프로세스

입출력을 많이 사용하는 프로세스

스케줄링을 할 때 입출력 집중 프로세스의 우선순위를 CPU 집중 프로세스보다 높이면 시스템의 효율이 향상

2-3 전면 프로세스와 후면 프로세스

전면 프로세스

화면의 맨 앞에 놓인 프로세스
현재 입력과 출력 사용
사용자와 상호작용 가능

후면 프로세스

사용자와 상호작용이 없음
사용자의 입력 없이 작동
-> 일괄 작업 프로세스
전면 프로세스의 우선순위가 후면 프로세스보다 높음

3. 다중 큐

3-1 준비 상태의 다중 큐

준비 상태에 들어올 때 자신의 우선순위에 해당하는 큐의 마지막에 삽입

프로세스의 우선순위를 배정하는 방식

1. 고정 우선순위 방식

그 프로세스는 끝날 때까지 우선순위 바뀌지 않음
구현은 쉽지만 작업 효율 떨어짐

2. 변동 우선순위 방식

작업 중간에 우선순위 바뀜
효율성 향상

3-2 대기 상태의 다중 큐

효율을 높이기 위해 대기 상태에서는 같은 입출력을 요구한 프로세스끼리 모아 놓음
동시에 끝나는 인터럽트를 처리하기 위해 인터럽트 벡터라는 자료 구조 사용
-> 준비 큐로 옮김

4. 스케줄링 알고리즘

4-1 FCFS (First Come First Served) 스케줄링

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식
-> 효율성 떨어짐
큐가 하나라 모든 프로세스는 우선순위가 동일
현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU 가 작업하지 않고
쉬는 시간이 많아져 작업 효율이 떨어짐
-> 콘보이 효과

4-2 SJF(Shortest Job First) 스케줄링

최단 작업 우선 스케줄링이라고도 함
준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식
-> 콘보이 효과 완화
그러나 실행 시간이 긴 이유로 계속 두로 밀려 공평성이 떨어짐
-> 아사 현상
-> 에이징 기법으로 아사 현상 완화.
프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지 양보하도록 규정하는 것
운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어려움

4-3 HRN(Highest Response ratio Next) 스케줄링

SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘
최고 응답률 우선 스케줄링이라고도 함
프로세스의 우선순위를 결정하는 기준 : (대기 시간+ CPU 사용 시간) / CPU 사용 시간

4-4 라운드 로빈 스케줄링

선점형 알고리즘 중 가장 단순하고 대표적인 방식
프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행
효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 고려하여 타임 슬라이스를 적절히 설정해야 함
-> 타임 슬라이스가 너무 길지도 짧지도 않게

4-5 SRT(Shortest Remaining Time) 우선 스케줄링

기본적으로 라운드 로빈 스케줄링을 사용하지만
CPU 를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택
운영체제가 프로세스의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않음

4-6 우선순위 스케줄링

프로세스의 중요도에 따른 우선순위를 반영한 스케줄링 알고리즘
비선점형 방식과 선점형 방식에 모두 적용할 수 있음
준비 큐에 있는 프로세스의 순서를 무시하고 우선순위가 높은 프로세스에 먼저
CPU 를 할당하므로 공평성을 위배하고 아사 현상을 일으킴

4-7 다단계 큐 스케줄링

우선순위에 따라 준비 큐를 여러 개 사용하는 방식
우선순위는 고정형 우선순위를 사용
상단의 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작됨
프로세스가 CPU 를 한 번씩 할당받아 실행될 때마다 프로세스의 우선순위를 낮춤으
로써 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화
우선순위에 따라 타임 슬라이스의 크기가 다름
-> 한번 CPU 를 잡을 때 많이 작업하라고 낮은 우선순위의 타임 슬라이스를 크게 함
마지막 큐는 들어온 순서대로 작업을 마치는 FCFS 스케줄링 방식으로 동작

5. 동기적 인터럽트와 비동기적 인터럽트

동기적(synchronous) 인터럽트

프로세스가 실행 중인 명령어로 인해 발생
예) 어떤 수를 0으로 나눔
ctrl + C로 프로세스를 중단
프로그램상의 문제(오버플로우, 메모리 잘못 접근)

비동기적(asynchronous) 인터럽트

하드웨어적인 오류로 발생하거나 또는 키보드,마우스 입력
예) 하드디스크 읽기 오류
메모리 불량
키보드, 마우스 인터럽트