리눅스 커널 심층 분석 - 4장, 프로세스 스케줄링

task_struct 맴버 

• need_resched 
  • 이놈이 필요한건 task_struct->state가 변경될 때 변경하기 위함임. 
  • 예를 들어 irq가 TASK_INTERRUPTABLE을 받아 RUNNABLE로 변경할 때 need_resched를 set해줌. 

A flag checked by ret_from_sys_call( ) to decide whether to invoke the schedule( ) 

function (see Section 4.8.3).[3] 

[3] Beside the values 0 (false) and 1 (true), the need_resched field of a swapper kernel 

thread (PID 0) in a multiprocessor system can also assume the value - 1; see the later 

section Section 11.2.2.6 for details. 

• policy 

The scheduling class. The values permitted are: 

• rt_priority 

The static priority of a real-time process; valid priorities range between 1 and 99. The static priority of a conventional process must be set to 0. 

• counter 

The number of ticks of CPU time left to the process before its quantum expires; when a new epoch begins, this field contains the time-quantum duration of the process. Recall that the update_process_times( ) function decrements the counter field of the current process by 1 at every tick. 

• do_fork()가 자식을 만들면, 다음 연산을 한다. 부모랑 자식이랑 counter를 반반 나누고 schedule() 호출 

p->counter = (current->counter + 1) >> 1;  current->counter >>= 1;  if (!current->counter)  current->need_resched = 1;

• 이 짓을 하는 이유는, 예를 들어, 부모가 자식을 만들었는데 자식은 부모를 복사하니깐 counter가 부모랑 같게되고, 만일 이 상태에서 자식이 스스로를 kill 하면서 다시 자식을 만들고 kill하는 것을 반복하면 부모 counter는 계속 남아있고 자식 counter도 계속 복사되기 때문에 결국 끝나지 않기 때문이다! 

• nice 

Determines the length of the process time quantum when a new epoch begins. This field contains values ranging between - 20 and + 19; negative values correspond to "high priority" processes, positive ones to "low priority" processes. The default value 0 corresponds to normal processes. 

• cpus_allowed 

A bit mask specifying the CPUs on which the process is allowed to run. In the 80 x 86 architecture, the maximum number of processor is set to 32, so the whole mask can be encoded in a single integer field. 

• cpus_runnable 

A bit mask specifying the CPU that is executing the process, if any. If the process is not executed by any CPU, all bits of the field are set to 1. Otherwise, all bits of the field are set to 0, except the bit associated with the executing CPU, which is set to 1. This encoding allows the kernel to verify whether the process can be scheduled on a given CPU by simply computing the logical AND between this field, the cpus_allowed field, and the bit mask specifying the CPU. 

• processor 

The index of the CPU that is executing the process, if any; otherwise, the index of the last CPU that 

executed the process. 

멀티태스킹 

• 협동형 
  • 스케줄러가 없고 실행 중인 프로세스가 중단할지 말지 결정 
• 선점형 
  • 리눅스는 처음부터 선점형, osx는 9 이후, win3.1 이후에 선점형 
  • 스케줄러가 실행 중인 프로세스를 중단하는 preempty(선점)를 할 수 있음 
• 리눅스의 스케줄러는 2.5 부터 정비를 하여 2.6에 O(1) 스케줄러를 적용하여 2.6.23부터 CFS를 사용함. 
  • O(1)은 process 중심 시스템엔 효과적이지만 IO 중심 시스템엔 쥐약임 

정책 

• IO 중심이냐 processor 중심이냐? 
  • IO 중심: 응답 빠르지만 process에 할애하는 시간이 적음 
  • process 중심: 많은 연산에 적합하지만 응답성이 떨어짐 
  • Linux는 IO에 관대하지만 연산에도 충실함. 
• 스케줄링 방식 
  • 프로세스 우선순위 
    • 우선순위가 높은 process는 더 자주 실행되고 긴 time slice를 할당 받음. 
  • time slice:  
    • 프로세스가 얼마나 오랫동안 실행되는 가를 뜻함. 
    • 프로세스는 정해진 time slice 기본 값을 가지고 시작한다. 
• time slice를 길게 하면 응답 성능 떨어지고, 짧게 하면 연산 성능이 떨어짐. 
• 프로세스의 우선순위에 따라 time slice를 할당하는데, 
  • 비실시간 우선순위(nice): -20 ~ +19, 클 수록 다른 process에 친절nice 하여 우선순위가 떨어짐. 
    • $ ps -el 
    • 스케쥴 정책:  
      • scheduled normal(O(1)은 scheduled other라고 했었음) 
  • 실시간 우선순위: 0 ~ 99, 클 수록 우선순위 높음. 0~99 
    • $ ps -eo state, uid, pid, ppid, rtprio, time, comm 
    • 스케쥴 정책:  
      • scheduled fifo - 우선순위 높은 놈들 뽑는 정책 
      • scheduled RR - 동일한 우선순위 가지고 있는 놈들 중 뽑는 정책 
  • 다른 os는 우선순위가 같은 것이 없지만 linux는 출생이 우선순위가 없었다. 그래서 우선순위 높은것만 고르면 되는데 linux는 동일한 우선순위가 생길 수 있다. 그게 scheduled RR정책임. 
  • O(1) scheduler는 CPU 중심 task는 NICE를 높여버림. 이는 부하가 많을 때는 잘 동작함. 하지만 부하가 작으면 쓸데없는 scheduling이 되어 불필요한 load가 생김. 이를 개선한 것이 CFS임. 
  • osx는 절대 시간을 할당하고, linux는 비율(CFS)로 할당함. 
• 일반적인 apps는 100 ~ 139번이고 이를 non-realtime task임. 
• fifo --> RR --> normal class 순서로 우선순위 정함. 
• CFS나 O(1)은 non-realtime에 대한 것만 말함. 

리눅스 스케줄링 알고리즘 

• sched.c>에 code가 있음 
• 모듈화된 스케줄러 클래스가 프로세서를 여러가지 방법으로 스케줄링하는 구조임. 
• CFS(complete fair scheduler): sched_fair.c> 
  • nice 값에 따라 time slice를 적용할 때 네 가지 문제점. 
    • 각 nice 값에 따라 time slice 절대값을 정해야 하기 때문에 nice 값이 낮은 프로세스 둘 만 스케줄링 되는 경우 전체시간에 한번만 스케줄 하면 되는데 절대값 마다 스케줄링을 하느라 쓸데없이 자주 스케줄링이 됨. 
    • 인접한 nice 값에 상대적인 차이를 극복해야 함. 예를 들면 nice 19는 5/100, nice 18은 10/100인데 둘 차이는 두배?? ㅋㅋ 
    • 커널 tick time에 영향을 받는다. 
    • IO process 처리에만 편향된 스케줄링을 할 수 있다. 
  • 목표 응답 시간인 20ms를 전체 process 개수 n으로 나눠서 time slice(epoch)를 정하고 slice를 가장 실행이 덜 된 프로세스에 주어 실행 시킨다. 
  • 각각의 process는 스케줄러가 각기 다른 base time quantum를 설정해 준다. nice()나 setpriority()를 이용해서 설정할 수 있다. 자식은 부모에게 물려받음. 
  • n이 커져서 전환 비용이 커지면 time slice의 최소 한계(최소 세밀도 = 1ms)를 지킨다. 
  • nice 값은 절대적인 크기가 아닌 상대적인 비율로 적용된다. 
  • vruntime이 가장 작은 process를 선택함. 
  • __pick_next_entry()는 rbtree 가장 왼쪽 노드에 해당하는 프로세스를 실행한다. 
  • cfs_rq->rb_leftmost에 저장하고 rb_leftmost == NULL이면 더 이상 수행할 process가 없다는 뜻이므로 idle이 됨. 
  • enqueue_entity(): 프로세스를 rbtree에 넣는 작업 
  • denqueue_entity(): 제거 
• sched.c> schedule() 
  • 역할: 다음에 실행할 프로세스를 선택, 실행함. 
  • 우선순위가 높은 스케줄러 클래스부터 낮은 순위로 돌아가면서 우선순위가 가장 높은 프로세스를 찾아냄. by pick_next_task() 
  • 이놈은 task_struct->need_resched를 확인하고 실행됨, kernel process인 경우에는 thread_info->preempty_count==0임을 확인하고 수행함. 
• wait과 run queue 
  • TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE은 wait queue에서 특정 조건이 일어나길 기다리며 실행되지 않는다. 
  • 휴면 / 활성 처리 작업은 race condition이 발생할 위험이 있다. 
  • wait queue 
    • <linux/wait.h> wait_queue_heat_t 형임 
    • sleep 계열 함수나 getchar()와 같은 함수가 호출되면 wait queue에 들어감. 
    • wait()을 실행하면 parent에 신호를 줌. 
    • wait queue는 여러 개가 있다. 인터럽트 발생하면 해당 wait queue를 확인하여 필요한 process를 깨운다. 
    • example 

    DEFINE_WAIT(wait); //매크로로 대기열에 추가할 항목(wait)을 만듬  add_wait_queue(q, &wait); //q는 휴면상태가 들어갈 대기열, 대기열에 wait 추가.  while(!condition) { //조건이 만족 할 때 까지 looping  prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE); //process 상태를 TASK_INTERRUPTIBLE로 변경  if (signal_pending(current) {  /* 시그널 처리 */  schedule();  }  finish_wait(&q, &wait); //q->state = TASK_INTERRUPTIBLE

  • run queue 
    • wake_up(): 주어진 대기열에 있는 모든 작업을 깨움. 조건을 발생시킨 코드에 추가하는 것이 일반적임. 
    • try_to_wake_up(): state = TASK_RUNNING 
    • enqueue_task(): task를 rbtree에 추가하고 task 우선순위가 높으면 need_resched 설정함. 

선점과 컨텍스트 전환 

• .text, .data, .bss, stack, heap, lib 한 세트를 context라고 하고 가상으로 4G 메모리임. context switching은 cpu에 context를 교체하는 과정을 말함. 
• sched.c> context_switch():  
  • 실행 중인 한 작업에서 다른 작업으로 전환 
  • schedule() 함수가 새로 실행할 process를 선택하면 context_switch() 호출됨. 
  • <asm/mmu_context.h> switch_mm()을 호출해서 mmu table를 새 process에 맞춤 
  • <asm/system.h> switch_to()를 호출해 프로세스에 맞게 프로세서 상태를 변경함. 
• task->need_resched 
  • 프로세스를 선점할 필요가 있을 때 scheduler_tick()함수가 설정하거나 
  • 깨어난 프로세스가 현제 프로세스보다 우선순위가 높을 때 try_to_wake_up()함수를 통해 설정됨. 
  • ret_from_sys_call()로 확인 가능함. 
  • swapper(process 0)는 need_resched 가 항상 -1임. 
• kernel 과 user의 선점 
  • user 선점:  
    • 인터럽트 처리나 syscall을 마치고 user 공간으로 돌아갈 때 need_resched를 확인하고 발생함. 
    • 보통 각 architecture에 entry.S에 어셈블리로 구현됨. 
  • kernel 선점: 
    • kernel도 user에 의해 선점 가능하지만, preempt_count가 0이 되어야 가능함. user는 이 것이랑 관계 없는듯… ㅋㅋㅋ 
    • 다른 선점형 kernel은 kernel이 선점하면 협력형으로 수행된다. 즉 kernel이 실행중인 경우에는 scheduler가 개입할 수 없다. kernel이 작업을 마치거나 스스로 대기 상태로 들어갈 때 까지 실행된다. 
    • linux는 완전 선점형으로, 실행 중인 작업이 rock을 하지 않은 상태면 안전한 상태로서, kernel도 선점 가능함. 선점은 preempty 
      • thread_info->preempt_count: rock을 설정하면 한 개씩 증가하고, 0이 되면 안전한 상태가 되고, 선점 가능함. 
    • 다음 경우에 kernel 선점이 됨. 
      • 인터럽트 처리를 마치고 kernel 공간으로 돌아갈 때 
      • kernel code가 다시 선점 가능한 상태가 되었을 때 
      • kernel 내부 작업이 명시적으로 schedule() 함수를 호출하는 경우 
      • 커널 내부 작업이 중단되 대기 상태가 되어 schedule() 함수를 호출하게 되는 경우 

실시간 스케줄링 정책(dynamic priority) 

• 
  
• 비실시간 스케줄링 정책: SCHED_NORMAL 
  • static priority, 또는 conventional priority. 
  • 실시간 스케줄링이 무조건 우선시됨. 
• 실시간 스케줄링 정책:  
  • SCHED_FIFO: time slice 없이 FIFO로 스케줄하는 알고리즘, SCHED_NORMAL보다 우선시함. 
  • SCHED_RR: time slice가 있는 것 빼고는 SCHED_FIFO와 동일함. 
  • 실시간 우선순위는 0 ~ MAX_RT_PRIO -1이며 nice는 MAX_RT_PRIO ~ MAX_RT_PRIO + 39임. 

스케줄러 관련 syscall 

• nice()	nice값 설정
  sched_setscheduler()  sched_getscheduler()	스케줄링 정책 설정 / 확인  주로 task_struct->policy, task_struct->rt_priority 설정  policy: SCHED_FIFO, SCHED_RR, SCHED_OTHER  rt_priority: 0이면 비활성화, 1~99는 활성화
  sched_setparam()	실시간 우선순위 설정
  sched_get_priority_max()  sched_get_priority_min()	실시간 우선순위 최대 / 최소값 확인
  sched_rr_get_interval()	time slice값 확인
  sched_getaffinity()  sched_getaffinity()	지속성 정보 설정 / 확인  프로세스가 되도록이면 같은 processor를 사용하도록 하는데 cpus_allowed를 이용해서 사용 가능한 processor를 제한할 수 있음
  sched_yield()	일시적으로 프로세서를 양보함