[운영체제] Uniprocessor Scheduling

Scheduling

 

처리기 스케줄링의 목적을 한마디로 표현하면 "응답 시간이나, 처리량, 효율성을 증대시키기 위해 처리기가 다음에 실행할 프로세스를 선택하는 것" 이다. (응답시간 ↓, 처리량 ↑, 효율성 ↑)

 

대기 큐의 구조를 최적화하는 문제도 스케줄링의 성능에 중요한 요소일 것이다.

 

Types of Scheduling

 

 

Long - Term Scheduling

- Batch System

- 프로세스를 시스템으로 진입시킬지 말지를 결정한다.

- 멀티프로그래밍의 정도를 제어하는 역할

- 프로세스가 많아질수록, 자기 순서에 할당받게 될 실행시간은 짧아진다.

- 시분할 시스템에서 대화형 프로그램의 경우에는 실질적인 프로세스 생성 요청이 장기 스케줄러로 들어온다.

 

프로세스는 언제 생성되는가?

- 각 프로세스들이 종료될 때

- 프로세서의 부하가 일정 수준 이하로 떨어지는 순간

 

 

어느 프로세스를 선택하여 올릴 것인가?

- FCFS (First Come First Served)

- Priority

- Execution time

- I/O requirements

- Balancing of processor-bound and I/O-bound processes

 

 

 

 

Medium - Term Scheduling

- 스와핑 기능의 일부

- 멀티프로그래밍의 정도를 제어하는 일

 

 

Short - Term Scheduling

- dispatcher로 라고도 불림.

- 매우 자주 실행됨.

- 이벤트가 발생할때 호출된다. (Clock interrupt, Memory Fault, I/O interrupts, Operating system calls, Signals)

 

 

Short-Term Scheduling Criteria

 

우선순위에 기반한 스케줄링

 

- 스케줄러는 항상 우선순위가 가장 높은 프로세스를 다음번 프로세스로 선택

- 우선순위를 나타내기 위한 여러가지의 준비 큐를 가지고 있음.

- 낮은 우선순위의 프로세스가 계속 할당받지 못해 실행되지 못할 가능성이 있다는 점 -> starvation 발생

 

 

 

Scheduling Policies (스케줄링 정책들)

- FCFS

- Round Robin

- SPN (Shortest Processes Next)

- SRT (Shortest Remaining Time)

- HRRN (Highest Response Ratio Next)

- Feedback

 

 

1. Selection function

w = 대기한 시간과 실행한 시간을 모두 합쳐 시스템에 들어온 후 지금까지 경과한 시간

e = 지금까지 실행하는 데에만 걸린 시간

s = 프로세스가 시작해서 종료하기까지 걸릴 총 서비스 시간 (당연히 e를 포함하고 있으며, 이 값은 이미 계산되어 있어야 한다. 아니라면 프로세스가 이 정보를 미리 시스템에 알려주어야 한다.)

 

* 선택함수 max[x]는 시스템에 진입한지 가장 오랜 시간을 보낸 프로세스를 선택하라는 뜻이므로 FCFS 정책이다.

 

 

2. Decision mode

Selection function이 호출되는 시점

 

- Nonpreemptive (비선점 모드)

 

프로세스가 일단 실행 상태에 진입하면 종료되거나 자발적으로 CPU를 놓을 때(스스로 블록시키거나, 입출력 요구 등으로 인해 준비 큐에서 빠지는 상황)까지는 CPU를 빼앗기지 않는다.

 

- Preemptive (선점 모드)

 

- 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비큐로 이동될 수 있다.

- 현재 수행중인 프로세스가 운영체제에 의해 강제적으로 CPU를 떠날 수 있다.

- 한 프로세스가 프로세서를 오랫동안 독점하는 현상을 방지할 수 있다.

 

 

 

First-Come-First-Served (FCFS)

 

 

- Selection function : max[w]

- Decision Mode : nonpreemptive

- 프로세스는 준비 큐에 들어간다.

- 현재 실행중인 프로세스가 종료되면 준비 큐에서 대기중이던 프로세스 중 가장 오랫동안 기다렸던 프로세스가 다음번 실행할 프로세스로 선정된다. 

 

 

 

 

FCFS는 짧은 프로세스보다는 긴 프로세스에게 유리하다.

처리기 중심 프로세스를 우대한다.

 

다음의 예를 보자

다음과 같이 Y는 서비스 시간이 W나, Y에 반해 100배기 때문이다.

또한, nonpreempt 모드이기 때문에 처리기 중심 프로세스는 종료될 때까지 계속 실행할 것이다. 그 동안 다른 프로세스들은 준비 상태일 것이므로 프로세스에게 더 유리하다.

 

 

 

 

Round-Robin

- Selection function : constant

- Decision Mode : preemptive (based on a clock)

 

Time quantum = 1 일때

 

 

Time quantum = 4 일때

 

 

- 위 예시와 같이 Time quantum이 있기때문에 Clock interrupt가 주기적으로 발생한다.

- 인터럽트가 발생하면 현재 실행중이던 프로세스는 레디 큐로 이동한다. (준비 큐에서 FCFS 방식으로 프로세스 선택)

- time slicing이라고도 불린다.

 

* 설계 이슈 : time quantum(시간 할당량)의 길이

time quantum이 짧다면 -> 짧은 프로세스일수록 상대적으로 일찍 종료될 수 있지만, 오버헤드가 상당히 커지게 됨.

time quantum이 길다면 -> FCFS와 같은 효과를 가진다.

 

- 범용 시분할 시스템에서 효율적이다.

- Drawback (약점)

처리기-중심 프로세스와 입출력-증심 프로세스를 차별할 수 밖에 없는 한계를 가지고 있음.

I/O 작업이 위주인 프로세스의 경우에는 주어진 time quantum을 다 쓰지 못하고 프로세서를 떠나야 하는 경우가 자주 발생

 

-> Virtual Round Robin Scheduler 제시

 

 

 

기존 라운드 로빈에서는 입출력이 완료된 프로세스는 준비 큐의 끝으로 들어가게 되어 있으나(그래서 입출력-중심 프로세스와 처리기-중심 프로세스가 준비큐에서 섞임), 가상 라운드 로빈에서는 입출력이 완료된 프로세스는 보조 큐라고 하는 별도의 FCFS 큐로 진입한다.

다음번 프로세스를 고르는 시점에서는 스케줄러는 보조 큐에서 대기 중인 프로세스를 준비 큐보다 먼저 실행한다.

 

 

 

Shortest Process Next (SPN)

- Selection function : min[s]

- Decision mode : Nonpreemptive policy

- 가장 짧은 프로세스를 먼저 실행시킨다.

- processing time을 알아야한다.

- long process에게 페널티가 있다.

- Response time이 향상된다.

 

 

 

processing time을 어떻게 추정할 것인가?

운영체제는 각 작업을 몇 번씩 실행시켜 본 후 평균 실행 시간에 대한 통계를 내어 활용해도 된다.

 

 

 

 

Ti = 해당 프로세스의 i번째 스케줄링 순번 때 실행한 처리기 시간
Si = i번째 스케줄링 순번 때 예상되는 실행시간
S1 = 첫 번째 스케줄링 순번 때 예상되는 실행시간

 

 

위의 식에서는 모든 스케줄링 순번에서의 실행 시간에 동일한 가중치를 두고 있다. 즉, 각항에 동일한 상수 1/n이 곱했다.

과거의 데이터를 그 시점에 따라 다른 가중치를 두어 활용하는 방식을 time series(시계열 방식) 이라 하는데, 이에 기반하여 미래 값을 예측하는 기법을 Exponential averaging(지수적 평균)이라고 한다. 앞의 수식을 다음과 같이 나타낼 수 있다.

 

 

 

 

하지만 발생할 수 있는 단점은 짧은 프로세스들이 계속해서 시스템에 진입한다면, 긴 프로세스가 기아(starvation)에 빠질 수 있다는 점이다.

 

이 또한 비선점모드로 동작하기 때문에 FCFS에서 예시로 들었던 예시 중 프로세스 Y를 생각하면 알 수 있을 것이다.

 

 

 

Shortest Remaining Time (SRT)

Selection function : min[s-e]

Decision mode : Preemptive version of SPN

긴 프로세스는 starvation에 빠질 가능성이 있다.

 

 

 

 

 

Highest Response Ratio Next (HRRN)

Selection function : max((w+s)/s)

Decision mode : Non-preemptive

R 값이 가장 큰 프로세스를 다음번 프로세스로 선택한다.

 

서비스 시간이 짧은 프로세스의 R값이 상대적으로 크기 때문에, 짧은 프로세스를 우대하는 면이 있지만, 대기 시간 때문에 시스템에서 오래 머문 긴 프로세스도 오래 머물면 머물수록 R 값이 커지기 때문에 홀대받지 않는다.

 

 

A와 B가 진행하고 Time 9 이후로는 C = (5+4)/4, D = (3+5)/5, E =(1+2)/2 이므로 C E D 순서로 진행한다.

 

 

 

Feedback

프로세스들의 예상되는 service time을 예측하기 어려운 경우 위에 SPN, SRT, HRRN 방법을 사용할 수 없다.

짧은 프로세스에 대한 선호도를 높일 수 있는 또 다른 방법은 오랫동안 실행하고 있는 작업들이 단계적으로 불이익을 받도록 하는 것이다.

즉, 남아 있는 실행 시간에 관심을 두기 보다는 지금까지 실행한 시간에 관심을 두면 유사한 효과를 본다는 것이다.

 

규칙 1: 우선순위(A) > 우선순위(B)일 경우, A가 실행, B는 실행되지 않는다.

규칙 2: 우선순위(A) = 우선순위(B), A와 B는 RR방식으로 실행된다.

규칙 3: 작업이 시스템에 들어가면 최상위 큐에 배치된다.

규칙 4: 작업이 지정된 단계에서 배정받은 시간을 소진하면, 작업의 우선순위는 감소한다.(즉, 한 단계 아래 큐로 이동)

 

multilevel feedback 이라고도 불림.

 

 

 

 

 

 

 

- 긴 프로세스일수록 더 낮은 단계의 레디 큐로 밀리게 된다.

- processing time을 estimate하지 않아도 된다.

- 스케줄링을 시간할당량이 있는 선점 모드로 운영하면서 동시에 동적인 우선순위 정책을 병행하여 사용

- 새로 도착한 프로세스일수록, 짧은 프로세스일수록 오래된 프로세스나 긴 프로세스보다 우대받는 정책

- 긴 프로세스들의 반환 시간이 과도하게 길어질 수 있다는 점이다. -> starvation 발생가능성이 있음.

 

starvation 가능성을 줄이는 방법은 시간 할당량의 크기를 큐 별로 다르게 하여 프로세스 선점 시점을 다양하게 하는 것이다.

 

 

 

 

전체적으로 정리해보면

 

 

 

 

 

 

 

Fair-Share Scheduling

- 사용자 응용 프로그램이 여러 개의 프로세스(또는 쓰레드)들로 구성된 경우가 많다.

- 자신의 프로세스 집합이 어떻게 동작하는지에 관심을 가진다.

- 프로세스 집합 단위의 스케줄링 방식이다.