라운드 로빈 대기시간 계산 - laundeu lobin daegisigan gyesan

스케줄링들을 크게 비선점과 선점으로 분류하였습니다. '선점(preemtive)'의 사전적 의미는 '남보다 앞서서 지지하는 것'입니다. CPU 스케줄링에서는 실행 중인 프로세스를 CPU가 대기 상태(block)로 만들 수 있는 권한을 차지하고 있는 것을 선점 스케줄링이라고 합니다. 실행 중인 프로세스를 블록 시키는 기준은 타임 슬라이스(time slice; 시간 할당량)입니다. 그래서 선점, 비선점을 구분하는 방법의 기준이 됩니다.

비선점 스케줄링인 FCFS에 타임 슬라이스 개념을 추가하면, 선점 스케줄링인 라운드 로빈이 되고, 이와 마찬가지로 SJF는 SRT와 대응됩니다.

HRN은 비선점이며, Highest Response ratio라는 값이 높은 것을 우선 처리하는 스케줄링입니다. 관련 공식은 기사 시험에서 자주 다루니 꼭 암기하는 것이 좋습니다.

본 문제에서는 다루는 라운드 로빈(Round Robin) 스케줄링은 FCFS 스케줄링처럼 먼저 대기 큐에 있는 프로세스를 먼저 처리하지만, 정해진 시간할당량(time slice)이 지나면, 그 프로세스는 block이 되어 대기큐에 입력이 되며, 그다음 순서의 프로세스들을 같은 방식대로 처리합니다.

단일 처리 시스템에서는 실행 중인 프로세스(A)가 존재하는데 다른 프로세스(B)가 입출력을 요청하면 그 프로세스(B)는 이전의 프로세스(A)의 자원을 놓을때까지 대기하고 있어야합니다. 하지만 다중 프로그래밍에서는 여러 프로세스들이 동시에 돌아갈 수 있으며, 프로세스가 자원(프로세서 등)을 요청하면 운영체제는 그 자원을 적절히 분배하여 프로세스에게 할당합니다. 그래서 다음과 같은 장점을 얻을 수 있습니다.

1. CPU의 활용 극대화

2.프로세스 처리율(시간 당 작업량)을 늘릴 수 있습니다.

프로세스는 필요한 자원을 할당받기 위해 큐에 대기합니다. 그래서 그 큐에 있는 프로세스를 어떻게 스케쥴링하는지가 프로세스 스케줄링 알고리즘이라고 합니다. 그레서 어떤 스케줄링 알고리즘이 있는지 봅시다. 

잠깐 프로세스 스케줄링에 관한 용어 몇가지만 알아보고 가도록 합시다. 대기 시간, 실행 시간, 반환 시간입니다. 

1 선입선처리 스케줄링(First Come First Served, First In First Out)

선입선처리(FCFS, FIFO) 알고리즘은 말 그대로 먼저 요청한 프로세스가 먼저 자원을 제공받으며 이미 사용중이라면 사용이 끝날때까지 기다려야하는 스케줄링 방식입니다.

프로세스 5개가 있고, 각가 P1의 실행시간 10, P2의 실행시간 5, P3의 실행시간 6, P4의 실행시간 9, P5의 실행시간 10이라고 할때 반환 시간을 알아보도록 하죠.

먼저 요청한 프로세스가 먼저 제공받으니 P1부터 차례대로 자원을 할당받습니다. 그래서 프로세스의 반환시간과 대기시간을 구하면 아래와 같습니다.

2. 최소 작업 우선 스케줄링(Shortest Job First)

프로세스의 실행 시간을 이용하여 가장 짧은 시간을 갖는 프로세스가 먼저 자원을 할당받는 방식입니다. 이 방식은 선점할 수도 있는 스케줄링 방식입니다. 이전에 FIFO방식은 중간에 다른 프로세스가 들어오면 그 프로세스는 대기해야했죠? 이 스케줄링 방식은 선점 또는 비선점이 가능합니다. 위와 같은 프로세스라고 할때 비선점형 SJF 스케줄링의 결과는 아래와 같습니다.

자 P1이 먼저 요청해서 자원을 할당받아 놓은 상태인데, P2가 도착합니다. 비선점형이기 때문에 P2는 우선 기다리고 있는데 P1의 작업이 끝나기 전에 P3, P4 ,P5의 요청이 도착하네요. 그러면 실행 시간이 가장 작은 P4가 자원을 할당받아 쓰고 그 다음인 P3이 자원을 할당받아 사용합니다. 이렇게 되면 위와 같은 결과가 도출되지요.

그렇다면 비선점형 SJF는 어떨까요? 아래의 표가 선점형 SJF의 결과입니다.

이해를 돕기 위해서 아래의 간트 차트를 보세요.  P1이 먼저 도착해서 수행하고 있는 와중에 P2가 도착하는데요. P2는 수행되어야할 시간이 P1보다 크니 P1은 계속 작업을 수행합니다. 그러다가 P3가 도착하는데 P1이 수행해야할 시간보다 P3의 수행시간이 더 짧으니 P3가 작업을 수행합니다. 그런데 P4가 다음에 도착하네요. P4가 더 적은 시간을 갖으니 P4를 수행합니다. 이때 P4가 끝나면 남아있는 프로세스 중에서 가장 적은 수행시간을 갖는 P3의 작업을 이어서 하게 됩니다.

3. 우선순위 스케줄링

우선순위 스케줄링은 프로세스마다 우선순위라는 속성이 붙게 됩니다. 우선순위 스케줄링도 역시 선점, 비선점형으로 스케줄링이 가능합니다. 숫자가 높을 수록 우선순위가 높고 만약 우선순위가 같다면 FIFO방식으로 동작합니다.

그래서 아래는 선점형에서의 결과를 나타낸 표입니다. 약간 헷갈릴 수 있을텐데요. P1 먼저 수행하다가 P3가 오면 우선 순위가 P3가 더 높으니까 P1은 대기하고 P3가 작업을 수행합니다.

다음은 비선점형일때의 결과 표입니다.

만약 우선순위가 낮은 프로세스가 높은 프로세스에 의해 실행이 되고 있지 않은 상황이라면 어떻게 될까요? 이때는 그 프로세스의 우선순위를 점차 높여 처리받게끔 하는 에이징이라는 기법을 사용합니다.

4. 라운드 로빈 스케줄링(Round-Robin)

라운드 로빈 스케줄링은 시분할 시스템을 위해 설계된 스케줄링 기법입니다. 이 스케줄링은 작은 단위의 시간인 시간 할당량(Time-Slice)을 정의하여 그 시간 만큼 자원을 할당하는 방식입니다. 그래서 그 시간안에 작업을 끝내지 못하면 다음 프로세스가 다시 그 시간만큼 자원을 할당받아씁니다. 여기서 시간 할당량을 5로 정하고 간트 차트와 결과를 보면 아래와 같습니다. 

OS에서 핵심적인 부분 중 하나인 Scheduling입니다.

상당히 중요한 부분인 만큼 긴 내용이 되겠군요..ㅜ

먼저 대표적인 스케줄링 기법으로 라운드로빈 방식이 있습니다.

- 라운드 로빈 스케줄링(Round Robin Scheduling, RR)은 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum/Slice)로 CPU를 할당하는 방식의 CPU 스케줄링 알고리즘입니다.

(==) 같은말로, 컴퓨터 운영에서, 컴퓨터 자원을 사용할 수 있는 기회를 프로그램 프로세스들에게 공정하게 부여하기 위한 한 방법으로서, 각 프로세스에 일정시간을 할당하고, 할당된 시간이 지나면 그 프로세스는 잠시 보류한 뒤 다른 프로세스에게 기회를 주고, 또 그 다음 프로세스에게 하는 식으로, 돌아가며 기회를 부여하는 운영방식이라 풀어 말할 수 있겠습니다.

보통 시간 단위는 10 ms ~ 100 ms 정도로, 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 되고, 문맥 전환의 오버헤드가 큰 반면에 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리합니다.

그렇다면 이 스케줄링이란 무엇일까요?

1) 스케줄링(Scheduling) 이란?

- 일반적인 스케줄링이란 처리할 일들의 진행순서를 정하는 일입니다. 

1) 프로세스 스케줄링이란 CPU를 사용하려고 하는 프로세스들 사이의 우선 순위를 관리하는 일을 말하고, 

2) 디스크 스케줄링은 디스크를 사용하려고 하는 프로세서들 사이의 우선 순위를 관리하는 일들을 말합니다. 

스케줄링은 처리율과 CPU 이용률을 증가시키고, 오버헤드/응답시간/반환시간/대기시간을 최소화 시키기 위한 기법입니다. 즉, CPU가 쉬지않고 계속 열심히 일할 수 있도록 효율적인 계획을 잡아 주는 것이 스케줄링입니다.

2) 스케줄링 방식 -> 비선점 스케줄링과 선점 스케줄링

- 스케줄링의 적용 시점에 따라 비선점형과 선점형의 2가지로 구분할 수 있습니다.

1) 비선점형 스케줄링은 프로세스가 (실행->대기), (실행->종료) 로의 상태전이가 있을 때 적용되며,

2) 선점형 스케줄링은 (실행->대기), (실행->준비), (대기->준비), (수행->종료) 모든 상태변화에서 적용됩니다.

 (앞선 Process State Trasition Diagram, 선점형/비선점형 글을 참고로 보시면 됩니다.)

- 비선점 스케줄링 은 이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케줄링 기법입니다. 선점 방식보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버헤드도 적습니다. 일괄처리 시스템에 적합하고, CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다는 단점도 있습니다.

- 선점 스케줄링 은 하나의 프로세스가 CPU를 할당 받아 실행하고 있을 때 우선 순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 기법입니다. 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있으며, 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하며 긴급한 프로세서를 제어할 수 있습니다.

(이 또한, 앞선 선점형 OS와 비선점형OS 글에서 다루었던 부분입니다.)

그렇다면, 이 스케줄링 알고리즘들에는 어떤것들이 있는지 아래에서 살펴보겠습니다.

3) 비선점형 스케줄링 알고리즘 : FIFO, SJF, HRN

-FIFO(First In First Out) : 가장 간단한 방식으로 선입선출의 방식입니다. 먼저 들어오면 먼저 나가는 방식으로, 아무리 중요한 작업이 있다 하더라고 그 작업 보다 먼저 들어온 작업이 끝나기 전까지는 절대 먼저 실행될 수 없는 비효율적인 방식이라고 말할 수 있습니다. FIFO라고도 하고 FCFS(First Come First Served Scheuling)이라고도 합니다. 관련은 없지만 선입선출이라는 면에서 자료구조의 Queue를 한번 떠올려보게되네요.ㅎㅎ

-SJF(Shortest Remaining Time First Scheduling) : 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식입니다. 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에게 할당 순위가 밀려 연기 상태에 빠질 수 있다는 단점이 있습니다.

-HRN(Highest Response-ratio Next) : 실행시간이 긴 프로세스에 불리한 SJF기법을 보완하기 위한 것으로 대기 시간과 서비스 시간을 이용하는 방식입니다. '우선순위 = (대기시간+서비스시간)/서비스시간' 의 공식을 이용하여 우선순위를 계산하여 우선순위가 높은 것부터 실행하는 방식입니다. 

이렇게 프로세스가 자원을 기다리고 있는 시간에 비례하여 우선순위를 부여함으로서 무한 연기의 문제를 방지하는 것을 ‘에이징(Aging)기법’이라고 합니다.

4) 선점형 스케줄링 알고리즘 : SRT, RR, MQ

-SRT(Shortest Remaining Time) : 비선점 스케줄링인 SJF 기법을 선점 형태로 변경한 기법입니다. SJF처럼 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식으로, 단지 차이점은 ‘선점형’으로 바뀌어 중요한 프로세스가 있으면 점유시간이 길어도 먼저 실행 시킬수 있는 권한이 생겼다는 것입니다.

- RR(Round Robin) : 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위로 CPU를 할당하는 방식입니다. 보통 시간 단위는 10ms ~ 100ms 정도이고 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 됩니다. 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하고, 할당되는 시간이 클 경우 비선점 FIFO기법과 같아지게 됩니다.

(위에서 설명한 부분입니다..^^)

- 다단계 큐(MQ, Multi-level Queue) : 프로세스를 특정 그룹으로 분류할 수 있을 경우 그룹에 따라 각기 다른 분비 상태 큐를 사용하는 기법입니다. 프로세스가 특정 그룹의 준비상태 큐에 들어갈 경우 다른 준비상태 큐로 이동할 수 없습니다. 하위 준비 상태 큐에 있는 프로세스를 실행하는 도중이라도 상위 준비 상태 큐에 프로세스가 들어오면 상위 프로세스에게 CPU를 할당해야 합니다.

사진에 보이는 것처럼 Level 1, 2, 3으로 큐가 불리 되어 있습니다. 레벨 1의 큐가 모두 완료 되어야만 레벨 2의 큐로 넘어갈 수 있고 레벨2의 큐가 모두 완료되어야 그다음으로 넘어 갈수 있는 방식입니다.

공유하기

게시글 관리

'OS' 카테고리의 다른 글