[쉽게 배우는 운영체제] 4장 : CPU 스케줄링 (2/2) [OS]

다중 큐

프로세스를 효율적으로 관리하기 위해 여러 개의 큐를 만든다.

 

---

 

준비 상태의 다중 큐

매번 프로세스 제어 목록을 검색하면 효율성이 떨어져 우선순위에 따라 다중 큐를 운영한다.

 

대기 상태의 다중 큐

시스템의 효율을 높이기 위해 대기 상태에서는 같은 입출력을 요구한 프로세스를 모은다.

 

 

 

스케줄링 알고리즘

스케줄링 알고리즘은 선점형 알고리즘과 비선점형 알고리즘으로 나뉜다.

 

*스케줄링 알고리즘 종류

 

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

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

 

비선점형 알고리즘

1. FCFS 스케줄링

동작 방식

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

 

- 프로세스가 큐에 도착한 순서대로 실행되며, 한 번 실행되면 그 프로세스가 끝나야만 다음 프로세스를 실행할 수 있다.

- 큐가 하나라 모든 프로세스는 우선순위가 동일하다.

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

 

*콘보이 효과 : 단순하고 공평하지만, 처리시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들을 하염없이 기다려 시스템의 효율이 떨어지는 문제

 

2. SJF 스케줄링

동작 방식

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

 

- 최단 작업 우선 스케줄링이라고도 한다.

- 콘보이 효과 완화

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

- 실행시간이 긴 작업이 계속 연기되어 아사 현상(혹은 기아 현상)이 일어날 수 있다.

 

*에이징

아사 현상의 완화 방법으로 프로세스가 양보할 수 있는 상한선을 정하는 방식

 

3. HRN 스케줄링

동작 방식

SJF 스케줄링에서 발생할 수 있는 아사 현상을 해결하기 위해 만들어진 비선점형 알고리즘

 

- 최고 응답률 우선 스케줄링이라고도 한다.

- 실행시간이 짧은 프로세스의 우선순위를 높게 설정하면서도 대기 시간을 고려하여 기아 현상을 완화한다.

- 대기 시간이 긴 프로세스의 우선순위를 높임으로써 CPU를 할당받을 확률을 높인다.

 

선점형 알고리즘

1. 라운드 로빈 스케줄링

동작 방식

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

 

- 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행한다.

- 문맥 교환에 따른 추가 시간을 고려해 타임 슬라이스를 적절히 설정해야 한다.

 

 

2. SRT 스케줄링

동작 방식

기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당박을 프로세스를 선택할 때 남아 있는 작업이 가장 적은 프로세스 선택하는 방식

 

- 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 문맥 교환을 해야 하므로 SJF에는 없는 작업이 추가한다.

- 운영체제가 프로세스의 종료 시간을 정확히 예측하기가 어렵고, 아사 현상이 일어날 수 있다.

 

 

3. 다단계 큐 스케줄링

동작 방식

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

 

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

 

 

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

동작 방식

우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점 보완한 방식

 

- CPU를 사용하고 난 프로세스는 원래의 큐로 돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다.

- 우선순위에 따라 타임 슬라이스의 크기가 다르다.

- 우선순위가 낮은 우선순위의 타임 슬라이스를 크게 설정한다.

 

둘 다 가능

우선순위 스케줄링

동작 방식

프로세스는 중요도에 따라 우선순위를 갖는데 이러한 우선순위를 반영한 스케줄링 알고리즘

 

- 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현한다.

- 시스템의 효율성이 아닌 프로세스 중요도를 기준으로 결정한다. 

- 고정 우선순위 알고리즘 : 단순하게 구현할 수 있지만 시시각각 변하는 시스템의 상황을 반영하지 못해 효율성이 떨어진다.

- 변동 우선순위 알고리즘 : 일정 시간마다 우선순위를 새로 계산하고 이를 반영하기 때문에 시스템이 복잡하지만 시스템의 상황을 반영해 효율적인 운영이 가능하다.

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!