연속적 미디어의 서비스 질 보장을 위한 스케쥴링

길아라(Ara Khil),구제웅(Jewoong Ku) 한국정보과학회 2003 한국정보과학회 학술발표논문집 Vol.30 No.1A

분산 환경의 많은 멀티미디어 응용들은 연속적 음성/화상 자료들을 위한 실시간 특성을 가지는 패킷들을 생성하고, 실시간 태스크 스케쥴링 이론에 따라 이들을 전송한다. 본 논문에서는 광대역폭 통신망을 기반으로 하는 분산 멀티미디어 응용의 연속 미디어를 위한 트래픽의 특성을 모델링하고, 보다 사용자의 요구에 따른 서비스 질의 보장을 위하여 비선정적 경성 실시간 태스크 스케쥴링 이론인 PDMA 알고리즘을 도입한다. 또한, 응용 시스템의 고 품질 서비스를 유지하기 위하여 새로운 트래픽 발생 요청이 현재 진행 중인 서비스 내용에 영향을 주지 않도록 제어하는 사용권 제어 기법을 제안한다. 제안하는 사용권 제어 기법은 PDMA 알고리즘을 위한 충분조건식이기 때문에 이를 만족하는 메시지 집합에 대하여 PDMA 알고리즘은 항상 실행가능한 스케쥴을 찾을 수 있다. 따라서, 새로운 요청을 포함하는 전체 메시지 집합이 제안하는 사용권 제어 기법의 조건들을 만족하면, 새로운 요청에 의한 트래픽의 발생을 허용한다. 그렇지 않은 경우 새로운 요청을 거절한다.

연속적 멀티미디어 트래픽의 서비스 질 보장을 위한 스케쥴링

길아라(Ara Khil) 한국정보과학회 2003 정보과학회논문지 : 시스템 및 이론 Vol.30 No.1·2

분산 환경의 많은 멀티미디어 응용들은 연속적 음성/화상 자료들을 위한 실시간 특성을 가지는 패킷들을 생성하고, 실시간 태스크 스케쥴링 이론에 따라 이들을 전송한다. 본 논문에서는 광대역폭 통신망을 기반으로 하는 분산 멀티미디어 응용의 연속 미디어를 위한 트래픽의 특성을 모델링하고, 보다 사용자의 요구에 따른 서비스 질의 보장을 위하여 비선점적 경성 실시간 태스크 스케쥴링 이론인 PDMA 알고리즘을 도입한다. 또한, 응용 시스템의 고 품질 서비스를 유지하기 위하여 새로운 트래픽 발생 요청이 현재 진행 중인 서비스 내용에 영향을 주지 않도록 제어하는 사용권 제어 기법을 제안한다. 제안하는 사용권 제어 기법은 PDMA 알고리즘을 위한 충분조건식이기 때문에 이를 만족하는 메시지 집합에 대하여 PDMA 알고리즘은 항상 실행가능한 스케쥴을 찾을 수 있다. 따라서, 새로운 요청을 포함하는 전체 메시지 집합이 제안하는 사용권 제어 기법의 조건들을 만족하면, 새로운 요청에 의한 트래픽의 발생을 허용한다. 그렇지 않은 경우 새로운 요청을 거절한다. 끝으로 본 논문에서 제안하는 사용권 제어 기법을 이용하는 스케쥴링의 실용성을 입증하기 위한 모의실험 결과를 보인다. Many of mutlimedia applications in distributed environments generate the packets which have the real-time characteristics for continuous audio/video data and transmit them according to the real-time task scheduling theories. In this paper, we model the traffic for continuous media in the distributed multimedia applications based on the high-bandwidth networks and introduce the PDMA algorithm which is the hard real-time task scheduling theory for guaranteeing QoS requested by the clients. Furthermore, we propose the admission control to control the new request not to interfere the currentservices for maintaining the high quality of services of the applications. Since the proposed admission control is sufficient for the PDMA algorithm, the PDMA algorithm is always able to find the feasible schedule for the set of messages which satisfies it. Therefore, if the set of messages including the new request satisfies the conditions of the proposed admission control, it admits the new request to generate the new traffic. Otherwise, it rejects the new request. In final, we present the simulation results for showing that the scheduling with the proposed admission control is of practical use.

[서평]Linux Kernel Internals(Second Edition)

길아라(Ara Khil) 한국정보과학회 1999 정보과학회지 Vol.17 No.5

[탐방]「한국소프트웨어진흥원」

길아라(Ara Khil) 한국정보과학회 2001 정보과학회지 Vol.19 No.4

초기호출시간이 지정된 실시간 주기적 태스크의 비선점적 스케쥴링

길아라(Ara Khil),맹승렬(Seungryoul Maeng) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.4

단일 프로세서 시스템에서 초기호출시간이 지정된 주기적 태스크를 비선점적 스케쥴링하는 문제는 NP-hard 문제로 알려져 있다. 본 논문에서는 초기호출시간이 지정된 주기적 태스크의 스케쥴링 성공율을 향상시키기 위하여 주기적 태스크의 반복성과 예측가능성을 이용하는 새로운 스케쥴링 전략과 새로운 비선점적 스케쥴링 알고리즘을 제안한다. 본 논문에서 제안하는 스케쥴링 전략은 주어진 문제를 각각 주어진 스케쥴링 시간구간내에서 순방향 또는 역방향으로 스케쥴링하는 두 개의 부-스케쥴링 문제로 나눈 후, 이들 두 개의 실행가능한 부-스케쥴들을 적용하는 시간구간에 따라 결합하여 하나의 완전한 실행가능한 스케쥴을 구하는 정적 스케쥴링 전략이다. 이 때, 보다 효율적으로 주어진 문제를 분할하기 위하여 초기호출 시간과 주기와의 관계식을 제시한다. 제안된 스케쥴링 알고리즘은 선택한 태스크 호출을 비선점적 최소 마감시간 우선 (earliest- deadline-first, EDF) 알고리즘으로 스케쥴링할 경우 발생할 수 있는 다른 태스크 호출의 마감시간 초과를 미리 계산한다. 계산 결과, 다른 태스크의 마감시간 초과가 예상되면, 선택한 태스크의 스케쥴링을 연기하므로써 예상된 마감시간 초과를 회피한다. 그렇지 않은 경우, 선택한 태스크 호출은 비선점적 최소 마감시간 우선 알고리즘의 경우와 통일한 방법으로 스케쥴링한다. 제안된 스케쥴링 알고리즘은 최소 마감시간 우선 알고리즘으로 실행가능한 스케쥴을 찾을 수 있는 태스크 집합에 대해서는 항상 실행가능한 스케쥴을 찾을 수 있다. 본 논문에서 제안된 스케쥴링 전략 및 스케쥴링 알고리즘의 향상된 성능은 모의실험 결과로써 나타내 보인다. The problem of non-preemptive scheduling of real-time periodic tasks with specified release times on a uniprocessor system is known as NP-hard problem In this paper, we propose the new scheduling strategy and the new scheduling algorithm which use the reperitiveness and the predictability of periodic tasks for improvements of schedulabilities of real-time periodic tasks with specified release times. The proposed scheduling strategy is the static scheduling strategy that suggests dividing the given problem into two subproblems which find feasible schedules in the forward scheduling or in the backward scheduling within specific time intervals and combining the two feasible schedules into a complete feasible schedule for the original problem. We present the release times as a function of periods for the efficient problem division. The proposed scheduling algorithm schedules periodic tasks by using the heuristic that precalculates if the scheduling of the selected task leads that a task misses a deadline when tasks are scheduled by the non-preemptive EDF algorithm. It defers the scheduling of the selected task to avoid the precalculated deadline-missing. Otherwise, it schedules the selected task in the same as the non-preemptive EDF algorithm. Our scheduling algorithm can always find a feasible schedule for the set of periodic tasks with specified release times which is schedulable by the non-preemptive EDF algorithm. We show the improvements on the performance of the proposed scheduling strategy and scheduling algorithm by simulation results.

초기호출시간이 지정된 실시간 주기적 태스크의 단일 프로세서 시스템 상에서의 비선점적 스케쥴링

길아라(Ara Khil),정의훈(Euihoon Jeong),맹승렬(Seungryoul Maeng) 한국정보과학회 1996 한국정보과학회 학술발표논문집 Vol.23 No.1A

단일 프로세서 시스템에서 초기호출시간이 지정된 주기적 태스크를 비선점적 스케쥴링하는 문제는 NP-hard문제로 알려져 있다. 본 논문에서는 초기호출시간이 지정된 주기적 태스크의 스케쥴링 성공율을 향상시키기 위하여 새로운 스케쥴링 전략과 새로운 스케쥴링 알고리즘을 제안하고 이들의 성능 분석을 위한 모의실험 결과를 보인다. 본 논문에서 제안하는 스케쥴링 전략은 우선, 태스크들의 주기와 초기호출시간을 이용하여 두 개의 스케쥴링 경계시간을 계산하고, 이들을 이용하여 주어진 문제를 각각 다른 시간구간 내에서 실행가능한 스케쥴을 찾는 두 개의 부-문제로 나눈다. 또한, 스케쥴링 경계시간점들의 효율적인 계산을 위한 각 태스크의 초기호출시간과 주기간의 합수를 찾는다. 본 논문에서 제안하는 스케쥴링 알고리즘은 최소 마감시간 우선 (earliest-deadline-first) 정책에 기반한 휴리스틱을 사용하여 주어진 시간구간 내에서 초기호출시간이 지정된 주기적 태스크 집합의 스케쥴링 성공율을 향상시킨다. 즉, 선택한 태스크의 스케쥴링 전에 다른 태스크들의 마감시간 초과 발생을 예상하여 스케쥴링 순서를 변경하므로써 마감시간 초과 발생을 회피한다. 결국, 제안된 알고리즘은 주어진 시간구간 내에서 최소 마감시간 우선 알고리즘으로 스케쥴링 가능한 태스크 집합에 대해서는 항상 실행가능한 시케쥴을 찾을 수 있다. 끝으로, 모의실험 결과로써 제안된 스케쥴링 전략 및 스케쥴링 알고리즘의 향상된 성능을 나타내 보인다.

링크구조분석을 이용한 스팸메일 분류

이신영(Shin Young Rhee),길아라(Ara Khil),김명원(Myung Won Kim) 한국정보과학회 2007 정보과학회논문지 : 소프트웨어 및 응용 Vol.34 No.1

기존의 내용기반 스팸메일 분류는 전자메일이 이미지를 많이 가지고 있고 텍스트는 적게 가지고 있을 경우에는 내용을 분석하기 어려우므로 스팸메일을 분류하는 데 한계가 있다. 이와 같은 문제를 해결하기 위하여 본 논문에서는 전자메일의 구조를 분석하는 링크구조분석 스팸메일 분류 알고리즘을 제안한다. 이것은 전자메일 안의 하이퍼링크의 개수와 하이퍼링크가 가리키는 웹 문서들이 다른 웹 문서에 의해 링크된 수를 측정하여 전자메일의 중요도를 계산한 후 의사결정트리를 학습하여 스팸메일과 정상메일을 분류한다. 또한 위의 링크구조분석 알고리즘과 하이퍼링크의 서버 주소만을 이용한 변형된 링크구조분석 알고리즘, 그리고 SVM(support vector machine)을 이용한 내용기반 방법을 다수결 원칙으로 결합한 통합 스팸메일 분류 시스템을 제안한다. 실험 결과, 제안한 링크구조분석 알고리즘은 기존의 내용기반방법 보다 스팸메일 분류 정확도가 94.8%로 약간 향상되었으며 또한 통합 스팸메일 분류 시스템도 내용기반 방법과 비교하여 향상된 97.7%를 나타냈다. The existing content-based spam mail filtering algorithms have difficulties in filtering spam mails when e-mails contain images but little text. In this thesis we propose an efficient spam mail classification algorithm that utilizes the link structure of e-mails. We compute the number of hyperlinks in an e-mail and the in-link frequencies of the web pages hyperlinked in the e-mail. Using these two features we classify spam mails and legitimate mails based on the decision tree trained for spam mail classification. We also suggest a hybrid system combining three different algorithms by majority voting: the link structure analysis algorithm, a modified link structure analysis algorithm, in which only the host part of the hyperlinked pages of an e-mail is used for link structure analysis, and the content-based method using SVM (support vector machines). The experimental results show that the link structure analysis algorithm slightly outperforms the existing content-based method with the accuracy of 94.8%. Moreover, the hybrid system achieves the accuracy of 97.6%, which is a significant performance improvement over the existing method.

에너지 효율적인 센서 네트워크를 위한 발전된 방향성 메시징 기법

양창우(changwoo yang),길아라(ara khil) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.2A

저전력 Nano-Q+ 를 위한 방향성 메시징 기법의 설계 및 구현

김우진(Woojin Kim),길아라(Ara Khil) 한국정보과학회 2009 한국정보과학회 학술발표논문집 Vol.36 No.2A

다중 프로세서 시스템에서 문맥교환을 줄이기 위한 변형된 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.