스케줄링 알고리즘

목차

01. 운영체제의 개요
02. 컴퓨터의 구조와 성능 향상
03. 프로세스와 스레드
04. CPU 스케줄링
05. 프로세스 동기화
06. 교착 상태
07. 물리 메모리 관리
08. 가상 메모리의 기초
09. 가상 메모리 관리
10. 입출력 시스템과 저장장치
11. 파일 시스템
12. 네트워크와 분산 시스템

---

스케줄링 알고리즘

 

스케줄링 알고리즘의 선택 기준

• CPU 사용률
• 처리량
• 대기 시간
• 응답 시간
• 반환 시간

알고리즘의 성능을 비교할때 평균 대기시간을 본다.
모든 프로세스의 대기시간을 합한 프로세스의 수로 나눈 값이다.

 

FCFS 스케줄링

First Come First Served
준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식

처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어진다.

 

SJF 스케줄링 

Shor Job Fisrt
실행시간이 짧은 작업부터 CPU를 할당하는 비선점형 방식

운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
공평하지 못하다.

 

HRN 스케줄링

Highest Response ratio Next
서비스를 받기 위해 기다린 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식
대기 시간을 고려해 아사 현상을 완화 시킨다.

각 프로세스 우선순위 계산 후 → 프로세스의 대기시간을 계산해준다.

 

라운드 로빈 스케줄링 (RR 스케줄링)

한 프로세스가 할당받은 시간 동안 작업을 하다가 작업을 완료하지 못하면 맨 뒤로가서 차례를 기다리는 방식이다.

효과적으로 작동하려면 문맥 교환에 따른 추가 시간을 잘 고려해 타임 슬라이스를 설정한다.

• 타임 슬라이스가 큰 경우 → 너무 크면 FCFS 스케줄링과 다를 바 없다.
• 타임 슬라이스가 작은 경우 → 문맥 교환이 잦아져서 비효율 적이다.

 

SRT 우선 스캐줄링

Shortest Remaining Time
SJF 스케줄링에 타임 슬라이스를 첨가한 SJF의 선점형 버전이라고 생각하면 된다.

SJF 스케줄링에는 없는 문맥 교환을 해야하므로 추가 작업이 필요해서 좋은 알고리즘은 아니다.
그래서 SRT 스케줄링은 SJF 스케줄링과 마찬가지로 프로세스 종료 시간을 예측하기 어렵고 아사현상이 일어날 수 있다.

 

우선순위 스케줄링

프로세스는 중요도에 따라 우선순위를 가진다.
다양한 기준으로 우선순위를 설정해서 스케줄링하는 방식이다.
그렇기 때문에 다양하게 구현할 수 있다.

-고정 우선 순위 알고리즘

한번 우선순위를 부여 받으면 종료 될 때까지 변경할 수 없다.
동적으로 반응이 불가능하기에 효율성이 떨어진다.

- 변동 우선순위 알고리즘

일정 시간마다 우선순위를 새로 계산하고, 이를 반영하기 때문에 시스템의 상황을 반영해서 효율적으로 운영

우선순위 스케줄링은 효율성 보다는 프로세스의 중요도가 우선된다. (그 안에서 효율성을 따짐)

 

다단계 큐 스케줄링

우선순위에 따라 준비 큐를 여러 개 사용한다.
운영체제가 우선순위를 부여해준다.
우선순위는 고정형 우선순위를 사용한다.
상단의 큐가 끝나야 다음 큐의 작업이 시작된다.

 

다단계 피드백 큐 스케줄링

우선순위가 낮은 프로세스의 작업이 연기되는 것을 해결하기 위해 만들었다.

CPU를 사용한 프로세서는 우선순위가 낮아진다. CPU를 사용하고 난 프로세스는 원래의 큐로 돌아가지않고,
우선순위가 하나 낮은 큐의 끝에 들어간다.

CPU가 한 번씩 할당받아 실행될때 마다 우선순위를 낮춤으로서 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화

우선순위에 따라 타임 슬라이스의 크기를 다르게 설정한다.