1. Project Introduction

프로세스는 실행하며 CPU burst와 I/O burst의 사이클을 가지게 된다. 다른 표현으로는 CPU execution과 I/O waiting의 사이클을 가진다고도 한다. (CPU burst : CPU 할당 받아서 실제 처리되는 부분, I/O burst : I/O 작업 처리하는 시간)

위 사진처럼 모든 프로세스는 CPU burst로 시작하고, 그 뒤에는 I/O burst, 그 뒤에 다시 CPU burst의 순환을 갖고, 가장 마지막에 다시 CPU burst로 끝이 나게 된다.

만약 A 프로세스의 I/O 작업을 기다리는 상황에(wait for I/O) 다른 프로세스를 실행시키지 못한다면 분명 굉장한 시간 낭비가 될 것이다. 이처럼 어떤 프로세스의 I/O 작업을 기다리는 상황에서 다른 프로세스에게 올바른 기준에 의해 CPU를 할당하는 것이 CPU 스케줄링이다.

2. Project Goals

이번 프로젝트는 Ready Queue에 있는 프로세스들 중 어떤 프로세스를 어떤 기준에 의해 CPU를 할당해야 하는지를 결정하는 것이다. 스케줄링이 필요한 이유는 CPU 이용율(CPU Utilization)을 최대화하기 위해서 이다. 만약 하나의 프로세스가 CPU를 점유하여 실행하다가

특정 I/O처리를 기다려야 한다면, 나머지 프로세스는 Ready Queue에 머무르게 되고 I/O처리를 하는 시간(I/O Burst)동안 CPU는 쉬게 될 것이다. 이는 CPU 이용률을 떨어뜨리게 된다. 따라서 적절한 스케줄링 방법을 사용하여 CPU Burst Time을 최대로 하는 것이 스케줄링의 목적이며 이번 프로젝트의 목적이다. 또한, 각종 스케줄링 정책을 활용하여 CPU burst와 I/O burst에 따른 성능 비교를 통해 프로세스 상태에 따른 효율적인 스케줄링 정책을 찾는 것 또한 목표로 한다.

3. Concepts used in CPU simulation

1) 스케줄링이란?

스케줄링이란 현재 실행 중인 프로세스로부터 다른 프로세스로 CPU를 넘겨주어야 할 때, 기다리고 있는 여러 프로세스 중에 OS가 누구를 선택해야 할지에 대한 방식이나 기준을 설정하는 것이다. 따라서 한정된 자원으로 최대한의 성능을 이끌어내기 위해서는 CPU를 적절하고 효율적으로 사용해야 한다. 따라서 OS는 실행 대기 중인 프로세스들에게 자원 배정을 적절히 하여 시스템의 성능을 끌어올리는 역할을 한다.

스케줄링은 다음과 같은 때에 일어난다.

⦁ Running → Waiting 상태 : ( ex. I/O 요청, 자식프로세스 종료 - wait() 요청을 통해 종료)
⦁ Running → Terminate 상태 : ( ex. 부모프로세스의 종료 )
⦁ Running → Ready 상태 : ( ex. 인터럽트 발생 )
⦁ Waiting → Ready 상태 : ( ex. I/O 완료 )

1-1) 스케줄링 단계

▷ 장기 스케줄링

어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것 인가를 결정하는 단계로서 시분할 스케줄링의 경우 사용자의 접속 시도를 허용할지 말지 결정하는 것을 예로 들 수 있다. 장기 스케줄러의 경우 수행 횟수가 적으며, 대부분 FIFO(First in First out)형태로 사용하게 된다.

▷ 중기 스케줄링

보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가를 결정한다. 어떤 프로세스를 다시 Swap in을 할 것인가를 결정하는 것으로 장기와 단기 사이의 중간단계에 속한다.

▷ 단기 스케줄링

준비상태에 있는 프로세스들 중에서 어느 프로세스에게 CPU를 할당할지를 결정하는 단계로서, 프로세스 스케줄러 또는 디스패처에 의해 수행된다.

인터럽트가 발생 혹은 실행 중인 프로세스에 의해 System Call이 발생하는 경우 수행되는 단계이다.

1-2) 스케줄링 정책

멀티 프로세스 운영체제에서 하나의 CPU가 여러 프로세스를 실행하기 위해선 스케줄링 정책이 중요하다.

● Non-Preemptive Scheduling(비 선점 스케줄링) ( ex) FIFO, SJF, HRN )
비 선점형 OS는 현재 실행 중인 프로세스보다 높은 우선순위를 가지는 프로세스가 실행된다고 해서 실행 대상을 바로 변경하지 않는다.
새로 실행된 높은 우선순위의 프로세스가 실행되기 위해서는 현재 실행 중인 프로세스가 명시적으로 CPU를 양보할 때까지, 혹은 I/O 작업 등으로 block 상태가 될 때까지 기다려야만 한다.

● Preemptive Scheduling(선점 스케줄링) ( ex) RR, SRT, MFQ )
선점형 OS는 실행 중인 프로세스보다 높은 우선순위의 프로세스가 실행되면, 스케줄러에 의해 실행 순서가 적극 조정되는 OS를 뜻한다.
또한, 비 선점형 OS에 비해 훨씬 더 스케줄링이 복잡하게 처리가 되어 있는데, 우선순위가 같은 프로세스들 간 실행 배분에도 관여하기 때문이다.

● Priority Scheduling(우선순위 스케줄링)

각각의 프로세스마다 우선순위를 부여해서 우선순위가 높은 프로세스를 먼저 실행시키는 알고리즘이다.

1-3) 스케줄링 기법

1. FIFO(First In First Out)

FIFO 스케줄링은 프로세스들이 대기 큐에 도착한 순서에 따라 CPU를 할당받는 방식이다. FIFO 방식은 하나의 프로세스가 CPU를 할당받게 되면 프로세스가 모두 완료될 때까지 CPU를 점유하게 된다. 따라서 다른 스케줄링 방식에 비해 작업 완료 시간을 예측하기가 쉽다. 하지만 선점이 불가능하기 때문에 수행시간이 긴 프로세스가 할당받은 상태라면 수행시간이 짧은 프로그램이 오랜 시간 대기할 경우가 생기고 중요한 작업이 대기 하는 상황이 발생할 수 있다.

2. SRT (Shortest Remaining Time)

SRT 방식은 대기 큐에서 기다리는 작업 중 수행시간이 가장 짧다고 판단되는 것을 가장 먼저 수행하는 스케줄링 방법이다. FIFO방식 보다 평균대기 시간을 감소시키지만 큰 작업일수록 FIFO에 비해 예측이 어렵다. 긴 작업보다 짧은 작업 일 수록 오버헤드 면에서 볼 때 유리하다. 하지만 이 방법은 수행할 작업이 얼마나 긴지를 정확히 판단해서 수행해야 하는데 수행시간을 정확히 얻는 것이 어렵다.

3. HRN(Highest Responce ratio Next)

대기 시간과 실행 시간을 적절하게 혼합하여 어느 작업에 CPU를 먼저 할당할지 결정하는 방법 (HRN 값 = (대기 시간 + 실행 시간) / 실행 시간)

4. Round-Robin (순환 처리)

라운드 로빈 스케줄링은 FIFO 방식으로 각 프로세스는 같은 크기의 타임 퀀텀을 할당받는다.
만약 프로세스가 할당받은 시간 동안 작업을 완료하지 못하면 다음 프로세스로 넘어가고 실행 중이던 프로세스는 준비 완료 리스트의 가장 뒤로 보내진다.

5. Multi-level-Queue (다단계 큐)

Multi Level Queue는 대기 큐가 여러 개 존재한다. 이때, 프로세스는 생성될 때 정해지는 우선순위에 따라 해당 우선순위에 해당하는 대기 큐에 등록된다. 각 큐는 별도의 스케줄링 알고리즘을 가지고 있으며 큐 사이에도 스케줄링이 존재한다. 즉, 각 큐는 절대적인 우선순위를 가진다. 우선순위가 높은 큐에 존재하는 프로세스부터 실행되며 상위 우선순위 큐가 비어야만 다음 우선순위의 대기 큐를 실행할 수 있다. 작업은 한 큐에서 다른 큐로 옮겨지지 않기 때문에 스케줄링 부담이 적지만 융통성이 떨어진다.

우선순위가 낮은 프로세스가 오랫동안 CPU 할당을 기다리는 기아현상이 발생할 수도 있다.

6. Multi-level Feedback Queue (다단계 피드백 큐)

Multi-level-Queue의 공평성 문제를 완화하기 위해 나온 알고리즘이다. 이 알고리즘에서는 우선순위가 변동되기 때문에 큐 사이의 이동이 가능하다. 즉, 여러 개의 ready queue를 사용하여 각 queue마다 priority(우선순위) 와 time quantum을 다르게 할당하고 프로세스가 들어오면 가장 상위 queue에 넣었다가, 해당 queue의 time quantum이 지나도 프로세스가 종료되지 않았다면 하위의 queue로 끌어내리는 스케줄링 방식이다. 일정 시간동안 수행되지 못하고 남아있는 프로세스(기아상태)는 다시 상위 큐로 끌어올려주는 에이징 기법을 사용하여 상위 큐로 끌어올리기도 한다.

1-4) 스케줄링의 목적

⦁ No starvation : 각각의 프로세스들이 오랜 시간동안 CPU를 할당받지 못하는 상황이 없도록 한다.

⦁ Fairness : 각각의 프로세스에 공평하게 CPU를 할당해준다.

⦁ Balance : Keeping all parts of the system busy

⦁ Batch System : 일에 대한 요청이 발생했을 때, 즉각적으로 처리하는 것이 아닌 일정기간 또는 일정량을 모아뒀다가 한 번에 처리하는 방식

⦁ Throughput : 시간당 최대의 작업량을 낸다.

⦁ Turnaround time : 프로세스의 생성부터 소멸까지의 시간을 최소화한다.

⦁ CPU utilization : CPU가 쉬는 시간이 없도록 한다.

⦁ Interactive System : 일에 대한 요청에 대해 즉각적으로 처리하여 응답을 받을 수 있는 시스템

⦁ Response time : 즉각적으로 처리해야하는 시스템이므로 요청에 대해 응답시간을 줄이는 게 중요하다.

⦁ Time Sharing System : 각 프로세스에 CPU에 대한 일정시간을 할당하여 주어진 시간동안 프로그램을 수행할 수 있게 하는 시스템

⦁ Meeting deadlines : 데이터의 손실을 피하며, 끝내야하는 시간 안에 도달해야한다.

⦁ Predictability : 멀티미디어 시스템에서의 품질이 저하되는 부분을 방지해야한다.