7-4. Task Scheduling in Linux (4)

중앙대학교 3-2 리눅스 응용 설계 (손용석 교수님) 과목 정리입니다.

__schedule()

• scheduling의 key function
• current task의 실행을 멈추고, 새롭게 실행될 next task가 선택된다.
• next task를 실행하기 위해 user address space information, register, 두 task의 kernel stack 이 전환된다.

• 이전 task의 state가 TASK_RUNNING이 아니고, preempt 값이 false인 경우 prev_task를 처리한다.
  • Ex. task가 sleep API를 사용하는 경우 task는 run queue에서 dequeue 된다.
• signal_pending_state는 Task state가 TASK_INTERRUPTIBLE인 경우 true 반환
• task를 전환하기 전에 prev task가 처리해야 하는 signal이 있는 경우, task state가 TASK_RUNNING으로 변경되어, run queue에서 dequeue 되지 않는다.
• 처리할 신호가 없으면 해당 task는 run queue에서 dequeue 되고, state는 sleep으로 변경된다.
• on_rq field 또한 0으로 변경된다.

pick_next_task()

• 현재 task가 모든 할당된 time slice를 사용했거나, CPU를 양보할 필요가 있는 경우 scheduler가 실행할 task를 선택해야 한다.

• current task가 fair scheduling class를 사용하고 run queue에 fair task 밖에 없는 경우, 다음 task는 CFS run queue에서 탐색된다.
• CFS run queue에서 next task를 찾는다.
• task가 없는 경우 load balancing을 수행하고, 다른 core에서 task를 가져온다.
  • normal task가 fetch 되었을 때 higher priority를 가진 task가 있을 때 RETRY return
  • 전체 scheduling class 중에서 다시 찾는다.
• fair_schedule로 못 찾는 경우 : 다음 task로 가장 낮은 priority를 갖는 idle thread를 선택한다.
  • 이 경우, fair scheduling class의 pick_next_task()가 normal task를 선택하지 못하거나, load balancing이 실패한 것.

• priority 순으로 정렬된 모든 scheduling class를 순회한다.
• 각 class에 구현된 pick_next_task가 다음 실행할 task를 찾기 위해 호출된다.
• 실행할 task가 선택되었을 때 해당 task를 삭제하고 종료한다. task를 찾지 못한다면 다음 scheduling class에서 task를 탐색한다.

• 현재 scheduling entity를 가져온다.
• 다음 task를 선정한다.
• group cfs run-queue를 가져온다.
• 이전 scheduling entity를 run-queue에 넣는다.
• 선택된 scheduling entity를 run-queue에서 dequeue
• scheduling entity를 CFS run-queue의 current entity로 설정한다.

• __pick_first_entity : CFS run-queue에서 첫 번째 entity를 가져온다.
• 현재 task가 left가 되는 경우
  • CFS run-queue에 leftmost scheduling entity가 없을 때 (CFS run-queue에 삽입된 scheduling entity가 없는 것)
  • current scheduling entity의 vruntime이 leftmost scheduling entity보다 작을 때 (현재 task가 leftmost task보다 우선순위 높음)

put_prev_entity()

• 이전 scheduling entity를 runqueue에 삽입하고 runqueue의 current field를 초기화한다.

• run-queue에서 current entity가 dequeue 되었는지 확인(해당 entity를 실행하려면 dequeue되어야 함)
  • dequeue 되지 않았으면 update_curr() 호출
• (다시 확인) current entity가 run-queue에서 dequeue 되지 않은 경우
  • run-queue에 enqueue (no sleep)
• runqueue의 현재 실행중인 scheduling entity를 나타내는 curr field 초기화
  • curr field는 set_next_entity에서 설정된다.

set_next_entity()

• 해당 함수는 run queue의 current entity를 설정한다.
  • current entity가 되었기 때문에, current entity가 될 task는 run-queue에서 dequeue되어야 한다. Runtime information도 update된다.

• 다음 current entity를 red black tree에서 dequeue
• run queue의 current entity를 해당 entity로 설정
• sum_exec_runtime (해당 entity의 running time의 합)을 prev_sum_exec_runtime에 backup 해둔다.
• 새로운 current entity가 곧 실행되기 때문에, execution time을 update해야 한다.
  • se→exec_start를 run queue clock time으로 수정한다.

__enqueue_entity

• run queue에 이전 task를 삽입한다.

__dequeue_entity()

• rb_leftmost를 update한다.
• 입력받은 rb_node가 leftmost node인 경우, rb_next는 새로운 leftmost node를 찾는다.
• node를 red-black tree에서 삭제한다.

enqueue_task()

• event-driven scheduling은 enqueue_task()에서 직접 호출된다.

enqueue_task_fair()

• enqueue될 entity의 계층적 구조는 bottom-up 방식으로 탐색한다.
  • task가 별도로 생성된 task group의 대기열에 있는 경우 두 번 이상 반복하여 계층을 검색한다.
  • task group이 없거나 root task group 대기열에 있는 경우 search operation은 한 번만 실행된다.
• entity가 run-queue에 이미 삽입되었는지 확인
  • 삽입된 경우 → on_rq field를 1로 설정
  • on_rq field가 1이면, 해당 entity의 모든 parent entity가 enqueue되었다는 것을 보장한다.

enqueue_entity()

• 삽입된 entity의 vruntime을 normalize
  • 즉, entity가 run-queue의 다른 entity들보다 나중에 실행된다.
• entity의 load weight를 run-queue의 load weight로 추가한다.

dequeue_task()

• event-driven scheduling은 dequeue_task를 직접 호출한다.

dequeue_task_fair() and dequeue_entity()

• virtual runtime 업데이트
• dequeue 실행

Running Example in CFS

• run queue는 red black tree로 구현된다.
• 처음에는 vruntime이 모두 0

• scheduling tick이 1ms이므로 time slice는 4.0518이지만 5ms 실행한다.
• T1의 vruntime을 0.536으로 수정 → base weight를 task weight로 나눈 값에 실행 시간을 곱한 값으로 수정

결과