본문 바로가기
HOME> 논문 > 논문 검색상세

학위논문 상세정보

비주기적 태스크의 효율적 처리를 위해 개선된 슬랙 스틸링 알고리즘 원문보기
Improved slack stealing algorithm for efficient processing of aperiodic task

  • 저자

    한대만

  • 학위수여기관

    水原大學校 敎育大學院

  • 학위구분

    국내석사

  • 학과

    電子計算學科

  • 지도교수

  • 발행년도

    1999

  • 총페이지

    iv, 39 p.

  • 키워드

  • 언어

    kor

  • 원문 URL

    http://www.riss.kr/link?id=T8954205&outLink=K  

  • 초록

    본 논문은 고정 우선순위를 가지는 주기 태스크와 동적으로 발생하는 비주기 태스크를 스케줄링하는 슬랙 스틸링(slack stealing) 알고리즘의 문제점을 개선한다. 슬랙 스틸링 알고리즘은 비주기 태스크의 발생에 따라 슬랙 스틸링 서버가 적합한 우선순위를 비주기 태스크에 부여하여 즉시 서비스 가능하도록 함으로써 불필요한 대기시간을 최소화하고 있다. 하지만, 슬랙 스틸링을 수행하기 위해서는 임의의 시점까지 주기적 태스크의 수행 시간을 구해야 한다. 그리고, 주기적 태스크의 수행시간은 슬랙 알고리즘을 적용하는 동안 매 시간 마다 다시 구해지고 있다. 이때 사용되는 시간 복잡도는 계산에 적용되는 태스크의 수가 n 이라면 O(n)으로 나타난다. 본 논문에서는 스케줄링된 주기적 태스크의 슬랙타임과 수행시간을 테이블에 저장하고 비주기 태스크가 사용할 수 있는 슬랙(slack)계산에 사용함으로서 동적으로 발생하는 비주기적 태스크의 복잡도를 O(log n)으로 감소시키고 응답시간을 향상시킨다. 본 논문에서 제안한 알고리즘을 모의 실험을 통하여 증명한다.


    This paper intend to improve the problems of slack stealing algorithm scheduling for periodic tasks with fixed priority and aperiodic tasks which occur dynamically. Slack stealing algorithm reduces the unnecessary waiting time by making the service possible immediately when slack stealing server give suitable priority to aperiodic tasks according to the status of aperiodic tasks arrivals at runtime. But to performs the slack stealing, we must calculate time of periodic tasks till the point of random. And execution time of periodic tasks is being repeatedly calculated every hours while the slack algorithm is applied. We show time complexity when is used as to O(n) if tasks number which is applied to the calculation is n. In this paper, storing periodic tasks complexity which is occurring dynamically reduces O(log n)and progresses the response time by using aperiodic tasks which uses slack calculation. we prove the algorithm proposed in this paper through the simulation.


 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역