Journal of the Korea Institute of Information and Communication Engineering 한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 19, No. 9 : 2213~2221 Sep. 2015 온디맨드거버너정책에따른작업스케줄링기법의성능평가 탁성우 * Performance Evaluation of Job Scheduling Techniques Incorporating the Ondemand Governor Policy Sungwoo Tak * Department of Computer Science and Engineering, Pusan National University, Pusan 609-735, Korea 요약 안드로이드기반스마트폰플랫폼에서사용하는온디맨드거버너 (Ondemand Governor) 는 CPU 사용률 (Utilization) 에따라 CPU 동작주파수를조절한다. CPU 사용률의변화량은작업스케줄링에의해영향을받으며, CPU 동작주파수증감에따라스마트폰의전력소비량도증감한다. 따라서작업스케줄링방식에따라변하는 CPU 사용률및동작주파수는스마트폰의전력소비에영향을미친다. 이에온디맨드거버너정책을작업스케줄링기법에적용시켜 CPU 사용률및전력소비, 그리고작업마감시한측면에서비교분석하였다. ABSTRACT The ondemand governor used in android-based smartphone platforms is a CPU frequency scaling technique. The ondemand governor sets the CPU operating frequency depending on the CPU utilization rate. Job scheduling affects the CPU utilization rate. The power consumption is proportional to the value of operating frequency. Consequently, CPU frequency scaling and CPU utilization rate have an effect on power consumption in a smartphone. In this paper, we evaluated the performance of job scheduling techniques incorporating the ondemand governor in terms of CPU utilization, power consumption, and job deadline miss ratio. 키워드 : 온디맨드거버너, 안드로이드, 스마트폰, 전력소비, 작업스케줄링 Key word : Ondemand governor, Android, Smartphone, Power consumption, Job scheduling Received 19 May 2015, Revised 26 June 2015, Accepted 10 July 2015 * Corresponding Author Sungwoo Tak(E-mail:swtak@pusan.ac.kr, Tel:+82-51-510-2387) Department of Computer Science and Engineering, Pusan National University, Pusan 609-735, Korea Open Access http://dx.doi.org/10.6109/jkiice.2015.19.9.2213 print ISSN: 2234-4772 online ISSN: 2288-4165 This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License(http://creativecommons.org/li-censes/ by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited. Copyright C The Korea Institute of Information and Communication Engineering.
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 19, No. 9 : 2213~2221 Sep. 2015 Ⅰ. 서론본논문에서는제한된배터리자원을사용하는안드로이드기반스마트폰플랫폼에서온디맨드거버너를적용시킨작업스케줄링의성능을비교분석하였다. 온디맨드거버너는리눅스기반다양한시스템플랫폼에서사용되고있다 [1]. 온디맨드거버너는주기적으로관찰한 CPU 사용률 (Utilization) 을사용하여 CPU 동작주파수를조절한다. CMOS 기반 CPU 구동전압은 CPU 동작주파수값에비례하며, CPU 소비전류량은 CPU 구동전압에비례한다 [2,3]. 온디맨드거버너는 CPU 사용률이임계점이하가될때, CPU 동작주파수를 20% 씩선형으로감소시킨다. 그리고동작주파수의감소는전류소비량을감소시켜스마트폰의전력소비를감소시킨다. 온디맨드거버너외에보존형 (Conservative), 파워세이브 (Powersave), 그리고퍼포먼스 (Performance) 거버너가기본적으로제공하고있다 [4,5]. 참고문헌 [6] 에서는, 온디맨드거버너정책을사용하는스마트폰이 CPU 동작주파수에비례하여전력을소비하였다. 참고문헌 [7] 과 [8] 에서는 CPU 사용률증가에따라 CPU 소비전류량도선형으로증가함을보여주었다. 그러나참고문헌 [6] 부터참고문헌 [8] 까지수행한온디맨드거버너정책의성능평가는단순히 CPU 사용률에따른전력소비량의분석이었다. CPU 사용률의변화량은작업스케줄링에의해영향을받는다. CPU 스케줄링방식은작업보존형 (Work Conserving) 및비작업보존형 (Non-Work Conserving) 스케줄링, 실시간 (Real-time) 및비실시간 (None-realtime) 스케줄링, 그리고선점형 (Preemptive) 및비선점형 (Non-Preemptive) 으로구분된다 [9]. 작업보존형방식은처리해야할작업이있는경우, 유휴시간없이해당작업을바로처리한다. 비작업보존형방식은처리해야할작업을바로처리하지않고, 일정시간동안유휴시간을가진후작업을처리한다. 비실시간스케줄링과달리, 실시간스케줄링방식은작업의실시간속성을보장한다. 비선점형스케줄링과달리, 선점형스케줄링방식에서는최상위우선순위를가진작업이 CPU 사용권한을항상먼저선점한다. 그림 1은온디맨드거버너성능평가과정을보여준다. 성능평가과정의주요 4개구성인자는 (1) 작업속 성, (2) 작업스케줄링, (3) 스마트폰 CPU 속성, 그리고 (4) 온디맨드거버너정책이다. 작업은실행요청시각, 실행주기, 최악실행시간, 그리고마감시한속성을가진다. Performance evaluation of job scheduling according to the ondemand governor policy (1) Job properties Release time Period Worst-case execution time Deadline Android-based smart phone platform Job arriaval Job selection (3) CPU properties Operating frequency scaling Power consumption reduction by lowering the CPU operating frequency (2) Job scheduling Different job execution sequences by different job scheduling policies Job: Different CPU busy time and idle time variations Job scheduling policy: non-job conserving / job conserving / real-time / non-real-time / preemptive / non-preemptive scheduling (4) Ondemand governor policy CPU frequency calculation CPU busy time and idle time by CPU utilization occurrence Operating frequency calculation 그림 1. 작업스케줄링의성능평가과정 Fig. 1 Operation procedures for job scheduling performance evaluation 작업속성 ( 그림 1-(1)) 은성능평가에사용되는작업들의속성값이다. 작업은스케줄링 ( 그림 1-(2)) 을통해실행순서가결정되며, CPU ( 그림 1-(3)) 에서실행된다. 그리고 CPU 사용률변화량에따라온디맨드거버너정책 ( 그림 1-(4)) 이적용되어 CPU 동작주파수를조절한다. 본논문의구성은다음과같다. II장에서는온디맨드거버너정책과작업스케줄링간의상관관계를분석하였다. III장에서는온디맨드거버너정책을적용한작업스케줄링의시뮬레이션및성능평가를수행하였다. 마지막으로 IV장에서는결론을기술하였다. Ⅱ. 온디맨드거버너정책과작업스케줄링기법 온디맨드거버너정책의동작과정은표 1과같다. 본논문에서는 1GHz Qualcomm QSD8250 Snapdragon ARM 프로세서가장착된구글넥서스원 (Nexus One) 2214
온디맨드거버너정책에따른작업스케줄링기법의성능평가 스마트폰을사용하였다. 그리고슈퍼유저권한으로시스템파일에접근하기위하여루팅을하였다. 온디맨드거버너는샘플링주기마다 CPU 사용률을계산하여 CPU 동작주파수를증가혹은감소시킨다 ( 표 1의 ondemand() 함수동작과정 ). 표 1에서기술한변수들은안드로이드커널디렉터리 /sys/devices/ system/cpu/ cpux/cpufreq/ondemand/ 에시스템파일형태로존재한다. 표 1. 온디맨드거버너정책의동작과정 Table. 1 Operation procedures of the ondemand governor policy 1. Initialization 1.1 cpu_info_transition_latency = 40ms; 1.2 cpuinfo_min_freq = 100MHz; 1.3 cpuinfo_max_freq = 1GHz; 1.4 up_threshold = 80; down_threshold = 20; 1.5 sampling_rate_min = 10ms; 2. set_sampling_rate() { 2.1 sampling_rate = cpu_info_transition_latency; 3. ondemand() { 3.1 CPUfreq = cpuinfo_max_freq; while(1) { 3.2 sampling_rate = max(sampling_rate, sampling_rate_min) ; 3.3 every sampling_rate: 3.4 calculate CPU utilization since the last check 3.5 if (CPU utilization > up_threshold) CPUfreq = cpuinfo_max_freq; 3.6 else if (CPU utilization < down_threshold) CPUfreq = max(cpuinfo_min_freq, CPUfreq * 0.2); 샘플링주기는시스템파일 cpu_info_transition_ latency에저장된 40ms로설정하였다 ( 표 1의동작과정 1.1). cpu_info_transition_latency는 CPU가동작주파수를변경하는데걸리는지연시간이다 [10]. 샘플링주기의최소한계값 (sampling_rate_min) 은 10ms로설정하였다 ( 표 1의동작과정 1.5). 샘플링주기 sampling _rate의최소한계값은 sampling_rate_min으로설정된다 ( 표 1의동작과정 3.2). 온디맨드거버너의동작과정은다음과같다. 온디맨드거버너는초기 CPU 동작주파수를최고주파수 (cpuinfo_max_freq) 로설정한다 ( 표 1의동작과정 3.1). 샘플링주기마다 CPU 사용률이 상위임계치 (up_threshold) 혹은하위임계치 (down_ threshold) 범위에있는지확인한다 ( 표 1의동작과정 3.5와 3.6). 상위임계값은 CPU 사용률 80% 로설정하였다 ( 표 1의동작과정 1.4). 샘플링주기동안 CPU 사용률이 80% 이상이면, CPU 동작주파수는최대주파수값으로설정된다 ( 표 1의동작과정 3.5). 하위임계값은 CPU 사용률 20% 로설정하였다 ( 표 1의동작과정 1.4). 샘플링주기동안 CPU 사용률이 20% 이하이면, CPU 동작주파수를 20% 씩감소시킨다 ( 표 1의동작과정 3.6). 최소 CPU 동작주파수 (cpuinfo_min_freq) 값은 100MHz로설정하였다 ( 표 1의동작과정 1.2). 지금까지살펴본온디맨드거버너의핵심동작방식은 CPU 사용률에따라동작주파수를조절하는것이다. CPU 사용률의변화량은작업스케줄링방식에의해영향을받는다. 성능분석에적용한기본스케줄링방식은 FCFS (First Come First Service) 기반비실시간스케줄링과 EDF(Earliest Deadline First) 기반실시간스케줄링기법이며, 이를다음과같이변형시켰다. 첫째, EDF는기본적으로선점형 (Preemptive) 스케줄링방식이며, P_EDF (Preemptive EDF) 로표현한다. P_EDF에대한변형으로비선점형 (Non-Preemptive) EDF 스케줄링방식을구현하였으며, NP_EDF (Non Preemptive EDF) 로표현한다. NP_EDF 스케줄링은마감시한이가장이른작업의실행이완료되면, 대기중인작업들중에서마감시한이가장이른작업을실행할수있다. 한편, FCFS는실행요청된순서대로작업을처리하는비선점형스케줄링방식이며, NP_FCFS (Non Preemptive FCFS) 로표현한다. 둘째, 작업실행시간이짧은작업을먼저실행하는 JFS (Job First with Shortest Execution Time) 정책을적용시켜변형된 FCFS 및 EDF 스케줄링을구현하였다. JFS 정책을통해작업들의평균응답시간을빠르게하고실행대기중인작업들의마감시한초과율도부가적으로감소시킬수있다. 변형된스케줄링방식은 NP_FCFS_JFS, P_EDF_JFS, NP_ EDF_JFS 스케줄링이다. 셋째, 비작업보존형스케줄링인작업그룹기반스케줄링 (Job Group based Scheduling) 방식을제안하였다. 첫째와둘째에서기술한스케줄링방식들은작업보존형스케줄링방식이다. 구현한작업그룹기반스케줄링방식은 JG_NP_FCFS, JG_P_EDF, JG_NP_EDF, 2215
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 19, No. 9 : 2213~2221 Sep. 2015 JG_NP_ FCFS_JFS, JG_P_EDF_JFS, 그리고 JG_NP_ EDF_JFS이다. 작업그룹기반스케줄링에서는작업그룹상수 JGC (Job Group Constant) 값을사용하여작업그룹을형성한다. 그룹을형성할때, CPU 실행유휴시간을그룹내에존재하도록한다. 그리고온디맨드거버너정책이실행유휴시간동안동작주파수를감소시켜스마트폰의전력소비를감소시킨다. 표 2는구현된 6개의작업그룹기반스케줄링방식에서 JG_NP _EDF 스케줄링의동작과정을보여준다. 표 2. JG_NP_EDF 스케줄링방식의동작과정 Table. 2 Operation procedures of the JG_NP_EDF scheduling scheme 1. Insert_Job(): /* Insert a job Job i at queue Job_Ready_Q according to a sequence of ordered deadlines */ 1.1 Job_Ready_Q Job i, where Job(AD) 1 Job(AD) 2 Job(AD) i... Job(AD) n in such a way that the resulting sequence of size n + 1 is also ordered 2. Select_Job(): 2.1 if (Job_Ready_Q = ) { Select Job k, where Job k Job_Ready_Q and Job(AD) k MinJob(AD) JGC; 2.2 Job_Ready_Q Job_Ready_Q Job k; 2.3 Run Job k; 5ms인경우, 작업그룹의마감시한은 25ms가된다. 마감시한이 25ms 내에있는작업들은이작업그룹에포함된다. 나머지작업그룹스케줄링방식은스케줄링방식에따라표 2의 1.1 과정만다르며, 나머지과정은서로유사하다. Job1 Job3 Job arrival sequences 0 5 10 15 20 25 Job1 Job1 Job3 Job1 Job(RD)1 = 16 Job(RD)2 = 8 Job(RD)3 = 4 NP_FCFS Jo Job3 Job1 Job1 Job1 P_EDF b2 Job3 Job1 Job1 NP_EDF Job3 Job1 Job1 NP_FCFS_JFS Jo Job3 Job1 Job1 Job1 P_EDF_JFS b2 NP_EDF_JFS Job3 Job1 Job1 Job1 Job3 IDLE Job1 JG_NP_FCFS time JG_NP_EDF 스케줄링에서는작업그룹상수 JGC 값을사용하여작업그룹을형성한다. 작업 Job i 의절대적마감시한 Job(AD) i 는작업의실행요청시간 Job(R) i 와상대적마감시한 Job(RD) i 의합이다. i는작업식별자이다. Insert_Job() 함수에서는절대적마감시한이가장이른작업순서대로작업준비큐 Job_Ready_Q에저장한다 ( 표 2의동작과정 1.1). Job_Ready_Q에저장되어있는작업을선출하는 Select_Job() 함수의동작과정은다음과같다. 작업그룹상수 JGC 값과작업준비큐에서마감시한이가장이른작업의시한 Job(AD) 1 값을 MinJob(AD) 로설정한후, 작업그룹을형성한다 ( 표 2의동작과정 2.1). 작업 Job k 의 Job(AD) k 와 Job(AD) 1 간의차이가작업그룹상수 JGC 값보다작은경우, Job(AD) 1 이속한작업그룹에포함된다. 해당작업그룹의마감시한은 Job(AD) 1 과 JGC 값의합으로구성된다. 예를들어, JGC 값이 20ms이고 Job(AD) 1 이 Jo Job3 Job1 Job1 IDLE Job1 JG_P_EDF b2 Job3 Job1 IDLE Job1 JG_NP_EDF Job3 Job1 IDLE Job1 JG_NP_FCFS_JFS Jo Job3 Job1 Job1 IDLE Job1 JG_P_EDF_JFS b2 Job3 Job1 IDLE Job1 JG_NP_EDF_JFS 그림 2. 스케줄링방식별작업실행동작과정 Fig. 2 Job execution traces according to scheduling schemes 그림 2는표 3에서기술한 3개의작업이작업스케줄링들에의해처리되는동작과정을보여준다. 표 3에서 Job(P) i 는작업 Job i 의주기를나타내며, 2216
온디맨드거버너정책에따른작업스케줄링기법의성능평가 Job(E) i 는작업 Job i 의실행시간을나타낸다. Job(R) i 와 Job(RD) i 는작업요청시간과상대적마감시한을나타낸다. 작업 FCFS 스케줄링인경우, 동시에도착한작업들이있을때작은작업식별자 i를가진작업이먼저실행된다. 예를들어, NP_FCFS에서는시각 0일때, 동시에요청된작업 Job 1 과 Job 2 중에서 Job 1 을먼저실행시킨다. 실행시간이짧은작업을우선적으로먼저실행시키는NP_FCFS_JFS인경`우, 시각 0에서요청된작업 Job 1 과 Job 2 중에서실행시간이짧은 Job 2 가먼저실행된다. 시각 3에서 Job 2 가실행완료된후, Job 1 과 Job 3 중에서실행시간이짧은 Job 3 를실행한다. 표 3. 태스크집합 Table. 3 A set of tasks Job i Job(R) i Job(P) i Job(RD) i Job(E) i Job 1 0 16 16 5 Periodic Job 2 0 None 8 3 Aperiodic Job 3 2 None 4 2 Aperiodic 비선점형작업그룹기반 JG_NP_EDF 스케줄링의동작과정을살펴보면다음과같다. 작업그룹상수 JGC 값은 10으로설정하였다. 시각 0일때, 작업준비큐에서마감시한이가장이른작업의마감시한 MinJob (AD) 1 값은 Job 2 의마감시한 8 (= Job(AD) 2 ) 로설정되며, 이값을기반으로하여작업그룹이형성된다. 그리고마감시한이가장이른 Job 2 가먼저실행된다. 비선점형스케줄링정책에의해 Job 3 는 Job 2 가실행완료될때까지기다린다. 시각 3에서 Job 2 가실행완료된후, 실행대기중인 Job 1 과 Job 3 중에서실행시간이짧은 Job 3 이먼저실행권한을획득한다. 표 2의동작과정 2.1을사용하여 Job 3 이 Job 2 가속한작업그룹에포함되는지를확인하는과정은다음과같다. 표 2의동작과정 2.1에서 Job(AD) k 는 Job(AD) 3 값인 6 (= Job(R) 3 + Job(RD) 3 = 2 + 4) 으로설정된다. MinJob(AD) 에는 Job(AD) 2 값인 8 (= Job(R) 2 + Job(RD) 2 = 0 + 8) 이삽입된다. 따라서 Job(AD) 3 (= 6) MinJob(AD) (= 8) JGC (= 10) 이만족되어 Job 3 은 Job 2 가속한작업그룹에포함되어실행된다. 시각 10에서실행된 Job 2 의실행이완료된후, 시각 13에서다시실행요청된 Job 2 가작업그룹에포함되기위해서는표 2의동작과정 2.1을만족해야한다. Job(AD) 2 (= Job(R) 2 + Job(RD) 2 = 13 + 8 = 21) MinJob(AD) (= 8) JGC (= 10) 이만족되지않기에시각 13에서 Job 2 는다음작업그룹에포함된다. 그리고시각 13부터시각 18 까지는실행유휴시간으로설정된다. 이외에다른작업그룹기반스케줄링도이와유사하게실행된다. 지금까지살펴본작업그룹스케줄링기법의이론적인성능분석은다음과같다. min (1) 수식 (1) 은시각 T까지생성된 K 개의작업그룹에서발생된실행유휴시간의평균값을나타낸다. k는그룹식별자를나타낸다. Job(E) k,i 는 k 번째그룹에속한작업 Job i 의실행시간을나타낸다. MinJob(AD) k,1 은 k 번째그룹에속한가장이른작업의마감시한값을나타낸다. 수식 (2) 는 k 번째그룹의실행유휴시간을나타낸다. k 번째그룹은해당그룹에서마감시한이가장이른작업의 MinJob(AD) k,1 값과작업그룹상수 JGC 값을기반으로하여형성된다. 작업 Job m+1 의절대마감시한 Job(AD) m+1 이 MinJob(AD) k,1 과 JGC 값의합보다큰경우, Job m+1 의실행을지연시키고다음작업그룹에포함시킨다. 이러한과정을통해작업그룹 k는 Idle만큼의실행유휴시간이발생한다. 수식 (1) 에서시각 T 동안작업그룹상수 JGC값이증가하는경우, 형성되는작업그룹의개수 K는감소한다. 그리고 K 값의감소로인해평균실행유휴시간 Idle average 값은증가한다. 여기에서작업그룹상수 JGC 와작업그룹의개수 K는반비례관계임을알수있다. 그러나 JGC 값을계속증가시키더라도실행유휴시간 Idle average 값이무한히계속증가하지않는다. 이러한현상이발생되는이유는다음과같다. JGC 값을계속증가시키면작업그룹 k 내에포함되는작업의수가증가 (2) 2217
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 19, No. 9 : 2213~2221 Sep. 2015 한다. 즉, 작업그룹 k에추가된마지막작업 Job m 의실행요청시간 Job(R) k,m 과 Job(E) k,m 의값이증가하여수식 (2) 의실행유휴시간 Idle 값은감소한다. 실행유휴시간은온디맨드거버너정책을적용한스마트폰의전력소비량감소에영향을미친다. 그리고실행유휴시간및작업그룹의형성은수식 (1) 과수식 (2) 에서기술한 JGC 값에영향을받는다. 이에주어진작업집합에대하여최대실행유휴시간을생성하면서작업마감시한초과율을최소화하는 JGC 값을적용하면, 스마트폰의전력소비량감소및실시간서비스의품질을보장할수있다. Ⅲ. 성능분석먼저, 성능분석에사용되는작업집합을무작위로생성하는랜덤작업생성알고리즘을기술하였다. 작업생성알고리즘은표 4와같다. CPU 사용률은개별작업마감시한분의작업실행시간들의합으로계산하였다. 총 N개의작업을고려하는경우, 로표현된다. 작업생성알고리즘의입력은작업사용률 TU이며출력은입력된작업사용률을생성하는작업집합이다. 작업생성알고리즘에서사용하는변수는다음과같다. i는작업식별자이다. 1부터최대 N개까지의작업을생성할수있다. 표 4에서기술한작업생성알고리즘의실행순서는다음과같다. 먼저, 작업의실행시간을랜덤하게생성한다 ( 표 4의동작과정 1.1). MinE는생성되는작업실행시간의최소값이다. MaxE는생성되는작업실행시간의최대값이다. RandGen(MinE, MaxE) 함수는 MinE 부터 MaxE 내에서랜덤값을생성한다. RandGen() 함수는표 4의동작과정 2에서기술하였다. 표 4의동작과정 1.2 부터 1.6까지는작업 Job i 에대한사용률 Job(U) i, 주기 Job(P) i, 상대적마감시한 Job(RD) i 를생성하는과정이다. 표 4의동작과정 1.2 에서는작업 Job i 를제외하고 i보다큰식별자값을가지는작업들의사용률합을랜덤하게생성한다. 생성된사용률은 NextTU에저장된다. TU는작업 Job i 를포함하고 i보다큰식별자값을가지는작업들의사용률합이다. 표 4의동작과정 1.3에서는작업 Job i 의사용률 Job(U) i 를계산한다. TU와 NextTU간의차이값이 Job(U) i 가된다. NextTU가 ε에근접하면, 더이상할당가능한작업사용률이없기때문에작업생성알고리즘은실행을중지한다 ( 표 4의동작과정 1.4). ε은 0에가까운양의실수값이며, 본논문에서는 0.0001로설정하였다. 표 4의동작과정 1.5에서는동작과정 1.1에서생성된작업실행시간 Job(E) i 와동작과정 1.3에서생성한작업사용률 Job(U) i 를곱하여작업의상대적마감시한 Job(RD) i 을생성한다. 표 4. 작업생성알고리즘 Table. 4 Job generation algorithm i 1; N, MinE, MaxE Constants given by a user; TU Input value given by a user; 1. while (True) { 1.1 Job(E) i RandGen(MinE, MaxE); 1.2 NextTU TU RandGen(0, 1) 1/(N-1-i) ; 1.3 Job(U) i TU - NextTU; 1.4 if (NextTU < ε) return sucess; else if (NextTU < 0) return failure; 1.5 Job(RD) i Job(E) i Job(U) i; 1.6 Job(P) i Job(RD) i; 1.7 TU NextTU; 1.8 i i + 1; 2. RandGen(MinE, MaxE): 2.1 rand a random number between 0 and 1; 2.2 return (MinE + rand * MaxE); 성능평가에사용되는구글넥서스원 (Nexus One) 스마트폰은 1GHz Qualcomm QSD8250 Snapdragon ARM 프로세서를사용한다. 이프로세서의동작전류량은 CPU 동작주파수에따라변하며, 최대 1GHz에서 240mA/sec, 245MHz에서 70mA/sec, 그리고 19.2MHz 에서 25.62mA/sec만큼의동작전류량을소비한다. 동작주파수는 19.2MHz 단위로감소하거나증가하며, 동작주파수에따른전류소비량은선형으로변한다 [6,7]. 성능평가요소로는전류소비량과작업의마감시한초과율, 그리고실행유휴시간을사용하였다. 표 4에서제시한알고리즘을사용하여개별사용률 0.1부터 0.9 까지 0.1 단위로각각 10개의작업집합을생성한후, 시뮬레이션을실행하였다. 시뮬레이션시간은 1시간으로설정하였다. 2218
온디맨드거버너정책에따른작업스케줄링기법의성능평가 보는바와같이, 실행시간이짧은작업을우선적으로실행하는 NP_FCFS_JFS 스케줄링의마감시한초과율이 NP_FCFS 스케줄링보다낮음을확인하였다. 그림 3. 평균전류소비량 Fig. 3 Average current consumption 그림 3은작업보존형스케줄링방식인 NP_FCFS, NP_FCFS_JFS, P_EDF, P_EDF_JFS, 그리고 NP_EDF_ JFS의평균전류소비량을보여준다. 작업보존형스케줄링은처리해야할작업이있으면작업을계속처리해야하므로, 작업보존형스케줄링의종류와상관없이개별작업집합의평균전류소비량은동일하였다. 그리고사용률증가에따라평균전류소비량도선형으로증가하였다. 온디맨드거버너정책은주기적으로 CPU 사용률을샘플링하여동작주파수를선형으로조절하기때문에동작주파수에따른전류소비량도선형으로변한다. 그림 4. NP_FCFS 방식의마감시한초과율 Fig. 4 Deadline miss ratio by NP_FCFS schemes 그림 4에서는실행시간이짧은작업을우선적으로처리하는 JFS 방식의마감시한초과율성능을비교하였다. 마감시한을고려하는 EDF 방식은 JFS 방식에영향을받지않는다. 따라서그림 4에서는작업보존형스케줄링방식인비선점형 NP_FCFS 스케줄링방식의평균및최악마감시한초과율만을보여준다. 그림 7에서 그림 5. 평균소비전류차이와마감시한초과율 Fig. 5 Average deadline miss ratio 그림 5는비작업보존형스케줄링방식이작업보존형스케줄링방식에비해감소된평균전류소비량과증가된마감시한초과율을보여준다. 전체적으로비작업보존형스케줄링방식이작업보존형스케줄링방식보다낮은전류량을소비한다. 그리고마감시한초과율측면에서도비보존형작업스케줄링방식은 FCFS 방식을제외하고, 작업보존형스케줄링방식과매우유사한성능을보여주었다. 그림 6과그림 7은비선점형과비작업보존형을동시에고려한스케줄링기법에서성능이가장우수한 JG_NP_EDF_ JFS 스케줄링방식의세부성능을보여준다. 성능분석에사용한사용률은 0.4와 0.7이며, 작업그룹상수값에따라변하는평균소비전류및마감시한이다. 작업그룹상수 25까지는작업그룹상수값이증가하면, 실행유휴시간이증가하여전류소비량이감소하는경향을보여준다. 그러나실행유휴시간의증가로인해작업의마감시한초과율도증가하는경향을보여준다. II장의식 (2) 에서기술한바와같이, 작업그룹상수가증가하는경우, 작업그룹내에포함되는작업의수가증가하여실행유휴시간이감소하여전류소비량은증가한다. 그리고작업보존형스케줄링방식의소비전류량및마감시한초과율에수렴한다. 또한작업그룹상수가증가하는경우, 작업그룹내에포함되는작업의수가증가하기때문에해당작업들의마감시한초과율은감소한다. 2219
한국정보통신학회논문지 (J. Korea Inst. Inf. Commun. Eng.) Vol. 19, No. 9 : 2213~2221 Sep. 2015 그림 6. 평균소비전류와마감시한초과율 ( 사용률 : 0.4) Fig. 6 Average current consumption and deadline miss ratio (Utilization: 0.4) 그림 7. 평균소비전류와마감시한초과율 ( 사용률 : 0.7) Fig. 7 Average current consumption and deadline miss ratio (Utilization: 0.7) TCP 서버를운영하며, 스마트폰과와이파이를통해 400K바이트메시지를 분동안계속해서송수신한다. 각각의메시지는마감시한을가지며각각의메시지는스케줄링에서처리해야할작업으로대응된다. 작업그룹상수값은마감시한초과율이가장낮고전류소비가가장작은작업그룹상수값을 JG_NP_EDF_JFS에사용하였다. 비작업보존형스케줄링방식 JG_NP_ EDF_JFS에서는실행유휴시간동안와이파이네트워크인터페이스가수면모드로전환되어전력소비를감소시킬수있으며, CPU 동작주파수도온디맨드거버너정책에의해감소되기때문에전체전력소비를감소시킬수있었다. 작업스케줄링기법의성능분석결과를정리하면다음과같다. 온디맨드거버너의핵심동작방식은샘플링주기동안발생한 CPU 사용시간을측정한다. 측정된 CPU 사용시간을샘플링주기로나누어계산된 CPU 사용률 (Utilization) 에따라동작주파수를조절하는것이다. CPU 사용시간과 CPU 유휴시간을포함한 CPU 사용률의변화량은작업스케줄링에의해영향을받는다. 즉온디맨드방식과작업스케줄링간의밀접한연관이있음을확인하였다. 그리고 CPU 사용률과동작주파수변화는스마트폰의전력소비량변화에영향을미치는것을확인하였다. 제안한비작업보존형스케줄링인작업그룹기반스케줄링 (Job Group based Scheduling) 방식이온디맨드거버너정책을사용하는경우전력소비와작업마감시한보장측면에서우수한성능을보여주었다. Ⅳ. 결론 그림 8. 스마트폰의전력소비량 Fig. 8 Current consumption of the smart phone 안드로이드기반앱환경에서는선점형스케줄링을적용하지못한다. 이에비선점형에서성능이가장우수한 JG_NP_EDF_JFS 및 NP _EDF_JFS 스케줄링을스마트폰에적용하였다. 그림 8은이러한환경에서소비된전류량을보여준다. 스마트폰에장착된배터리용량은 1400mAh이다. 사용한실험환경은리눅스환경에 온디맨드거버너정책을사용하는안드로이드기반스마트플랫폼에서는실행유휴시간이스마트폰의전력소비를감소시킬수있는중요한성능인자이다. 이에본논문에서는작업들간에실행유휴시간을생성하는비작업보존형스케줄링기법을제안하여작업보존형스케줄링기법과성능을비교분석하였다. 성능분석을수행한결과, 비작업보존형스케줄링방식이전력소비및마감시한측면에서우수한성능을제공하였다. 2220
온디맨드거버너정책에따른작업스케줄링기법의성능평가 ACKNOWLEDGMENTS This work was supported by a 2-Year Research Grant of Pusan National University REFERENCES [ 1 ] V. Pallipadi and A. Starikovskiy, The Ondemand Governor, in Proceedings of Linux Symposium, Ottawa, Canada, pp. 223-228, 2006. [ 2 ] P. Pillai and K.G. Shin, Real-Time dynamic voltage scaling for low-power embedded operating systems, in Proceedings of ACM symposium on Operating Systems Principles, pp. 89-102, 2001. [ 3 ] S. Tak, Performance evaluation of real-time power-aware scheduling techniques incorporating idle time distribution policies, Journal of the Korea Institute of Information and Communication Engineering, vol. 18, no. 7, pp. 1704-1712. [ 4 ] M. Kim, Y. Kim, S. Chung, and C. Kim, Measuring variance between smartphone energy consumption and battery life, IEEE Computer Magazine, vol. 47, no. 7, pp.59-65, 2014. [ 5 ] D. Brodowski and N. Golde, Linux CPUFreq Governors [Internet]. Available: www.kernel.org/doc/documentation/ cpu-freq/governors.txt. [ 6 ] M.J. Johnson, and K.A. Hawick, Optimizing energy management of mobile computing devices, in Proceedings of International Conference on Computer Design, Las Vegas, USA, pp. 1-7, 2012. [ 7 ] R. Murmuria, J. Medsger, A. Stavrou, and J.M.Voas, Mobile application and device power usage measurements, in Proceedings of International Conference on Software Security and Reliability, Gaithersburg:USA, pp. 147-156, 2012. [ 8 ] K. Nagata, S. Yamaguchi, and H. Ogawa, A Power Saving Method with Consideration of Performance in Android Terminals, in Proceedings of International Conference on Autonomic & Trusted Computing, Fukuoka:Japan, pp. 578-585, 2012. [ 9 ] F. Cottet, J. Delacroix, C. Kaiser, and Z. Mammeri, Scheduling in Real-Time Systems, Wiley, 2002. [10] A. Mazouz, A. Laurent, B. Pradelle, and W. Jalby, Evaluation of CPU frequency transition latency, Computer Science - Research and Development, vol. 29, no. 3-4, pp. 187-195, Aug. 2014. 탁성우 (Sungwoo Tak) 2003 년 2 월미국미주리주립대학교 Computer Science 박사 2004 년 ~ 현재부산대학교정보컴퓨터공학부교수 ( 부산대컴퓨터및정보통신연구소, 스마트제어센터겸임연구원 ) 관심분야 : 유무선네트워크, 위치인식 2221