CPU 스케줄링

💡 스케줄링 단계

레벨 1 - 고수준 스케줄링: 시스템에서 전체 프로세스의 수를 결정

레벨 2 - 중간 수준 스케줄링: 프로세스가 활성화 상태일 때 문제가 발생한 경우 이미 활성화된 프로세스의 일부를 보류 상태로 보낸다.

레벨 3 - 저수준 스케줄링: 준비 상태에 있는 프로세스를 실행 상태로 보내거나, 실행 상태를 대기 상태로 보내거나 가장 작은 단위의 스케줄링

 

CPU 스케줄링을 할 때 고려사항들이 무엇이 있을까 ❓

우선순위가 높은 프로세스는 중요도가 높기에 더 자주 많이 사용된다. 

커널 프로세스, 전면 프로세스, 대화형 프로세스, 입출력 프로세스는 우선순위가 높고

일반 프로세스, 후면 프로세스, 일괄처리 프로세스, CPU 집중 프로세스는 우선순위가 낮다.

 

입출력 프로세스가 CPU 집중 프로세스보다 먼저 실행 상태에 들어가야 시스템 자원을 더욱 효율적으로 사용 가능(사이클 훔치기)하다.

입출력 프로세스가 입출력을 처리하는 동안 CPU 집중 프로세스가 CPU를 사용할 수 있기 때문이다. 

 

다중 큐가 왜 필요할까❓

프로세스의 중요도는 PCB에 표시되어 있지만 CPU 스케줄러가 매번 PCB를 검색하는 것은 비효율적

 

👀 준비 상태의 다중 큐

우선순위마다 큐가 존재하며 준비 상태에 들어올때 자신의 우선순위 큐에 가장 마지막 원소 값으로 들어온다.

 

👀 대기 상태의 다중 큐

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

 

준비상태의 다중 큐와 대기상태의 다중 큐의 차이

준비 큐는 한번에 하나의 PCB만 이동, 대기 큐는 동시에 여러 개의 PCB 이동 -> 인터럽트 벡터

 

프로세스 우선순위 배정방법

1️⃣ 고정 우선순위 방식: 운영체제가 프로세스에게 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는다.

2️⃣ 변동 우선순위 방식: 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식

 

반전 우선순위: 프로세스의 낮은 우선순위를 높은 우선순위로 바꾸는 것 

 

💡 스케줄링 알고리즘

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

 

✌ 비선점형 스케줄링

FCFS 스케줄링: 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 스케줄링, 큐가 하나라 모든 프로세스는 우선순위가 동일, 초기 일괄 작업 시스템에서 사용 -> 콘보이 효과, CPU의 쉬는 시간이 향상

 

SJF 스케줄링: 준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식, 큐가 하나라 모든 프로세스는 우선순위가 동일 -> 프로세스 종료시간 예측 어려움(대화형 프로세스가 많기에), 아사 현상 발생

 

HRN 스케줄링: SJF 스케줄링의 아사현상을 해결하기 위해 만들어진 비선점형 알고리즘, 큐가 하나라 모든 프로세스는 우선순위가 동일, 대기시간과 CPU 사용시간을 고려하기에 에이징을 구현했다고 볼 수 있음 -> 여전히 공평성 위배 가능성이 높음

 

✌ 선점형 스케줄링

라운드 로빈 스케줄링: 타임 슬라이스 동안 작업을 하다가 타임 아웃이 되면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 순환 순서 방식, 큐가 하나라 모든 프로세스는 우선순위가 동일

 

라운드 로빈 스케줄링 방식에서 고려해야 하는 것은 타임 슬라이스 크기와 문맥 교환이다.

 

1. 타임 슬라이스가 너무 큰 경우 : 하나의 작업이 끝난 뒤 다음 작업이 시작되는 것(FCFS 스케줄링처럼 보임)

 

2. 타임 슬라이스가 너무 작은 경우: 문맥 교환이 너무 자주 일어나서 문맥 교환으로 많은 시간을 낭비하여 실제 작업을 못 하게 됨

 

SRT 스케줄링: SJF 스케줄링 + 라운드 로빈 스케줄링, 즉 SJF 스케줄링의 선점형 버전 -> 현재 실행 중인 스케줄링과 큐에 있는 프로세스의 남은 시간을 주기적으로 계산, 문맥 교환 발생

 

✌ 둘 다 가능

우선순위 스케줄링 : 우선순위를 어떻게 정하느냐에 따라 다양하게 구현 ( SJF 스케줄링, HRN 스케줄링, SRT 스케줄링 전부 가능) -> 우선순위를 바꿈으로 인해 오버헤드 발생, 아사 현상

 

 

다단계 큐 스케줄링

고정형 우선순위에 따라 준비 큐를 여러개 사용하는 방식, 우선순위에 따라 다양한 방식 구현 가능, 큐 자체는 라운드 로빈 방식으로 운영, 상단의 큐에 있는 모든 프로세스 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다. -> 우선순위가 낮은 큐에 있는 프로세스인 경우 작업이 연기

 

다단계 피드백 큐 스케줄링

오늘날 운영체제가 일반적으로 사용하는 방식, 변동 우선순위 방식

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

2. 우선 순위에 따라 타임 슬라이스의 크기가 다르다.

우선순위가 낮을수록 타임 슬라이스의 크기는 커진다. -> 우선순위가 낮다는 것은 어렵게 CPU를 얻었다는 것이고 따라서 한번 얻은 거 오래 사용하라는 것 -> 우선순위가 가장 낮은 프로세스는 타임 슬라이스가 무한대이므로 비선점형 -> FCFS 스케줄링 방식으로 동작 (유닉스 운영체제에서 타임 슬라이스를 고정하지 않고 10~200 밀리초 사이에서 조정할 수 있도록 한 이유)

 

 

인터럽트가 왜 나왔을까 ❓

CPU가 입출력 장치의 상태를 주기적으로 검사해서 일정 조건이 만족할 때 데이터를 처리했다. 

점점 컴퓨터 주변장치들(마우스, 키보드, 프린터, 하드디스크 등등)이 많아져서 입출력까지 관여하는데 한계가 발생하기에 인터럽트 방식이 나왔다.

 

Polling 방식: CPU가 직접 입출력 장치에서 데이터를 가져오고 내보내는 방식

인터럽트 방식: CPU가 입출력 관리자에게 입출력 명령을 보내고 데이터 전송이 완료되면 완료 신호를 CPU에게 보내는 방식

 

동기적 인터럽트(= 사용자 인터럽트) : 프로세스가 실행 중인 명령어로 인해 발생하는 인터럽트

비동기적 인터럽트 : 실행 중인 명령어와 무관하게 발생하는 인터럽트

 

CPU가 여러개의 입출력 작업을 입출력 관리자에게 동시에 시킬 수 있는데 이때마다 인터럽트를 발생시키면 비효율적

인터럽트 벡터를 통해 여러 인터럽트를 동시에 처리

 

인터럽트 벡터: 인터럽트와 인터럽트 핸들러를 1:1로 연결한 자료구조

 

인터럽트 처리과정

1. 인터럽트 발생 시 현재 실행 중인 프로세스는 일시 정지 상태가 되며, 재시작을 위해 현재 프로세스 정보를 임시로 저장

2. 인터럽트 컨트롤러가 실행되어 인터럽트 처리 순서 결정

3. 해당 인터럽트에 해당하는 인터럽트 핸들러 실행

4. 인터럽트 처리를 마치면 일시 정지된 프로세스가 다시 실행되거나 종료