동적 우선순위 상한 프로토콜의 스케줄링 가능성 조건 개선

오성흔,양승민,O, Seong-Heun,Yang, Seung-Min 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.11

실시간 시스템에서 태스크가 공유 자원을 사용할 때 제한되지 않은 우선순위 역전이 발생할 수 있다. 이는 실시간 태스크의 스케줄링 가능성 보장을 불가능하게 한다. 따라서 우선순위 역전을 제한하는 자원 접근 프로토콜들이 연구되었으며 주기적 태스크 집합의 스케줄링 가능성 분석을 위한 충분조건이 제시되었다. 본 논문에서는 동적 우선순위 상한 프로토콜을 사용할 경우 개선된 스케줄링 가능성 충분조건을 제시한다. 제시된 방법에서는 높은 우선순위의 태스크들의 마감시간을 놓치지 않는 범위 내에서 낮은 우선순위를 가진 태스크가 계속 수행될 수 있다는 사실을 이용하였다. 이렇게 함으로써 높은 우선순위를 가진 태스크가 낮은 우선순위를 가진 태스크를 위해서 허용해 줄 수 있는 시간은 높은 우선순위를 가진 태스크의 최악 블록킹 시간에서 제외될 수 있다. 태스크의 최악 블록킹 시간이 감소하게 되므로 동적 우선순위 상한 프로토콜의 스케줄링 가능성 충분조건은 개선된다. When tasks access shared resources in real-time systems, the unbounded priority inversion may occur. In such cases it is impossible to guarantee the schedulability of real-time tasks. Several resource access protocols have been proposed to bound the duration of priority inversion and sufficient conditions are given to guarantee the schedulability of periodic task set. In this paper, we show an improved sufficient condition for schedulability when the dynamic priority ceiling protocol is used. Our approach exploits the fact that a lower priority task can continue to execute as far as the higher priority tasks do not miss their deadlines. This permitting execution time of the higher priority tasks for a lower priority task can be excluded from the worst-case blocking time of the higher priority tasks. Since the worst-case blocking time of tasks can be reduced, the sufficient condition for schedulability of dynamic priority ceiling protocol becomes further tight.

Special Report - 지상파 UHDTV 콘텐츠 보호 기술 표준화 현황

오성흔,O, Seong-Heun 한국정보통신기술협회 2016 TTA저널 Vol.167 No.-

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

오성흔,길아라,양승민 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.27 No.6

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

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

오성흔,길아라,양승민 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.2

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

실시간 시스템을 위한 최소 여유시간 우선 기반의 최소 선점을 갖는 스케줄링 알고리즘

오성흔(Sung-heun Oh),양승민(Seung-min Yang) 한국정보과학회 1999 정보과학회논문지 : 시스템 및 이론 Vol.26 No.4

최소 여유시간 우선(Least-Laxity-First) 스케줄링 알고리즘은 여유시간이 작은 태스크가 높은 우선순위를 갖는 동적 우선순위 스케줄링 방법으로서 단일 프로세서 시스템에서 최적임이 증명되었다. 그러나, 이 알고리즘은 최소 여유시간을 가진 태스크가 여러 개 존재하여 여유시간 충돌이 발생한 경우 이 태스크들 간에 빈번한 문맥교환이 발생하게 되는 문제점이 있어 실용적이지 못하다. 본 논문에서 제안하는 최소 여유시간 우선 기반의 최소 선점을 갖는 스케줄링 알고리즘(Least-Laxity-First with Minimum Preemption 또는 LLF/MP)은 여유시간이 충돌 했을 때에 문맥교환을 최소화함으로써 최소 여유시간 우선 스케줄링 알고리즘의 단점을 해결하였다. LLF/MP 스케줄링 알고리즘은 불필요한 문맥교환을 줄임으로써 시스템 오버헤드로 인한 시스템의 성능 저하를 방지할 수 있고 보다 많은 시스템 자원을 예측 불가능한 비주기적 태스크에게 할당할 수 있다. 본 논문에서는 LLF/MP 스케줄링 알고리즘을 제시하고 이 알고리즘이 최적이고 최소 선점을 가짐을 증명한다. 모의 실험 결과를 통하여 LLF/MP 스케줄링 알고리즘의 향상된 성능을 보인다. 프로세서 이용률이 증가할수록 유휴시간 충돌의 가능성이 높기 때문에 높은 프로세서 이용률에서 LLF/MP 스케줄링 알고리즘은 보다 좋은 성능을 갖는다. The Least-Laxity-First scheduling algorithm assigns higher priority to a task with the least laxity, and has been proved to be optimal for a uniprocessor system This algorithm, however, is impractical to implement because laxity-tie results in the frequent context witches among the tasks. The Minimum Preemption scheduling algorithm based on Least-Laxity-First(LLF/MP) proposed in this paper solves the problem of the LLF scheduling algorithm by minimizing the number of context switchings. By reducing the system overhead due to unnecessary context switchings, the LLF/MP scheduling algorithm avoids the degradation of system performance and provides more system resources for unanticipated aperiodic tasks. In this paper, we propose the LLF/MP scheduling algorithm and prove its optimality and the minimum preemption property. We show the performance enhancement of the proposed LLF/MP scheduling algorithm by using simulation results. LLF/MP scheduling algorithm performs much better at a high processor utilization, due to the high possibility of laxity-ties as the processor utilization increases.

동적 우선순위 상한 프로토콜의 스케줄링 가능성 조건 개선

오성흔(Sung-Heun Oh),양승민(Seung-Min Yang) 한국정보과학회 2001 정보과학회논문지 : 시스템 및 이론 Vol.28 No.11·12

실시간 시스템에서 태스크가 공유 자원을 사용할 때 제한되지 않은 우선순위 역전이 발생할 수 있다. 이는 실시간 태스크의 스케줄링 가능성 보장을 불가능하게 한다. 따라서 우선순위 역전을 제한하는 자원 접근 프로토콜들이 연구되었으며 주기적 태스크 집합의 스케줄링 가능성 분석을 위한 충분조건이 제시되었다. 본 논문에서는 동적 우선순위 상한 프로토콜을 사용할 경우 개선된 스케줄링 가능성 충분조건을 제시 한다. 제시된 방법에서는 높은 우선순위의 태스크들의 마감시간을 놓치지 않는 범위 내에서 낮은 우선순위를 가진 태스크가 계속 수행될 수 있다는 사실을 이용하였다. 이렇게 함으로써 높은 우선순위를 가진 태스크가 낮은 우선순위를 가진 태스크를 위해서 허용해 줄 수 있는 시간은 높은 우선순위를 가진 태스크의 최악 블록킹 시간에서 제외될 수 있다. 태스크의 최악 블록킹 시간이 감소하게 되므로 동적 우선순위 상한 프로토콜의 스케줄링 가능성 충분조건은 개선된다. When tasks access shared resources in real-time systems, the unbounded priority inversion may occur. In such cases it is impossible to guarantee the schedulability of real-time tasks. Several resource access protocols have been proposed to bound the duration of priority inversion and sufficient conditions are given to guarantee the schedulability of periodic task set. In this paper, we show an improved sufficient condition for schedulability when the dynamic priority ceiling protocol is used. Our approach exploits the fact that a lower priority task can continue to execute as far as the higher priority tasks do not miss their deadlines. This permitting execution time of the higher priority tasks for a lower priority task can be excluded from the worst-case blocking time of the higher priority tasks. Since the worst-case blocking time of tasks can be reduced, the sufficient condition for schedulability of dynamic priority ceiling protocol becomes further tight.

분산 컴퓨팅 환경에서 실시간 메시지 통신을 위한 TTP / C 프로토콜

오성흔(Sung-Heun Oh),최중섭(Joong-Sup Choi),양승민(Seung-Min Yang) 한국정보과학회 2000 정보과학회논문지 : 시스템 및 이론 Vol.27 No.5

분산 실시간 시스템에서의 노드간 주고 받는 메시지는 크게 동기적 메시지와 비동기적 메시지로 나눌 수 있다. 동기적 메시지는 샘플링된 음성이나 화상 데이타와 같이 주기적으로 발생되는 메시지로 전달시간 제약을 가지므로 종단간 마감시간을 보장해 주어야 한다. 비동기적 메시지는 비주기적인 메시지로 일정하지 않게 발생하며 일반적으로 전달 시간 제약사항이 엄격하지 않다. 본 논문에서는 분산 환경에서 동적으로 발생하는 동기적 메시지에 대해 높은 마감시간 보장성을 제공하는 실시간 프로토콜 TTP/C(timed token protocol with concession)을 제안한다. TTP/C는 비동기적 메시지나 긴급하지 않은 동기적 메시지의 전송 대역폭을 양보함으로써 긴급한 동기적 메시지의 마감시간을 보장한다. 또한 TTP/C는 노드에서 전송되는 동기적 메시지의 발생시간이 주기와 다르게 일정치 않더라도 높은 보장성을 갖는다. 모의 실험을 통하여 TTP/C가 기존의 TTP에 비해 동기적 메시지의 마감시간 보장성에 대해 높은 성능 향상을 가져옴을 보인다. Messages in distributed real-time systems are categorized into two groups: synchronous messages and asynchronous messages. Synchronous messages, such as sampled audio and image data, are generated periodically with delivery time constraints. Protocols should guarantee the end-to-end deadlines for such messages. Asynchronous messages are non-periodic and may arrive in a random way with no strict time constraints. In this paper, we propose TTP/C(timed token protocol with concession), an extension of TTP protocol, to achieve higher timeliness guarantee for synchronous messages in distributed real-time systems. In TTP/C, a node concedes the allocated bandwidth to other nodes with urgent synchronous messages to be sent provided that the node has no urgent messages. TTP/C works very well even if the synchronous messages are generated with some jittering by nodes. The simulation results show the improved performance of TTP/C protocol for guaranteeing synchronous messages deadlines compared to the existing TTP protocols.

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

오성흔(Sung-Heun Oh),길아라(Ara Khil),양승민(Seung-Min Yang) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.1·2

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

실시간 시스템을 위한 최소 선점을 갖는 최소 유휴시간 우선 스케줄링 알고리즘

오성흔(Sung-Heun Oh),임형택(Hyung-Taek Lim),양승민(Seung-Min Yang) 한국정보과학회 1998 한국정보과학회 학술발표논문집 Vol.25 No.1A

최소 유휴시간 우선(Least-Laxity-First 또는 LLF) 스케줄링 알고리즘은 유휴시간이 작은 태스크가 높은 우선순위를 갖는 동적 우선순위 스케줄링 방법으로서 단일 프로세서 시스템에서 최적임이 증명되었다. 그런데, 이 알고리즘은 유휴시간이 같은 태스크가 존재하는 경우 이 태스크들 간에 빈번한 문맥교환이 발생하게 되는 문제점이 있어 실용적이지 못하다. 최소 선점을 갖는 최소 유휴시간 우선(Least-Laxity-First with Minimum Preemption 또는 LLF/MP) 스케줄링 알고리즘은 유휴시간이 충돌 했을 때에 문맥교환을 최소화함으로써 LLF 스케줄링 알고리즘의 단점을 해결하였다. 본 논문에서는 LLF/MP 알고리즘을 제시한다. LLF/MP 스케줄링 알고리즘은 불필요한 문맥교환을 줄임으로써 보다 많은 시스템 자원을 예측 불가능한 비주기적 태스크에게 할당할 수 있다.

제한수신기술

신용태,오성흔 한국방송공학회 2008 방송과 미디어 Vol.13 No.4