[정리] 04 CPU 스케줄링

목차

• 1. 스케줄링의 개요
• 2. 스케줄링 시 고려사항
• 3. 다중 큐
• 4. 스케줄링 알고리즘 
• 5. 인터럽트 처리

 

 

1. 스케줄링의 개요

- CPU스케줄러는 프로세스가 생성된후 종료 될때 까지의 모든 상태 변화를 조정하는 일을 담당한다.

( 여러 프로세스의 상황을 고려하여, CPU와 시스템 자원을 배정할지에 대한 결정권을 가지고 있다.)

 

 

1.1 스케줄링의 단계

- CPU 스케줄링은, 규모에 따라 고수준/중간수준/저수준 스케줄링으로 구분됨.

 

1) 고수준 스케줄링 ( 승인 스케줄링 )

- 시스템내의 전체 작업수를 조절하는 역할. 

- 어떤 작업을 시스템이 승인할지, 거부할지 결정권자.

 

2) 중간 수준 스케줄링

- 프로세스가 승인이 되어 활성화가 되더라도 여러가지 상황으로 시스템에 과부화가 걸릴수 있다.

그럴때 중간에서, 중지 / 활성화 로 프로세스 수를 조절하여 과부하를 막는 역할.

 

3) 저수준 스케줄링

- 어떤 프로세스에게 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지에 대한 결정을 하는 역할

( 막상 CPU를 할당해 주고 작업을 진행할수 있게 해주는 실무적인 담당자 라고 생각하면 편하다. )

 

1.2 스케줄링의 목적

- CPU 스케줄링의 목적은 모든 프로세스가 공평하게 작업하도록 하는것.

- 특정 프로세스가 시스템 자원을 독점하거나, 파괴하는것을 막기 위해 중요도에 따라 우선 순위를 배정한다.

(모든 프로세스가 공평하게 CPU를 할당받아야 하지만, 시스템의 안정성과 효율성으로 인해

중요한 프로세스는 작업 순위가 높다. - 운영체제 같은 프로세스들..)

• 1) 공평성 - 모든 프로세스가 자원을 공평하게 배정받아야한다.
• 2) 효율성 - 시스템 자원이 사용되지 않는 시간이 (놀고있는 시간) 없도록 자원을 사용해야한다.
• 3) 안정성 - 우선순위를 사용해 중요 프로세스가 먼저 작동하도록 해야한다. (예를들면 운영체제 같은것?)
• 4) 확장성 - 프로세스가 증가해도 시스템이 안정적으로 작동해야한다.
• 5) 반응시간 보장  - 응답이 없는경우 시스템이 멈춘것으로 간주하기에, 적절한 시간내에 응답이 나가야한다.
• 6) 무한 연기 방지 - 특정 프로세스의 작업이 무한 연기 되면 안된다. 

2. 스케줄링시 고려 사항

- 우선적으로 CPU를 할당할지 결정할때 고려해야할 사항이 있다.

• 선점형 스케줄링 - CPU를 할당받아 실행중이더라도, CPU를 강제로 뺏을수 있는 스케줄링 방식
• 비선점형 스케줄링 - CPU를 한번 할당받으면 작업이 끝날때 까지 다른 프로세스가 빼앗을수 없는 스케줄링 방식.

1) 선점형 스케줄링

• 장점 - 하나의 프로세스가 CPU를 독점 할수 없기에, 빠른 응답 시간을 요구하는 대화형 시스템이나 시분할 시스템에 적합.
• 단점 - 문맥 교환같은 부가적인 작업으로 인해 낭비가 발생.

2) 비선점형 스케줄링

• 장점 - 선점형 스케줄링보다 스케줄러의 작업량이 적고, 문맥 교환에 의한 낭비가 적다
• 단점 - 실행상태에 들어가 CPU를 사용하면 해당 프로세스가 종료되거나 자발적으로 대기 상태가 되지않으면 계속 실행되기에,                      전체 시스템의 처리율이 떨어지게 된다.

 

2.1) 프로세스 우선순위

- CPU 스케줄러는 우선순위를 사용한다. 우선순위가 있다는것은 프로세스의 중요도가 다르기 때문이다.

- 우선 순위가 높은것은 더 빨리, 더 자주 실행 된다는 의미.

( 커널 프로세스와, 일반 프로세스 중 더 중요한것은 커널프로세스 이므로 우선순위는 커널 프로세스가 더높다.)

 

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

• CPU 집중 프로세스 - 수학 연산과 같이 CPU를 많이 사용하는 프로세스.
• 입출력 집중 프로세스 - 저장 장치에서 데이터를 복사하는 일과 같이 입출력을 많이 사용하는 프로세스.

( 사용자에게 바로바로 응답을 보여줘야하는 프로세스의 경우 우선순위가 높고,

 뒤에서 작업을 천천히 해도되는경우 혹은 사용자와 상호 작용이 없는 경우 우선순위가 낮다.)

 

3) 다중 큐

- 프로세스의 중요도는 프로세스 제어 블록에 표시 된다.

그러나, 모든 프로세스 제어 블록을 일일히 검색하는건 번거로워 우선순위에 따라 여러개의 큐를 만들어두면 편리하다.

 

1) 준비 상태의 다중큐

- 한번에 하나의 프로세스를 꺼내어 CPU를 할당한다.

 

2) 대기 상태의 다중 큐

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

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

- 여러개의 프로세스 제어 블록을 동시에 꺼내 준비 상태로 옮긴다.

 

4) 스케줄링 알고리즘

구분	종류
비선점형 알고리즘	FCFS 스케줄링, SJF 스케줄링, HRN 스케줄링
선점형 알고리즘	라운드 로빈 스케줄링, SRT 스케줄링, 다단계 큐 스케줄링, 다단계 피드백 큐 스케줄링
둘다 가능	우선순위 스케줄링

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

• CPU 사용률
• 처리량
• 대기시간 - 프로세스가 생성된후 실행되기 전까지 대기 하는 시간
• 응답시간 - 첫 작업을 시작후, 첫번째 출력이 나오기 까지의 시간
• 반환시간 - 대기 시간을 포함하여 실행이 종료 될때 까지의 시간

* 요즘 시스템은 사용률과 처리량을 계산하기 어렵기 때문에, 주로 대기시간/응답시간/반환 시간을 계산한다

 

 

4.2 ) 스케줄링 알고리즘 종류

1) FCFS 스케줄링

- 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식. (선입선출 방식)

• 장점 - 단순하고 공평한 알고리즘.
• 단점 - 처리 시간이 긴 프로세스가 CPU를 선점 할경우, 다른 프로세스는 정지 상태가 길어져 시스템 효율이 떨어짐.

2) SJF 스케줄링

- 준비 큐에 있는 프로세스 중에서 실행시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식 ( 최단 작업 우선 스케줄링)

• 장점 - 작은 작업을 먼저 실행하기에 시스템 효율성이 좋아진다. 
• 단점 - 공평하지 못하다(아사 현상) / 운영체제가 프로세스의 종료 시간을 예측하기 어렵다.

아사 현상 - 미리 들어온 프로세스가 있더라도, 작은 프로세스가 계속 들어오면 미리 들어온 프로세스는 계속 기다려야한다.

 

3) HRN 스케줄링 

- 서비스를 받기 위해 기다린 시간과, CPU 사용 시간을 고려 하여 스케줄링을 하는 방식

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

• 장점 - 아사 현상 완화
• 단점 - 공평성 위배

4) 라운드 로빈 스케줄링

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

- 선점형 알고리즘중 가장 단순하고 대표적인 방식. 프로세스가 작업을 완료 할때까지 계속 순환하며 실행.

• 장점 - CPU를 일정시간 사용한후, 다른 프로세스에게 주기때문에 앞의 긴 작업을 무작정 기다리는 일이 줄어든다.
• 단점 - 선점형 방식에선, 작업 도중 다른 프로세스에게 CPU 할당권이 넘어가기 때문에, 문맥 교환의 시간이 추가된다.

5) SRT 우선 순위 스케줄링

- SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식. ( 최소 잔류 시간 우선 스케줄링)

- 라운드 로빈 스케줄링은 큐 순서대로 CPU 할당한다면, SRT 스케줄링은 남은 시간이 적은 프로세스에게 CPU를 먼저 할당.

• 장점 - 평균 대기시간이 짧다
• 단점 - 아사현상 / 프로세스의 종료시간 예측이 어려움 / 프로세스의 남은 시간 주기적 계산 필요

6) 우선순위 스케줄링

- 우선 순위를 반영한 스케줄링 알고리즘 ( 어떤 기준으로 우선순위를 정하느냐에 따라 다양하게 구현 가능)

- 사전에 나온 스케줄링들 중 장,단점이 있는데 그 중에서 우선순위를 부여해 스케줄링방식을 구현할수있다.

• 장점 - 위에 나온 알고리즘의 장,단점을 판단하에 우선순위를 매겨서 사용할수 있다.
• 단점 - 정답이 없다. 상황 판단 하에 우선순위를 매겨야한다.

7) 다단계 큐 스케줄링

- 우선순위에 따라 준비 큐를 사용하는방식

• 장점 - 프로세스가 큐에 삽입되는 것만으로 우선순위가 결정되낟.
• 단점 - 우선순위가 높은 큐 프로세스의 작업이 끝나기 전까지는 하위 프로세스는 작업할수 없다.

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

- 우선순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링의 문제점을 보완한 방식. (오늘날의 운영체제가 이방식을 채택.)

- 프로세스가 CPU를 한번씩 할당받아 실행 될때마다 프로세스의 우선순위를 낮춤으로써,

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

 

5) 인터럽트 처리

5.1) 인터럽트 개념

- 과거에는 입출력 장치가 거의 없기에 입출력 요청하면 운영체제가 주기적으로 폴링하며, 직접 확인해서 처리했는데, 

 현대에는 모든 입출력을 관리하기 힘들어, 입출력을 요청하고, 완료되면 이벤트를 발생시켜 이 사실을 알리게 했는데 이를 인터럽트라 한다

 

5.2) 동기적 인터럽트와 비동기적 인터럽트

1. 동기적 인터럽트 - 프로세스가 실행중인 명령어로 인해 발생
2. 비동기적 인터럽트 - 실행중인 명령어와 무관하게 발생한다.

 

5.3) 인터럽트 처리 과정

- 인터럽트에는 해당 인터럽트가 발생하면 어떤일을 할지 정의되어 있다. 

 

*인터럽트 벡터 - 한순간에 인터럽트가 여러개 발생하면 이를 묶어서 처리하는 개념 ( 각 인터럽트를 처리하는 함수가 연결 되어 있다. )

 

5.4) 이중모드

- 운영체제가 커널프로세스와 사용자프로세스 두모드를 전환하며 일처리를 하는것을 말한다.

- 운영체제가 자원을 보호하기 위해 사용하는 기법. (사용자 프로세스는 시스템 자원에 직접 접근을 막는다.)

 

1)  커널 프로세스 - 운영체제와 관련된 커널 프로세스가 실행되는 상태

2) 사용자 프로세스 - 사용자 프로세스가 실행되는 상태.