CPU 스케줄링(1) : 기본 개념

다중 처리기 시스템에서는 어느 한순간에 다수의 프로세스들이 메모리 내에 위치하게 되고, 여러 개의 CPU가 수많은 프로세스들을 처리해야 하여 어떠한 프로세스의 대기가 발생하는 일이 발생한다. 이때 OS가 CPU를 쉬지 않고 여러 프로세스들을 끊임없이 작업 중일 수 있도록 프로세스의 배분 및 교환을 해주는 것을 CPU 스케줄링이라고 한다.

즉, 프로세스가 다른 일 처리하는 거 기다리는 동안 CPU 못 쉬게 하고 계속 굴리려고 일거리를 계속 갖다 주고 바꿔주고 하는 것!(이걸 프로세스의 생애주기 동안 모든 상태변화에 대해함)

 

스케줄링은 공평성, 효율성, 안정성, 반응 시간 보장, 무한 연기 방지를 목표로 한다.

1. 공평성: 모든 프로세스가 자원을 공평하게 배정받아야 하며, 특정 프로세스가 배제되어서는 안 됨

2. 효율성: 시스템 자원을 놀리는 시간 없이 스케줄링해야 함

3. 안정성: 우선순위를 사용하여 중요한 프로세스가 먼저 처리되도록 해야 함

4. 반응 시간 보장: 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 함

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

 

스케줄링에는 3가지의 단계가 있다.

1. 장기 스케줄링(long term 장기=job 작업=admissin scheduling)에서는 시스템 전체의 작업 수를 조절하여 시스템 동작 시 실행 가능한 프로세스의 총개수가 정해진다.

2. 중기 스케줄링 mid term은 저수준이 원만하게 이뤄지도록 중지suspend와 활성화active로 시스템 전체의 활성화된 프로세스 수를 조절하여 완충하는 역할을 한다. 여기에 있는 애들은 보류 상태의 프로세스이다.

3. 단기 스케줄링 short-term은 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정한다. 

여기에 있는 프로세스들은 준비 상태에 있는 프로세스이고, 단기 스케줄링은 실행 빈도가 잦기 때문에 한 번 실행할 때 드는 시간을 줄이는 것이 중요하다. 아래 내용부터는 거의 이 단기 스케줄링의 내용이다. 

 

프로세스가 대기 상태에 있다가 CPU를 할당받아 실행하면 CPU burst, 입출력 작업을 하면 I/O burst라고 하는데,

CPU를 많이 써서 CPU burst가 많은 프로세스는 CPU bound process(CPU 집중 프로세스), 입출력 많이 써서 I/O burst가 많은 프로세스는 I/O bound process(입출력 집중 프로세스)라고 한다.

이 버스트의 분포는 CPU 스케줄링 알고리즘을 선택하는 데에 있어 매우 중요한 역할을 한다.

 

프로세스의 우선순위(사용자 요구에 즉각 반응해야 하는 애들이 우선!)

1. 커널 프로세스 > 일반 프로세스

2. 전면 프로세스 > 후면 프로세스

3. 대화형 프로세스 > 일괄 처리 프로세스

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

 

 

CPU 스케줄링은 CPU 스케줄러에 의해 수행되며 CPU가 유휴 상태가 될 때마다 CPU 스케줄러는 준비 완료 큐에 있는 프로세스 중 하나를 선택하여 실행한다. 이때 준비 완료 큐는 FIFO, 우선순위, 트리 등 다양한 자료 구조를 통해 구현된다. 개념적으로 볼 때 준비 완료 큐에 있는 모든 프로세스들은 CPU에서 실행될 기회를 기다리면서 대기하고 있으며, 큐에 있는 레코드들은 일반적으로 프로세스들의 PCB, 즉 프로세스 제어 블록이다.

CPU의 제어를 단기 스케줄러가 선택한 프로세스에게 넘겨주는 '디스패처 dispatcher' 모듈을 통해 문맥 교환, 사용자 모드로의 전환, 프로그램 재시작을 위한 유저 프로그램의 이동과 같은 작업을 수행한다.

 

스케줄링 알고리즘의 성능 척도

<CPU의 입장>

CPU utilization(CPU 사용률): 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율. 가장 이상적인 수치는 100%.

Throughput(처리량): CPU가 단위 시간당 처리하는 프로세스의 개수.

 

<프로세스의  입장>

Trun-around time(반환 시간): 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간이다. 프로세스의 대기 시간 + 실행시간으로, 총 처리 시간이라고도 한다. 여기서 대기는 N(0<=N<=무한) 번 가능하다.

Waiting time(대기 시간): 프로세스가 CPU를 할당받아 실행되기 전 대기 상태일 때의 시간이다. 보통 준비 큐에서 대기를 하는 시간이다.

Response time(응답 시간): 대화식 시스템에서 프로세스가 대기 상태에 들어와 CPU를 최초로 얻기까지 걸리는 시간이다. 대기 시간과의 차이점은 대기는 반환과 마찬가지로 여러 번 있을 수 있어 그 총합이 대기 시간이고, 응답은 최초의 한 번이다. 프로세스 입장에서 CPU를 한 번도 못 얻은 것과 한 번이라도 얻는 것은 사용자 응답에 있어서 중요한 차이가 있기 때문에 중요하다.

 

=> <CPU 이용률, 처리량> 최대화 & <반환 시간, 대기 시간, 응답 시간> 최소화되면 효율성 쵝오

 

스케줄링의 방법들

CPU 스케줄링 결정은 다음의 네 가지 상황에서 발생할 수 있다.

 

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때
   EX) 입출력 요청에 의해 전환

2. 프로세스가 종료할 때

-> 이 두 케이스는 비선점 스케줄링 방식을 사용하는데, 이는 프로세스가 CPU를 점유하고 있으면 뺏을 수 없는 방식이다. 필요한 문맥 교환만 일어나기 때문에 오버헤드가 상대적으로 적지만, 프로세스 배치에 따라 효율성 차이가 많이 난다.

 

3. 프로세스가 실행/대기 상태에서 준비 완료 상태로 전환될 때
  EX) 시간 종료에 의한 인터럽트로 전환 / 입출력 종료 

-> 선점 스케줄링: 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 뺏을 수 있는 방식. CPU 처리 시간이 매우 긴 프로세스의 CPU 독점 사용을 막을 수 있어 효율적이지만 잦은 문맥 교환으로 오버헤드 다수 발생 가능