[ 운영체제 ] CPU 스케줄링 개요

1. CPU 스케줄링 개요

 

운영체제는 CPU를 프로세스들에게 공정하고 합리적으로 배분해준다.

이를 CPU 스케줄링이라고 한다!

 

1.1 프로세스 우선순위

 

프로세스는 각각 우선순위를 갖고있다.

우선순위가 높을수록 빨리 처리해야한다는 의미이다.

 

대표적으로 우선순위가 높은 프로세스에는 입출력작업이 많은 프로세스가 있다.

입출력작업을 할동안은 CPU는 다른 프로세스를 실행시킬 수 있으므로 입출력작업을 먼저 실행시키는 것이 좋다!

 

비디오 재생이나 디스크 백업작업을 담당하는 프로세스와 같이 입출력이 많은 프로세스를 I/O bound process라고 하고

수학연산, 컴파일, 그래픽 처리와 같이 CPU작업이 많은 프로세스들을 CPU bound process라고 한다.

*CPU를 이용하는 작업을 CPU burst 입출력장치를 기다리는 작업을  I/O burst라고 한다. 

 

1.2 스케줄링 큐

 

다음 프로세스를 실행시킬때마다 PCB를 뒤적거리며 누굴뽑지? 할 수는 없다!

그래서 우리는 프로세스들은 줄세워 놓는다!

이런식으로 프로세스들의 줄을 스케줄링 큐라고한다. 

 

이 뿐만 아니라 운영체제가 관리하는 모든 자원들은 큐로 관리된다

대표적으로 CPU를 이용하고 싶은 프로세스들이 줄 서는 준비큐와 입출력장치를 사용하기 위해 줄 서는 대기큐가 있다.

 

준비 상태에 있는 프로세스들의 PCB는 준비큐에 마지막에 삽입되어 CPU를 사용할 차례를 기다린다. 

운영체제들은 큐에 삽입된 순서대로 하나씩 떠내서 실행하되, 우선순위가 더 높은 프로세스를 먼저 실행한다.

 

 

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

 

선점형 스케줄링이란 프로세스가 CPU를 비롯한 자원을 사용하고 있더라도 운영체제가 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식이다.

이 방법은 프로세스가 자원사용을 독점할 수 없다는 장점이 있지만, 

context switch를 많이 해야하기때문에 오버헤드가 발생할 수 있다. 

 

비선점형 스케줄링이란 하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기상태로 가기전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식이다. 

이는 오버헤드는 적지만 프로세스들이 골고루 자원을 자용하기는 힘들다.

 

 

2. CPU스케줄링 알고리즘

 

2.1 FCFS 스케줄링 (선입 선처리 스케줄링)

 

First come first served 스케줄링을 줄인말이다.

말 그대로 먼저 온 프로세스를 먼저 처리하는 비 선점형 스케줄링 방식이다. 

선착순이기 때문에 공정해보이지만 뒤에 있는 프로세스들이 기다리는 시간이 길어진다.

이런 경우라면 고작 2ms짜리를 실행시키기 위해 100ms를 기다려야할수도 있다.

이를 호위효과라고 한다.

 

2.2 SJF스케줄링 (최단 작업 우선 스케줄링)

 

Shortest Job First의 줄임맛이다. 

이 친구도 말 그대로 짧은 프로세스를 먼저 처리하는 비선점형 스케줄링 방식이다. 

 

 

2.3 round robin 스케줄링 

 

FCFS스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식이다.

타임 슬라이스랑 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미한다.

라운드 로빈은 타임슬라이스만큼의 시간을 돌아가며 CPU를 사용하는 선점형 스케줄링이다. 

 

라운드 로빈에서는 타임슬라이스의 크기가 매우 중요하다.

타임슬라이스가 너무 크면 FCFS와 다를게 별로 없어지고 너무 작으면 context switch가 많이 일어나서 오버헤드가 걱정..

 

2.4 SRT 스케줄링 (최소 잔여 시간 우선 스케줄링)

 

Shortest Remaining Time의 줄임말이다.

이 방법은 SJF스케줄링과 라운드로빈을 합친 방식이다.

이 방법은 정해진 타임 슬라이스만큼 CPU를 사용하되 남은 작업시간이 적은 프로세스를 다음 프로세스로 선택한다. 

 

2.5 priority 스케줄링 (우선순위 스케줄링)

 

프로세스별로 우선순위를 부려하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘이다.

하지만 이 방법으로 하다보면 우선순위가 낮은 친구들은 계속 선택받지 못할 수 있다.

이를 기아현상이라고 한다. 

이를 방지하지위해 오랫동안 대기한 프로세스들의 우선순위를 높여주는 에이징(aging)이라는 기법이 있다.

 

2.6 multilevel queue 스케줄링 (다단계 큐 스케줄링)

 

이는 우선순위 스케줄링의 발전된 형태이다. 

이는 우선순위 별로 준비 큐를 여러개 사용하는 스케줄링 방식이다.

우선분위가 높은 큐의 프로세스들을 먼저 처리하고, 우선순위가 제일 높은 큐가 비어있다면 그 다음 우선순위 큐를 본다.

 

2.7 multilevel feedback queue 스케줄링 (다단계 피드백 큐 스케줄링)

 

이는 multilevel queue의 발전된 형태이다.

multilevel queue는 우선순위 조정이 안되어 기아현상이 일어날 수도 있다.

하지만 multilevel feedback queue 스케줄링은 큐 사이에 이동이 가능하다!

 

새로운 프로세스가 있다면 우선 우선순위가 가장 높은 우선순위 큐에 삽입되고 타임슬라이스 동안 실행된다.

그리고 만약 해달 큐에서 실행이 끝나지 않는다면 다음 우선순위 큐로 넘어간다.

프로세스를 오래 필요로하는 프로세스는 우선순위가 낮아지는 것이다..!

이렇게 되면 자연스럽에 실행시간이 적은 프로세스들이 먼저 끝나게된다.

또, 너무 낮은 우선순위에 오래 있다면 에이징 기법을 이용해서 우선순위를 올려줄 수 있다.