[OS] 4. CPU 스케줄링 알고리즘 (쉽게 배우는 운영체제 4장)

쉽게배우는 운영체제, 한빛미디어 - 요약 및 공부한 내용입니다.

1. 스케줄링의 분류

스케줄러란

- CPU 스케줄러 또는 프로세스 스케줄러라 하며,

- 프로세스가 생성된 후 종류될 때 까지 모든 상태변화를 조정하는 것

​

1) 고수준 스케줄링

- 가장 "큰 틀" 에서 이루어지는 CPU 스케줄링

( = 장기 스케줄링, 작업 스케줄링, 승인 스케줄링)

​

- 시스템 내의 "전체 작업 수" 를 조절하는 것

​

2) 저수준 스케줄링

- 가장 "작은 단위"의 스케줄링

- 프로세스의 상태를 관리

​

3) 중간수준 스케줄링

- "중지" 와 "활성화" 로 전체 시스템의 활성된 프로세스 수를 조절하여 시스템의 과부화를 방지한다.

​

스케줄링 목적

⇨ 6가지 : 공평성, 효율성, 안정성, 확장성, 반응시간의 보장, 무한 연기 방지

​

1. 공평성 : 모든 프로세스가 공평하게 자원을 받아야 한다.

2. 효율성 : 시스템 자원이 쉬는 시간 없이 사용되도록 스케줄링하고, 쉬고있는 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.

3. 안전성 : 우선순위를 사용하여 중요 프로세스 먼저 작동하도록 하고, 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.

4. 확장성 : 프로세스가 증가해도 시스템이 안정적으로 작동해야한다.

5. 반은시간의 보장 : 적절한 시간안에 사용자에게 반응해야 한다.

6. 무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

​

 

---

2. 스케줄링 시 고류 사항

1) 선점형과 비선점형

선점형

: 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운용체제가 CPU를 강제롤 할당하는것을 선점형이라 한다.

비선점형

: 선점 불가능한 방식을 비선점형이라 한다.

​

2) 프로세스 우선순위

- 중요도에 따라 프로세스의 우선순위를 달리함

- 우선순위가 높다면 cpu를 먼저, 더 오래 차지하게 됨

- 커널 프로세스의 우선순위가 일반 프로세스보다 높음

- 프로세스 우선순위가 같다는 것은 모든 프로세스의 중요도가 같다는 것을 의미한다.

​

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

- cpu를 할당받아 실행하는 작업을 cpu버스트, 입출력 작업을 입출력 버스트라고 함

​

- cpu 집중 프로세스

· 연산과 같이 cpu를 많이 사용하는 프로세스

· cpu버스트가 많은 프로세스

​

- 입출력 집중 프로세스

· 저장장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스

· 입출력 버스트가 많은 프로세스

- cpu 집중 프로세스와 입출력 집중 프로세스가 같이 있을 때 입출력 집중 프로세스를 먼저 실행하는 것이 효율적

​

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

전면 프로세스

· GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스

· 현재 입출력을 사용하는 프로세스

· 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 함

​

후면 프로세스

· 사용자와 상호작용이 없는 프로세스

​

---

3. 다중 큐

1. 준비 상태의 다중 큐

<다중 큐란>

- 우선순위에 따라 여러 개의 큐를 만들면 편리 CPU에서 프로세스(시스템)을 관리하는 편리하다.

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

- 이렇게 우선순위별로 큐를 정렬하여 프로세스를 관리하는 것을 다중 큐라 한다.

​

<우선순위 배정 방식>

고정 우선순위 방식

· 우선순위가 프로세스가 끝날 때까지 바뀌지 않는 방식

· 구현이 쉽지만 시스템의 변화에 대응하기 어려워 작업 효율이 떨어짐

​

변동 우선순위 방식

· 우선순위가 프로세스 작업 중간에 변하는 방식

· 구현이 어렵지만 시스템의 효율성을 높일 수 있음

​

2) 대기 상태의 다중 큐

- 시스템의 효율을 높이기 위해 대기 상태에서 같은 입출력을 요구한 프로세스끼리 모아놓음

(입출력이 완료되기를 기다리는 프로세스가 모여있다.)

​

- 같은 입출력을 요구하는 프로세스끼리 묶어둔다.(한 큐)

​

4. 스케줄링 알고리즘

1) 스케줄링 종류

- 비선점형 알고리즘 : FCFS, SJF, HRN

- 선점형 알고리즘 : RR, SRT, 다단계 큐, 다단계 피드백

- 둘다 : 우선순위 알고리즘 ( 선점, 비선점 가능 )

​

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

1. cpu 사용율

• 전체 시스템 동작 시간 중 cpu가 사용된 시간을 측정

2. 처리량

• 단위 시간당 작업을 마친 프로세스의 수로, 이 수치가 클수록 좋은 알고리즘

3. 대기시간

• 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간, 이 시간이 짧을 수록 좋음

4. 응답시간

• 프로세스 시작 후 출력 또는 반응이 나올 때까지 걸리는 시간, 짧을 수록 좋음

5. 반환 시간

• 프로세스가 생성, 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간, 대기시간 + 실행시간

3) 스케줄링 알고리즘

1. FCFS - First in First out

- 비선점형 알고리즘

- 큐에 도착한 순서대로 CPU에 할당한다.( 선입선출 알고리즘 이라고도 함 )

- 우선순위는 각 프로세스가 동일하다.

​

2. SJF - 최단 프로세스 우선 스케줄링

- 비선점형 알고리즘

- 실행시간이 가장 짧은 작업부터 실행한다.

(단점)

1. 아사현상

: 실행시간이 긴 프로세스 계속해서 밀리는 아사현상이 발생할 수 있다.

​

2. 무한 봉쇄

​

⇨ (문제 해결) 에이징 기법

: 프로세스가 1번 양보할때마다 나이를 먹여 최대 몆번까지 양보할 수 있는지를 제한한다. (나이먹기)

​

3. HRN - 최고 응답률 우선 스케줄링

- 비선점형 알고리즘

- SJF의 아사현상을 해결한 알고리즘

- HRN 스케줄링에서 프로세스 우선순위를 결정한다.

 

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

⇨ 오래기다릴수록 우선순위 UP

​

(단점)

: 우선순위를 계속해서 계산하여야 한다.

​

4. RR(Round Robin)

- 선점형 알고리즘

- 타임슬라이스 만큼 돌아가며 프로세스에 CPU 할당

​

⇨ 시간안에 프로세스를 다 실행하지 못하면, 큐의 맨뒤로 돌아간다.

⇨ 우선순위가 적용되지 않은 가장 단순한 "선점형 기법"

⇨ 작업을 무작정 기다리는 콘베이효과 Down

문맥교환시간을 고려 해야한다.

(장점)

반응시간이 짧아져 사용자에게 매우 빠르게 느껴짐

​

5. SRT

- SJF + RR

- 선점형 알고리즘

- CPU를 할당받을 프로세스를 선택할 때

- 남아있는 작업시간이 가장 적은걸 선택

​

(단점)

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

- 아사현상이 발생할 수 있다.

- 전체적인 프로세스 수행 시간의 단축이 가능하나 새 프로세스가 도착할 때 마다 스케줄링을 해야 함

​

6. 우선순위 스케줄링

- 준비큐의 순서 무시

- 우선순위데로 프로세스를 CPU에 할당한다.

- 선점/비선점 둘다 가능

​

⇨ 비선점형 : 작업중인 프로세스가 끝나면, 우선순위데로 차례데로 CPU에 할당

⇨ 선점형 : 프로세스가 작업중일때, 새로운 프로세스가 큐에 들어오면, 그 즉시, 우선순위를 계산하여 우선순위가 더 높은 프로세스가 CPU를 선점

​

7. 다단계 큐 스케줄링

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

- 우선순위에 따라 다단계로 나뉘어 있어 프로세스가 큐에 삽입되면 우선순위가 결정

- 우선순위가 높은 상위 큐 프로세스의 작업이 끝나기전에 하위 큐 프로세스의 작업 불가

8. 다단계 피드백 큐 스케줄링

- 다단계 큐 + RR 적용

- 우선순위를 가진 여러 개의 큐를 사용

- cpu를 사용하고 난 프로세스는 우선순위가 하나 낮은 큐의 끝으로 들어감

- 프로세스의 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커진다

- 마지막 큐의 경우 무한대의 타임 슬라이스를 얻어 FCFS 스케줄링 방식으로 동작