라운드 로빈 스케줄링 예시 - laundeu lobin seukejulling yesi

[운영체제 목차 책 추천]

Round Robin (RR) Algorithms

이번에 살펴볼 스케줄링 알고리즘은 RR입니다. 이 포스팅을 보기 전에 스케줄링 게시글을 읽고 오기를 권장해요

사실 time sharing system(시분할 시스템)이 나온 뒤로부터 수행되는 스케줄링 알고리즘이 요 녀석 RR알고리즘이예요.

자아아ㅏ 그럼 Round Robin이 어떤 알고리즘인지 자세히 살펴보기 전에 이름 기원을 살펴보도록 해요.

Round ?? 라운드? 우리가 아는 1라운드, 2라운드, 3라운드.. 한 번 도는 것을 라운드라고 하죠?

Robin 이 로빈은 로빈슨 크루소의 로빈이 아니고 로빈이라는 새 이름에서 가져왔다고 해요.

robin이라는 새가 새끼한테 모이를 줄 때, 10명이 있으면 조금씩 나눠서 조금 주고, 또 조금 주고 한 라운드를 다 돌면 그 다음에 다시 처음 새끼부터 조금씩 주는 것을 반복한다고 해요. 그래서 robin이라는 새처럼 한 라운드에 조금씩 전부 분배하고 다시 반복하는 스케줄링에 Round Robin라고 이름을 붙였다고 합니다.

이거는 일단 모두에게 공평한 알고리즘이겠죠? FCFS의 preemptive version이라고 할 수 있습니다.

공평하게 들어온대로 처리하면 waiting time이 너무 커지니까 컴퓨터는 time sharing 방식을 이용하는 것이죠. 이것이 Round Robin이고 줄여서 RR알고리즘이라고 부릅니다.

현재 지금 우리의 운영체제는 Priority + RR 형태로 스케줄링 되고 있다는 것~!

큰 그림으로 봤을 때 윈도우 리눅스 모두 priority + RR을 취하고 있습니다.

RR의 장단점?!

RR에서 time quantum이란 한마디로 한 새끼한테 주는 모이의 양이예요.

10개의 새끼에게 콩 30개를 분배한다고 할 때, 콩 3개씩 준다고 하면 3바퀴를 도니까 round는 3이 되고 time quantum은 3이 되겠죠! 컴퓨터 개념에서는 일을 끝내야 할 프로세스마다 얼만큼 시간동안 머물러서 작업을 하고 교체할건지를 time quantum이라고 합니다.

RR은 time quantum의 크기가 얼마냐에 따라서 장점과 단점이 존재합니다.

사진은 quantum이 작아질수록 context switches 가 늘어나는 것을 보여주고 있어요

if too small, we spend all our time in context switches

if small, then context switches are frequent incurring high overhead(CPU utilization drops)

If too large, RR policy is the same as FCFS policy

If large, then response time drops.

만약 지금 현재 CPU burst가 10인데 time quantum이 10보다 크면 context switching이 한 번도 일어나지 않죠 이 CPU burst만 쭉 수행이 되는거예요. 하지만 time quantum이 6이면 10중에 6까지 쓰고 프로세스를 바꿔야하니까 context switching이 한 번 일어나게 되는거죠. time quantum이 작을수록 일어나는 context switching 수는 늘어납니다. time quantum이 극단적으로 무한대다 이러면 그 프로세스의 크기만큼 CPU가 처리하다가 해당 프로세스가 끝나야 다른 프로세스가 처리되므로 결국 FCFS와 똑같은 알고리즘이 되는거죠. 따라서 적당한 time quantum의 크기를 정하는 것이 중요합니다.

그래서 이 time quantum을 정하는 룰이 rule of thumb에 나와있습니다

'A rule of thumb is that 80 percent of the CPU bursts should be shorter than the time quantum.'

CPU burst의 80% 정도를 포함 할 수 있도록 time quantum을 설정해야 한다!

왜냐? context switches자체가 오버헤드! 다른 것을 다시 수행해야 하기 때문에 context-switching을 줄이는게 좋습니다.

그래서 time quantum을 크게 하면 좋은데 또 무작정 크게할 수는 없어요 얼마나 크게 해야 하지? CPU burst의 80프로를 커버할 수 있을 정도로! 이것이 rule of thumb입니다.

문제를 풀면서 RR 완벽하게 이해하기~

예시 1 - 도착시간이 같을 때

time quantum이 1이라고 할 때, waiting time, turnaround time, response time, completion time을 구해라! (동시에 도착했지만 순서는 P1,P2,P3로 가정)

<해설>

처음 대기큐에는 P1, P2, P3가 들어가 있는 것입니다.

가장 먼저 들어온 P1이 1초 동안 수행됩니다. 따라서 3초 걸리는 P1은 2초가 남게 돼요.

타임퀀텀만큼 돌았으면 P1을 그 다음 대기큐로 넣고 다음 대기 중인, P2가 1초 동안 수행되겠죠? (대기큐 P2, P3, P1)

그러면 P2는 이제 3초가 수행되어야 프로세스가 완료될거예요. (대기큐 P3,P1,P2) 마찬가지로 다음은 P3이 1초 동안 수행되고 2초가 남게 될 겁니다. 이런식으로 각각 프로세스가 완료될 떄까지 타임퀀텀만큼 대기하고 있는 프로세스들을 불러와서 수행시킵니다. 

이를 그림으로 표현하면 아래와 같습니다.

자 이 정보를 기반으로 문제가 요구하는 시간들을 계산해봅시다.

먼저 completion time은 끝날 때까지의 시간을 말합니다. 이를 정리해보면~~~ 아래와 같습니다. 뒤에서부터 프로세스들을 확인하면 되므로 쉽습니다.

그 다음 turnaround time는 요청한 다음에 끝날 때까지의 시간이었으나 Completion time - Arrival time하면 나오겠죠? 여기서는 도착시간이 0으로 다 같으므로 completion time과 turnaround time이 같습니다.

즉 평균 turnaround time은 (7+9+10)/3 = 26/3 = 8.67이 됩니다.

그 다음은 waiting time을 볼까요? waiting time은 다른 애가 수행되고 있어서 내가 기다려야 하는 시간을 말해요. 즉 총 걸리는 작업 수행 시간에서 내 프로세스가 CPU에서 수행중인 시간을 빼면 남들이 CPU에서 수행되는 시간, 즉 내가 기다리는 시간이므로 turnaround time- burst time하면 됩니다.

즉 평균 waiting time은 (4+6+6)/3 = 16/3 = 5.33이 됩니다

response time은 프로세스가 처음으로 응답하기까지 시간입니다. 즉 처음 프로세스가 응답하는 시간에서 프로세스가 도착한 시간을 빼주면 프로세스가 시작부터 응답하기까지 걸리는 시간인 response time이 됩니다! 근데 여기서는 도착한 시간이 모두 0이므로 response time은 처음 프로세스가 응답하는 시간만 생각해주시면 돼요. 0,1,2가 되겠죠?

예시 2 - 도착시간이 다를 때

똑같이 풀면 됩니다. 다만 앞에 읽으면서 유추하셨겠지만 도착시간이 다를 경우, response time이나 turnaround time이나 달라지는 부문이 어느정도 있겠죠?

time quantum이 3이라고 할 때, 평균 turnaround time, 평균 waiting time, 평균 response time을 구해라!

<해설>

마찬가지로 풀이해볼게요 반복하는 느낌으로~~

가장 먼저 도착한 애가 1등으로 도착한 프로세스가 제일 먼저실행되겠죠? 따라서 9초 걸리는 P4가 1초에 들어와서 time quantum(3초)동안 수행이 됩니다. P4의 주어진 시간이 다되기 전 즉 4초 안에 P2, P3가 들어오네요 즉 P1이 수행 중일 때 ready queue에는 P3, P2에서~~ P4가 끝나면서 ready queue가 P3, P2, P4가 됩니다. 

그럼 다음에는 P3이 3초동안 수행되겠죠? 그리고 P3이 수행되는 도중 6초에 P1이 들어오고 ready queue에는 P2, P4, P1이 있게 됩니다.

이런식으로 쭉 수행이 반복적으로 되는 거예요. P4는 초반 burst가 9였으니 3번은 자기 차례가 와야 끝이 날 거고, P3도 3번, P2와 P1은 두 번 자기 차례가 와야 끝나겠네요! 

이렇게 말로 주저리 주저리 설명하려니까 복잡하고 헷갈리죠!?그래서 보통 아래와 같이 표를 사용해서 간편하게 나타냅니다.

텍스트 추가

자 이 정보를 기반으로 문제가 요구하는 시간들을 다시 한 번 계산해봅시다.

먼저 Turnaround time은 요청한 다음에 끝날 때까지의 시간이었으니까 Completion time - Arrival time하면 나오겠죠.

Waiting time은 다른애가 수행되고 있어서 내가 기다려야 하는 시간으로 앞에서 설명했듯이 Turnaround time - burst time하면 됩니다.

response time은 프로세스가 처음으로 응답하기까지 시간입니다. 즉 처음 프로세스가 응답하는 시간에서 프로세스가 도착한 시간을 빼주면 프로세스가 시작부터 응답하기까지 걸리는 시간인 response time이 됩니다! 

어려운 말로 요약된 글들이지만 내 포스팅을 보고 나면 이해될 문장(ㅎㅎㅎㅎ)

- FCFS에 의해서 프로세스들이 내보내지며 각 프로세스는 같은 크기의 CPU시간을 할당한다.

- CPU시간이 만료될 때까지 처리를 완료하지 못하면 CPU는 대기중인 다음 프로세스로 넘어가며, 실행 중이던 프로세스는 준비 완료 리스트의 가장 뒤로 보내진다.

이전 포스팅 ↓

[운영체제 OS]우선순위 스케줄링(Priority Scheduling) 총정리,장단점, aging 스케줄링, 우선순위 부여기준

[운영체제 목차] 안녕하세요!! 오늘은 우선순위 스케줄링에 관한 내용을 들고 왔어요 ㅎㅎ 우선순위 스케줄링이란? 우선순위 알고리즘이 나오게 된 흐름! 이전 SJF가 되었던 SRTF가 되었던 이 스케줄링 방식은 우..

jhnyang.tistory.com

다음 포스팅! ↓

[운영체제]Multilevel Queue 다단계큐, 멀티레벨큐

[운영체제(OS) 목차 &책 추천] Multilevel Queue 다단계 큐란? 이 포스팅을 보기전에 RR과 FCFS에 대해서 이해를 하고 오셔야합니다 RR과 FCFS가 무엇인지 잘 모른다면 이전 포스팅을 보고 오시는 것을 추천드려요..

jhnyang.tistory.com

공감 또는 댓글 또는 광고보답 등 여러분의 응원은 항상 감사드립니다. 더욱 질 좋은 포스팅으로 찾아뵐게요!