[운영체제] CPU 스케줄링

💡 CPU 스케줄링이란?

: CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 하며, CPU 스케줄링은 CPU 스케줄러가 하는 모든 작업을 가리킨다.

 

1. 스케줄링의 단계

• 고수준 스케줄링: 시스템 내의 프로세스 수(멀티프로그래밍 정도)를 조절하는 것이다.
• 중간수준 스케줄링: 전체 시스템의 활성화된 프로세스 수를 조절하여 과부하를 막는 것이다.
• 저수준 스케줄링: 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기상태로 보낼지 등을 결정하는 것이다.

 

2. 스케줄링의 목적 

• 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 하며, 자원 배정 과정에서 특정 프로세스가 배제되면 안된다.
• 효율성: 시스템 자원이 유휴 시간 없이 사용되도록 스케줄링을 하고, 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.
• 안정성: 우선순위를 사용하여 중요 프로세스가 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.
• 확장성: 프로세스가 증가해도 시스템이 안정적으로 작동하도록 해야 한다. 또한 시스템 자원이 늘어나는 경우 이 혜택이 시스템에 반영되게 해야 한다.
• 반응 시간 보장: 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
• 무한 연기 방지: 특정 프로세스의 작업이 무한히 연기되어서는 안된다.

 

3. 선점형 스케줄링 vs 비선점형 스케줄링

- 선점형 스케줄링

: 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이다.

• 장점: 프로세스가 CPU를 독점할 수 없어 대화형이나 시분할 시스템에 적합
• 단점: 문맥 교환의 오버헤드가 많다.

- 비선점형 스케줄링

: 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다.

• 장점: CPU 스케줄러의 작업량이 적고 문맥 교환의 오버헤드가 적다
• 단점: 기다리는 프로세스가 많아 처리율이 떨어진다.

 

4. CPU 집중 프로세스 vs 입출력 집중 프로세스

- CPU 집중 프로세스

: 수학 연산과 같이 CPU를 많이 사용하는 프로세스를 말한다. 즉 CPU 버스트가 많은 프로세스이다.

 

- 입출력 집중 프로세스

: 저장장치에서 데이터를 복하는 일과 같이 입출력을 많이 사용하는 프로세스를 말한다. 즉 입출력 버스트가 많은 프로세스이다.

 

📌 사이클 훔치기

: 입출력 집중 프로세스가 CPU 집중 프로세스보다 먼저 실행 상태로 들어가는 가는 경우를 말한다. 입출력 집중 프로세스가 먼저 들어가면 입출력 요구로 인해 대기 상태로 옮겨지기 때문에 다른 프로세스가 CPU를 사용할 수 있지만 CPU 집중 프로세스가 먼저 실행 상태가 되면 자신의 타임 슬라이스를 다 쓸때까이 다른 프로세스가 실행되지 못한다. 

 

5. 전면 프로세스 vs 후면 프로세스

- 전면 프로세스

: GUI를 사용하는 운영체제에서 화면의 맨 앞에 놓인 프로세스. 현재 입력과 출력을 사용하는 프로세스이며, 사용자와 상호작용이 가능하여 상호작용 프로세스라고도 한다.

 

- 후면 프로세스

: 사용자와 상호작용이 없는 프로세스. 압축 프로그램처럼 사용자의 입력 없이 작동하기 때문에 일괄 작업 프로세스라고도 한다.

 

6. 스케줄링 알고리즘 선택 기준

• CPU 사용률: 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
• 처리량: 단위 시간당 작업을 마친 프로세스의 수
• 대기 시간: 작업을 요청한 프로세스가 작업을 시작하기 전까지 대기하는 시간
• 응답 시간: 프로세스 시작 후 첫번째 출력 또는 반응이 나올 때까지 걸리는 시간
• 반환 시간: 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간

 

7. 스케줄링 알고리즘

1) FCFS 스케줄링 (first come first serve)

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

- 모든 프로세스의 우선순위가 동일하다

- 현재 작업 중인 프로세스가 입출력 작업을 요청하는 경우 CPU가 작업하지 않고 쉬는 시간이 많아진다.

 

📌 콘보이 효과

: 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리게 된다. 

 

2) SJF 스케줄링 (shortest job first)

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

- 시간이 오래 걸리는 작업이 앞에 있고 간단한 작업이 뒤에 있으면 그 순서를 바꾸어 실행해서 FCFS의 콘보이 효과를 완화할 수 있다.

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

 

📌 아사 현상 (무한 봉쇄)

: 실행시간이 짧은 프로세스가 계속 들어오면 실행시간이 긴 프로세스는 계속 뒤로 밀려 무한 연기된다. 그렇게 되면 프로세스의 공평성이 현저히 떨어진다. 

 

📌 에이징

: 프로세스가 양보할 수 잇는 상한선을 정하는 방식. 아사현상을 완화 할 수 있지만 에이징 값을 어떤 기준으로 정할것인지가 문제라 에이징에도 한계가 있다.

 

3) HRN 스케줄링 (Highest Response Ratio Next)

: 최고 응답률 우선 스케줄링. 대기 시간과 CPU 사용 시간을 고려하여 스케줄링을 하는 방식.

- 우선순위를 정할 때 대기시간을 고려함으로써 아사 현상을 완화한다.

- 여전히 공평성을 위배

 

4) 라운드 로빈 스케줄링

: 한 프로세스가 할당받은 시간(타임슬라이스) 동안 작업을 하다가 작업을 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식.

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

- 타임슬라이스가 큰 경우 작업이 끝난 뒤 다음 작업이 시작되는 것처럼 보임.

- 타임 슬라이스가 작은 경우 문맥 교환에 많은 시간을 낭비.

 

5) SRT 스케줄링

: 최소 잔류 시간 우선 스케줄링. CPU를 할당받을 프로세스를 선택할 때 남아 있는 작업 시간이 가장 적은 프로세스를 선택하는 방식.

- 남아있는 작업 시간을 주기적으로 계산해야 하기 때문에 SJF 스케줄링에는 없는 작업이 추가됨.

- SJF 스케줄링과 마찬가지로 종료 시간을 예측하기 어렵고 아사 현상이 일어남.

 

6) 다단계 큐 스케줄링

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

- 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입되어 실행

- 우선 순위가 낮은 프로세스의 작업이 연기되는 문제가 발생

 

7) 다단계 피드백 큐 스케줄링

: 변동 우선순위 알고리즘의 전형적인 예. CPU를 사용하고 난 프로세스가 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어감.

- 오늘날의 운영체제가 CPU 스케줄링을 위해 일반적으로 사용하는 방식.

- 다단계 큐에서 우선순위가 낮은 프로세스의 실행이 연기되는 문제를 완화.

- 우선 순위에 따라 타임 슬라이스의 크기가 다른데, 낮을 수록 점점 커지고 마지막 큐는 무한대의 타임 슬라이스를 가짐. (FCFS방식)