운영 체제 (Operating System) - Task Scheduler에서 Priority 조정을 위한 System Call 구현

1. Task structure

프로그램을 실행하면 프로세스와 스레드가 생성되면서 일련의 실행흐름이 탄생하게 된다. 리눅스 커널의 관점에서 이 실행 흐름을 보았을 때, 프로세스와 스레드는 task로 관리되는데, 이렇게 표현된 task를 스케줄러가 적절히 자원을 분배하고 실행시켜 프로세스가 진행된다.

여기서 task와 관련된 모든 정보를 ‘문맥’이라고 표현하는데 여기에는 시스템 문맥, 메모리 문맥, 하드웨어 문맥이 포함된다. 시스템 문맥이란 task의 정보를 유지하기 위해 커널이 할당한 자료구조 들로 task_struct이 여기에 포함된다. 이 자료구조에는 task의 상태, 관계, 메모리, ID등 다양한 정보를 포함한다. 이 정보들을 용도에 따라 그룹화하면 다음과 같이 표현된다.

 

1. ID : pid, tgid, uid, euid, suid, fsuid, gid, egid, sgid, fsgid

2. 상태 : state

3. 관계 : real_parent, parent

4. 스케줄링 정보 : prio, policy, cpus_allowed

5. 시그널 정보 : signal, sighand, blocked, pending

6. 메모리 정보

7. 파일 정보 : files

8. 스레드 구조체

9. 시간 정보 : start_time, real_start_time

10. 포맷 정보 : personality

11. 자원 제한 정보 : rlim_max, rlim_cur

 

이 중에서도 눈여겨 볼 부분은 ID 그룹의 pid이다. 하나의 프로세스를 흐름에 의거하여 여러 개의 태스크로 나누어 커널은 관리하는데, 동일한 pid를 갖지만 모두 서로 다른 task structure를 갖는다. 그렇기 때문에 스케줄러가 각 태스크를 독립적으로 스케줄링하여 concurrent한 실행 실행을 구현할 수 있는 것이다. 하지만 동일한 pid를 갖게 되므로, 이를 통해 각 태스크를 하나의 프로세스로서 관리할 수 있다.(예 : running, exit과 같은 프로세스 상태) 이러한 자료 구조를 이용하여 태스크로 각 스레드에게 독립적인 실행 흐름을 보장하면서 하나의 프로세스로서 관리할 수 있는 것이다.

 

 

2. CFS (Completely Fair Scheduler)

CFS은 스케줄링 기준을 시간 단위로 설정하고 존재하는 task들에 대하여 공평한 CPU 시간을 할당하는 것을 목표로 하는 스케줄러로, RSDL스케줄러를 기초로 한 RB-Tree 데이터 구조를 사용하여 O(logN)의 성능을 갖는 스케줄러이다. CFS가 어떻게 task에게 공평한 CPU시간을 할당하는지 알기 위해서는 다음 세 요소를 이해해야 한다.

 

1. 자원 분배를 위한 타임 슬라이스

타임슬라이스란 스케줄러가 프로세스에게 부여한 실행 시간으로 CFS의 실행 단위 시간을 의미한다. 리눅스가 CPU 클럭을 이용하여 시간을 계산하는데, CPU 클럭 한 틱이 지날 때 마다 그 틱에 해당하는 시간 만큼 타임 슬라이스가 줄며 완전히 소진 되는 경우 선점 스케줄링 대상으로 컨택스트 스위칭이 일어나 다른 task에게 일정 시간 만큼의 자원을 할당 하고 실행 흐름이 넘어간다.

 

2. 태스크 선택의 우선순위

우선 순위는 CFS 스케줄러가 context switching 시 다음 프로세스를 선택하는 기준 중 하나로, 우선순위가 더 높은 프로세스를 먼저 CPU에서 실행시키고, 더 많은 타임 슬라이스를 할당함으로써 많은 자원을 할당한다. 이 우선순위는 뒤이어 설명할 vruntime과 공평성 개념 등에 의해서 구현되고, task_struct에 속성으로도 구현된다.

 

3. 다음 태스크 선택의 기준인 가상 실행 시간(vruntime)

가상 실행 시간(vruntime)이란 프로세스가 load weight과 같은 여러 지표가 고려된 실행된 시간을 정규화 한 시간 정보로, 이 값을 기준으로 CFS는 지향하는 공정한 스케줄링을 시행한다.

vruntime += execution time x (default weight/process weight)

예를 들어 vrumtime의 시간이 작을 수록(허용된 시간이 작업 시간이 작을 수록) 더 많은 프로세서 시간을 할당 받게됨으로써 다른 task와 공평하게 자원을 할당받게 된다. 다음 실행 프로세스로 CFS는 vruntime이 가장 작은 값을 갖는 프로세스를 선택하게 되는데, 이는 RB-Tree의 최하단, 좌측에 있는 프로세스를 참조하는 방식으로 구현된다. 앞서 서술한 우선순위도 vruntime에 의해 구현 되는데, 우선 순위가 높은 프로세스를 낮은 우선순위의 프로세스에 비해 vruntime이 서서히 증하가게 함으로써 자연스럽게 실행 빈도를 높이는 방식으로 구현된다.

 

이외에도 대기자 공평성 개념이 포함되어 현재 실행할 수 없는 작업이 나중에 실행이 필요해질 때 대기시간에 상응하는 시간을 할당 받을 수 있도록 보장되어 시간이 공평하게 분배되게 한다.

 

 

3. 구현

다음은 실제 구현한 방식이다. CFS의 소스 코드인 fair.c에서 vruntime을 연산하는 부분인 update_curr함수를 다음과 같이 수정하였다. 우선순위를 높이기 위해서 vruntime의 증가량을 일반 프로세스보다 1/1000배로 설정하였고, 우선순위를 낮추기 위해서 vruntime의 증가량을 일반 프로세스보다 1000배로 설정하였다. 이후, faster_pid와 slower_pid를 설정하기 위해 system call을 정의하여 빌드하였다