Karatus::[Kernel of Linux] 6. Scheduling

지난 강의 요약 - Process Management (2)

kernel thread의 특징에 대해 알아보았다. user space에서 동작하는 thread와는 달리 address access의 접근 제한이 없다는 특징을 가지고 있고 주로 daemon 같은 것들이 kernel thread 형식으로 존재한다.

process state의 종류에 대해 몇 가지 알아보았고 종류별 상관관계가 존재한다.

cpu를 차지할 프로세스를 선택하고 관리하는 것을 스케줄링이라고 한다. 다음으로 cpu를 차지할 프로세스를 선택하기 위해 필요한 조건으로 두 가지를 소개했다. 첫 번째로는 highest priority다. 높은 priority를 지닐수록 cpu를 먼저 선점할 기회가 많아진다. 두 번째는 remaining timeslice다. RR(Round-Robin) 스케줄러를 쓴다면 각 프로세스마다 일정한 timeslice를 부여하여 스케줄링할 것이다. 하지만 미처 그 시간을 다 쓰지 못한 채로 다른 프로세스에 의해 preemption 될 수도 있다. 공평한 cpu 점유를 위해 남은 timeslice가 존재하는 프로세스의 선택도 고려해야 한다.

priority를 기준으로 스케줄링을 진행하기 위해 고려한 ready queue의 모델은 여러 가지가 있을 수 있지만 O(1) scheduling을 할 수 있는 모델은 bitmap 배열을 통해 각 priority에 task가 존재하는지 체크하고 2개의 prio_array를 가져서 하나는 active, 다른 하나는 expired로 동작하는 방식이다. active에 존재하는 task가 하나도 없을 경우, active와 expired를 서로 바꾼다. 그럼 다시 expired에 존재하는 tasks는 초기화된 timeslice를 가진 상태가 된다.

kernel에서 preemption이 일어나는 경우는 크게 3가지다. (preempt_count가 0이고 need_resched flag가 set 상태일 때) unlock() 함수 호출 이후, interrupt handler가 끝났을 때와 명시적으로 kernel에서 schedule() 함수를 호출했을 때이다.

1. Timer and Time Management

1.1 Terminology

HZ
- tick rate (architecture마다 다르다)
  #define HZ 1000 (include/asm-i386/param.h)
- 대부분의 architecture에서 HZ는 1000으로 쓰인다.
- HZ의 값에 따라서 CPU에 걸리는 instruction의 개수가 달라진다.
jiffies
- 시스템 부팅 이후 몇 번의 tick이 발생했는지에 대한 global value다.
jiffies-HZ-Time
- jiffies, HZ를 알면 부팅 이후 시간이 얼마나 흘렀는지를 계산해서 알 수 있다.

1.2 Hardware Clocks and Timers

Real-Time Clock(RTC)는 nonvolatile(비휘발성)하게 시간을 표시해준다. 또 배터리로 시스템이 꺼져있더라도 계속 동작한다. 반면에 System Timer는 주기적으로 CPU에게 interrupt를 발생시킨다. wall time도 초기화시키는데 여기서 wall time이란 간단히 말해 task가 시작되고 끝날 때까지의 시간이다.

비유하자면 System Timer는 그냥 정기적으로 인터럽트를 발생시키는 장치이고, RTC는 말 그대로 손목시계 같은 것이다.

1.3 Timer Interrupt Handler

do_timer() 함수를 살펴보자. 이 함수는 Timer Interrupt의 handler다. 예제 기준으로 3줄이 존재하는데 첫 번째 코드는 단순하다. Timer Interrupt가 발생할 때마다 jiffies를 1씩 늘려주는 코드다. 참고로 64-bit integer 자료형을 쓰므로 언젠가 overflow가 일어나겠지만 몇 만년 이상이 걸리는 숫자이기 때문에 상관이 없다. 두 번째 코드는 update_process_times() 함수인데 인자로 현재 mode가 어떤 mode인지를 넘긴다. PCB를 보면 mode마다 jiffies를 따로 두어 시간을 계산한다. utime이 user mode time, stime이 system time을 나타낸다.

그런데 위에 보이는 예제는 사실 꽤 오래된 예제다. 지금은 굉장히 달라진 do_timer()의 모습을 볼 수 있다.

v5.15.10 기준으로는 위와 같은 코드로 완전히 바뀌었다. global variable인 jiffies_64에 전달받은 ticks를 더한 뒤, calc_global_load() 함수를 호출한다. 이 함수는 간단히 말해서 load average를 계산하고 업데이트해주는 함수다. do_timer() 함수는 caller는 tick_periodic() 함수에서 쓰인다.

생김새가 위 예제에서 소개한 옛 do_timer()와 비슷하다. 단순히 jiffies를 증가시키는 것이 아닌 CPU 별로 처리하고 있는 부분이 추가된 것이다. <tick_do_timer_cpu == cpu>의 조건을 만족하면 내부에서 jiffies_lock을 획득하고 do_timer() 함수를 통해 1 tick을 고정적으로 전달하고 있는 것을 확인할 수 있다. 이전과 달리 현재 timer를 handling 할 의무를 가진 CPU를 검사하는 부분, lock을 획득하는 부분이 생긴 것이다.

참고로 구글링 하다가 알게 된 건데 do_timer() 함수는 현재 tick_periodic() 함수에서만 호출된다. 이전 버전에서는 tick_do_update_jiffies64() 함수에서 tick을 증가시켜주기 위해 사용했었는데 지금은 do_timer() 함수를 통해 jiffies를 증가시키지 않고 그냥 바로 jiffies에다가 tick을 더해버리게 바뀌었다. calc_global_load() 함수를 사용할 필요가 없기 때문에 그렇지 않을까 싶은데 자세한 건 찾아봐야겠다.

1.4 Usage of Timer

Timer Interrupt는 보통 delay 기능을 위해 많이 사용된다. 일상생활과 마찬가지로 시간을 통해 많은 것들을 제어할 수 있기 때문이다. 일상생활에서 10분 뒤 약속을 잡는다든지 라면을 3분 동안 끓이기 위해 시간을 재는 것처럼 (위 예시에서 나온 대로) time_before() 매크로 함수를 통해 10 ticks 동안 busy looping을 수행할 수도 있고 micro or milli seconds 단위로도 셀 수 있다.

저작자표시 비영리 동일조건