개요
오늘은 안드로이드에서 사용되는 스케줄링 알고리즘(scheduling Algorithm)에 대해서 알아보도록 하겠습니다.
안드로이드는 Linux Kernal 부터 시스템 앱까지 다양한 소프트웨어가 결합된 하나의 거대한 플랫폼 입니다.
안드로이드의 플랫폼 구조, 즉 플랫폼 아키텍처는 아래의 그림과 같습니다.
안드로이드 개발자 사이트의 설명을 인용하자면,
안드로이드란 "Android는 다양한 기기와 폼 팩터에 사용할 수 있도록 제작된 Linux 기반의 오픈소스 소프트웨어 스택" 이라고 설명할 수 있습니다.
따라서, 이러한 안드로이드 플랫폼에서도 다른 운영체제, 예를 들면 Window나 Mac처럼
컴퓨터에서 동작할 다양한 프로그램들 즉 '프로세스'의 관리를 위한 '스케줄링 알고리즘'이 적용됩니다.
스케줄링 알고리즘에 대한 자세한 설명은 아래의 포스팅을 참조하시면 좋을 것 같습니다.
[운영체제] 선점 스케줄링(Preemptive)과 비선점 스케줄링(Nonpreemptive) 기법
개요 오늘은 지난 포스팅에 이어서 실제로 운영체제가 프로세스에게 컴퓨터 자원을 효율적으로 분배하는 전략, 즉 스케줄링 기법에 대해서 알아보도록 하겠습니다. 선점 스케줄링(Preemptive)과
1-hee.tistory.com
안드로이드의 스케줄링 알고리즘
그렇다면 안드로이드는 어떤 스케줄링 알고리즘을 사용할까요?
안드로이드의 플랫폼 아키텍처를 살펴 보시면 안드로이드는 리눅스 커널을 사용하고 있습니다.
따라서, 안드로이드 플랫폼에서 앱이라는 프로그램의 스케줄링을 하기 위해서 사용하는 스케줄링 알고리즘은
리눅스 커널에서 기본적으로 채택하는 스케줄링 알고리즘이
CFS(Completely Fair Scheduler)이기 때문에 CFS로 관리되고 있습니다.
CFS에 대한 자세한 설명은 아래의 문서를 참조해주세요.
https://en.wikipedia.org/wiki/Completely_Fair_Scheduler
Completely Fair Scheduler - Wikipedia
From Wikipedia, the free encyclopedia Linux process scheduler Location of the "Completely Fair Scheduler" (a process scheduler) in a simplified structure of the Linux kernel. The Completely Fair Scheduler (CFS) is a process scheduler that was merged into t
en.wikipedia.org
선점 스케줄링(Preemptive)과 비선점 스케줄링(Nonpreemptive)의 차이
안드로이드에서 사용하는 CFS 알고리즘을 살펴보기 전,
선점 스케줄링(Preemptive)과 비선점 스케줄링(Nonpreemptive)의 차이에 대해서 알아보도록 하겠습니다.
운영체제는, 한정된 컴퓨터 자원을 최대한 공정하고 빠르게 관리하여
결과적으로 모든 프로그램들이 한정적인 자원을 함께 사용할 수 있도록 설계됩니다.
운영체제가 효율적으로 자원을 분배하기 위한 전략에는 다양한 기술들,
예컨데 알고리즘이나 자료구조 등이 사용되고 이외에도 스케줄링 성능에 영향을 줄 수 있는 요인까지 고려하고 있습니다.
이러한 과정에서 탄생한 두 가지 주요한 스케줄링 전략이
선점 스케줄링(Preemptive)과 비선점 스케줄링(Nonpreemptive) 기법이고,
이 두 가지 스케줄링 기법은 일반적인 조건에서 'Preemption'이라는 부분에서 큰 차이점이 있습니다.
왜냐하면, 일반적으로 비선점 스케줄링 기법에서는 프로세스
즉, 실행중인 프로그램이 자원을 다 쓸 때까지 최대한 기다려 주지만,
선점 스케줄링 기법에서는 실행중인 프로그램이더라도
사용중인 자원, 특히 CPU와 같은 비싼 자원을 임의로 회수할 수 있습니다.
그리고, 일반적으로 운영체제에서 이러한 자원의 '분배'를 실제로 담당하는 '스케줄러'가
프로세스에 할당했던(allocated) 자원을 강제로 회수하는 것을 'Preemption'이라고 부르고 있습니다.
따라서, 일반적인 조건에서는 선점 스케줄링 기법에서는 스케줄러에 의해 Preemption이 자주 일어나
이로 인한 추가적인 비용, 즉 문맥 교환(Context Switching)으로 인한 오버 헤드(overhead)가 발생할 수 있으나
비선점 스케줄링 기법에서는 일반적으로 프로세스가 자원의 사용을 종료할 때까지
기다리기에 Preemption이 거의 일어나지 않습니다.
예측 가능성(Predictability)과 단순성(Simplicity) vs 공정성(Fairness)과 반응성(Responsiveness)
운영체제에서 스케줄링 기법이 비선점 스케줄링과 선점 스케줄링 크게 두 가지로 나뉠 수 밖에 없는 불가항력적인 이유가 있습니다.
운영체제에서는 자원을 최대한 많은 프로세스에 빠르고, 공평하고, 효율적으로 분배하며 프로세스가 정상적으로 동작하도록 관리하고자 합니다.
이러한 목표를 달성하기 위해서는 다음과 같은 부분이 고려되어야 합니다.
먼저, 프로세스가 언제부터 언제까지 자원을 사용할 지 예상할 수 있는 '예측 가능성(Predictability)'이 중요합니다.
이러한 특성은 스케줄러가 사용하는 스케줄링 알고리즘이 최대한 단순할수록(Simplicity) 계산하기 용이합니다.
다음으로, 특정한 프로세스가 CPU와 같은 비싼 컴퓨터 자원을
혼자 독식하지 않도록 잘 관리해주는 '공정성(Fairness)'이 중요합니다.
마지막으로, CPU와 같은 비싼 자원을 사용하기 위해
프로세스가 기다리는 시간을 최대한 단축시키는 '반응성(Responsiveness)' 이 매우 중요합니다.
아쉽게도 이러한 중요한 특성들은 상호 배타적인 성향이 있습니다.
앞서 설명한 예측 가능성과 단순성을 중요한 인자로 선택한다면,
공정성과 반응성은 일정 부분 포기해야 하고, 이는 곧 비선점형 스케줄링이 추구하는 방향이 됩니다.
반면에 공정성과 반응성을 중요한 인자로 선택한다면,
예측 가능성과 단순성은 일정 부분 포기해야 하고, 이는 곧 선점형 스케줄링이 추구하는 방향이 됩니다.
따라서, 운영체제가 프로세스의 스케줄링을 관리하는 기법은
스케줄링 알고리즘에서 중요하게 생각하는 특성 간에 상호 배타적인 관계로 인해
크게 두 가지로 나뉘게 될 수 밖에 없었을 것입니다.
CFS(Completely Fair Scheduler) 알고리즘이란?
CFS(Completely Fair Scheduler)는 비선점 스케줄링(Nonpreemptive)의 기법 중 하나입니다.
CFS는 리눅스 커널의 2.6.23 버전(October 2007)에 추가되었는데,
CFS의 가장 큰 특징은 공정성을 가장 중시하여 설계된 알고리즘 이라는 점입니다.
이외에도 CFS가 가진 주요한 특징은 아래와 같습니다.
| 특징 | 설명 |
| 시간의 비례적 할당 | - CFS는 시간의 비례적 할당을 통해 공정성을 유지합니다. 각 프로세스에게 CPU 시간이 할당되며, 이 할당은 시간의 비율로 이루어집니다. - 예를 들어, 프로세스 A가 프로세스 B에 비해 CPU 시간을 두 배로 할당받았다면, A는 B보다 두 배 더 많은 CPU 시간을 사용할 수 있습니다. |
| 가상 타임 슬라이스 | - CFS는 가상 타임 슬라이스를 사용하여 CPU 시간을 할당합니다. - 각 프로세스는 가상 타임 슬라이스를 할당받고, 이 슬라이스 동안 CPU를 사용할 수 있습니다. - 가상 타임 슬라이스는 프로세스의 우선순위에 따라 동적으로 조절됩니다. |
| 레드-블랙 트리 구조 | - CFS는 레드-블랙 트리 구조를 사용하여 프로세스들을 관리합니다. - 이를 통해 프로세스의 우선순위를 효율적으로 관리하고, 스케줄링 작업을 빠르게 수행할 수 있습니다. |
| 무한 대기 없음 | - CFS는 무한 대기를 허용하지 않습니다. - 즉, 어떤 프로세스도 무한히 대기하지 않고 CPU 시간을 할당받을 수 있습니다. |
아래는 CFS 알고리즘을 단순화하여 구현한 코드 예제입니다.
아래의 알고리즘에서는 CFS에서 실제로 고려하는 모든 요인을 고려하지 않고,
최대한 단순화하여 CFS 알고리즘의 메인 스케줄링 알고리즘만을 고려하여 구현되었습니다.
자세한 설명은 주석을 참조해주세요.
소스코드
// Completely Fair Scheduler
public class CFS extends Scheduler implements Nonpreemptive {
// CFS에서 관리하는 Process 객체,
// 프로세스의 실행시간, 도착시간, 종료시간과 우선순위 그리고 가상 실행시간을 인자로 가진다.
public class Process extends Task implements Comparable<Process>{
private int priority;
private int virtualRuntime;
public Process(String name, int cpuTime) {
super(name, cpuTime);
}
public Process(String name, int cpuTime, int arraivalTime){
super(name, cpuTime, arraivalTime);
}
public int getPriority() {
return priority;
}
public void setPriority(int priority) {
this.priority = priority;
}
public int getVirtualRuntime() {
return virtualRuntime;
}
public void setVirtualRuntime(int virtualRuntime) {
this.virtualRuntime = virtualRuntime;
}
public void execute(int time){
this.virtualRuntime += time;
}
@Override
public int compareTo(Process o) {
return Integer.compare(this.priority,o.priority);
}
}
Queue<Process> cfsQueue;
Queue<Process> endProcessList;
public CFS(){
this.taskList = new PriorityQueue<Task>();
cfsQueue = new PriorityQueue<CFS.Process>();
endProcessList= new LinkedList<CFS.Process>();
this.time = 0;
}
@Override
public void addTask(Task task) {
/**
* 엄연히 따지자면, 우선순위는 더 복잡한 인수들의 계산식 등을 통해 구하지만,
* 현재 코드에서는 조금더 단순화 시키기 위해서,
* CPU를 사용한 시간이 적은 프로세스에게 우선적으로 CPU를 할당한다고 전제하고
* 우선순위 = CPU 사용시간으로 부여합니다.
* 이는, 다른 우선순위가 없을 경우 CFS에서 우선순위로 삼는 인자 중 하나 입니다.
*/
Process process = new Process(
task.getName(),
task.getCpuTime(),
task.getArrivalTime()
);
process.setPriority(task.getCpuTime());
this.cfsQueue.offer(process);
}
public Process getNextProcess() {
return cfsQueue.poll();
}
public void executeProcess(Process process, int time) {
process.execute(time);
// cfsQueue.offer(process);
}
@Override
public void run() {
/*
* CFS에서 타임 슬라이스를 정할 때는,
* 운영체제가 현재 컴퓨터의 상황을 고려하여 동적으로 정함.
*
* 이러한 슬라이스는 동적이라 언제 측정?하느냐에 따라 달라질 수 있음
*
* 그리고 이러한 타임 슬라이스를 운영체제에서 고려하는 기준은 다음과 같음
*
* ① 프로세스의 우선순위(Priority)
* CFS에서는 우선순위가 높은 프로세스에게 더 많은 CPU 시간을 할당합니다.
* 따라서 프로세스의 우선순위는 타임 슬라이스를 결정하는 데 중요한 역할을 합니다.
*
* ② 프로세스의 가상 런타임(Virtual Runtime)
* 가상 런타임은 해당 프로세스가 CPU를 사용하는 데 예상되는 시간을 반영합니다.
* 가상 런타임이 긴 프로세스는 더 긴 타임 슬라이스를 할당받게 됩니다.
*
* ③ CPU 부하 상태(CPU Load)
* 시스템의 CPU 부하 상태를 고려하여
* 타임 슬라이스를 동적으로 조절할 수 있습니다.
* 예를 들어, CPU가 과부하 상태인 경우 타임 슬라이스를 감소시켜
* 다른 프로세스에게 더 많은 기회를 주는 등의 조치를 취할 수 있습니다.
*
* ④ CPU 사용률(CPU Utilization)
* CPU 사용률을 고려하여 타임 슬라이스를 조절할 수 있습니다.
* 만약 CPU 사용률이 낮다면 각 프로세스에게
* 더 긴 타임 슬라이스를 할당하여 CPU의 효율을 높일 수 있습니다.
*
* ⑤ 프로세스의 상태(Process State)
* 대기 중인 프로세스나 I/O 작업을 수행하는 프로세스 등의 상태에 따라
* 타임 슬라이스를 조절할 수 있습니다.
* 예를 들어, I/O 대기 중인 프로세스는 CPU 시간을
* 잠시 할당받지 못하므로
* 이를 고려하여 타임 슬라이스를 조절할 수 있습니다.
*
* 하지만, 현재 구현하는 CFS 알고리즘에서는
* 이러한 인자를 모두 고려하진 않고,
* Nonpremmptive 한 스케줄링임을 고려해
* 타임 슬라이스 = CPU 사용 시간 이라고 전제합니다.
* 따라서, CFS 알고리즘에서는 프로세스의
* '우선순위'라는 인자에 따라서만, 그 순서가 결정됩니다.
*/
this.time = 0;
this.taskLength = cfsQueue.size();
int cnt = 0;
int virtualTimeSlice = 10; // 타임 슬라이스... 현재는 고정 값을 갖도록 선언
while(this.cfsQueue.size() != 0){
// 프로세스 실행
Process nextProcess = getNextProcess();
if (nextProcess != null) {
System.out.println("Executing process: " + nextProcess
+ "priority : "+nextProcess.getPriority());
executeProcess(nextProcess, virtualTimeSlice ); // 가상 타임 슬라이스: 10
time += nextProcess.getCpuTime();
nextProcess.setEndTime(this.time);
this.endProcessList.offer(nextProcess);
}
if(cnt == 1){
addTask(new Task("TASK 06", 30, 17)); // 중간에 task가 추가되는 상황을 고려
}
cnt++;
}
}
// 프로세스의 평균 대기 시간을 구하는 메서드
// 대기시간 = 종료시간 - 도착시간 - CPU 실행 시간
@Override
public float getAvgWaitTime() {
int totalWaitTime = 0;
int size = endProcessList.size();
for(Process process : endProcessList){
int waitTime = process .getEndTime() - process .getArrivalTime() - process .getCpuTime();
// System.out.println("result... " + process+", wait Time : "+waitTime);
totalWaitTime += waitTime;
}
return (float) (totalWaitTime * 1f / size * 1f);
}
// 프로세스의 평균 응답 시간을 구하는 메서드
@Override
public float getAvgResponseTime() {
// 응답시간 = 종료시간 - 도착시간
int totalResponseTime = 0;
for(Process mProcess : endProcessList){
int responseTime = mProcess .getEndTime() - mProcess .getArrivalTime();
totalResponseTime += responseTime;
// System.out.println("result... " + mTask+", wait Time : "+waitTime);
}
return (float) (totalResponseTime * 1f /this.taskLength*1f);
}
}
정리하며...
안드로이드에서 앱과 같은 프로그램의 스케줄을 관리하는 CFS 알고리즘은
안드로이드의 전체적인 컨셉과 잘 어울리는 부분이 많은 것 같습니다.
예컨데, 안드로이드 애플리케이션을 구성하는 요소는
크게 액티비티(Activity), 브로드캐스트 리시버(Broadcase Receiver),
콘텐츠 프로바이더(Content Provider), 서비스(Service)인데,
이들은 Intent라는 매개체로 상호간에 균형 잡힌 상호작용을 추구합니다.
또한, 이러한 구성요소로 이루어진 애플리케이션 간에도 최대한 공평하게
한정된 컴퓨터 자원, 일반적으로는 스마트폰이나 태블릿의 컴퓨터 자원을 사용하도록
그 기반에는 CFS 알고리즘이 역할을 수행하고 있습니다.
이러한 점에서 CFS 알고리즘은 안드로이드의 플랫폼과 잘 어울리는 성향을 가진 스케줄링 전략이라는 생각이 드는 것 같습니다.
참고자료
https://developer.android.com/guide/platform?hl=ko
플랫폼 아키텍처 | Platform | Android Developers
Android는 다양한 기기와 폼 팩터에 사용할 수 있도록 개발된 Linux 기반의 오픈소스 소프트웨어 스택입니다. 다음 다이어그램에서는 Android 플랫폼의 주요 구성요소를 보여줍니다. Android 플랫폼의
developer.android.com
https://docs.kernel.org/scheduler/sched-design-CFS.html
CFS Scheduler — The Linux Kernel documentation
Small detail: on "ideal" hardware, at any time all tasks would have the same p->se.vruntime value --- i.e., tasks would execute simultaneously and no task would ever get "out of balance" from the "ideal" share of CPU time.
docs.kernel.org
https://en.wikipedia.org/wiki/Completely_Fair_Scheduler
Completely Fair Scheduler - Wikipedia
From Wikipedia, the free encyclopedia Linux process scheduler Location of the "Completely Fair Scheduler" (a process scheduler) in a simplified structure of the Linux kernel. The Completely Fair Scheduler (CFS) is a process scheduler that was merged into t
en.wikipedia.org
'모바일(Mobile) > 안드로이드(Android)' 카테고리의 다른 글
| [Android] 안드로이드 기기와 USB 외부 장치 (0) | 2024.03.25 |
|---|---|
| [Android] SQLite와 데이터 베이스 오버 플로우에 관하여 (0) | 2024.03.11 |
| [Android] 데이터 바인딩과 뷰모델(DataBinding & ViewModel) (1) | 2023.11.09 |
| [Android] 안드로이드 스튜디오에서 원격으로 디버깅 하기 with ADB (1) | 2023.10.17 |
| [Android] 데이터 바인딩(DataBinding) (0) | 2023.09.21 |
