CPU Scheduling: CPU 스케줄링 (1/2)

CPU는 프로그램의 기계어 명령을 실제로 수행하는 중앙처리장치이다. 프로그램이 시작되어 메모리에 올라가면 pc(레지스터의 일종)가 cpu가 실행해야 할 명령의 메모리 주소값을 가리키고 있다. cpu는 컴퓨터 내부에 하나밖에 없기 때문에 매우 효율적으로 사용하여야 하는 하드웨어 자원이다. 

<프로그램 실행 관련된 기계어 명령>

- 일반명령

1. cpu 내부에서 수행되는 명령 ex) add 연산 (레지스터에 있는 두 값을 더해 레지스터에 저장하는 명령. cpu 내에서만 수행되므로 정말 빠르다)

2. 메모리 접근을 필요로 하는 명령 ex) load, store (load : 메모리 데이터 -> cpu / store : 계산된 결과값 -> 메모리 둘 다 cpu 내에서만 수행된느 것보단 느리지만 비교적 짧은 시간이 걸림)

 - 특권 명령

1. 입출력을 동반하는 명령 : 위의 일반 명령에 비해서 오래 걸린다. 

 

<프로세스의 특성 분류> 

 프로그램은 cpu - i/o - cpu - i/o - cpu - i/o 이렇게반복되어서일어난다.

 

* CPU bound process

사용자 프로그램이 직접 cpu를 가지고 빠른 명령을 수행하는 단계 계산 위주의 단계

즉, i/o를 한번 수행한 후 다음번 i/o를 수행하기까지 직접 cpu를 잡고 명령을 수행하는 일련의 작업

few very lont cpu bursts

* I/O bound process

I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계이다. 사람과의 interaction이 많다. 대화형 프로그램 

many short cpu bursts

프로그램은 cpu burst 와 i/o burst의 반복이지만 프로그램 종류에 따라 빈도는 다를 수 있다. 

 

위 그래프에서 알 수 있듯 i/o bound job은 cpu를 아주 짧게 쓰고 중간에 i/o가 끼어드는 job(process)이다. cpu를 많이 쓰는게 아니라 i/o가 끼어 드니까 cpu 사용빈도가 높은 것이다. 

cpu bound job은 cpu를 길게 쓰고 빈도는 적다.

여러 종류의 job이 섞여 있기 대문에 job에게 적절한 response를 제공해야 한다. = interactive job에서 적절한 response를 제공해야 한다. cpu는 공평함보다 효율성이 우선이고 i/o를 너무 오래 기다리게 해서는 안된다. cpu 버스트 짧은 프로세스에게 우선적으로 cpu 사용권을 주는 스케줄링 필요하다.

 

<CPU Scheduler & Dispatcher>

- cpu 스케줄러

cpu 스케줄러(운영체제 안에서 수행되는 코드임. 하드웨어 아니다)는 ready 상태의 프로세스 중에서 이번에 cpu를 누구에게 줄지 프로세스를 고르는 역할을 수행한다. 사용자 프로세스는 cpu를 잡고 수행하다가 시간이 다 되어 타이머 인터럽트가 발생하면 cpu scheduler가 호출이 된다. 그러면 cpu 스케줄러는 ready queue에서 cpu를 기다리는 프로세스 중 하나를 선택해 cpu를 할당하게 된다. 이 밖에도 cpu 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있을 때가 있는데

1. running -> blocked (ex. i/o 요청하는 시스템 콜 했을 떄) - 자진 반남
2. running -> ready (ex. 할당 시간 만료 되어 timer interrupt 발생했을 때) - 강제 빼앗김
3. blocked -> ready (ex. i/o 완료 후 인터럽트) - 강제 빼앗김
4. terminate (종료되어서 할일 없을 때) - 자진 반납

1, 4, 와 같은 스케줄링을 (자진반납) nonepreemptive(비선점형) 방식이라고 하며 2,3과 같은 방식을 (강제 빼앗김) preemptive(선점형)방식이라고 한다. 사실 1, 3을 제외한 모든 스케줄링은 선점형이라고 생각할 수 있다. 그리고 3번은 i/o 완료 되었다고 바로 cpu를 받는 것은 아닌데, priority가 높으면 받을 수도 있다. 

비선점형 방식은 cpu를 획득한 프로세스가 자진해서 프로세스를 내놓기 전까지는 프로세스를 내놓지 않는 방식을 말하고, 선점형 방식은 프로세스가 cpu를 계속 사용하길 원하더라도 강제로 빼앗을 수 있는 것을 말한다. 

 

- dispatcher

cpu 스케줄러가 어떤 프로세스에게 cpu를 줄지 결정한다면, cpu를 넘겨주는 역할을 할 것이 필요하다. 그것이 dispatcher이다. 애는 운영체제 안에서 수행되는 코드이며 cpu의 제어권을 cpu scheduler에 의해 선택된 프로세스에게 넘긴다. 디스패처는 현재 수행 중이던 프로세싀 문맥을 그 프로세스의 pcb에 저장하고, 새롭게 선택된 프로세스의 pcb로부터 문맥을 복원한 뒤 그 프로세스에게 cpu를 넘기는 과정을 수행한다. 이 과정을 context switch(문맥 교환)이라고 한다. 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 cpu를 전달하기까지 걸리는 시간을 디스패치 지연 시간(dispatch latency)라고 한다. 디스패치 지연시간의 대부분은 문맥교환 오버헤드에 해당한다.

 

<Scheduling Criteria>

프로세스 1개의 개념 x, cpu burst의 개념 그니까 프로세스가 완전 종료될때까지가 아니라 한 cpu 버스트가 끝날때까지다.

- 시스템(CPU) 입장에서 성능 적도

(1) CPU utilization (이용률)

keep the CPU as busy as possible: CPU가 놀지 않고 일한 비율

(2) Throughput (처리량)

# of process that complete their execution per time until: 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지 (cpu burst 완료한 프로세스의 개수), 즉 cpu 서비스를 원하는 프로세스 중 몇개가 원하는 만큼의 cpu를 사용하고 이번 cpu 버스트를 끝내어 준비 큐를 떠났는지 측정한 것 -> 주어진 시간에 더 많은 프로세스들이 cpu 작업을 완료하기 위해선 cpu 버스트가 짧은 프로세스에게 우선적으로 할당하는 것이 유리하다. 

- 프로세스(사용자) 입장에서 성능 척도

(3) Turnaround Time (소요시간, 반환시간)

amount of time to execite a particular process: cpu를 쓰러 들어와서 cpu버스트 끝나고 나갈 때까지 총 걸린 시간. 준비 큐에서 기다린 기간 + 실제로 cpu 사용한 시간

(4) Waiting Time (대기 시간)

amount of time a process has been waiting in the ready queue: 레디 큐에 들어와서 줄서서 기다린 시간. cpu 사용하고 또 줄서고 또 줄서고 이런 식으로 여러번 줄 설 수 있다. 그 시간들의 총합임

(5) Reponse Time (응답 시간)

amount of time it takes from when a reqiest was submitted until the first response is produced: 레디큐에 들어와서 처음으로 cpu를 얻기까지 걸린 시간

타이머 인터럽트가 빈번히 발생할수록 각 프로세스가 cpu를 연속적으로 사용할 수 있는 시간은 짧아진다. 그러므로 처음 cpu를 얻기까지 걸리는 시간은 줄어들어 응답 시간은 향상된다. 응답시간은 대화형 시스템에 적합한 성능 척도로 사용자에게 가장 중요한 성능 척도라고 할 수 있겠다.

나는 이제부터 중국집 사장이다. 주방장(cpu)을 고용했다.

1 = 주방장이 놀지 않고 일하는 시간

2 = 중국집 손님을 단위시간 당 몇명이나 먹였나

3 = 손님이 들어와서 주문(코스요리)하고 먹고 중간중간 다음 코스 요리 기다린 시간까지 더한 것

4 = 손님이 순수하게 기다린 시간 (먹은 시간은 제외)

5 = 첫 음식 나올 때까지 기다린 시간