[논문]다중 프로세서 시스템에서 문맥교환을 줄이기 위한 변형된 LLF 스케줄링 알고리즘

오성흔; 길아라; 양승민

다중 프로세서 시스템에서 문맥교환을 줄이기 위한 변형된 LLF 스케줄링 알고리즘
A Modified Least-Laxity First Scheduling Algorithm for Reducing Context Switches on Multiprocessor Systems 원문보기

정보과학회논문지. Journal of KIISE. 시스템 및 이론, v.30 no.2, 2003년, pp.68 - 77

오성흔 (㈜디지캡) , 길아라 (숭실대학교 컴퓨터학부) , 양승민 (숭실대학교 컴퓨터학부)

초록
AI-Helper

최소 여유시간 우선(Least-Laxity First, LLF) 스케줄링 알고리즘은 작은 여유시간을 가진 태스크가 높은 우선순위를 갖는 스케줄링 알고리즘으로써 단일 프로세서 시스템에서 최적이고 다중 프로세서 시스템에서 준최적으로 증명되었다. 그러나 이 스케줄링 알고리즘은 여유시간 충돌이 발생하였을 때 태스크 간에 빈번한 문맥교환이 발생하게 되는 문제점이 있어 실용적이지 못하다. 본 논문에서는 과도한 문맥교환을 일으키는 LLF의 문제점을 해결하기 위해 다중 프로세서 시스템을 위한 MLLF/MP(Modified Least-Laxity First on Multiprocessor) 스케줄링 알고리즘을 제안한다. MLLF/MP는 태스크의 여유시간 역전이 발생하더라도 마감시간을 놓치지 않는 범위에서 태스크를 연속적으로 수행시킴으로써 빈번한 문맥교환이 발생하는 것을 방지한다. MLLF/MP 또한 다중 프로세서 시스템에서 준최적임을 증명한다. 모의 실험 결과를 통하여 MLLF/MP는 LLF보다 적은 스케줄링 오버헤드를 가짐을 보인다.

Abstract ▼ AI-Helper

The Least-Laxity First(or LLF) scheduling algorithm assigns the highest priority to a task with the least laxity, and has been proved to be optimal for a uni-processor and sub-optimal for a multi-processor. However, this algorithm Is Impractical to implement because laxity tie results in the frequent context switches among tasks. In this paper, a Modified Least-Laxity First on Multiprocessor(or MLLF/MP) scheduling algorithm is proposed to solve this problem, i.e., laxity tie results in the excessive scheduling overheads. The MLLF/MP is based on the LLF, but allows the laxity inversion. MLLF/MP continues executing the current running task as far as other tasks do not miss their deadlines. Consequently, it avoids the frequent context switches. We prove that the MLLF/MP is also sub-optimal in multiprocessor systems. By simulation results, we show that the MLLF/MP has less scheduling overheads than LLF.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

MLLF/MP는 LLF와 같이 다중 프로세서 시스템에서 준최적의 특성을 가지고 있다. 본 논문에서는 MLLF/MP의 준최적성을 수학적으로 증명하고 모의 실험 결과를 통하여 LLF, EDZL, MLLF/MP의 문맥교환 발생비율을 비교함으로써 MLLF/MP의 향상된 성능을 보인다,
본 논문에서는 다중 프로세서 시스템에서 문맥교환횟수의 발생을 감소시킴으로써 LLF보다 낮은 스케줄링오버헤드를 갖는 MLLFMP(Modified Least-Laxity First on Multiprocessor) 스케줄링 알고리즘을 제안한다. 이 스케줄링 알고리즘에서는 태스크의 여유시간 우선순위 역전(laxity priority inversion)이 발생하더라도 마감시간을 놓치지 않는 범위에서 현재 수행되는 태스크를 계속 수행시킴으로써 빈번한 문맥교환이 발생하는 것을 방지한다.

가설 설정

- 여유시간은 정규 분포(normal distribution)를 갖는다. 프로세서의 개수가 변하는 경우의 실험에서는 여유시간의 평균은 25로 지정하였고 여유시간의 표준편차를 10으로 지정하였다.
- 최악수행시간은 정규 분포(normal distribution)를 갖는다. 최악수행시간의 평균은 5()으로 지정하였고 최악수행시간의 표준편차는 25로 지성하였다.
• 태스크 제약사항 : 한 태스크는 동시에 두 개 이상의 프로세서에서 수행될 수 없다.
가정 2 모든 태스크는 서로 독립적이며 항상 선점 가능하다.

제안 방법

4장에서는 다중 프로세서 시스템에서의 LLF와 LLF/MP의 특성을 살펴 본 후 MLLFA1P 스케줄링 알고리즘을 제시하고 준최적성을 수학적으로 증명한다. 5장에서의 모의 실험을 통하여 LLF, EDZL, MLLF/MP의 문맥교환 발생비율을 비교한다. 6장에서 결론으로 논문을 맺는다.
각 실험에 대한 성능 분석의 척도로써 문맥교환발생비율과 스케줄링 성공비율을 비교한다. 문맥교환 발생비율의 비교는 비교 대상의 스케줄링 알고리즘이 모두 실행 가능한 스케줄을 갖는 태스크 집합에 대해서만 수행하였다.
개수를 크게 하였다. 그리고 태스크 사이의 여유시간충돌이 발생하는 확률을 증가시키기 위해서 최악수행시간의 크기를 크게 하였다.
먼저 살펴 본다. 다음 MLLF/MP 스케줄링 알고리즘을 제안하고 그 특성을 살펴 본다.
본 실험에서는 스케줄링 가능성을 높이기 위해 태스크 집합을 구성하는 태스크의 개수를 적게 하는 대신각 다중 프로세서 시스템에 대해 실험하는 태스m 집합의 개수를 크게 하였다. 그리고 태스크 사이의 여유시간충돌이 발생하는 확률을 증가시키기 위해서 최악수행시간의 크기를 크게 하였다.
본 실험에서는 크게 프로세서의 개수가 변하는 경우와 태스크의 평균 여유시간이 변하는 경우로 나누어 수행한다. 각 실험에 대한 성능 분석의 척도로써 문맥교환발생비율과 스케줄링 성공비율을 비교한다.
본 장에서는 MLLF/MP 스케줄링 알고리즘을 제안하기 전에 LLF와 LLF/NP 스케줄링 알고리즘의 작동 방식을 먼저 살펴 본다. 다음 MLLF/MP 스케줄링 알고리즘을 제안하고 그 특성을 살펴 본다.
보인다. 이 모의 실험에서는 두 개 이상의 프로세서를 갖는 다중 프로세서 시스템에서 LLF, EDZL, MLLF/MP의 문맥교환 발생비율과 스케줄링 성공비율을 비교한다.
프로세서의 개수가 변하는 경우의 실험에서는 여유시간의 평균은 25로 지정하였고 여유시간의 표준편차를 10으로 지정하였다. 평균 여유시간이 변하는 경우의 실험에서는 평균 여유시간을 15에서 35까지 단위 5씩 변화 시키면서 수행하였다, 그리고 각 평균 여유시간에 대해 여유시간의 표준편차는 1()으로 고정하였다.

대상 데이터

시스템을 고려한다. 각 다중 프로세서 시스템에 대해서 서로 다른 임의의 태스크 집합 1000개를 모의 실험하여 평균을 구하였다. 본 실험에서는 다음과 같은 가정을 한다.
본 실험에서는 2, 4, 6, 8 개의 프로세서를 가진 다중프로세서 시스템을 고려한다. 각 다중 프로세서 시스템에 대해서 서로 다른 임의의 태스크 집합 1000개를 모의 실험하여 평균을 구하였다.

성능/효과

MLLF/MP는 여유시간 충돌이 발생하였을 때 여유시간역전이 발생하더라도 태스크를 연속시켜 수행함으로써 빈번한 문맥교환을 막아 스케줄링 오버헤드를 줄인다. 본 논문에서는 MLLF/MP의 준최적성을 수학적으로 증명하였으며 모의 실험 결과를 통하여 LLF에 비해 적은 문맥교환 발생비율을 가짐을 보였다.
본 장에서는 모의 실험 결과를 제시함으로써 제안한 MLLF/MP 스케줄링 알고리즘의 향상된 성능을 보인다. 이 모의 실험에서는 두 개 이상의 프로세서를 갖는 다중 프로세서 시스템에서 LLF, EDZL, MLLF/MP의 문맥교환 발생비율과 스케줄링 성공비율을 비교한다.
문맥교환 발생비율을 보여 준다. 실험 결과를 통해 EDZL과 MLLF/MP는 LLF에 비해 적은 문맥교환 횟수를 가짐을 알 수 있다. 그림 9에서 프로세서개수가 증가할수록 MLLF/MP와 EDZL에 대한 LLF의 문맥교환 발생비율이 감소하는 것을 볼 수 있다.
이상의 실험 결과를 통하여 준최적인 MLLF/MP는 LLF 에 비하여 보다 작은 문맥교환을 일으킴으로써 LLF에 비해 스케줄링 오버헤드가 적음을 알 수 있다.
증명 : 시간 r에서 LLF에 의해 스케줄링 가능한 태스크 집합이 MLLF/MP에 의해 스케줄링 되었을 때 시간 T+1의 태스크 집합은 여전히 LLF에 의해 스케줄링 가능함을 증명한다.

후속연구

그리고 LLF, EDZL, MLLFA1P와 같이 태스크의 여유시간을 고려하는 스케줄링 알고리즘은 공통적으로 매 시간 마다 태스크의 여유시간을 변경하고 관리야 하는 스케줄링 오버헤드를 갖는다. 그러므로 제안한 MLLF/MP 뿐만 아니라 LLF, EDZL 구현을 위한 효율적인 자료구조 및 접근 방법의 연구가 필요하다.

참고문헌 (9)

M.L. Dertouzos and A.K. Mok, 'Multiprocessor On-Line Scheduling of Hard-Real-Time Tasks,' IEEE Transactions on Software Engineering, Vol. 15, No. 12, December 1989

상세보기
A. K. Mok, 'Fundamental Design Problems of Distributed Systems for the Hard-Real-Time Environment,' Ph.D. Thesis, Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, Massachusetts, May 1983
C.L. Liu and J.W. Layland, 'Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment,' Journal of the Association for Computing Machinery, 20(1), 1973

상세보기
M.L. Dertouzos, 'Control Robotics: the Procedural Control of Physical Processes,' Information Processing 74, North-Holland Publishing Company, 1974
오성흔, 양승민, '실시간 시스템을 위한 최소 여유시간 우선 기반의 최소 선점을 갖는 스케줄링 알고리즘,' 한국정보과학회 논문지(A), 제26권, 제4호, pp.443-454, 1999년 4월
조성제, 이석균, 유해영, '산발적인 경성 실시간 태스크를 위한 온라인 스케줄링 알고리즘,' 한국정보과학회 논문지(A), 제25권, 제7호, pp. 708-718, 1998년 7월
S.K. Dhall and C.L. Liu, 'On a Real-Time Scheduling Problem,' Operations Research, Vol. 26, No. 1, pp. 127-140, February 1978

상세보기
Michael B. Jones, Joseph S. Barrera III, Alessandro Forin, Paul J. Leach, Daniela Rosu and Marcel-Catalin Rosu, 'An Overview of the Rialto Real-Time Architecture,' In Proceedings of the Seventh ACM SIGOPS European Workshop, Connemara, Ireland, pages 249-256, September, 1996

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증