다중처리기 시스템에서 데드라인과 여유시간을 통합한 실시간 스케줄링 기법

조성제(Seongje Cho) 한국정보과학회 2002 정보과학회논문지 : 시스템 및 이론 Vol.29 No.11·12

실시간 시스템에서 많은 요청을 처리하기 위해 다중처리기 구조가 필수적이 되었다. EDF나 LLA와 같은 기존의 실시간 온라인 스케줄링 알고리즘들은 다중처리기 시스템에서 실시간 태스크들을 스케줄링하는 데 적합하지 않다. EDF의 경우 문맥교환 오버헤드가 낮지만 다중처리기 이상현상을 보이며, LLA의 경우 준최적이지만 문맥교환 오버헤드가 높다. EDZL은 두 알고리즘의 문제점을 일부 해결하였으나 세 개 이상의 처리기에서는 준최적이 아니다. EDA2는 과부하 단계에서 좋은 성능을 보이지만 준최적이 아니다. 본 논문에서는 새로운 두개의 온라인 스케줄링 알고리즘 ED/LL과 ED2/LL을 제안한다. ED/LL은 다중처리기에서 준최적이며, 정상부하 단계에서 낮은 문맥교환 오버헤드와 높은 성공률을 보인다. 그러나, 시스템이 과부하 상태가 되면 ED/LL은 비효율적이다. 이를 해결하기 위해, ED2/LL은 정상 부하 단계에서는 ED/LL또는 EDZL을 사용하고 과부하 단계에서는 EDA2를 사용한다. 실험을 통해 ED2/LL이 정상부하 단계에서는 물론 과부하 단계에서도 좋은 성능을 보임을 확인할 수 있었다. For real-time systems, multiprocessor support is indispensable to handle the large number of requests. Existing real-time on-line scheduling algorithms such as Earliest Deadline First Algorithm (EDF) and Least Laxity Algorithm (LLA) may not be suitable for scheduling real-time tasks in multiprocessor systems. Although EDF has low context switching overhead, it suffers from “multiple processor anomalies.” LLA has been shown as suboptimal, but has the potential for higher context switching overhead. Earliest Deadline Zero Laxity (EDZL) solved somewhat the problems of those algorithms, however is suboptimal for only two processors. Another algorithm EDA2 shows very good performance in overload phase, however, is not suboptimal for multiprocessors. We propose two on-line scheduling algorithms, Earliest Deadline/Least Laxity (ED/LL) and ED2/LL. ED/LL is suboptimal for multiprocessors, and has low context switching overhead and low deadline miss rate in normal load phase. However, ED/LL is ineffective when the system is overloaded. To solve this problem, ED2/LL uses ED/LL or EDZL in normal load phase and uses EDA2 in overload phase. Experimental results show that ED2/LL achieves good performance in overload phase as well as in normal load phase.

다중처리기에서 주기적인 실시간 태스크 스케줄링

조성제(Seongje Cho) 한국정보과학회 2002 한국정보과학회 학술발표논문집 Vol.29 No.2Ⅰ

다중처리기 상에서 실시간 태스크 스케줄링에 대한 연구가 현재 많이 수행되고 있지만, 주로 Pfair(P-Fairness)와 EDF(Earliest Deadline First) 알고리즘에 대한 연구이다. Pfair는 이론적인 연구에 초점을 두고 있으며, EDF는 처리기들을 효율적으로 이용하지 못하는 문제점을 가지고 있다. 본 논문에서는 다중처리기 상의 주기적인 실시간 태스크 집합을 대상으로, LLA(Least Laxity Algorithm) 알고리즘이 높은 스케줄링 가능성(schedulability)을 가짐을 먼저 보인다. 다음으로 기존 알고리즘을 제시한다. ED/LL은 LLA보다 문맥교환 횟수는 적고 EDF보다 스케줄링 가능성이 높으며, 구현 오버헤드도 크지 않다.

산발적인 경성 실시간 태스크를 위한 온라인 스케줄링 알고리즘

조성제(Seongje Cho),이석균(Suk Kyoon Lee),유해영(Haeyoung Yoo) 한국정보과학회 1998 정보과학회논문지 : 시스템 및 이론 Vol.25 No.7

매우 복잡한 분산 실시간 시스템을 개발하는데 있어 실시간 운영체제의 다중처리기 지원이 필수적이다. Earliest Deadline Algorithm(EDA)이나 Least Laxity Algorithm(LLA)과 같은 기존의 온라인 스케줄링 알고리즘들은 다중처리기 시스템에서 비주기적인 실시간 태스크들을 스케줄하는데 적합하지 않다. EDA는 문맥교환 오버헤드가 낮지만 스케줄링 성공률이 떨어지는 "다중처리기 이상현상"을 나타낸다. LLA는 다중처리기 시스템에서 준최적이라고 알려진 것처럼 스케줄링 성공률이 높지만, 높은 문맥교환 오버헤드를 유발한다. 본 논문에서는 새로운 실시간 온라인 스케줄링 알고리즘인 Earliest Deadline Zero Laxity(EDZL)와 EDA2를 제안한다. EDZL은 기본적으로 EDA에 기반하고 있으나 여유시간이 0인 태스크가 발생하면 LLA를 사용하는 기법으로, 두 개의 처리기 시스템에서 준최적인 알고리즘이다. EDZL은 다중처리기 환경에서도 스케줄링 성공률이 뛰어나며 문맥교환 오버헤드도 낮다. 또 다른 알고리즘 EDA2은 EDA에 과부하 처리 기법을 보완한 것으로, 과부하 상태의 스케줄링 시 대기 태스크들 중에서 스케줄 가능하지 않은 모든 태스크를 제거하여 실시간 시스템의 성능을 향상시켜 준다. Multiprocessor support for real-time operating systems will be indispensable to the development of highly sophisticated and distributed real-time systems in the near future. The existing on-line scheduling algorithms EDA(Earliest Deadline Algorithm) and LLA(Least Laxity Algorithm) are not sufficient for scheduling real-time sporadic tasks in multiprocessor systems. EDA has low context switching overhead, but suffers from "multiple processor anomalies." LLA shows a high pass rate in task scheduling (shown as suboptimal), but has the potential for high context switching overhead. We propose a new on-line scheduling algorithm EDZL(Earliest Deadline Zero Laxity) which is a suboptimal algorithm for two processors. EDZL is based on EDA fundamentally but uses LLA as soon as laxity value of any task becomes zero EDZL has both a high pass rate in scheduling and low context switching overhead even in multiprocessor systems. We, also, present an efficient algorithm EDA2 under overloaded phases. EDA2 improves EDA in overloaded phase handling technique and enhances performance of real time system by removing infeasible tasks from ready queue at scheduling time.

선반입과 캐슁 기법을 이용한 이주 프로세스의 효율적인 수행

조성제(Seongje Cho),조유근(Yookun Cho) 한국정보과학회 1996 정보과학회논문지 : 시스템 및 이론 Vol.23 No.8

본 논문에서는 효율적인 부하 균등화를 위하여 페이지 선반입(page prefetch) 기법과 텍스트 세그먼트 캐슁(text segment caching) 기법을 이용하는 새로운 비선점형 프로세스 전송(nonpreemptive process transfer) 정책을 제안한다. 페이지 선반입 기법이란 이주 프로세스에 의해 창조될 다음 페이지를 근원지 노드의 디스크로부터 원격 노드의 메모리로 미리 반입시켜 디스크 접근 지연 시간과 네트워크 전송 지연 시간을 단축시키는 방법이다. 페이지 선반입은 서버 프로세스에 의해 수행되며 이주 프로세스의 전송 지연 시간을 단축시켜 준다. 이 기법은 프로그램의 페이지 이주 순서를 반영하는 페이지 부재 궤적에 기반하여 수행되는데, 이를 위해 본 시스템은 해당 프로그램의 이전 실행 시에 발생된 페이지 부재 궤적을 수집하여 이용한다. 텍스트 세그먼트 캐슁 기법은 목적지 노드로 이주되어 실행이 종결된 프로세스에 대하여 일정 기간동안 텍스트 세그먼트를 목적지 노드의 메모리에 유지함으로써 프로세스 이주시 텍스트 세그먼트를 전송할 필요가 없도록 하여 준다. 텍스트 캐슁 기법 하에서 원격 노드로 이주될 프로세스로 동일한 프로세스가 또다시 선택될 경우, 그 프로세스가 이전에 이주된 적이 있는 노드로 이주시켜 실행시킴으로써 텍스트 세그먼트를 전송할 필요없이 고속 수행할 수 있다. 제시된 두 기법을 적용하여 실험한 결과 이주 프로세스의 응답 시간과 수면 시간이 많이 단축되었다. In distributed computing environment, load balancing has been one of main issues. For efficient load balancing, we propose a new nonpreemptive process transfer policy based on page prefetch and text segment caching schemes. Page prefetch scheme tries to reduce disk access and network transfer latencies by transferring beforehand the predicted pages which a migrated process will reference shortly to memory of a remote node from disk of a source node. Prefetch is performed by server process and reduces process transfer latency. The prefetch is implemented using page fault traces that are obtained at a previous execution of program and reflect the sequence of page migration. Text segment caching scheme tries to eliminate text segment transfer of a migrated process by caching the text segment in the destination node for a period of time after the process has terminated. If the process needs to be migrated again under our text caching scheme, it can be executed rapidly on the node where it has previously been migrated without transferring its text segment. Experimental results show that our schemes induce little overhead and are effective in reducing the response time and the sleep time of migrated processes.

페이지 선반입시 메모리 오염 감소 정책과 선반입 버퍼 할당 정책

조성제(SeongJe Cho) 한국정보과학회 1997 정보과학회논문지 : 시스템 및 이론 Vol.24 No.11

Page prefetch is a scheme to reduce pagein delay incurred at page fault exception under demand paging system. Prefetch scheme tries to reduce the cost of handling page fault by predicting the next page reference and fetching the page from secondary storage to memory before it is requested. If the prefetched pages are referenced, the scheme enhances system performance; if the pages are not and kept in memory, memory gets polluted with them. In addition, the working set size of each process is diminished because a portion of memory is allocated for prefetching space. As a result, the performance may be more degraded than without the prefetch scheme. Under prefetch system based on page fault traces, we present policies of page prefetch that reduce memory pollution, maintain efficiently the pages which are not referenced shortly, and determine the optimal size of prefetch buffer space out of restricted memory. The proposed policies enhance performance of each application under any level of memory load. 요구 페이징 시스템에서 페이지 부재 결함 처리 시에 발생되는 페이지 반입 지연을 줄이기 위한 방법으로 페이지 선반입이 도입되었다. 페이지 선반입은 프로세스가 참조하리라고 예상되는 페이지를 실제 참조되는 시점보다 먼저 그 페이지를 보조 기억장치로부터 주 기억장치로 반입하여 페이지 부재 결함 처리 비용을 줄이고자 하는 기법이다. 이 기법에서 선반입된 페이지가 참조되면 시스템 성능이 향상되지만 이 페이지가 참조되지 않고 메모리만 차지하게 될 경우에는 메모리를 오염시킨다. 또한 메모리 일부를 선반입용 공간으로 할당함으로써 프로세서들의 작업 집합의 크기가 줄어들어 선반입을 적용하지 않는 경우보다 시스템 성능이 오히려 더 저하되기도 한다. 본 논문에서는 페이지 부재 궤적을 이용한 선반입 시스템에서 메모리 오염을 줄이는 방안과 선반입된 페이지 중에서 즉시 참조되지 않은 페이지를 처리하는 방안, 그리고 각 프로세스에 할당된 메모리 중에서 선반입용 버퍼로 어느 정도의 공간을 할당하는 것이 최적인가를 결정하는 방안을 제시한다. 제시된 선반입 방안은 임의 메모리 부하 상태에서 다른 응용에 영향을 주지 않고 각 응용의 성능을 향상시켜 준다.

C++ 언어를 위한 데이터 obfuscation 도구 구현 및 테스트

조병민(ByoungMin Cho),노진욱(JinUk Noh),오현수(Hyunsoo Oh),장혜영(Hye-Young Chang),정민규(Mingyu Jung),이승원(Seungwon Lee),박용수(Yongsoo Park),우제학(Jehak Woo),조성제(Seongje Cho) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.1

상용 응용 소프트웨어들은 주요 정보 및 알고리즘들을 내포하고 있어, 악의적인 역공학자들에 의해 특정 소프트웨어를 decompile하여 자료구조 및 제어 흐름을 분석하려는 공격이 이루어 지고 있다. 본 논문에서는 MS 윈도우 XP 상의 Visual C++ (MFC 포함) 프로그램을 역공학 공격으로부터 보호하기 위한 데이터 obfuscator를 구현하고 그 성능을 평가한다. 구현한 obfuscator는 C++ 소스코드를 입력 받아 3가지의 데이터 obfuscation 알고리즘을 적용한 후, 이를 다시 소스코드로 재생성하는 도구로 큰 성능저하 없이 구현 가능함을 알 수 있다.

객체 개념에 기반한 분산 공유 메모리 시스템

이병주(ByaungJoo Lee),조성제(SeongJe Cho),조유근(YooKun Cho) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.1

다중 컴퓨터 시스템에 다중 처리기 시스템의 특성인 공유 메모리 기법을 적용한 분산 공유 메모리 (DSM)는 분산 하드웨어 구성을 용이하게 해 주고 간편한 병렬 프로그래밍 모델을 제공해 준다. 또한 DSM 시스템은 공유 메모리 양식(style)의 동기화 기법을 제공하며 여러 분산된 태스크가 유연셩있게 데이타를 공유하게 해 준다. 본 논문에서는 기존 DSM의 단점을 일부 보완해 줄 수 있는 DOM 시스템을 제시한다. 본 DOM 시스템은 공유 데이타에 대한 액세스와 일관성을 객체 단위로 관리하며 메시지 전송량을 줄이면서 시스템의 효율을 높이고자 했다. 이를 위해 일관성 프로토콜로는 선택적인 쓰기-갱신 기법을 사용하며, 객체마다 소유자가 있어 객체에 대해 동기화와 액세스 관리를 담당한다. 이러한 고려 사항 외에도 req_list 자료 구조가 있어 데이타 액세스 요청을 일괄 처리하게 해 주며, 큰 공유 데이타 갱신 요청시에는 RPC를 선택적으로 지원한다.

MS 원도우 시스템에서 실해 파일의 효율적인 암호화에 관한 연구

최종천(Jongcheon Choi),조성제(Seongje Cho) 한국정보과학회 2007 한국정보과학회 학술발표논문집 Vol.34 No.1D

파일 보호 기법은 정보보호와 접근제어라는 측면에서 다양하게 연구되어지고 있다. 이러한 파일 보호기법 중 암호화 파일 시스템에 대한 많은 여구가 진행 되고 있다. 본 연구에서는 기존의 암호화 파일 시스템에서 발생하는 파일에 전체에 대한암호화 효율성을 개선하기 위한 기법으로 MS 원도우즈 실행파일 형식인 PE 파일 형식 헤더부분과 코드영역에 대한 암호화 방안을 제안하여 실행 가능한 파일에 대한 효율적인 암호화 기법과 보호방안을 제공하고자 한다.

시한폭탄 기반의 악성 웹 콘텐츠들의 효율적인 탐지 방법

김동진(Dongjin Kim),조성제(Seongje Cho),김홍근(Hongkun Kim) 한국정보과학회 2010 한국정보과학회 학술발표논문집 Vol.37 No.1A

SPIKE를 활용한 웹 서버 취약점 분석 방법SPIKE를 활용한 웹 서버 취약점 분석 방법

최종천 ( Jongcheon Choi ),조성제 ( Seongje Cho ) 한국정보처리학회 2004 한국정보처리학회 학술대회논문집 Vol.11 No.2

인터넷 관련기술이 발전하고 소프트웨어의 개발 규모가 커짐에 따라 소프트웨어 취약성 분석이 점점 더 복잡해지면서 중요해지고 있다. 바이너리코드만 주어지는 상용 소프트웨어의 경우 보안 취약성 분석을 위해 블랙박스테스트 기법이 필요하며, 네트워크 관련 소프트웨어의 경우 다양한 공격도구가 알려져 있어 이에 대한 취약성 분석이 우선하여야 한다. 본 논문에서는 마이크로소프트 윈도우 2000 환경에서 SPIKE를 활용하여 아파치 웹 서버를 바탕으로 네트워크 소프트웨어 취약점을 분석하였다. SPIKE는 취약점 분석을 좀더 효율적이고 체계적으로 분석하기 위한 블랙박스테스트 기법을 제공하여 준다.