[OS] 단일처리기 스케줄링

안녕하세요. 회사와 함께 성장하고 싶은 KOSE입니다.

이번 포스팅은 스케줄링에 대해서 정리하는 시간을 가지도록 하겠습니다.!

 

 

1. 처리기 스케줄링 유형

처리기의 스케줄링은 응답 시간이나 처리량 효율성을 증대시키기 위해 처리기가 다음에 실행할 프로세스를 선택하는 것으로 일반적으로 스케줄링은 3단계로 이루어져 있습니다.

 

장기 스케줄링

프로세스가 CPU에 의해 실행될 수 있는 자격을 부여할지 여부를 결정하는 역할을 수행합니다. 장기 스케줄링은 프로세스를 시스템으로 진입시키는 여부를 판단하므로 멀티프로그래밍을 제어하는 역할을 한다고 볼 수 있습니다. 장기 스케줄링은 일괄 처리 큐에서 소정의 규정에 따라 작업들을 골라 프로세스로 만들어줍니다.

 

일괄 처리 큐

• 일괄 처리 큐(Batch Queue)는 여러 작업들이 한 번에 처리되도록 대기열에 모아두는 방식
• 일괄 처리 큐의 주요 역할은 시스템의 효율성을 높이고 자원을 최적화하기 위해 관련 작업을 그룹화하고 순차적으로 처리
• 주로 백그라운드에서 실행되는 작업에 사용될 수 있으며, 작업들을 우선순위에 따라 정렬하여 작업을 처리할 수 있고 유사한 작업을 그룹화하여 한 번에 처리하는 기능을 수행

 

장기 스케줄러가 프로세스를 선택하는 알고리즘

• FCFS(First com first Service)
• 우선순위 기반
• 예상되는 실행 시간의 길이
• 입출력 우대

 

중기 스케줄링

중기 스케줄링은 스와핑 기능의 일부라고 할 수 있습니다. 장기 스케줄링에서 프로세스를 생성했을 때, 주메모리에 프로세스를 스왑인 해야하는 상황이 생길 수 있습니다. (반대로 스왑 아웃 상황) 이 경우 중기 스케줄링은 이러한 스와핑 과정을 수행하는 것을 의미할 수 있습니다. 

단기 스케줄링

단기 스케줄링은 CPU 스케줄러라고 불리며 프로세스들 사이에서 CPU를 할당하는 역할을 수행합니다. 단기 스케줄러는 프로세스들 사이에서 CPU를 우선순위 혹은 요구사항을 고려하여 실행 순서를 결정하고, 컨텍스트 스위칭을 관리합니다. 이때, 디스패쳐와 함께 작동하여 컨텍스트 스위칭을 수행합니다. 

 

디스패쳐란

프로세스 간의 컨텍스트 스위칭을 수행하는 역할을 담당하며 단기 스케줄러와 함께 작동합니다. 디스패처는 단기 스케줄러가 선택한 프로세스를 실행하기 위해 현재 실행 중인 프로세스의 상태를 저장하고 새로 선택된 프로세스의 상태를 불러오는 작업을 수행합니다. 

 

단기 스케줄링 호출

• 새로운 프로세스가 생성되어 실행 대기 상태에 들어감
• 실행 중인 프로세스가 입출력을 요청, 시스템 호출 등을 인해 대기 상태로 전환
• 실행 중인 프로세스가 종료되거나 시간 할당량이 만료되어 다른 프로세스에게 CPU를 넘겨줌

 

 

2. 스케줄링  평가 척도

 

사용자 중심의 성능 관련 평가척도

• 반환시간: 프로세스가 시스템으로 진입한 후로부터 종료할 때까지 걸린 시간을 의미하며, 실제 실행 시간뿐만 아니라, CPU나 다른 자원들을 사용하기 위해 대기한 시간 모두 포함합니다.
• 응답시간: 대화형 프로세스가 시스템에 요구를 한 후, 이에 대한 시스템으로부터 첫 번째 응답이 올 때까지의 시간을 의미합니다. 프로세스는 사용자에게 실행 결과를 출력해 주는 사이에 시스템에 또 다른 요청을 하는 경우가 종종 있습니다. 따라서, 사용자의 입장에서 보면 시스템의 반응 속도를 가늠하기에는 반환 시간보다 응답 시간이 더 적합합니다.
• 완료 기한: 프로세스가 완료되어야 하는 시점에 기한이 있다면, 스케줄러는 다른 평가 척도가 희생당하더라도 완료 기한을 만족시킬 수 있는 프로세스의 수를 최대화하는 방향으로 설계해야 합니다.

 

사용자 중심의 기타 평가척도

• 예측 가능성: 같은 작업이라면 실행될 때마다 동일한 기간 동안 실행되어야 하고, 시스템의 부하 정도에 상관없이 동일한 비용으로 실행되어야 합니다. 만약 실행할 때마다 응답 시간이나 반환 시간이 많이 차이 난다면 사용자들은 시스템을 신뢰하지 못하게 됩니다.

 

시스템 중심의 성능 관련 평가 척도

• 처리량: 처리량을 중시하는 스케줄러는 단위 시간 내에 완료될 수 있는 프로세스의 수를 최대화하는 정책을 사용합니다. 이는 처리해야 할 작업의 양에 관련된 척도로써 각 프로세스 실행 시간의 길고 짧음에 따라 크게 좌우될 수  있습니다. 
• 처리기 이용률: 처리기 이용률이란 전체 시간 중에 처리기가 바쁘게 실행을 한 시간의 비율을 의미합니다. 여러 사용자들이 공유하여 사용하는 고가의 시스템에서 처리기 이용률은 시스템을 효율적으로 사용하고 있느냐 아니냐가 매우 중요한 성능 척도입니다. 

 

시스템 중심의 기타 평가 척도

• 공정성: 시스템이 어떤 특정 목적을 위해 공표하지 않은 이상 어떤 프로세스도 스케줄러로부터 차별을 받아서는 안됩니다. 즉 프로세스가 처리기를 할당받지 못하는 기아 상태 발생을 줄여야 합니다.
• 우선순위: 프로세스들에게 우선순위가 부여되면, 스케줄러는 높은 우선순위의 프로세스를 우대해야 합니다.
• 균형 있는 자원: 활용 스케줄러는 시스템 내의 자원들이 가능한 최대로 활용되도록 해야 합니다.

 

 

3. 스케줄링 정책

 

준비 큐에서 대기 중인 프로세스 중 하나를 선택하는 알고리즘을 함수 형태로 표현한 것은 선택 함수라고 부릅니다. 스케줄링이 선택함수를 적용하는 과정에 사용하는 용어는 다음과 같습니다.

• w: 대기한 시간과 실행한 시간을 모두 합쳐 시스템이 들어온 후 지금까지 경과한 시간
• e: 지금까지 실행하는 데에만 걸린 시간
• s: 프로세스가 시작해서 종료하기까지 걸릴 총 서비스 시간(e를 포함). 이 값은 시스템에 의해 미리 계산되거나 프로세스가 이 정보를 미리 시스템에게 알려주어야 함. 

 

결정 모드는 선택 함수가 호출되는 시점이 언제인가 하는 것을 나타냅니다. 

• Nonpreemptive(비선점) 모드: 프로세스가 일단 실행 상태에 진입하면 종료되거나 자발적으로 CPU를 놓을 때까지는 CPU를 빼앗기지 않습니다. 자발적으로 CPU를 놓는다는 것은 자기가 스스로 블록 시키거나 입출력 요구 및 시스템 서비스 호출 등으로 인해 스스로 준비 큐에서 빠지는 상황을 의미합니다.
• Preemptive(선점) 모드: 현재 실행 중인 프로세스라 할지라도 운영체제에 의해 인터럽트가 걸려 비자발적으로 준비 큐로 이동될 수 있습니다. 현재 실행 중인 프로세스를 선점시킬 수 있는 시점으로는 새로운 프로세스가 진입, 하드웨어로부터 인터럽트가 걸려 이를 대기 중이던 선점된 프로세스가 다시 준비 큐로 들어오는 것, 또는 클록 인터럽트에 의해 주기적으로 스케줄러가 호출되는 시점 등을 들 수 있습니다. 

Preemptive 모드는 NonPreemptive 모드 스케줄링에 비해 프로세스 간 문맥 교환이 자주 발생하기 때문에 이로 인한 오버헤드가 크다고 할 수 있습니다. 하지만 최근 처리기는 문맥 교환에 드는 비용을 최소화하기 위해 하드웨어 수준에서 문맥 교환 연산을 제공하므로 오버헤드 문제가 해결되고 있습니다. 따라서, 기아 상태를 방지할 수 있는 Preemptive 모드가 나은 서비스를 제공합니다. 

 

 

스케줄링 정책의 특징

 

	선택 함수	결정 모드	처리량	응답 시간	문맥 교환 비용	프로세스들에게 미치는 영향	기아 발생 여부
FCFS	max[w]	비선점		길어질 수 있음	최소	입출력 프로세스에 불리	X
Round Robin	상수	선점	시간할당량이 낮으면 처리량이 낮음	짧은 프로세스에게 좋은 응답 시간 제공	최소	공정	X
SPN	min[s]	비선점	높음	짧은 프로세스에게 좋은 응답 시간	커질 수 있음	긴 프로세스에 불리	O
SRT	min[s - e]	선점	높음	좋은 응답	커질 수 있음	긴 프로세스에 불리	O
HRRN	max ((w + s) / s)	비선점	높음	좋은 응답	커질 수 있음	어느 정도 공정	X
Feedback		선점			커질 수 있음	입출력 중심  프로세스 우대	O

 

 

4. FCFS(First-Come-First-Served)

 

FCFS는 가장 단순한 형태의 스케줄링 정책으로 FIFO라고도 합니다. 큐잉 체계를 엄격하게 지키고 있으므로 다음의 절차에 따라 진행됩니다.

 

프로세스	도착 시각	서비스 시간(Ts)	시작 시각	종료 시각	반환 시간(Tr) 종료시간 - 도착시간	정규화된 반환시간 (Tr/Ts)
W	0	1	0	1	1	1
X	1	100	1	101	100	1
Y	2	1	101	102	100	100
Z	3	100	102	202	199	1.99
평균					100	26

 

이 표를 토대로 확인할 수 있는 부분은 긴 프로세스의 경우 상대적으로 짧은 프로세스보다 서비스 시간 자체가 길기 때문에 정규화된 반환시간이 적습니다. 하지만 Y 프로세스는 서비스 시간이 매우 짧지만 앞의 X 프로세스의 긴 시간으로 인해 반환시간이 늦어져 비효율적인 것을 확인할 수 있습니다. 

 

이를 처리기 중심 프로세스와 입출력 중심 프로세스로 대입하여 생각해 보면 다음과 같습니다.

•  입출력 중심 프로세스는 무거운 작업이지만 실제 네트워크 및 디스크 처리 대기 시간이 긴 것이고 CPU의 실행 시간으로 보면 프로그램 카운터로부터 명령어를 입출력 컨트롤러에게 전달하고 제어하는 역할이므로 CPU 버스트는 짧습니다.
• 반면 처리기 중심 프로세스는 실제 CPU가 연산해야 하는 작업이 많으므로 많은 시간이 소요됩니다.
• 따라서, 빠른 시간 내 CPU 버스트를 마칠 수 있는 작업인 입출력 중심의 프로세스임에도 오랜 시간을 대기해야 하므로 비효율적이라고 볼 수 있습니다.

 

 

5. Round Robin

 

라운드 로빈 방식은 어떤 긴 프로세스가 일정 시간을 넘어가는 순간 실행을 강제로 선점(preemption)시키는 것을 의미합니다. 이때 클록 인터럽트가 주기적으로 발생하게 되는데 이 인터럽트 루틴으로 인해 현재 실행 중이던 프로세스는 준비 큐로 이동시키고 준비 큐에서 FCFS 방법으로 다음 프로세스를 골라 실행시킵니다.

 

여기서 사용되는 개념이 시간 할당량으로 모든 프로세스는 정해진 시간 조각만큼만 실행한 후 강제적으로 CPU를 빼앗습니다.

• 시간할당량이 짧은 경우: 시간할당량이 짧은 경우, 짧은 프로세스에게 유리하지만, 짧은 할당 시간으로 인해 컨텍스트 스위칭이 빈번하게 발생하므로 오버헤드가 발생할 수 있습니다.
• 시간할당량이 긴 경우: 긴 프로세스의 경우 끝날 때까지 다른 프로세스가 대기해야 하므로 정규화된 반환 시간이 매우 길었습니다. 만약 시간할당량이 긴 프로세스의 프로세스 시간과 비슷하거나 더 큰 경우 결국 짧은 프로세스는 긴 프로세스의 시간을 전부 기다려야 하게 되므로 FCFS의 문제점을 해결할 수 없습니다.

 

라운드 로빈 방식은 공평한 시간 할당량으로 프로세스를 처리하기 때문에 시분할 시스템이나 트랜잭션 처리 시스템에 매우 효과적일 수 있습니다. 하지만 라운드 로빈 방식에도 입출력 중심 프로세스를 처리하는데 한계가 있습니다. 이 절차를 정리하면 다음과 같습니다.

(공부한 내용이 명확하게 이해가 되지 않아서 제가 이해한 바를 바탕으로 정리하였습니다. 따라서, 사실과 다를 수 있습니다.)

 

• 입출력 중심 프로세스는 처리기 중심 프로세스보다 상대적으로 짧은 CPU 버스트를 가집니다. 따라서 할당된 시간보다 빠르게 1번 요청을 수행하면 입출력 큐로 이동하여 입출력 완료까지 대기합니다. 입출력이 완료되면 준비 큐로 이동합니다.
• 이 과정에서 만약 시간 할당량이 5초라면 2초만 사용하게 되고 3초는 사용하지 못하고 반납하게 됩니다.
• 이어서 만약 처리기 중심 프로세스가 실행이 된다면 이 프로세스는 주어진 시간을 모두 활용한 후 다시 준비큐로 이동하게 됩니다.
• 이 과정을 정리하면, 실제 CPU는 짧은 버스트를 가짐에도 불구하고 입출력 요청을 수행하게 되면 입출력 큐로 이동하고 다시 준비큐로 가게 되므로 실제 시간 할당량을 전부 채우지 못하게 되는 문제가 발생할 수 있습니다.

 

이를 해결하기 위한 방법이 개선된 라운드 가상 라운드 로빈(Virtual Round Robin)입니다. 수행 절차는 다음과 같습니다.

• 입출력 중심 프로세스가 입출력 요청을 수행하면 입출력 큐로 가서 입출력 완료까지 대기합니다.
• 이후, 다시 준비 큐로 이동하는 것이 아니라 보조 큐로 이동하여 현재 수행 중인 프로세스가 CPU를 반납하면 준비 큐보다 먼저 보조 큐에 있는 입출력 중심 프로세스를 스케줄링합니다.
• 이때 만약 앞서 시간 할당량 5초를 기준으로 2초를 소모했다면 3초만 부여하여 다른 프로세스와 동일하게 5초만 수행될 수 있도록 합니다.

 

 

6. SPN(Shortest Process Next)

 

FCFS가 긴 프로세스에 효율적인 점을 극복하기 위해 짧은 프로세스에 우선순위를 두는 방식을 비선점 방식을 SPN이라고 합니다.

이 경우, 각 프로세스의 총 실행 시간을 미리 알아야 한다는 단점이 있는데, 이를 극복하기 위해 단순 평균 혹은 지수적 평균 방법을 적용합니다.

 

Sn+1 = aTn + (1 - a)Sn

 

여기서 알파는 0 < a < 1 사이의 가중치로 과거 측정치에 비해 상대적으로 최근 측정치에 어느 정도의 비중을 둘 것인가를 설정할 수 있는 파라미터입니다.

 

이를 적용하면, 일반적으로 반복되는 특정 프로세스에 대한 총 실행 시간을 예측하여 적용할 수 있습니다. 만약 짧을 프로세스가 있다면 우선순위를 얻게 되어 CPU를 할당받아 처리할 수 있습니다. 이 경우 긴 프로세스는 계속 대기하여 결국 CPU를 할당받지 못하게 되는 기아 상태에 빠질 수 있습니다.

 

 

7. SRT (Shortest Remaining Time)

 

SPN가 프로세스의 총 실행 시간에 따라 프로세스를 선택하는 스케줄링 방법이었다면, SRT는 프로세스가 남아있는 시간을 기준으로 선점 방식으로 프로세스를 선택하는 스케줄링입니다. 즉, 현재 실행 중인 프로세스가 남은 시간이 10초인데, 새로 들어온 프로세스의 남은 시간이 2초라면 선점 방식에 의해 프로세스 CPU를 빼앗고 준비 큐에 있는 프로세스를 선택할 수 있는 방법입니다.

이 역시, 긴 프로세스에 대해서는 기아 상태에 빠질 수 있다는 단점이 존재합니다.

 

 

8.HRRN(Hightest Response Ratio Next)

 

앞 서 정규화된 반환 시간이라는 평가 척도가 존재했었는데, 이러한 정규화된 반환 시간의 평균이 최소화시키는 방향으로 스케줄러를 최적화하는 방법을 HRRN이라고 합니다.

 

R = (w + s) / s
R = 응답 비율
w = 처리기를 기다리며 대기한 시간
s = 예상되는 서비스 시간

 

HRRN은 SPN, SRT처럼 프로세스들의 예상 실행시간에 대한 예측을 해야 한다는 점에서 단점이 있지만, HRRN의 장점은 대기 시간이 긴 프로세스에게도 우선권을 줄 수 있다는 점입니다.

 

해당 수식을 살펴보면, 짧은 프로세스의 경우 s가 매우 짧기 때문에 R의 값이 크게 나와 높은 우선권을 가질 수 있습니다. 하지만 s가 크더라도 만약 이를 상쇄시킬 정도로 w가 더 크다면 대기 시간이 그만큼 커져서 R이 커지게 됩니다. 따라서, 프로세스의 대기 시간을 고려할 수 있다는 점에서 장점을 가집니다.

 

 

9. FeedBack

 

FeedBack은 SPN, SRT, HRRN이 필요로 하는 프로세스의 총 실행시간을 예측할 수 없는 상황에 적용할 수 있습니다. FeedBack 방식은 현재 수행된 수행시간이 길어질수록 낮은 우선순위를 부여하는 방법으로 총 실행 시간을 예측할 수 없더라도 실행 시간이 길어진다면 곧 긴 프로세스임을 의미하므로 비슷한 효과를 얻을 수 있다는 개념입니다. 이를 구현하기 위해서는 우선순위 큐가 여러 개 구성되게 됩니다.(다단계 피드백)

 

수행 절차는 다음과 같습니다.

• 프로세스 A가 시간 할당량을 채우지 못하고 5초의 누적된 수행시간을 기록합니다.
• 프로세스 A는 우선순위 큐 RQ1에 입력이 되고 준비 큐에 있는 다른 프로세스들이 실행됩니다.
• 프로세스 B는 시간 할당량 이내에 처리되어 CPU가 반납되었고(누적시간 2초) 프로세스 C는 RQ0에서 나와 시간 할당량을 채우지 못하고 5초의 누적된 수행시간을 기록합니다.
• 이때,  프로세스 B가 입출력 요청을 완료하여 다시 RQ1으로 오게 되면 누적 시간이 적으므로 프로세스 B가 먼저 실행됩니다.
• 우선순위 큐 RQ1에서 프로세스 A를 빼서 실행했는데 시간 할당량을 채우지 못하여 10초의 누적된 수행시간을 기록합니다.

이러한 절차대로 수행될 경우, 짧은 프로세스의 경우 우선권을 얻을 수 있습니다. 하지만, 긴 프로세스의 경우 계속 우선권에서 밀려 기아 상태에 돌입할 수 있게 됩니다.

 

따라서, 우선순위 큐 RQn에 시간 할당량 p를 다르게 부여하는 방법이 있습니다. 예를 들어 RQ1은 p = 1, RQ2는 p = 2 등으로,
우선순위가 계속 밀린 긴 프로세스가 선택되면 긴 시간 할당량이 적용될 수 있도록 하는 방법도 있습니다.

(하지만, 실제 우선순위를 보장하지는 않으므로 계속 기아상태에 머물 수 있다는 점도 있습니다.)

 

이상으로 단일 처리기 스케줄링에 대한 정리를 마치도록 하겠습니다.

감사합니다!!!