[문제해설] 라운드로빈 알고리즘을 사용하여 A, B, C, D, E 작업을 실행 시킬 때 대기시간은 다음과 같다. 평균 대기시간은 얼마인가?

전자계산기조직응용기사 실기 필답형 기출문제 (운영체제-CPU 스케줄링) - 2013년1회

---

라운드로빈 알고리즘을 사용하여 A, B, C, D, E 작업을 실행시킬 때 대기시간은 다음과 같다. 평균 대기시간은 얼마인가?

 

 

 

 

---

- 문제 해설 -

운영체제 각론에서 다루는 알고리즘들 중 조직응용기사에서 다루는 부분은 다음의 3가지가 있습니다.

1. CPU 스케줄링(각론서에 따라 '프로세스 스케줄링' 혹은 그냥 '스케줄링' 이라고도 합니다.)

  CPU 스케줄링은 병행 시스템에서 CPU가 작업 대기 중인 프로세스(precess)들 중 어떤 것을 먼저 처리하느냐를 결정하는 알고리즘.

2. 페이지 교체

 메모리 할당 기법 중 페이징 기법에서 어떤 페이지를 희생(victim) 시킬 것인가를 결정하는 알고리즘.

3. 디스크 스케줄링

  기계적인 방식으로 액세스 하는 보조기억장치(대표적으로 HDD)에서 파일에 접근하는 방식.

 

본 문제는 CPU 스케줄링 중 라운드 로빈에 관한 문제입니다.

CPU 스케줄링에도 많은 종류가 있지만, 기사 시험에서 다루는 것만 간추려 정리하면 다음과 같습니다.

위 그림을 간단히 설명하면,

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

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

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

 

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

본 문제는 대기시간이 모두 주어졌고, 단순한 평균 대기시간을 구하는 것이기 때문에 그 값들의 평균을 구하면 됩니다.

위 식과 같이 프로세스들의 평균 대기시간은 23입니다.

 

본문제는 CPU스케줄링 문제치고는 너무 쉽게 출제되었습니다. 관련된 필기 문제를 참고하시면서 좀 더 복잡한 문제에 대비하시는 것이 좋습니다.

 

 

 

https://youtube.com/playlist?list=PLboXycXmAIDt4ObBRPVj29BuD2d27oRnO

전자계산기조직응용기사 실기 필답형