런큐
OS이론에서는 일반적으로 실행 요청을 한 프로세스들을 담고 있는 큐를 "레디큐"로 정의한다. 하지만 리눅스에서는 "런큐" 라는 개념으로, 레드블랙트리 구조를 띈다.
Per-cpu 별로 런큐가 존재한다.
percpu 타입의 변수인 runqueues 전역변수 주소에 __per_cpu_offset[] 배열에 저장된 percpu 오프셋을 더하면 각 CPU별로 관리하는 런큐의 주소를 알 수 있다.
삽입과정
먼저 프로세스가 런큐에 삽입되면, 런큐 구조체인 rq 필드 중 linked-list로 구현된 cfs_tasks에 자신의 task structure를 등록한다.(&se->group_node) 그후, account_entity_enqueue()에서 list_add로 linked_list에 추가.
CFS
- 타임슬라이스
- 우선순위
- 가상실행시간(vruntime)
타임슬라이스
프로세스마다 실행할 수 있는 단위 시간을 부여함. 이를 타임슬라이스
부여된 타임 슬라이스를 모두 소모하였다면, 선점 스케줄링 대상이 된다.
우선순위
우선순위가 높은 프로세스에 대해 다음과 같이 처리한다.
가장 먼저 CPU할당, 더 많은 타임슬라이스 할당
이것은 절댓값으로 사용되는것이 아닌, CPU 타임 슬라이스 할당 비율로 사용된다.
가상실행시간(vruntime)
프로세스가 그동한 실행한 시간을 정규화한 시간 정보
CFS가 프로세스를 선택하는 load weight같은 여러 지표가 고려된다.
가장 vruntime이 적은 프로세스를 선택
우선순위가 높은 프로세스는 vruntime이 더 천천히 증가한다. 즉 우선순위가 높을 수록 vruntime이 덜 증가한다.
타임 슬라이스 할당 방법
먼저 정수형 priority 는 sched_prio_to_weight() 함수에 의해 load weight로 변경된다.
그 이후, CFS필드에 런큐에 등록한 프로세스들의 load weight를 모두 합한 값을 load.weight에 저장한다.
타임슬라이스 = (프로세스 load weight / CFS 전체 load weight) * 스케줄링 레이턴시 이때, 스케줄링 레이턴시는 실행 대기 상태로 기다리는 프로세스들의 타임 슬라이스를 합한 값이다.
vruntime
vruntime += 실행시각 * (1024/load weight) priority가 크면 클 수록 vruntime이 천천히 증가한다.
sleep 상태에서는 업데이트되지 않는다.
새로 생성된 process는 vruntime이 0이므로 가장 먼저 실행된다?
-> 최소 runtime을 주기적으로 계산한다.
어떻게 레드-블랙 트리에 삽입하는가?
kernel/sched/fair.c
그래서 Red-Black Tree가 뭔가
balanced BST의 한종류인데, AVL 트리는 너무 빡빡하게 균형을 맞추려고 하기 때문에 오버헤드가 많이 발생한다.
레드-블랙 트리(RBT)에서의 리프: 데이터가 들어있는 노드 밑에 숨어있는 '빈 공간(NULL/NIL 포인터)' 자체를 리프 노드라고 칭함.
여기서, 4번,5번 규칙을 이용해서 적당한 균형을 유지한다.
가장 긴 경로가 가장 짧은 경로의 2배를 넘지 못한다는 점을 이용함.
insert할때, double red 문제는 다음과 같이 해결한다.
1. 삼촌이 RED이면 Parent, Uncle을 Black으로, Grandparent는 Red로 변경
- 삼촌이 black인 경우
구조를 변경한다.
현대 리눅스 커널은 EEVDEF를 사용한다고 한다.
