[논문]멀티프로세서 환경에서 슬랙 체크테이블(SCT)을 이용한 비주기 태스크 스케쥴링 알고리즘

서순영; 임종규; 구용완

멀티프로세서 환경에서 슬랙 체크테이블(SCT)을 이용한 비주기 태스크 스케쥴링 알고리즘
Aperiodic Task Scheduling Algorithm using Slack Check Table in Multiprocessor Environment 원문보기

서순영 (수원대학교 전자계산학과) , 임종규 (수원대학교 전자계산학과) , 구용완 (수원대학교 전자계산학과)

단일프로세서 환경에서 주기 태스크의 시간 제약 조건을 만족시키면서 비주기 태스크의 평균 서비스 시간을 최소화하는 연구가 계속 진행되어 왔으나, 최근의 시스템은 여러 개의 프로세서를 병렬처리하여 프로그램의 처리속도 향상을 꾀하는 멀티프로세서 환경으로 전환되어 가는 추세다. 따라서, 멀티프로세서 환경에서의 태스크 스케쥴링에 관한 다양한 여구가 필요하게 되었다. 일반적으로 멀티프로세서 환경에서는 주기 태스크를 스케쥴링하기 위해서 RMFF(Rate-monotonic First-Fit) 스케쥴링 알고리즘을 사용하는데, 이 알고리즘에서는 비주기 태스크의 스케쥴링을 위한 알고리즘을 추가로 요구한다. 따라서, 본 논문에서는 멀티프로세서 환경에서 주기 태스크와 비주기 태스크가 혼합되어 있을 때, 기존의 RMFF 방식에 슬랙 체크테이블(Slack Check Table;SCT)을 이용하여 비주가 태스크를 효율적으로 스케쥴링하기 위한 방법을 제안한다.

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

문제 정의

본 논문에서는 경성 마감시간을 갖는 주기 태스크는 RMFF 스케쥴링 알고리즘을 사용하고, 연성 마감시간을 갖는 비주 기 태스크의 효과적인 스케쥴링 알고리즘을 구현하기 위해 슬랙 체크테이블을 이용한 스케쥴링 알고리즘을 제안하였다. 슬랙 스틸링 스케쥴링 알고리즘이 비주기 태스크가 발생한 시점에서 슬랙을 계산하던 것을 개선하여 주기 태스의 할 당 직후에 초월주기만큼의 범위내에서 슬랙의 유무에 대한 정보를 갖는 테이블을 작성하고, 비주기 태스크가 발생하는 시점에서 이 슬랙 체크테이블을 참조하여 비주기 태스크를 스케쥴링한다.
본 논문에서는 멀티프로세서 환경에서 비주기 태스크를 효율적으로 스케쥴링하기 위한 방법을 살펴보고, 그에 대한 알고리즘을 제안하고자 한다.
본 장에서는 멀티프로세서 환경에서 주기 태스크 및 비주기 태스크에 대한 알고리즘을 간략히 살펴보기로 한다.
이상과 같이 스케쥴링 알고리즘에는 주기 및 비주기 알고리즘이 있으며, 본 논문에서는 이들 주기 및 비주기 태스크가 혼합된 태스크를 스케쥴링하기 위하여 기존의 RMFF 방법에 슬랙 체크테이블을 이용한 스케쥴링 알고리즘을 제안하고자 한다.

가설 설정

. 각 프로세서는 동등하며, 서로 독립적이다.
. 문맥교환(text switching)으로 인한 오버헤드(overhead) 는 무시할 수 있을 정도로 작다.
. 비주기 태스크는 임의의 시간에 동적으로 도착한다. - 각 태스크는 서로 독립적이며, 선점적(preemptable)이다.
. 주기 태스크는 경성 마감시간을 갖는다.

제안 방법

본 논문에서 제안한 스케쥴링 알고리즘은 주기 태스크를 스케쥴하기 위해서 기존의 RMFF 스케쥴링 알고리즘을 사용하였고, 각 프로세서에서 발생하는 슬랙을 검색하여 슬랙 체크 테이블을 생성한다. 또한, 주기 태스크를 서비스하는 동안 비주기 태스크가 발생하면 그 시점에서 각 프로세서의 슬랙 체크테이블을 참조하여 할당 가능한 프로세서에 비주기 태스크를 할당한다.
비주기 태스크가 발생한 시점에서부터 비주기 태스크가 필 요로 하는 실행시간만큼의 슬랙이 어느 정도의 시간이 경과 한 후인지에 대한 정보를 슬랙 체크테이블을 이용해서 검색 한다. 이 때 슬랙 체크테이블은 한형리스트를 이룬다.

성능/효과

위와 같은 알고리즘을 사용하여 슬랙 체크테이블에서 비주기 태스크를 할당할 수 있다. 따라서, 주기 태스크만 스케쥴링하던 RMFF 스케쥴링 알고리즘을 사용하면서 비주기 태스크도 함께 처리할 수 있도록 슬랙 체크테이블을 이용하여 개선한 비주기 태스크 스케쥴링 알고리즘의 효율성이 기존의 방 식보다 더 향상됨을 알 수 있다.
슬랙 스틸링 스케쥴링 알고리즘이 비주기 태스크가 발생한 시점에서 슬랙을 계산하던 것을 개선하여 주기 태스의 할 당 직후에 초월주기만큼의 범위내에서 슬랙의 유무에 대한 정보를 갖는 테이블을 작성하고, 비주기 태스크가 발생하는 시점에서 이 슬랙 체크테이블을 참조하여 비주기 태스크를 스케쥴링한다. 이로써 비주기 태스크가 발생할 때마다 슬랙 의 재계산에 소요되는 계산시간의 부담을 감소시킬 수 있고, 보다 짧은 시간 안에 비주기 태스크를 종료할 수 있었다. 향후 연구과제로는 문맥교환에 대한 오버헤드를 고려한 스 케쥴링이 가능하도록 해야하며, 멀티프로세서 환경에서 각각의 프로세서가 각 태스크의 연관성을 처리할 수 있도록 상호 작용하는 프로세스간의 연결에 대한 연구가 필요하다.

후속연구

이로써 비주기 태스크가 발생할 때마다 슬랙 의 재계산에 소요되는 계산시간의 부담을 감소시킬 수 있고, 보다 짧은 시간 안에 비주기 태스크를 종료할 수 있었다. 향후 연구과제로는 문맥교환에 대한 오버헤드를 고려한 스 케쥴링이 가능하도록 해야하며, 멀티프로세서 환경에서 각각의 프로세서가 각 태스크의 연관성을 처리할 수 있도록 상호 작용하는 프로세스간의 연결에 대한 연구가 필요하다. 또한 멀티프로세서 환경의 특성을 충분히 살린 스케쥴링 알고리즘에 대한 연구가 더 이루어져야갰다.

원문 보기

ScienceON 원문보기

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

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

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

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

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증

멀티프로세서 환경에서 슬랙 체크테이블(SCT)을 이용한 비주기 태스크 스케쥴링 알고리즘
Aperiodic Task Scheduling Algorithm using Slack Check Table in Multiprocessor Environment 원문보기

초록
AI-Helper