Kern Koh Kernel of Linux Scheduling 정리

• Linux에서는 기본적으로 우선순위가 제일 높은애가 돌아감 
• 근데 timeslice가 남아있는지도 고려함

• timeslice 남았을때 preempted task가됨
• ready 상태일때 나중에 remaining timeslice를 쓸 수 있음
• 20ms를 쓰다가 CPU가 다른 더 중요한 task한테 뺏기면 나중에 그 중요한 task가 끝나고 다시 80ms의 remaining timeslice를 쓸 수 있음
• 그래서 linux에서 CPU를 차지하려면 우선순위도 높아야되고 remaining timeslice가 0이 아니여야됨
• timeslice다 쓰면 다른 tasks가 timeslice 다 쓸때까지 기다리고 우선순위에 기반해서 스케쥴링됨

Scheduling Algorithm

• Ready Queue라는 하나의 리스트에 PCB를 매달아놓음
• 근데 이걸 High, Low Priority로 두개로 자르면 검색시간을 줄일 수 있음
• 두개로 부족하면 더 토막내면 됨

• bitmap을 사용해서 어디가 비었는지 사용중인지 쉽게 알 수 있음
• 검색시간 더 줄어들게 만들 수 있음
• bitmap과 queue 묶인 prio_array라는 구조체가 있음

• priority를 보고 태스크 리스트를 보면 됨
• 그러면 전부 뒤질 필요가 없음

• 만약 처리를 하다가 timeslice가 만료되면 Expired array로 이동함

• Active array에 달린 task들의 timeslice가 만료되면 Expired array에 달린 task들에게 timeslice를 배정함
• Expired array가 Active array가 됨

Kernel Preemption

• 두개의 processes가 똑같은 shared memory에 접근함
• 두 processes가 shared variable에 1씩 더해줌
• 결과적으로 11 -> 12 -> 13이라는 결과를 잘 얻을 수 있음
• 하지만 둘다 동시에 실행된다면 x 읽어서 레지스터 넣는 작업이 process A에서 실행되고 다시 저장하기 전에 x를 레지스터로 읽어오는 작업이 process B에서 실행된다면 둘다 레지스터에는 11이 저장되서 13이라는 결과를 얻지 못하고 하나가 손실됨
• 이게 lost update problem임
• lost update problem은 둘다 같이 실행시킬때 발생함
• 저 문제를 해결하기 위해서 한순간에 하나의 process만 critical section에 진입해야됨
• atomic한 작업을 끝낼때까지 끼어들어오면 안됨 끼어들면 아까 앞서 설명한 문제가 발생함
• Kernel mode때 모든 address space를 접근할 수 있어서 문제가 발생함

• UNIX는 Mutual Exclusion problem을 user mode가 CPU를 뺏으려 오면 주고 kernel mode면 안주다가 user mode로 돌아가면 줌으로서 해결
• 즉 atomic 하게 만드는거임
• 급하게 처리해야할 작업이 있을때, 처리 못한다는 단점이있음
• 배보다 배꼽이 큼
• Linux 엔지니어들이 생각해낸 방법은 아래와 같음
• 사진을 보면 두개의 processes가 read와 send를 호출하는데 하나의 동일한 커널 함수를 거침
• 지역변수는 어차피 kernel stack에 들어가있으니까 어떻게 되던 상관이 없음 하지만 문제는 전역 변수에 접근할때 생김
• global variable access할때 lock을 걸고 끝나면 lock을 푸는 방식을 사용함

• preempt_count는 그 thread의 lock 개수가 됨
• global variable에 access할때마다 count 1 증가
• global variable access 끝나면 count 1 감소
• preempt_count가 0이면 critical section에 없고 local variable 가지고 작업하고 있는거라 CPU 줘도 상관없음
• need_resched flag는 더 높은 priority의 프로세스가 기다리고 있으면 세팅됨
• 아까 급박한 작업을 처리해야될때 바로 처리하기 위해서 다시 스케쥴링해야함

• 커널이 점유 가능해질때

- 공유 자원 접근끝나고 unlock되서 preempt_count가 0, need_resched가 세팅되면 커널이 다시 점유

• interrupt handler가 커널로 리턴할때

- preempt_count = 0이고 need_resched가 set이면 커널이 다시 점유

• preemption points

Timers and Time Management

• 대부분 아키텍처에선 constant HZ가 100
• jiffies는 전역 변수고 boot 이후 tick의 수

• System Timer

- 주기적으로 CPU한테 interrupt 검

• RTC

- Nonvolatile

- 꺼져도 잘 돌아감

- boot때 kernel이 RTC 읽음

- wall time 초기화

• architecture-dependent routine

- 필요에 따라 system timer를 reset 혹은 확인

- 주기적으로 업데이트된 실제 시간을 RTC에 저장

- architecture-independent routine 호출

• architecture-independent routine

- jiffies 1증가

- 실제 시간 업데이트

- 리소스 사용량 업데이트

- 만료된 동적 타이머 돌리기  

• Timer Interrupt Handler임 

• timer interrupt 몇번 걸렸는지로 예측해서 나옴
• user, sys 합쳐서 real