혼합 우선순위 시스템에서 경성 비주기적 태스크 스케쥴링 알고리즘

김형일,이승룡,이종원,김정순(Hyungill Kim),Sungyoung Lee,Jongwon Lee,Jungsoon Kim 한국정보과학회 1995 정보과학회논문지 : 시스템 및 이론 Vol.22 No.10

본 논문은 주기적 태스크와 경성 비주기적 태스크가 혼합된 단일 처리기 실시간 시스템 에서 중단형 (preemptive) 경성 비주기적 태스크의 스케쥴링 기법인 자유지역 지시 (Free Region Indicating. FRI) 알고리즘을 제안한다. FRI 알고리즘은 온라인에서 경성 비주기적 태스크에 대하여 할당여부를 판단하며, 주기적 태스크와 비주기적 태스크들에 대하여 고정 우선순위와 가변 우선순위를 혼합한 스케쥴링 기법으로 저자가 개발한 임계 태스크 지시 (Critical Task Indicating: CTI) 알고리즘 [4] 을 확장한 것이다. CTI 알고리즘은 연성 비주기적 태스크 스케쥴링 알고리즘으로, 모의 실험 연구에 의하면 slack stealing 알고리즘 [6] 보다 성능 개선을 이루었으며 특히 시스템 과부하 시에도 잘 작동하였다.FRI 알고리즘은 모든 주기적 태스크의 마감시간을 보장할 뿐 아니라 오프라인에서 작성된 CTI 테이블과 스케쥴링 변동 사항에 대한 정보를 가지고 있는 FRI 테이블을 사용하므로써 알고리즘 수행시간 복잡도를 감소시켰으며 스케쥴링 예측성도 높였다. In this paper, we present a preemptive scheduling of hard-aperiodic task. so called the Free Region Indicating (FRI) algorithm. in jointly scheduling the periodic tasks and hard-aperiodic tasks on a uniprocessor real-time system in which hard deadlines of periodic and aperiodic tasks are scheduled in such a way of mixed scheduling of a fixed and dynamic priority algorithm. The algorithm executes an on-line acceptance test for the hard aperiodic tasks and it has extended the Critical Task Indicator (CTI) algorithm [4]of which simulation study shows a considerable performance improvement over the other soft-aperiodic task scheduling algorithms. such a slack-stealing algorithm [6], especially under a heavy transient overload. The FRI algorithm is not only to guarantee all the deadline of periodic tasks. but also to reduce time complexity and improve scheduling predictability since it maintains both the CTI and FRI tables which have scheduling informations and built off-line.

동적 추천 기능이 있는 음악 추천 서버 구현

김형일 ( Hyungil Kim ),박준태 ( Juntae Park ),김종일 ( Jongil Kim ),김경섭 ( Kyungsup Kim ),김용욱 ( Yonguk Kim ),김준태 ( Juntae Kim ) 한국정보처리학회 2007 한국정보처리학회 학술대회논문집 Vol.14 No.2

본 논문에서는 동적 추천 기능이 있는 자바 기반 음악 추천 서버를 소개한다. 본 논문에서 소개하는 추천 서버는 각 음악 사이의 유사도를 그래프로 저장하는 그래프 기반 협동적 여과 방식을 사용하며, 독립된 서버로 구성되어 클라이언트와 정해진 프로토콜에 따라 통신하도록 구현되었다. 또한 이 추천 서버는 특정 사용자나 특정 음악의 정적인(static) 성향뿐 아니라 시간에 따라 달라지는 동적인(dynamic) 성향에 맞는 추천도 가능하도록 설계되었다. 정적 성향이란 어떤 사용자가 가지고 있는 음악에 대한 기본적인 취향을 나타내고, 동적 성향이란 특정한 상황이나 분위기에 따라 유동적으로 변하는 성향을 의미한다. 본 논문에서 소개하는 추천 서버는 정적 성향과 동적 성향에 대하여 각각 추천할 수 있는 기능을 가지고 있으며, 이러한 기능을 바탕으로 실제 사용자들의 음악 다운로드 데이터를 이용하여 추천 데모 사이트를 구축하였다.

멀티미디어 추천시스템을 위한 속성 생성 기법

김형일(Hyungil Kim),엄정국(Jeongkook Eom) 한국멀티미디어학회 2008 멀티미디어학회논문지 Vol.11 No.2

게임에서 FSM-기반 확률 추정을 이용한 캐릭터의 행동제어

김형일(Hyungil Kim),윤현님(Hyunnim Yoon) 한국멀티미디어학회 2005 멀티미디어학회논문지 Vol.8 No.9

Sparse 표현을 이용한 X선 흡수 영상 개선

김형일(Hyungil Kim),엄원용(Wonyong Eom),노용만(Yong Man Ro) 한국멀티미디어학회 2012 멀티미디어학회논문지 Vol.15 No.10

선택적 우선순위 알고리즘 : 가변 우선순위 시스템에서 비주기적 태스크 스케쥴링

김형일(Hyungill Kim),이승룡(Sungyoung Lee),이종원(Jongwon Lee) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.7

슬랙 스틸링 기반 비주기적 태스크 스케쥴링은 슬랙 계산의 복잡도로 인하여 실용적이지 못하다는 문제점을 가지고있다. 이를 개선하기 위하여 본 논문에서는 가변우선순위 시스템 하에서 단순하게 슬랙을 계산할 수 있으며 임계 태스크 지정 (CTI: Critical Task Indicating) 스케쥴링 틀(framework)에서 최적인 선택적 우선순위 (APS: Alternative Priority Scheduling) 연성 비주기적 태스크 스게쥴링 알고리즘을 제안한다. 제안한 알고리즘은 저자가 개발한 EDF-CTI (Earliest Deadline First-Critical Task Indicating) 알고리즘을 확장한 것으로, 오프라인에서 생성한 예측성을 가진 CTI 테이블을 참조하여 온라인에서 우선순위 구동 스케쥴링인 최조 마감 우선순위 (EDF: Earliest Deadline First)와 임계 실행시간 우선 (CEF: Critical Execution time Frist) 스케쥴링 정책을 선택적 (alternatively)으로 적용하는 스케쥴링 기법이다. APS 알고리즘은 슬랙을 계산할 때 낙관적 (optimistic) 슬랙 계산 방식을 사용하는데, 이는 주기적 태스크의 모든 수준에서 슬랙을 계산해야만 하는 슬랙스틸링 기반 알고리즘의 최소 (minimal) 슬랙 계산 방법에 비하여 단순하다. 시뮬레이션 연구결과 제안된 알고리즘은 대부분의 경우 EDF-CTI 알고리즘 및 다른 비주기적 태스크 스케쥴링보다 비슷하거나 더 빠른 반응시간을 나타내었으며 시스템 과부하 상태에서도 잘 동작하였다. The major drawback of the slack stealing based schedulings for aperiodic requests is a high computational complexity to calculate slack which in consequence is considered impractical In order to resolve this problem, we introduce a new type of soft aperiodic task scheduling, called an Alternative Priority Scheduling (APS) Algorithm, which has a simple mechanism to calculate slack and is an optimal within a CTI (Critical Task Indicating) scheduling framework in dynamic: priority systems The APS algorithm has extended the EDF-CTI (Earliest Deadline First-Critical Task Indicating) algorithm developed by the authors The algorithm references the off line built CTI table which is created by the deadlinewise preassignment policy and choices either an EDF or a CEF (Critical Execution time First) algorithm alternatively at on-line. When calculating the slacks, the proposed algorithm uses an optimistic method which is simpler than the minimal slack calculation scheme used in the slack stealing algorithms. The simulation study shows that the proposed algorithm, in most cases, is slightly better than both the EDF-CTI algorithm and the other aperiodic scheduling algorithms in terms of short response time of aperiodic requests, and considerably improves the response time in transient overload.

가시성 검사를 이용한 3차원 게임에서의 효율적인 경로 탐색

김형일(Hyungil Kim),정동민(Dongmin Jung),엄기현(Kyhyun Um),조형제(Hyungje Cho),김준태(Juntae Kim) 한국멀티미디어학회 2006 멀티미디어학회논문지 Vol.9 No.11

청소로봇을 위한 속성기반 자동 청소기법

김형일(Hyungil Kim) 한국정보기술학회 2010 한국정보기술학회논문지 Vol.8 No.10

Cleaning robots have specific purposes to clean offices or living rooms. The random cleaning method is simply implemented because the cleaning paths are randomly determined and the robots move along the determined paths. However, a weakness of this method is that it takes a long time to clean. A boustrophedon cleaning method shows superior performance than the random cleaning. However, its weakness is the increase in areas which are cleaned several times in complicated environment. The template method classifies the arrangement of obstacles into several types and determines the cleaning paths by type. The template method can effectively perform the cleaning task using templates or environmental information. However, its weakness is that it can perform effective cleaning only in the environment suitable for each template type. This paper suggests the automatic cleaning method using features for improving the performance of cleaning robots. The method plans the cleaning paths using feature information on an absolute coordinate system. The effectiveness of the method was verified by a variety of simulations.

상황확률을 이용한 클러스터링기반 플로킹

김형일(Hyungil Kim) 한국정보기술학회 2009 한국정보기술학회논문지 Vol.7 No.6

The flocking method proposed here is one way of overcoming the shortcomings that may arise in the use of many system recourses when depicting a large-scale flock in animation or games. In the flocking method, the boid included in the flock responds to real-time environment change. Basic behavioral rules are used randomly when controlling the behaviors of the boid in flocking. Therefore, as flocking does not continuously maintain the information of the boid conditions, it uses few system resources. Behaviors of the boid, however, cannot match the real situation as they are randomly decided in the flocking and unnatural boid behavior decreases interest on the part of users. In this paper, we propose a clustering-based flocking using context probability to overcome the problems in flocking. When clustering-based flocking using context probability is applied to a large-scale flock, boids move naturally according to the characteristics of the group. Several experimental results that show the effectiveness of the proposed method are also presented.

디지털 콘텐츠를 위한 소속도를 이용한 사례기반 필터링

김형일(Hyungil Kim) 한국콘텐츠학회 2010 한국콘텐츠학회논문지 Vol.10 No.10

디지털 콘텐츠의 양이 방대해지면서 사용자가 원하는 디지털 콘텐츠를 검색하는 데 많은 시간이 필요하다. 그러므로 방대한 디지털 콘텐츠로부터 사용자가 원하는 콘텐츠를 제공하기 위해서는 디지털 콘텐츠를 분석하여 사용자에게 적합한 콘텐츠를 추출하는 기술이 필요하다. 그리고 빠른 시간 내에 사용자에게 적합한 디지털 콘텐츠를 찾기 위해서는 디지털 콘텐츠에 대한 필터링 기술이 필요하다. 본 논문에서는 개인에게 적합한 디지털 콘텐츠를 필터링하는 기법을 제안한다. 본 논문에서 제안한 기법은 디지털 콘텐츠에 대한 사례기반 정보를 분석하여 개인 사용자에게 적합한 디지털 콘텐츠를 제공한다. 사용자의 선호도 분석에는 디지털 콘텐츠 사용에 대한 사례를 이용한다. 다양한 시뮬레이션을 통해 제안한 기법의 효과를 확인하였다. As digital contents become vast in quantity, it takes long time for users to search the digital contents they want, which is a problem that has arisen. Therefore, it is required to have the technology that analyzes vast digital contents and extracts the appropriate contents for users in order to provide them with contents they want. For a fast searching of digital contents suitable for users, it is necessary to have the technology of filtering for digital contents. In this paper, we propose a method of filtering digital contents suitable for individual users. The method suggested in this paper is to analyze case-based information in digital contents and provide the digital contents suitable for individual users. The case for using digital contents is used for analysis of users' preference. Various simulations were conducted to confirm the effectiveness of the proposed method.