CPU 스케줄링 (2)

이번에 배운 내용은 'CPU의 사용시간'을 약수터의 물을 받는 시간이라고 생각하면 이해가 쉽다.

 

약수터에 여러 사람들이 모여있는데 그중에는 정수기에 넣을 물통을 들고 온 사람도 있을 것이고 물 한모금만 먹으러 온 사람도 있을 것이다.

 

정수기 통을 가져온 사람이 가장 빨리 와서 약수터에서 물을 받고 있으면 그 뒤로 도착한 많은 사람들은 그 사람이 끝나기만을 기다려야한다. 이렇게 빨리 온 순서대로 물을 받는 것을 FCFS 스케줄링 이라고 한다.

 

하지만 정수기 통을 가져온 사람 뒤에 물 한모금만 먹으러 온 사람이 있다고 생각해 보자.

 

정수기 통을 들고 온 사람이 물 한 모금만 먹으러 온 사람에게 순서를 양보해서 물을 먹고 자기는 나중에 받는 방법을 SJF 스케줄링이라고 한다.

 

이렇게 된다면 물이 많이 필요한 사람이 계속 늦어져 공평성에 어긋날 수 있다. 그래서 최대로 몇명까지 양보할 수 있는 값을 정한다면 공평성이 완화될 수 있다. 이것을 에이징 이라고 한다. 

 

또, 대기시간과 물을 담는 시간을 더하고 필요한 물의 양으로 나누어 순서를 정하는 방법도 있다. 이 방법을 HRN 스케줄링이라고 하는데 그렇게 된다면 대기시간을 고려하기 때문에 형평성에 어긋나지 않는다.

 

그러나 여전히 먼저 온 사람을 뒤로 보내야 한다는 문제가 있다. 

 

그래서 먼저 온 순서대로 물을 받지만 물을 받는 시간을 정해 자기가 받는 시간안에 물을 다 받지 못한다면 맨 뒤로 가 순서를 정하는 방법도 있다. 

 

이것을 라운드 로빈 스케줄링이라고 한다. 그러면 공평성도 어긋나지 않으며 효율도 좋을 수 있지만, 물을 받는 시간을 너무 적게 정한다면 앞 사람과 순서를 바꾸며 생기는 시간 (문맥교환)이 많이 생겨 결국 효율이 떨어질 수 있다.

 

그렇다고 너무 크게 정한다면 프로그램이 끊겨 보이는 문제가 생긴다. 이정도 예시를 보고 공부를 하면 더 쉽게 느낄 수 있다.

---

스케줄링 알고리즘

 

스케줄링 알고리즘의 평가기준

• CPU 사용률 : 전체 시스템 동작 시간 중 CPU가 사용된 시간
• 처리량 : 단위 시간당 작업을 마친 프로세스의 수
• 대기시간 : 작업을 요청하고 그 작업이 이루어질때까지 걸리는 시간
• 응답시간 : 프로세스 시작 후 첫 번째 출력값이 나올 때까지 걸리는 시간
• 반환시간 : 프로세스가 생성된 후 끝나고 사용하던 자원을 반환하는 데 까지 걸리는 시간

평균 대기 시간

모든 프로세스의 대기시간 / 프로세스의 수 

 

FCFS 스케줄링

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

→ 큐가 하나이기 때문에 모든 프로세스의 중요도가 동일하다.

→ 콘보이 효과 : 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스는 계속 기다려 시스템의 효율성이 떨어지는 효과

 

SJF 스케줄링

: 준비 큐에 있는 프로세스 중 실행시간이 짧은 작업부터 CPU를 할당하는 방식

→ 작은 작업을 먼저 실행하기때문에 효율성이 높아진다.

→ 운영체제가 프로세스의 종료 시간을 정확히 예측하기 어렵다. 

→ 공평성이 떨어진다. (에이징으로 해소 가능)

→ 아사현상 : 사용량이 작은 작업이 계속 들어오면 사용량이 큰 작업은 계속 뒤로 밀리는 현상

 

HRN 스케줄링

: 우선순위를 대기시간 + CPU사용시간/ CPU 사용시간 으로 정한 것

→ SJF 스케줄링에서 발생하는 아사현상을 대기시간을 고려함으로써 해소함

→ 여전히 공평성에 위배

 

라운드 로빈 스케줄링

: 각 프로세스에 CPU를 사용할 수 있는 할당 시간을 줌 (타임 슬라이스) 타임 슬라이스 안에 작업을 끝내지 못한다면 맨 뒤로 돌아가 순서를 기다림

→ 선점형 알고리즘중 가장 단순하고 대표적인 방법

→ 문맥교환이 많이 일어나면 효율이 떨어짐

→ 타임 슬라이스를 잘 조율하는 것이 중요

 

SRT 우선 스케줄링

: 타임 슬라이스를 주지만 CPU의 사용시간이 짧은 순서대로 순서가 정해짐

→ SJF + 라운드 로빈

→ 평균 대기시간이 짧지만 주기적으로 프로세스의 남은 CPU 사용량을 알아야 하기 때문에 비효율적

→ 아사현상 발생

 

우선순위 스케줄링

: 프로세스가 가지고 있는 중요도대로 우선순위를 부여하여 순서를 정하는 방식

→ 선점형, 비선점형 모두에 사용 가능

 

- 고정 우선순위 알고리즘

: 한번 우선순위를 부여받으면 프로세스가 종료될 때까지 우선순위가 고정 (효율성↓)

 

- 변동 우선순위 알고리즘

: 일정 시간마다 우선순위가 변함 (효율성↑)

 

- 공평성을 위배하고 아사현상을 일으킴

- 준비 큐에 있는 프로세스의 순서를 무시하고 프로세스의 우선순위를 매번 바꿔야 하기때문에 오버헤드 발생

 

다단계 큐 스케줄링

: 우선순위에 따라 준비 큐를 여러 개 사용하는 방식

→ 타임슬라이스의 크기를 조절해 전/후면 프로세스의 반응속도 조절 가능

→ 우선순위가 높은 프로세스의 작업이 끝나기 전에는 하위 프로세스의 작업을 할 수 없음

다단계 피드백 큐 스케줄링

: CPU를 사용하고 난 프로세스의 우선순위가 낮아짐 (우선순위가 낮은 프로세스의 불리함 해소) 

→ 우선순위에 따라 타임 슬라이스의 크기가 다름

우선순위가 낮은 프로세스가 타임 슬라이스가 큼

→ 오늘날에 일반적으로 사용하는 방식