Stack Resource Policy를 사용하는 동적 우선순위 스케줄링에서 작업 큐잉을 위한 효율적인 자료구조

한상철(Sangchul Han),박문주(Moonju Park),조유근(Yookun Cho) 한국정보과학회 2006 정보과학회논문지 : 시스템 및 이론 Vol.33 No.5·6

Stack Resource Policy (SRP)는 몇 가지 독특한 특성을 가진 실시간 동기화 프로토콜이다. 그 특성 중의 하나는 초기 수행 차단(early blocking)으로서, 공유자원을 요청하는 시점에 작업의 수행을 정지시키는 것이 아니라, 작업의 수행 시점 자체를 연기하도록 한다. SRP가 EDF와 같은 동적 우선순위 스케줄링 알고리즘과 같이 사용될 경우, 초기 수행 차단을 지원하기 위해 스케줄러는 수행이 블록(block)되지 않을 작업 중 가장 우선순위가 높은 작업을 선택해야 하며, 이러한 탐색 연산은 수행 오버헤드(runtime overhead)의 원인이 된다. 본 논문에서는 SRP와 EDF를 같이 사용할 때의 스케줄러 수행 오버헤드를 분석한다. 기존의 준비 큐(ready queue) 구현 방식과 탐색 알고리즘을 사용하면 작업의 수가 많아짐에 따라 작업 탐색 오버헤드가 매우 커진다. 이 문제를 해결하기 위하여, 본 논문은 스케줄러가 효율적으로 작업을 탐색할 수 있는 준비 큐 자료구조와 ??O(「log₂n」)의 복잡도를 가지는 작업 탐색 알고리즘을 제안한다. The Stack Resource Policy (SRP) is a real-time synchronization protocol with some distinct properties. One of such properties is early blocking; the execution of a job is delayed instead of being blocked when requesting shared resources. If SRP is used with dynamic priority scheduling such as Earliest Deadline First (EDF), the early blocking requires that a scheduler should select the highest-priority job among the jobs that will not be blocked, incurring runtime overhead. In this paper, we analyze the runtime overhead of EDF scheduling when SRP is used. We find out that the overhead of job search using the conventional implementations of ready queue and job search algorithms becomes serious as the number of jobs increases. To solve this problem, we propose an alternative data structure for the ready queue and an efficient job-search algorithm with ??O(「log₂n」) time complexity.

멀티프로세서 실시간 스케줄링에서 오프라인 동적 전압조절 기법

한상철(Sangchul Han),박민규(Minkyu Park),박문주(Moonju Park) 한국정보과학회 2013 정보과학회논문지 : 시스템 및 이론 Vol.40 No.6

멀티프로세서 실시간 스케줄링에서 동적 전압 조절(DVS, dynamic voltage scaling)에 관한 많은 연구가 있다. 하지만 대부분은 분할스케줄링(partitioned scheduling)에 관한 연구이며, 전역스케줄링 (global scheduling)에 관한 연구는 매우 적다. 본 논문은 전역 실시간 스케줄링 알고리즘인 EDF(k)에 적용하는 오프라인 DVS 기법을 제안한다. 이 기법은 주어진 동일 행속도(uniform speed)에 기반을 두어 태스크의 정적 개별 수행속도(individual speed)를 결정하고, 실제 수행시간이 최악 수행시간보다 적음을 고려하여 이중 수행속도(dual speed)를 결정한다. 실험 결과, 이 기법은 프로세서의 수가 8개일 때 동일 수행속도만 적용하는 경우에 비해 최대 약 23%의 에너지를 절감할 수 있다. There are many research on DVS(dynamic voltage scaling) in multiprocessor real-time scheduling. Most of them, however, can be applied to partitioned scheduling. There are a few research on DVS in global scheduling. This paper proposes an off-line DVS scheme for EDF^(k), which is a global scheduling algorithm for identical multiprocessor systems. This scheme determines static individual speed for each task based on the uniform speed, and then determines dual speed in order to utilize the difference between the actual execution time and the worst case execution time. The experimental results show that the proposed scheme can reduce the energy consumption by up to about 23% compared with the uniform speed technique when the number of processor is 8.

멀티코어 플랫폼에서 에너지 효율적 EDZL 실시간 스케줄링

한상철(Sangchul Han) 한국정보과학회 2016 정보과학회논문지 Vol.43 No.3

시스템 자원과 가용한 전력량이 한정적인 모바일 실시간 시스템은 시간제약의 만족뿐만 아니라 시스템 부하가 높을 때는 시스템 자원을 최대한 활용하고 시스템 부하가 낮을 때는 에너지 소모량을 줄일 수 있어야 한다. 멀티프로세서 실시간 스케줄링 알고리즘인 EDZL(Earliest Deadline until Zero Laxity)은 높은 시스템 이용률을 가지고 있으나 에너지 절감기법에 대한 연구가 매우 적다. 본 논문은 멀티코어 플랫폼에서 EDZL 스케줄링의 동적 전압조절(DVFS) 기법을 다룬다. 본 논문은 full-chip DVFS 플랫폼을 위한 동일속도와 per-core DVFS 플랫폼을 위한 개별속도 산정 기법을 제안한다. EDZL 스케줄 가능성 검사에 기반을 둔 이 기법은 단순하지만 효과적으로 태스크들의 수행속도를 오프라인에 결정할 수 있다. 또한 모의실험을 통하여 제안한 기법이 효과적으로 에너지를 절감할 수 있음을 보인다. Mobile real-time systems with limited system resources and a limited power source need to fully utilize the system resources when the workload is heavy and reduce energy consumption when the workload is light. EDZL (Earliest Deadline until Zero Laxity), a multiprocessor real-time scheduling algorithm, can provide high system utilization, but little work has been done aimed at reducing its energy consumption. This paper tackles the problem of DVFS (Dynamic Voltage/Frequency Scaling) in EDZL scheduling. It proposes a technique to compute a uniform speed on full-chip DVFS platforms and individual speeds of tasks on per-core DVFS platforms. This technique, which is based on the EDZL schedulability test, is a simple but effective one for determining the speeds of tasks offline. We also show through simulation that the proposed technique is useful in reducing energy consumption.

곡관 및 분기관이 존재하는 배관 검사용 이동 로봇 설계

한상철(SangChul Han),이건욱(KunWook Lee),문형필(Hyungpil Moon) 대한기계학회 2011 대한기계학회 춘추학술대회 Vol.2011 No.10

Periodical inspection and monitoring on industrial structure, such as nuclear power plant, petrochemical complex, ships, bridges are very important to secure safety industrial structure. However, most of current inspection methods have been performed in dangerous or limitative a place for human. In this paper, we introduce a pipe inspection climbing robot which consists of adhension mechanism and moving mechanism for climbing at high speed and obstacle avoiding mechanism for overcoming bend-pipe or branch-pipe. We have designed a robot mechanism and performed static equilibrium conditions and dynamic simulation using Recurdyn.

최소 여유시간 알고리즘의 예측성

한상철(Sangchul Han) 한국지능시스템학회 2008 한국지능시스템학회 학술발표 논문집 Vol.18 No.1

실시간 우선순위 스케줄링(priority-driven scheduling)에서 실제 수행시간에 기반하여 스케줄 할 때의 수행 종료 시간이 최대 실행시간에 기반하여 스케줄 할 때의 종료시간보다 빠름이 보장되면, 그 스케줄링 알고리즘을 ‘수행 종료시간 예측가능(predictable)하다’라고 한다. EDF(Earliest Deadline First)[l]와 같은 작업수준 고정 우선순위 (job-level fixed priority) 알고리즘은 수행 종료시간이 예측가능함이 알려져 있다. 본 논문은 작업수준 동적 우선순위(job-level dynamic priority) 알고리즘인 최소 여유시간 알고리즘(Least Laxity Algorithm, LLA)[2,3]이 수행 종료시간 예측가능함을 증명한다.

멀티프로세서 실시간 시스템에서 스케줄 가능성을 향상시킨 변형된 LLF 스케줄링 알고리즘

한정희(Junghee Han),한상철(Sangchul Han) 한국정보과학회 2012 정보과학회논문지 : 시스템 및 이론 Vol.39 No.3

LLF(Least Laxity First) 스케줄링 알고리즘은 작은 여유시간을 가진 태스크가 높은 우선순위를 갖는 동적 우선순위 실시간 스케줄링 알고리즘이다. LLF는 단일프로세서에서 최적임이 알려져 있지만, 멀티프로세서에서는 최적의 아니다. 본 논문은 LLF를 변형한 LazyLLF(Lazy Least Laxity First) 스케줄링 알고리즘을 제시한다. 이 알고리즘은 실시간 태스크의 우선순위를 일시적으로 역전시킴으로써 프로세서의 유휴시간을 줄여 스케줄 가능성을 향상시킨다. 본 논문은 증명을 통해 LazyLLF가 LLF보다 강 우월(strictly dominate)함을 보이고, 모의실험을 통해 LazyLLF와 LLF의 스케줄 성공률을 비교한다. LLF(Least Laxity First) is a dynamic priority scheduling algorithm that gives higher priority to an active job with less laxity. It is known that LLF is optimal on uniprocessor but not on multiprocessor. This paper presents LazyLLF(Lazy Least Laxity First) scheduling algorithm which is a modification of LLF. LazyLLF reduces processor idle time by allowing temporary priority inversion, so that it improves the schedulability of LLF. This paper proves that LazyLLF strictly dominates LLF, and compares the schedulability of LazyLLF and LLF through simulation.

다중처리기 상의 실시간 스케줄링 알고리즘의 우월 관계 및 성능

박민규(Minkyu Park),한상철(Sangchul Han),김희헌(HeeHeon Kim),조성제(Seongje Cho),조유근(Yookun Cho) 한국정보과학회 2005 정보과학회논문지 : 시스템 및 이론 Vol.32 No.7·8

하드웨어 기술이 발전하고 실시간 시스템들의 작업 부하가 커지면서 다중처리기를 실시간 시스템에 사용하는 것이 요구되고 있지만, 단일처리기와는 달리 다중처리기 실시간 스케줄링 문제는 대부분 효율적인 해결 방안이 알려져 있지 않다. 따라서 단일처리기 스케줄링 알고리즘을 다중처리기에 그대로 적용하는 연구와 단일처리기 스케줄링 알고리즘을 변형한 다중처리기 스케줄링 알고리즘에 관한 연구가 활발히 이루어지고 있다. 대표적인 알고리즘으로는 EDF(Earliest Deadline First), LLF(Least Laxity First), EDF-US[m/(2m-1)], EDZL(Earliest Deadline Zero Laxity) 알고리즘 등이 있으며, 이들 간의 비교 연구가 필요하다. 본 논문에서는 스케줄 가능성 측면에서 이 알고리즘들 사이의 우월(dominance) 관계를 밝혔다. EDF, LLF, EDF-US[m/(2m-1)] 간에는 우월 관계가 없으나, EDZL은 EDF보다 우월함을 증명하였다. 또한 모의실험을 통하여 EDZL은 선점을 적게 유발하고 처리기 이용률이 높음을 보였다. Multiprocessor architecture becomes increasingly common on real-time systems as computer hardware technology rapidly progresses and the workload of real-time systems increases. However, efficient solutions for many real-time multiprocessor scheduling problems are not known. Hence many researchers apply uniprocessor scheduling algorithms to multiprocessor scheduling or devise new algorithms based on these algorithms. Such algorithms are EDF (Earliest Deadline First), LLF (Least Laxity First), EDF-US[m/(2m-1)], and EDZL (Earliest Deadline Zero Laxity), and comparative studies on them are necessary. In this paper, we show the dominance relation of these algorithms with respect to schedulability, and we prove EDZL strictly dominates EDF. The simulation results show that EDZL has high processor utilization and it causes a small number of preemptions.

에너지 저장장치용 슈퍼커패시터 이온 도핑 제어를 통한 에너지 밀도 향상 연구

박병준,유선미,양성은,한상철,노태무,이영희,한영희,Park, Byung-jun,Yoo, SeonMi,Yang, SeongEun,Han, SangChul,No, TaeMoo,Lee, Young Hee,Han, YoungHee 한국전력공사 2019 KEPCO Journal on electric power and energy Vol.5 No.3

최근 전력 계통에 사용되는 주파수 조정용(F/R) 에너지 저장장치에 대하여 높은 에너지 밀도와 장수명의 안정성에 대한 요구가 증대되고 있다. 이와 관련하여 슈퍼커패시터는 장수명과 급속 충방전 특성이 우수하므로 이러한 F/R 적용을 위한 에너지 저장장치로 적합하게 여겨지고 있다. 슈퍼커패시터는 단주기 F/R 영역의 보완 운전을 담당하고 전력계통에 설치된 ESS의 장주기 운영 수명을 연장함으로써 기존 용량을 담당하는 리튬 배터리의 설치 규모와 양을 획기적으로 줄일 수 있다. 하지만 낮은 에너지 밀도는 전력 계통과 같은 큰 시스템에서 적용에 한계가 있으며 여전히 배터리를 대체할 수 있는 높은 에너지 밀도 요구에 어려움을 겪고 있다. 그러나 최근에는 리튬이온 커패시터(Lithium ion capacitor; LIC) 구조가 3.8 V 이상의 전압 구간을 구현할 수 있기 때문에 전기이중층 커패시터(Electric double layer capacitor; EDLC) 구조보다 고에너지 밀도 구현을 위한 구조로 각광을 받고 있지만 여전히 상용화를 위해서는 여러가지 전기화학적 성능에 대한 구체적인 검증 및 개발이 필요한 실정이다. 본 연구에서는 LIC의 에너지 밀도와 관계되는 용량을 증대하기 위하여 새로운 전극사전-도핑 방법을 설계하였다. 양극 활물질은 0.1% 이하의 상대습도 분위기 드라이룸에서 기계적 강도와 음극 도핑을 안정되게 수행될 수 있도록 $100{\mu}m$의 두께로 제작되었다. 또한 접촉 저항을 최소화하기 위하여 제조된 전극은 상온에서 $65^{\circ}C$까지 열 압축공정을 실시하였다. 최종적으로 LIC 구조에 대한 다양한 사전-도핑법을 설계하고 그 메커니즘을 분석하여 용량과 전기화학적 안정성이 향상된 새로운 LIC 사전-도핑 방법을 제안하였다. Recently, demand for high energy density and long cycling stability of energy storage system has increased for application using with frequency regulation (F/R) in power grid. Supercapacitor have long lifetime and high charge and discharge rate, it is very adaptable to apply a frequency regulation in power grid. Supercapacitor can complement batteries to reduce the size and installation of batteries. Because their utilization in a system can potentially eliminate the need for short-term frequent replacement as required by batteries, hence, saving the resources invested in the upkeep of the whole system or extension of lifecycle of batteries in the long run of power grid. However, low energy density in supercapacitor is critical weakness to utilization for huge energy storage system of power grid. So, it is still far from being able to replace batteries and struggle in meeting the demand for a high energy density. But, today, LIC (Lithium Ion Capacitor) considered as an attractive structure to improve energy density much more than EDLC (Electric double layer capacitor) because LIC has high voltage range up to 3.8 V. But, many aspects of the electrochemical performance of LIC still need to be examined closely in order to apply for commercial use. In this study, in order to improve the capacitance of LIC related with energy density, we designed new method of pre-doping in anode electrode. The electrode in cathode were fabricated in dry room which has a relative humidity under 0.1% and constant electrode thickness over $100{\mu}m$ was manufactured for stable mechanical strength and anode doping. To minimize of contact resistance, fabricated electrode was conducted hot compression process from room temperature to $65^{\circ}C$. We designed various pre-doping method for LIC structure and analyzing the doping mechanism issues. Finally, we suggest new pre-doping method to improve the capacitance and electrochemical stability for LIC.

청소년이 지각한 사회적 지지가 진로성숙에 미치는 영향에 대한 실패내성의 매개효과

홍국진(Hong, Gukjin),한상철(Han, Sangchul) 한국청소년정책연구원 2014 한국청소년연구 Vol.25 No.3

본 연구는 청소년이 지각한 사회적 지지와 진로성숙도와의 관계에서 실패내성의 매개효과를 검증하는데 목적이 있다. 부모나 또래, 교사에 의한 정서적ㆍ물질적ㆍ평가적 지지가 진로성숙도에 영향을 미칠 것이라는 가정과 더불어, 이 과정에서 청소년들의 실패내성 즉, 실패경험 그 자체를 긍정적으로 지각하고 반응하는 경향성이 진로성숙도에 의미있는 영향을 주며 또한 사회적 지지의 영향력을 매개해 줄 것으로 가정하였다. 이러한 연구목적을 달성하기 위해 D시에 소재한 중학교 2학년 학생 400명을 대상으로 설문조사를 실시하였고, 불성실하게 응답한 12명을 제외한 388명을 최종 자료분석의 대상으로 삼았다. 측정도구는 황윤경(1995)이 수정하여 사용한 ‘사회적 지지 지각척도’, 김아영(1994)이 개발한 ‘실패내성척도’, 이기학(1997)이 개발한 ‘진로성숙도척도’를 사용하였다. 자료분석은 SPSS를 이용한 위계적 회귀분석을 적용하였다. 본 연구의 주요 결과는 다음과 같다. 첫째, 청소년이 지각한 사회적 지지는 진로성숙에 의미 있는 영향을 준다. 둘째, 실패내성은 진로성숙에 의미 있는 영향을 준다. 셋째, 실패내성은 청소년이 지각한 사회적 지지와 진로성숙도와의 관계를 의미있게 매개한다. 즉, 실패내성은 사회적 지지의 영향력을 증가시키는 역할을 하였다. 청소년의 진로성숙도를 향상시키기 위해 사회적 지지가 지속적으로 필요할 뿐만 아니라 학교생활에서 겪는 많은 실패경험들을 긍정적으로 인식하고 대처해 나갈 수 있도록 지도할 필요가 있음을 논의하였다. The aim of the study is to examine the mediating effect of failure-tolerance on the relationship between social support and career maturity, as perceived by adolescents. Our hypothesis was as follows: First, social support, as perceived by adolescents, will have a significant influence on career maturity. Second, failure-tolerance will have a significant influence on career maturity. Third, failure-tolerance will mediate the relationship between social support, as perceived by adolescents and career maturity. The subjects of this study comprised 400 students of the second grade in a middle school in D city. Data analysis was conducted using 388 questionnaires, except for 12 questionnaires which produced unreliable answers, and were then subject to hierarchical regression analysis based on the Baron and Kenny(1986) model. The main results of this research are as follows. First, there is a significant relation between social support, as perceived by adolescents, and career maturity, with more social support, as it is perceived adolescents, having a positive effect on career maturity. Second, failure-tolerance showed a positive role in career maturity. This suggests that failure-tolerance has a positive impact on career maturity. Third, failure-tolerance was revealed to have a positive mediating effect on the relationship between a social support, as perceived by adolescents, and career maturity. The results of this research were discussed based on prior studies and were used to create suggestions and ideas for improving the career education of adolescents.

다중처리기 상의 실시간 스케줄링을 위한 동일 우선순위 처리 정책의 비교

박민규(Minkyu Park),한상철(Sangchul Han),김희헌(Heeheon Kim),조성제(Seongje Cho),조유근(Yookun Cho) 한국정보과학회 2004 한국정보과학회 학술발표논문집 Vol.31 No.1A

단일처리기에서는 우선순위가 동일한 작업들 사이의 수행 순서가 스케줄 가능성에 영향을 미치지 않는다. 그러나 다중처리기에서는 우선순위가 동일한 작업들의 수행 순서를 결정하는 정책에 따라 주어진 태스크 집합의 스케줄 가능성이 달라질 수 있다. 본 논문은 동일 우선순위 처리 정책 간의 관계를 연구하고, 모의실험을 통하여 스케줄 가능한 태스크 집합의 수와 스케줄 보장 이용률, 선점 회수의 측면에서 정책들의 성능을 비교하였다.