RISS 검색 - 국내학술지논문 상세보기

국문 초록 (Abstract)

라운드 로빈 기반 비례지분 스케줄링(Round Robin based Proportional Share scheduling, RRPS)은 각 태스크에게 지분(share)을 결정하는 비중(weight)이라는 속성을 정의하고 각 태스크의 비중에 비례하여 CPU ...

라운드 로빈 기반 비례지분 스케줄링(Round Robin based Proportional Share scheduling, RRPS)은 각 태스크에게 지분(share)을 결정하는 비중(weight)이라는 속성을 정의하고 각 태스크의 비중에 비례하여 CPU 자원을 할당한다. 라운드 로빈 기반 비례지분 스케줄링은 공평성(fairness)을 성능의 척도로 사용하며 스케줄링의 높은 공평성을 목표로 한다. 그러나 태스크들 간의 동기화로 인한 스케줄링의 공평성 문제에 대한 연구는 부족하다.
본 논문에서는 라운드 로빈 기반 비례지분 스케줄링에서 동기화로 인한 스케줄링의 지연이 높은 불공평성을 발생시킴을 보인다. 이를 비중역전(weight inversion)이라는 현상으로 설명한다. 다음, 비중역전을 방지하는 동기화 기법인 비중상속 프로토콜(weight inheritance protocol, WIP)을 제안한다. 또한, 공평성 분석과 시뮬레이션을 통해 비중상속 프로토콜이 불공평성을 감소시킴을 보인다.

다국어 초록 (Multilingual Abstract)

Round robin based proportional share scheduling(RRPS) defines weight which determines share for each task and allocates CPU resource to each task in proportional to its respective weight. RRPS uses fairness as the measure of performance and aims at high fairness of scheduling. However, researches for scheduling fairness problem due to synchronization among tasks have been rarely investigated.
In this paper, we discuss that scheduling delay due to synchronization may result high unfairness in RRPS. We explain such a situation as weight inversion. We then propose weight inheritance protocol(WIP), a synchronization mechanism, that prevents weight inversion. We also show that WIP can reduce unfairness using fairness analysis and simulation.

목차 (Table of Contents)

요약
Abstract
1. 서론
2. 관련 연구
3. 공평성 분석을 위한 GR³ 스케줄링 모델

요약
Abstract
1. 서론
2. 관련 연구
3. 공평성 분석을 위한 GR³ 스케줄링 모델
4. 비중 역전(Weight Inversion)
5. 비중상속 프로토콜
6. 시뮬레이션 측정
7. 결론 및 향후 연구 방향
참고문헌

참고문헌 (Reference)

1 J. Bennett, "WF2Q: Worst-case Fair Weighted Fair Queueing" 1996

2 J. Nieh, "Virtual-Time Round-Robin: An O(1) Proportional Share Scheduler" 245-259, 2001

3 S. Ramabhadran, "Stratified Round Robin: A Low Complexity Packet Scheduler with Bandwidth Fairness and Bounded Delay" 239-249, 2003

4 L. Kleinrock, "Queueing Systems,Volume II:Computer Applications" John Wiley & Sons 1976

5 L. Sha, "Priority Inheritance protocols: An Approach to real-time synchronization" 39 (39): 1990

6 C. A. Waldspurger, "Lottery and Stride Scheduling: Flexible Proportional-Share Resource Management" Massachusetts Inst. of Technology 1995

7 J. Nieh, "Group Ratio Round-Robin: An O(1) Proportional Share Scheduler" 245-259, 2004

8 A. Sarkar, "Frame-Based Proportional Round-Robin" 55 (55): 1121-1129, 2006

9 A. Demers, "Analysis and Simulation of a Fair Queueing Algorithm" 1-12, 1989

10 I. Stoica, "A Proportional Share Resource Allocation Algorithm for Real-Time, Time- Shared Systems" 288-, 1996