[혼공학습단 12기] 11강 - CPU 스케줄링

[ CPU 스케줄링 ]

운영체제가 프로세스들에게 공정하고 합리적으로 CPU 자원을 배분하는 것 

⇒ 컴퓨터 성능에 중요한 영향을 미침.

 

< IF > 프로세스가 사용하고 싶다고 말한 순위를 생각해 배정한다.

굉장히 비효율적인 것이다.

운영체제는 각 프로세스의 pcb에 우선순위를 명시하고, pcb에 적힌 우선순위를 기준으로 먼저 처리할 프로세스를 결정

 

[ I/O burst ]

- 비디오 재생, 디스크 백업은 입출력 작업이 많은 프로세스로, 입출력 집중 프로세스라 할 수 있다.

- 실행상태보다는 입출력을 위한 대기 상태에 더 머무르는 경향을 띤다.

 

[ CPU burst ]

- 수학 연산, 컴파일, 그래픽 처리 작업을 담당하는 프로세스로, CPU 집중 프로세스라 할 수 있다.

- 대기 상태보다는 실행 상태에 더 머무르는 경향을 띤다. 

 

프로세스는 일반적으로 cpu 버스트와 I/O 버스트가 왔다 갔다 일어난다. 

 

[ 스케줄링 큐 ]

- cpu를 사용하고 싶은 프로세스들, 메모리에 적재되고 싶은 프로세스들, 특정 입출력장치를 사용하고 싶은 프로세스들 모두 줄 서!

- FIFO 알고리즘 형태가 아니어도 된다. 

 

# 대표적인 큐

[ 준비 큐 ]

- cpu를 이용하고 싶은 프로세스들이 서는 줄

- 큐에 삽입된 순서대로 프로세스를 하나씩 꺼내어 실행하되, 그중 우선순위가 높은 프로세스를 먼저 실행한다. 우선순위가 높다면 큐에 늦게 삽입되어 줄을 서도 먼저 실행!(=vip)

 

[ 대기 큐 ]

- 같은 장치를 요구한 프로세스들은 같은 대기 큐에서 기다린다.

(ex. 하드디스크 사용하고 싶은 프로세스들끼리 같이 기다리고, 프린트 사용하고 싶은 프로세스끼리 기다리고)

 

[  선점형 스케줄링 ]

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

- 어느 하나의 프로세스가 자원 사용을 독점할 수 없는 스케줄링 방식

- 프로세스마다 정해진 시간만큼 cpu를 사용하고 정해진 시간을 모두 소비하여 타이머 인터럽트가 발생하면 운영체제가 해당 프로세스로부터 cpu 자원을 빼앗아 다음 프로세스에 할당하는 방식

- 대부분은 선점형

[ 장단점 ]

더 급한 프로세스가 있다면 언제든지 끼어들 수 있어 독점을 막고 골고루 자원을 배분할 수 있다. 

문맥 교환 과정에서 오버헤드가 발생할 수 있다. 

 

[  비선점형 스케줄링 ]

-  하나의 프로세스가 자원을 사용하고 있다면 그 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까진 다른 프로세스가 끼어들 수 없는 스케줄링 방식

- 하나의 프로세스가 자원 사용을 독점할 수 있는 스케줄링 방식

- 자원을 이용하고 있는 프로세스가 있다면 다른 프로세스들은 그 프로세스의 사용이 모두 끝날 때까지 기다려야 한다.

[ 장단점 ]

문맥 교환 과정에서 발생하는 오버헤드는 선점형 스케줄링보다 적다.

하나의 프로세스가 자원을 사용 중이라면 당장 자원을 사용해야 하는 상황이어도 못 씀(무한대기)

⇒ 자원을 골고루 사용할 수 x

 

[ 대표적인 스케줄링 종류 ]

1. [ 선입 선처리 스케줄링 ]

-  fcfs 스케줄링

- 준비 큐에 삽입된 순서대로 프로세스를 처리하는 비선점형 스케줄링 방식

- cpu를 먼저 요청한 프로세스로부터 cpu를 할당하는 스케줄링 방식

- 앞에 실행시간이 긴 프로세스들이 실행되고 있다면 해당 프로세스가 매우 짧은 시간 동안 실행될 수 있더라도 앞에 있는 긴 프로세스들이 끝나야만 실행될 수 있다. => 때때로 프로세스들이 기다리는 시간이 매우 길어질 수 있다.⇒ 호위효과 발생

 

2. [ 최단 작업 우선 스케줄링 ]

- sjf 스케줄링

- 호위 효과를 방지하기 위해 cpu 사용 시간이 긴 건 나중에, 짧은 건 먼저 처리하는 스케줄링 방식

- 기본적으론 비선점형 스케줄링 알고리즘이지만, 선점형 스케줄링으로 분류될 수도 있다.

 

3. [ 라운드 로빈 스케줄링 ]

- 선입 선처리 스케줄링에 타임 슬라이스라는 개념이 더해진 스케줄링 방식

- 타임 스케줄링 = 각 프로세스가 cpu를 사용할 수 있는 시간이 정해져 있는 것

- 정해진 타임 슬라이스만큼의 시간 동안 돌아가며 cpu를 이용하는 선점형 스케줄링

- 삽입된 순서대로 cpu를 이용하되 정해진 시간만큼만 cpu를 이용하고, 정해진 시간을 모두 사용하였음에도 아직 프로세스가 완료되지 않았다면 다시 큐의 맨 뒤에 삽입된다. (=문맥 교환 발생)

- 타임 슬라이스 크기가 매우 중요하다. ( 너무 크면 호위 효과 발생하고 / 너무 작으면 프로세스 처리하는 일보다 문맥 교환에 힘을 더 쓸 수 있기 때문 )

 

4. [ 최소 잔여 시간 우선 스케줄링 ]

- srt 스케줄링

- 최단 작업 우선 스케줄링 + 라운드 로빈

- 정해진 타임 슬라이스만큼 cpu를 사용하되, cpu를 사용할 다음 프로세스로 남아있는 작업 시간이 가장 적은 프로세스가 선택된다. 

 

5. [ 우선순위 스케줄링 ]

- 프로세스들에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 스케줄링 알고리즘

- 우선순위가 높은 프로세스를 우선하여 처리하기 때문에 우선순위가 낮은 프로세스는 우선순위가 높은 프로세스에 의해 실행이 계속 연기될 수 있다. (=기아현상),

- 우선순위가 낮은 프로세스의 실행은 계속 뒤로 밀린다..

⇒ 이에 에이징 기법을 쓴다. 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식

대기 중인 프로세스의 우선순위를 마치 나이 먹듯 점차 증가시키는 기법이기 때문에, 마냥 기다리는 프로세스가 없어질 수 있다!

 

6. [ 다단계 큐 스케줄링 ]

- 우선순위별로 큐를 여러 개 사용하는 스케줄링 방식

- 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 높은 큐가 비어있으면 그 다음 우선 순위 큐에 있는 프로세스들을 처리한다. 

- 큐를 여러 개 두기 때문에 프로세스 유형 별로 우선순위를 구분하여 실행하는 것이 편리해진다. 

⇒ 큐별로 타임 슬라이스를 여러 개 지정할 수 있고, 큐마다 다른 스케줄링 알고리즘을 사용할 수도 있다. 

- 프로세스들이 큐 사이를 이동할 수 없다. 이 때문에 우선순위가 낮은 프로세스는 계속 연기될 수 있다. (=다시 기아 현상 발생)

 

7. [ 다단계 피드백 큐 스케줄링 ]

- 다단계 큐 스케줄링은 큐 사이를 이동할 수 없어 기아 현상이 발생할 수 있는 단점을 가진다. ⇒ 이에 큐 사이를 이동할 수 있는 알고리즘인 7번이 등장

- 프로세스의 cpu 이용 시간이 너무 길면 낮은 우선순위 큐로 이동시키고, 프로세스가 낮은 우선 순위 큐에서 너무 오래 기다리면 높은 우선순위 큐로 이동시킨다. 

- 구현은 복잡하지만, 가장 일반적인 형태이다