[운영체제]4장 CPU 스케줄링

책 "쉽게 배우는 운영체제"를 참고하여 쓴 글입니다

스케줄링의 개요

CPU 스케줄링

고수준 스케줄링(장기 스케줄링, 작업 스케줄링): 시스템 내의 전체 작업 수를 조절하는 것이다. 이를 통해 시스템 내에서 동시에 실행 가능한 프로세스의 총 개수가 정해진다.

저수준 스케줄링(단기 스케줄링): 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다.

중간 수준 스케줄링: 중지와 활성화로 전체 시스템의 활성화된 프로세스 수를 조절하여 과부화를 막는다. 일부 프로세스를 중지 상태로 옮김으로써 나머지 프로세스가 원만하게 작동하도록 지원한다.

 

스케줄링의 목적(중요)

• 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 하며, 그 과정에서 특정 프로세스가 배제되어서는 안된다.
• 효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
• 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.
• 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.
• 반응 시간 보장:응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시슽ㅁ은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
• 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

스케줄링 시 고려 사항

선점형 스케줄링과 비선점형 스케줄링

선점형 스케줄링: 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식

비선점형 스케줄링: 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식

구분	선점형 스케줄링	비선점형 스케줄링
작업 방식	실행 상태에 있는 작업을 중단시키고 새로운 작업을 실행할 수 있다.	실행 상태에 있는 작업이 완료될 때까지 다른 작업이 불가능하다.
장점	프로세스가 CPU 독점할 수 없어 대화형이나 시분할 시스템에 적합하다.	CPU스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다.
단점	문맥 교환의 오버헤드가 많다	기다리는 프로세스가 많아 처리율이 떨어진다
사용	시분할 방식 스케줄링에 사용된다	일괄 작업 방식 스케줄링에 사용된다
중요도	높다	낮다

 

프로세스 우선순위

커널 프로세스 우선순위 > 일반 프로세스 우선순위

일반 프로세스의 우선순위는 사용자가 조절 가능하다

우선순위가 높다 == 더 빨리 자주 실행된다, CPU를 먼저, 더 오래 차지한다.

0번이 가장 높은 우선 순위이다.

 

CPU집중 프로세스와 입출력 집중 프로세스

CPU 집중 프로세스: CPU를 많이 사용하는 프로세스로 CPU 버스트가 많다.

입출력 집중 프로세스: 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스로 입출력 버스트가 많다

-> 이 둘이 같이 있을때는 입출력 집중 프로세스를 먼저 실행 상태를 옮기는 것이 효율적

 

전면 프로세스와 후면 프로세스

전면 프로세스: GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스를 말한다. 현재 입출력을 사용하는 프로세스이며, 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 한다.

후면 프로세스: 사용자와 상호작용이 없는 프로세스이다. 압축 프로그램과 같이 사용자의 입력 없이 작동하여 일괄 작업 프로세스라고도 한다.

전면 프로세스 우선순위 > 후면 프로세스 우선순위

 

 

다중 큐

준비 상태의 다중 큐

해당 그림처럼 프로세스는 준비 상태에 들어올 때마다 자신의 우선순위에 해당하는 큐의 마지막에 삽입된다.

 

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

고정 우선순위 방식: 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식. 시스템의 변화에 대응하기 어려워 작업 효율이 떨어진다

변동 우선순위 방식: 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식. 시스템의 효율성을 높일 수 있다.

 

대기 상태의 다중 큐

같은 입출력을 요구한 프로세스 끼리 모아놓는다.

 

스케줄링 알고리즘

구분	종류
비선점형 알고리즘	FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링
선점형 알고리즘	RR 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링
둘 다	우선순위 스케줄링

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

• CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정
• 처리량: 단위 시간당 작업을 마친 프로세스의 수, 수치가 클수록 좋은 알고리즘
• 대기 시간: 짧을수록 좋다
• 응답 시간: 짧을수록 좋다
• 반환 시간

• 대기 시간: 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
• 응답 시간: 첫 작업을 시작한 후 첫 출력이 나오기 까지의 시간
• 실행 시간: 프로세스 작업이 시작된 후 종료되기까지의 시간
• 반환 시간: 대기 시간+실행 시간

FCFS(First Come First Served) 스케줄링 (비선점)

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식, 선입선출 스케줄링

• 장점 : 문맥교환이 상대적으로 덜함, 오버헤드가 없다
• 단점: 콘보이 효과(처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다려 시스템의 효율성이 떨어짐), 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 쉬는 시간이 많아져 작업 효율이 떨어짐

 

SJF 스케줄링(비선점)

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식, 최단 작업 우선 스케줄링

• 단점
  • 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다
  • 공평하지 못하다: 아사 현상, 작업 시간이 길다는 이유만으로 계속하여 뒤로 밀린다
• 해결책
  • 프로세스가 자신의 작업 시간을 운영체제에 알려준다
  • 에이징(나이먹기): 프로세스가 양보할 수 있는 상한선을 정한다

프로세스	도착시간	실행시간	대기시간
A	0	10	0
B	1	28	33
C	2	6	12
D	3	4	7
E	4	14	16

 

HRN(Highest Response ratio Next)(비선점)

대기 중인 프로세스 중 우선순위가 가장 높은 것을 선택, SJF의 문제인 기아현상 보완한 기법

• 단점
  • 공평성이 위배

우선순위 = (대기시간+CPU 사용 시간) / CPU 사용 시간

프로세스	도착시간	실행시간	대기시간
A	0	10	0
B	1	28	33
C	2	6	12
D	3	4	7
E	4	14	16

 

프로세스	우선순위
A	(0+10) / 10 = 1
B	(33+28) / 28 = 2.2
C	(12+6) / 6 = 3.0
D	(7+4) / 4 = 2.8
E	(16+14) / 14 = 2.1

▶ C,D,B,E,A

 

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

순환 순서 방식, 한 프로세스가 할당 받은 시간(==타임 슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식

이때 타임 슬라이스는 되도록 작게 설정하되 문맥 교환에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요하다.

• 장점
  • 독점 방지
  • 첫 반응시간 빠름
• 단점
  • 문맥교환 다소 많음
  • 오버헤드 발생

프로세스	도착시간	실행시간
A	0	30
B	3	18
C	6	9

 

SRT 우선 스케줄링(선점형)

SJF 스케줄링와 RR 스케줄링을 혼합한 방식, 최소 잔류 시간 우선 스케줄링, 선점형 SJF 스케줄링이라 한다. 기본적으로 RR스케줄링을 사용하지만 CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업시간이 가장 적은 프로세스를 선택

작업	도착시간	실행시간
A	0	8
B	1	4
C	2	9
D	3	5

 

우선순위 스케줄링

어떤 기준으로 우선순위를 정하고 우선순위를 반영한 스케줄링 알고리즘, 비선점형 방식과 선점형 방식에 모두 적용할 수 있다. 시스템의 효율성보다 프로세스의 중요도에 따라 우선순위를 정한다.

• 고정 우선순위 알고리즘: 한 번 우선순위를 부여받으면 종료될 때까지 우선순위 고정, 효율성 떨어짐
• 변동 우선순위 알고리즘: 일정 시간마다 우선순위가 변한다. 효율성 O

다단계 큐 스케줄링

우선순위에 따라 준비 큐를 여러 개 사용

• 항상 가장 높은 우선순위 큐의 프로세스에 CPU할당
• 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에는 하위 큐 프로세스의 작업을 할 수 없다

 

다단계 피드백 큐 스케줄링

우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식. 

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