17. Scheduler Activation

서울대학교 컴퓨터공학과 김진수 교수님의 "고급 운영체제" 강의를 필기한 내용입니다.

다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.

Kernel, User level thread §

• 뭐 kernel thread 야 kernel code 가 실행되게 thread 생성해 주면 되니까 상관없는데
• User program 을 thread 로 실행시키는게 문제다.
• 이 user program 을 “누가” 실행시키냐에 따라 Kernel level thread, User level thread 로 나뉘는 것.

Kernel-level thread (1:1 Model) §

• Kernel level thread 는 user program 을 kernel thread 에서 실행시키는 것이다.
• 좀 더 자세히 말하면
  • 일단 user program 에서 thread 를 생성하기 위해 syscall 을 하면 kernel 로 점프하게 된다.
  • 그리고 여기서 kernel thread 를 만든 뒤, 여기에서 user program 으로 다시 뛰어서 user program 이 실행되는 thread 가 생성되는 것이다.
• 이렇게 user program 을 실행시키는 kernel thread 가 하나 생성되기에 user thread 와 kernel thread 가 1:1 로 매핑된다, 즉 1:1 model 이라고도 불리는 것.
• 장점은
  • User thread 가 kernel thread 로 구현되는 것이니 당연히 kernel 도 이 thread 의 존재를 알고, 따라서 그에 맞게 scheduling 해줄 수 있다.
    • 뒤에 User level thread 의 단점으로도 나오는 건데, kernel level thread 에서는 한 thread 의 block 이 다른 thread 에 영향을 주지 않는다.
• 하지만 단점은 아무래도 무겁다는 것이다..
  • 일단 어떤 실행 흐름이 변경되는 방법들에 대해 좀 비교해 보자.
  • 가장 가벼운 것은 function call 이다.
    • 그냥 Stack 에 넣어 SP 변경하고 PC 바꿔서 점프뛰면 되기 때문.
    • 하지만 이 function call 은 parallel 하게 작동하지 않는다. 이때문에 thread 를 사용하는 것
  • 다음으로는 thread 가 있다.
    • Thread 에서는 function call 과 다르게 별도의 stack 이 할당되고, register 들을 save 하고 점프뛰게 된다.
  • 근데 kernel level thread 에서는 그냥 점프뛸 수가 없다.
    • 대응되는 kernel thread 가 있기 때문에 kernel 로 진입하는 overhead 가 있고, 이때문에 느려지게 된다.
• 추가적인 단점으로는 thread API 가 다소 OS-specific 할 수 있다는 것이다.
  • 즉, portability 와 flexibility 가 떨어짐

User-level thread (N:1 Model) §

• User level thread 는 user program 을 kernel 도움 없이 또 다른 user program 인 thread library (runtime library) 가 돌려주는 것이다.
  • 이 thread library 에서 kernel 개입 없이 procedure call (아마 function calll?) 로 각 thread 를 실행시켜준다.
  • 그래서 이놈이 kernel 대신 thread 들 간의 scheduling 등과 같은 작업을 해준다.
    • 그래서 시간순서대로 보면 T1 -> lib -> T2 -> lib -> T3 이런 방식으로 와리가리하는 셈
  • 이건 결국에는 thread 간에 interleaving 을 할 때 stack, reg save 등과 같은 작업을 user level 에서도 가능하기 때문
  • 그래서 이 library 에서 yield() API 를 제공해 줘서 (당연히 syscall 은 아니다) 실행 흐름을 다른 thread 로 넘길 수 있다
• 따라서 여기에는 kernel thread 가 process 전체를 위해 하나만 생성되기에 N:1 Model 이라고도 한다.
  • 이 user thread 들이 하나의 kernel thread 에서 도는 것이기 때문에 scheduler activation 논문에서는 kernel thread 를 virtual processor 라고 표현한다.
  • 논문 읽을 때는 process = kernel thread = virtual processor 라고 치환하면서 이해하면 좋을 것이다.
• 즉, 하나의 kernel thread 에서 파생된 흐름이 user level 로 올라온 다음에 여기에서 중간중간 runtime lib 의 도움을 받으며 여러 실행흐름으로 돌아다니는 것
• 장점은
  • thread 가 변경되는 것에 kernel 이 개입하지 않기 때문에 가볍다.
  • 그리고, OS 종류에 의존적이지도 않다.
• 단점은
  • Multi-core 를 활용할 수는 없다
  • Kernel level scheduling 이 안된다.
    • 즉, 한 thread 에 IO block 이 걸리면 kernel 입장에서는 kernel thread 하나가 block 된 것이므로 모든 user thread 들이 block 된다.
  • 위 두가지는 결국에 이 user thread 들이 하나의 process, 하나의 kernel thread 를 근간으로 하기 때문

M:N Model §

• N:1 Model 에서 하나의 kernel thread 가 block 되었을 때 이것을 사용하는 모든 user thread 가 block 된다는 문제를 해결하기 위해
• 하나의 Process 에 여러 kernel thread 를 할당해서 thread library 에서 사용하게 하는 아이디어이다.
• 이렇게 하면 하나의 user thread 가 block 이 되었을 때, 해당 kernel thread 도 block 이 될 텐데 사용할 수 있는 kernel thread 가 몇개 더 있으므로 남은 kernel thread 를 나머지 user thread 에 붙여서 돌아가게 할 수 있다.
• 근데 이 방법은 문제가 있다..
  • Thread lib 에 user thread 들을 scheduling 하는 user level scheduler 가 있고
  • Kernel 에 kernel thread 들을 scheduling 하는 kernel level scheduler 가 있는데
  • 이 둘간에 소통이 안되기 때문에 문제가 발생하게 된다..
  • 대표적으로는 다음과 같은 문제가 발생할 수 있다.
    • User thread 가 놀고 있는데 여기에 kernel thread 를 할당해주거나
    • User thread 가 lock 을 잡고 작업을 하고 있는데 여기에서 kernel thread 를 뺏거나 등등

Scheduler activation §

#draft Scheduler Activation 논문 에서 더 자세하게 살펴보자.

• 위에서 소개한 thread 구현 방식들의 문제를 해결하고자 만든 새로운 threading design
  • SOSP‘92 에서 소개된 뒤 ToCS 저널에 올라갔다고 한다.
• Thread 가 block 되었을 때 다른 thread 들도 다 멈춰버리는 상황을 막되, user-level thread 의 가볍다는 장점은 살리자 라는 것이 목표

Pain point §

• Kernel level thread, User level thread 모두 문제가 있어서 M:N Model 이 나오게 된건데 여기에도 문제가 있다.
• M:N Model 에서의 문제는 layer 들 간의 소통이 효율적이지 않은 것에서부터 발생하는 것이라고 볼 수 있고, 여기에서 정보를 서로에게 더 많이 제공해서 소통을 원할하게 하는 것이 이 논문의 idea 이다
  • 이러한 layer arch 에서의 소통 해소를 위해 정보를 더 많이 주는 것이 약간 유행이랜다
• M:N 모델을 효율적으로 사용하기 위해 kernel abstract 를 변경하는 것이 이 논문의 contribution 이다
• 그리고 어느 정도까지 서로에게 정보 공유를 할지도 고려할 점

Scheduler activation §

• 이놈은 user thread 에 대한 정보를 좀 더 갖고 있는 kernel thread 이다
  • 즉, kernel thread 의 확장판인 것
• 이 SA 는 두가지 스택을 필요로 한다고 한다:
  • Kernel stack: syscall 에 사용된다.
  • User stack: upcall 에 사용된다.
    • 다만, 이 user stack 은 user thread 에서 사용하는 stack 이랑은 또 다른놈이다.
• 그리고 Activation Control Block 이라는 추가적인 자료구조도 필요하다고 한다.
  • User level thread 에 대한 문맥 정보 저장? 잘 모르겠음
• M 개의 user thread, N 개의 kernel thread (= virtual process, = scheduler activation) 가 있을 때
  • User thread 를 kernel thread 에 scheduling 하는 것은 user scheduler 가
  • Kernel thread (sa) 를 cpu 에 scheduling 하는 것은 kernel scheduler 가 담당한다.

syscall API §

• 이것의 구현을 위해 다음의 syscall 두개가 추가된다.
• 다만 생각해야 할 것은 이 syscall 들은 그냥 “hint” 일 뿐이다; 이 부탁을 kernel 이 들어줄지는 상황에 따라 다를 수 있다.

add_processor() §

• User runtime lib 은 이제 add_processor() syscall 이 있어서 user thread 를 돌릴 수 있는 sa 들을 더 달라고 요청할 수 있다
  • 근데 kernel 입장에서는 user 를 믿을 수 없기 때문에 무조건 주지는 않고 적절히 상황을 봐서 줄지 말지 정한다.

idle() §

• User-level scheduler 는 runnable thread 보다 더 많은 SA 가 할당되어 있을 경우, 이정도까지 필요하진 않다고 idle() 로 kernel 에게 알려줄 수 있다.
  • 물론 kernel 은 idle() 을 받아도 바로 SA 를 뺏지 않을 수도 있다; reallocation overhead 를 줄이기 위해 그냥 냅둘 수도 있다.

upcall API §

• syscall 과 반대로 kernel 이 user level scheduler 에게 찌르는 것을 upcall 이라고 하는데,

Block upcall §

• 우선 Thread 가 block 되었다는 것을 알려주는 upcall 은 다음과 같다:
  • User thread 가 뭔가를 하다가 block 되면 당연히 kernel 로 들어오게 되니까 kernel 은 이놈이 block 되었다는 것을 알고 있다
  • 하지만 user level scheduler 는 이것을 모르고 있고, 따라서 kernel 이 이 user thread 가 block 되었음을 user level scheduler 에게 알려준다
  • 그리고 이렇게 block 된 후에 kernel 에서는 block 된 놈에서 sa 를 뺏게 되는데, 이 upcall 덕분에 user level scheduler 의 입장에서 기존의 user thread 에서 sa 가 빼앗겨서 다른 user thread 를 돌릴 수 있다는 것을 인지하게 되고, 그에 따라 scheduling 할 수 있다

Unblock upcall §

• 그리고 그 user thread 가 block 에서 풀렸을 때 kernel 은 또 이것을 user level scheduler 에게 알려주게 되는데
  • 근데 이 것을 user level scheduler 에게 알려주는 방식이 좀 특이함
  • 잘 돌고 있는 user thread 하나를 더 sa 를 뺏어서 “원래 block 되어있었던 놈이 깨어났고 이놈이 깨어났다는 것을 알려주기 위해 하나 더 빼앗았다” 라고 user level scheduler 에게 알려주는 식이다.
  • 즉, (1) 지금은 깨어난 원래 block 되어있었던 놈 (2) 깨어난 것을 알려주기 위해 sa 가 뺏긴놈 을 user level scheduler 에게 알려준다

• 그리고 user level scheduler 는 알려주기 위해 뺏은 SA 를 깨어난 thread 에게 할당한다.
  • 즉, 깨어난 놈에게 다시 SA 를 붙여주기 위해 하나를 뺏었다고 생각할 수 있다.

Preempt upcall §

• 프로세스가 add_processor syscall 을 했는데, SA 가 부족한 경우에 다른 프로세스로부터 SA 를 뺏어서 할당할 수도 있다.
• 아래 예시는 B 에서 SA 가 필요해 add_processor syscall 을 하고, A 의 것을 뺏는 상황이다:

• 그럼 이 SA 가 뺏겼다는 것을 A 에게 알려주는데, 이때에도 unblock 상황과 비슷하게 SA 를 하나 더 빼앗는 식으로 알려준다.

• 이때에도 SA 를 빼앗아서 빼앗긴 thread 에게 연결시켜 준다.
  • 즉, 빼앗긴 thread 에게 SA 를 붙여주기 위해 하나를 더 빼앗는 것이라 생각할 수 있는 것.

Critical section §

• critical section 에 들어간 user thread 가 preemption (sa 빼앗김) 되면 deadlock 이 발생할 수도 있기 떄문에 + 여기에 아무도 못들어가기 때문에
• critical section 이 무사히 빠져 나올때 까지만이라도 계속 실행될 수 있게 한다
• critical section 의 정보는 user 만 알고 있는데 어떻게 이렇게 할 수 있었는지는 논문에서 확인하자..#draft

Evaluation §

• upcall performance 가 topaz 라는 thread 보다 5배 느리다?? 왜쓰노 이거
• n-body 라는 mem에 큰 array 를 만들어서 입출력하는 workload 를 사용한다

몇가지 TMI.. §

• sa 는 mechanism 이고 policy 는 allocation 등? 논문에 나온다
• solaris 에서 이것을 차용했다고 한다
• solaris 에서 lwp 가 이 sa 에 대응되는 개념
• 하지만 이 sa 는 더이상 사용되지 않는다 - solaris 9 가 되며 이것을 폐기했고 다시 1:1 로 돌아갔다
• linux 진영에서는 IBM 이 POSIX 를 지원하는 M:N 모델을 개발하려 했고 (NGPT), redhat 이 1:1 을 지원하는 thread 개발을 시작(NPTL) - 결국 redhat 이 이김
• 요즘은 대부분의 os 가 1:1 이다
• linux 도 thread 각각이 task stuct 를 가지며 마치 process 처럼 돌기 때문에 1:1 이다