Intro
병렬 프로그래밍을 구성하기 위해 단일 프로세서 환경에서는 process 간 메모리를 공유하는 방법을 사용했지만, 멀티 프로세서가 등장하며 thread라는 개념이 제시되었다. thread는 stack, PC, thread ID 정도만 다르고 process의 주소 공간을 공유하여 context switching이 편하고 병렬 프로그래밍에 잘 사용되고 있다. processor와 다른 실행 단위의 등장에 따라 thread를 관리할 주체가 필요한데, 이 주체에 따라 application이 관리하는 user-level thread와 kernel이 관리하는 kernel thread로 구분할 수 있다. user-level thread는 빠르고 flexible하지만, OS가 thread가 있는지 몰라서 성능이 저하되거나 잘못된 동작을 할 수 있다. kernel thread는 system 통합 문제는 없지만 느리고 flexible하지 못하다. 따라서 본 논문은 두 방법의 장점을 합친 SA(Scheduler Activation)를 제시한다.
여담으로 학부 OS 때 user thread, kernel thread, user-level thread, kernel-level thread의 개념에 대해 들었는데 그 개념과는 약간 다른 것도 같다.
Contribution
User-level thread와 kernel thread의 장점을 모은 새로운 thread 관리 메커니즘을 제시
- kernel thread의 성능이 user-level thread보다 안 좋음을 주장
- user-level thread를 다른 system service화 통합할 때에 생기는 문제가 user-level thread에 대한 kernel support가 부족하기 때문임을 주장
- user-level에서의 성능과 유연성에 대한 이점을 잃지 않으면서 kernel thread와 동일한 기능을 제공하는 새로운 kernel interface와 user-level thread 패키지 SA(Scheduler Activation) 제시
Thread의 관리 방법
User-level thread
Application에 있는 runtime library에 의해 관리되는 thread를 의미한다. 각 process (processor가 아니다) 를 virtual processor로 보고, process가 ready queue로부터 실행할 thread를 실제 processor(이하 physical processor)에 실행하게 한다. 따라서 processor가 보기에는 평소처럼 process의 단위로 스케줄링하는 것처럼 보인다.
[장점]
- fast: kernel의 개입이 필요없기 때문에 성능이 좋다. (procedure call 정도의 비용이 든다고 한다.)
- flexible, portable: kernel의 수정 없이 application level에서 수정이 가능하다. 따라서 실행 환경이나 프로그래밍 모델에 따라서 customize가 가능하다.
[단점]
실제 multiplexing은 physical processor에서 일어나므로, virtual processor와 physical processor 간에 차이가 있는 경우 성능이 저하되거나 잘못된 동작을 할 수 있다. 즉, OS가 thread가 있는지 모르기 때문에 poor decision을 내릴 수 있고, processor이기 때문에 여러 CPU로 실행할 수 없다.
- block되었을 때 다른 thread를 실행할 수 없다.
- kernel은 thread의 priority 정보를 모르므로 preemption이 불가능하다.
- kernel이 lock 정보도 알 수 없다.
Kernel thread
kernel이 직접 thread table을 가지고, 스케줄링한다.
ex) Mach, Topaz, V
[장점]
- functionality: kernel이 각 thread를 physical processor에 직접 schedule하기 때문에 system 통합 문제가 없다.
- I/O와 computation의 overlap이 가능하다.- 여러 CPU의 사용도 가능하다.
- process를 통한 병렬화보다는 비용이 작다. (10배 정도 좋다고 한다.)
[단점]
일반적으로 user-level thread보다 10배 정도 더 cost가 필요하다고 한다.
-
thread 관리 operation에 대한 access cost
같은 address space에서 thread만 바꾸더라도 모든 thread operation에 대해 protection boundary를 통과해야 한다. 이 과정에서 kernel trap이 발생하며 버그를 체크해야 한다.
→ 컴파일러 기술을 사용해 코드를 inline으로 확장하여 user-level thread를 사용하면 저렴하면서도 안전성이 보장된다. 이 경우 address space boundary가 user-level thread가 잘못 쓰는걸 방지해준다. -
cost of generality
Thread를 범용적으로 사용하기 위해서는 kernel이 모든 application에 필요한 기능을 제공해야 한다. 이는 반대로 특정 기능을 사용하지 않는 application에 대해서는 overhead가 될 수 있다.
→ user-level thread는 user-level의 library를 사용하므로 flexibility가 높다. -
flexibility 부족
병렬 프로그램의 종류가 다양하기 때문에 flexibility가 중요한데, kernel thread를 사용하면 kernel 수정하는 것도 힘들고, kernel 오류 가능성도 증가시킨다.
User-level을 위한 kernel 지원
논문에서는 user-level thread에서 가지는 system 통합의 부족이 user-level thread에 의한 것이 아니라 커널 지원이 부족해서라고 주장한다.
기존 user-level thread의 poor integration
기존 user-level thread는 kernel thread의 functionality를 보여주기 어렵다. 그 이유는 user-level에서 불가능하기 때문이 아니라, kernel 지원이 부족하기 때문이다.
아래의 두 특성이 kernel thread가 user-level thread를 지원하는 잘못된 abstraction임을 보여준다.
- kernel thread는 user-level에 알려주지 않고 block, resume, preempt된다.
- user-level thread state와 상관없이 scheduling한다.
Issue 1)
application은 physical processor의 수만큼 virtual processor를 만드는데, user-level thread가 blocking request를 보내거나, page fault가 발생하면 virtual processor 역할을 하는 kernel thread도 같이 차단된다. 따라서 실행할 다른 kernel thread가 없게 되고 I/O가 끝날 때까지 대기한다.
Issue 2) time slicing
- processor보다 실행 가능한 thread가 많을 때 time slicing을 수행하면, user-level thread가 lock을 잡고 있는 동안 다른 thread들은 lock이 풀릴 때까지 기다려야 한다.
- user-level thread에서 idle인 kernel thread에 의해 선점될 수 있다.
- user-level 기준으로 priority가 높은 애가 낮은 애에 의해 선점될 수 있다.
Issue 3) 논리적 정확성을 보장하기 어렵다.
모든 thread가 processor 시간을 받는다는 가정 하에 deadlock이 발생하지 않는데. user-level thread가 고정된 수의 kernel thread에 다중화되면 이 가정이 유지되지 않을 수 있다.
Effective Kernel Support for user-level management
본 논문에서 제시하는 kernel interface는 각 application의 thread system에 virtual processor를 제공함. 이 abstraction은 아래와 같은 특징을 가진다.
- kernel은 address space에 processor를 할당하며, 할당하는 수를 완벽히 제어
- 각 address space thread system은 할당된 processor에서 실행할 thread를 제어
- kernel은 할당된 processor 수를 변경할 때 application에 알린다. 또한 user-level thread가 kernel에서 block되거나 resume할 때 (I/O 또는 page fault에 의해)도 알린다.
- user-level은 application에 더 많거나 적은 processor가 필요할 때 kernel에 알린다. kernel은 이 정보를 사용해서 프로세서를 할당한다. 근데 processor 할당 결정에 영향을 주는 애들만 보내기 때문에 성능이 저하되지는 않는다.
- application은 virtual processor를 programmer에게 transparently하게 제공한다. 따라서 사용자는 kernel thread를 사용하는 것과 다름이 없다.
남은 부분은 이러한 abstracion을 위해 구현해야 할 아래 내용들에 대해 설명한다.
- kernel event를 user-level thread system에 vector화하는 방법
- application에서 kernel에 제공하는 정보
- user-level spinlock 처리 방법
SA: Vectoring of Kernel event
본 논문은 Scheduler Activation을 이용해 kernel event를 vector화한다. SA라는 이름은vectored event가 user-level thread system에게 어떤 processor에서 어떤 thread를 스케줄링하게 고려하게 하기 때문에 이름붙였다고 한다.
[SA의 3가지 역할]
- kernel thread가 수행하는 것과 동일하게 user-level thread를 실행하기 위한 context를 제공
- user-level thread system에 kernel event를 알린다 (이를 upcall이라고 한다).
- thread가 kernel에 의해 중지될 때 activation의 현재 user-level thread의 context를 저장하기 위해 kernel에 공간을 제공
[SA의 2가지 실행 스택]
- application address space 쪽
- user-level thread가 실행되면 user-level stack이 할당된다.
- user-level scheduler가 실행될 때 각 SA에서 실행 중인 user-level thread의 record를 유지한다.
- kernel 쪽
- kernel쪽의 SA stack에서 kernel을 호출하면 kernel stack을 사용한다.
- activation control block을 통해 kernel에서 block되거나 preemption될 때 context를 유지한다.
프로그램이 시작되면 kernel은 SA를 만들고 processor에 할당한 뒤 entry point에서 application adress space로 upcall을 보낸다. user-level thread system은 upcall을 받고 SA로 initialzie한 후 application thread를 실행하는 context로 사용한다. 첫번째 thread가 실행되면 더 많은 user-level thread를 만들고 추가 프로세서를 요청할 수 있다. 이 경우 kernel은 SA를 새로 만들고 upcall을 보낸다.
[kernel thread와의 차이점]
SA의 user-level thread가 kernel에 의해 중지될 때 kernel이 바로 resume하지 않고, user-level에 알리기 위해 새 SA를 만든다. 이후 user-level thread system이 이전 SA에서 thread state를 제거하고 이제 사용할 수 있음을 kernel에 알리고 새로 돌릴 thread를 결정한다.
(kernel thread는 event 없이 대기하다가 resume한다.)
따라서 SA를 사용하여 할당된 processor 수만큼 실행중인 SA가 정확히 있다는 invariant를 유지할 수 있다.
Upcall
event들을 vector화하여 upcall을 통해 여러 event를 한번에 보낸다.
Case 1 : IO request, completion
- kernel이 application에 2개의 processor를 할당하고 Add procesor upcall을 보낸다.
- user-level system이 ready queue에서 2개의 thread를 골라서 실행한다.
- thread 1이 kernel에서 block되면, thread 1을 실행하던 processor를 가져와서, block upcall을 보낸다.
- IO가 완료되면, 완료되었다는 것을 알리기 위해 processor가 필요하므로 실행중인 processor 하나를 preemption해서 사용해서 unblock, preempt upcall을 보낸다. (thread의 register state는 interrupt나 page fault handler에 의해 kernel에 저장되는데, 이 정보를 같이 보내줌)
- user-level에서 upcall을 보낸 SA에 ready queue에서 thread를 골라서 실행한다.
Case 2 : 한 address space로부터 processor를 가져와 다른 address space에 주는 경우
- kernel은 processor interrupt를 보내고, SA를 중지
- 다음 processor를 사용해 새 address space에 Add processor upcall
- 이전 space에서 실행 중인 SA 하나를 선점해서 processor preemption upcall
- 이전 space의 user-level scheduler가 upcall 발생한 SA에 실행할 thread 결정
- processor를 뺏을 때 이전 address space에 허가를 얻지 않아도 되지만, 이전 address space에 선점이 일어났다는 것은 알려야 한다.
- 마지막 processor가 선점되는 경우에는 kernel이 재할당할 때까지 upcall하지 않는다.
- cache locality를 사용하는 경우에는 어떤 프로세서인지도 upcall에서 명시한다.
[첨언]
- thread에 우선순위가 있는 경우 추가 선점이 발생할 수 있다. user-level이 각 processor에서 실행중인 thread를 알기 때문에 가능하다.
- kernel이 context를 중지하고 저장하는 것처럼 보이지만 정확히는 SA에서 발생한다. application은 SA 위에서 parallelism을 자유롭게 구축할 수 있으며, kernel 쪽은 kernel thread에서와 동작이 동일하다.
- 실행 중인 user-level thread가 없을 때 preemption이나 page fault가 발생해도 SA가 제대로 동작한다. 이 경우 kernel에 저장되는 state는 thread manager의 state이다.
- kernel에서 block된 user-level thread가 I/O가 끝났을 때 더 실행해야 할 수도 있는데, 이 경우 kernel은 thread가 다시 block되거나 kernel을 떠날 때까지는 재개한다. 이 때 kernel은 upcall에 이 정보를 알린다.
User-level event에 따른 processor allocation
합리적인 processor 할당은 각 address space가 사용 가능한 parallelism을 기반으로 해야 한다. 따라서 본 논문에서는 SA에서 priority를 고려하고 runnable thread가 있는 경우 idle하지 않도록 보장하는 policy를 제안한다.
Point: user-level이 모든 thread 작업을 알릴 필요는 없고 프로세서 할당 결정에 영향을 주는 것만 알려도 된다
address space는 processor보다 runnable thread가 많거나 반대의 상황으로 전환될 때 system call을 통해 kernel에 알린다. 하지만 system call의 수행이 불가능한 아래의 경우에는 kernel이 반영하지 않는다.
- 이미 모든 프로세서가 사용중인 경우 Add more processors 수행 불가
- system에 다른 task가 없는 경우 idle processor를 없애지 않는다.
Add more processor system call이 오면 idle processor가 있는 address space를 검색하고 있으면 넘겨준다. 근데 이 경우 application이 malicious해서 계속 추가 프로세스를 요청할 수도 있다. 따라서 process allocator는 더 적은 수의 processor를 사용하는 address space를 선호하며, 많이 쓰는 address space에는 processor를 포기하도록 장려한다.
반대로 전체 processor보다 thread 수가 적은 경우에는 재할당의 overhead를 피하기 위해 idle processor를 thread가 새로 생길 가능성이 높은 address space에 남겨놓는다.
(응답형 서비스의 경우에도 서비스 시간이 길어지면 priority을 줄이는데 이것과 유사하다고 한다.)
Critical Section
user-level thread가 block되거나 preemption되었을 때 critical section에 있었을 수 있다. 이 경우 아래의 문제가 생긴다.
- 다른 thread가 해당 lock에 대해 spin하면서 성능 저하
- deadlock (선점된 thread가 ready queue에 있는 애가 acquire하는 lock을 잡고 있는 경우)
또, critical section이 lock으로 안 잠겨있는 경우에도 문제가 발생한다.
일반적으로 deadlock을 해결하기 위해 deadlock이 일어나지 않도록 하는 prevention과, deadlock이 일어났을 때 복구하는 recovery 방법이 있다.
[Prevention 방법]
kernel과 user-level 간 scheduling, locking protocol을 사용한다. 하지만 이 경우 아래와 같은 이유로 효율적이지 않아서 SA에서는 사용하지 않는다.
- kernel이 address space의 priority semantic을 위반 → user-level에 processor allocation 권한을 부여해야 한다.
- page fault를 예방하기 위해 critical section에 있는 동안 access 가능한 모든 virtual page를 physcial memory에 고정해야 한다.
[Recovery 방법]
- upcall이 preemption이나 unblock을 알리면, thread system이 thread가 critical section에서 실행 중인지 확인한다.
- critical section에서 실행 중이었으면 user-level context switch를 통해 일시적으로 계속된다.
- critical section이 끝나면 user-level context switch로 upcall에 제어 포기를 알린다. 동시에 thread를 ready queue로 다시 옮긴다.
이 경우 lock을 잡고 있는 thread를 끝까지 실행하기 때문에 lock은 해제된다고 보장할 수 있다. SA에서도 recovery를 채택한다.
Implementation
멀티프로세서용 OS인 Topaz에 아래의 수정을 했다고 한다.
- thread를 block, resume, preemption한 경우 upcall 수행
- address space에 processor를 명시적으로 할당
user-level thread package인 FastThreads에 아래의 수정을 했다고 한다.
- upcall 처리
- interrupted critical section을 resume
- processor 할당 결정에 필요한 정보를 Topaz에 제공
[Processor allocation policy]
- priority를 고려
- processor가 idle 상태가 되지 않도록 보장
- priority가 가장 높은 address space에 균등하게 분배
- 모든 프로세서를 사용하지 않는 경우 다음 priority에 분배
- 프로세서 수가 priority가 동일한 애들의 정수배가 아니면 time slicing한다.
기존 Topaz application과의 호환성을 위해 Topaz kernel thread를 지원하긴 한다고 한다. kernel thread를 사용하는 application과 SA를 사용하는 application이 동일하게 processor에 대해 경쟁한다. 또 SA의 동작으로 processor의 static partitioning이 필요하지 않다고 한다.
[Thread Scheduling Policy]
kernel은 application이 병렬 처리를 관리하는 자료 구조에 대한 지식이 없다. application이 policy를 customize 가능하다. FastThread의 경우 cache locality를 위해 LIFO로 ready list를 구현했다고 한다.
추가 고려 사항들
[critical section 관련]
user-level thread가 preempt될 때 critical section 동안 계속 실행하기 위해 user-level thread system이 lock 여부를 알아야 한다. 이를 구현하는 방법은 critical section에 들어갈 때 flag를 설정하고 떠날 때 flag를 끄면 된다. 근데 page fault나 preemption은 드물게 일어나는데 flag 설정에 의한 overhead 때문에 common case에 대해 latency가 더 커진다. 따라서 common case에 대해 overhead를 줄이는 solution을 채택한다.
low-level critical section의 C source code에 exact copy를 만들고, 컴파일한 뒤 복사본의 끝부분에 processor를 resumer에게 돌려주는 코드를 추가한다.
이 경우 정상 실행할 때에는 원본 코드를 사용하고, preemption이 일어나면 critical section에 있는지 확인한 뒤, 맞다면 복사본을 실행한다. 따라서 정상적인 실행에 대해 overhead가 없다.
[SA 관리]
새 SA를 만드는 것도 자료 구조를 만들고 intialize하느라 cost가 든다. 따라서 discard된 SA를 캐싱해놓고 재사용할 수 있다. 또한 discard된 SA를 모아서 한번에 kernel에 반환할 수 있다.
Performance
functionality, flexibility는 앞에서 설명하여 평가하지 않는다. (특별히 평가할 방법도 없긴 하다.)
성능 면에서 아래를 평가한다.
- user-level thread operation의 cost는? (fork, block, yield)
- kernel과 user level의 통신 비용에 대한 cost는? (upcall)
- application의 성능에 대한 전반적인 영향은?
[Thread performance]
원래의 FastThread에 비해 null fork, signal-wait에서 latency를 거의 유지.
- null fork : 3 µs 저하가 있는데, 사용 중인 thread 수를 늘리거나 줄이고 kernel에 알려야 하는지 여부를 결정하는 시간이 추가되기 때문이라고 한다.
- signal-wait : 5 µs 저하가 있는데, 위의 요인과 preemption thread가 resume되었는지 확인하는 cost 때문이라고 한다.
[Upcall performance]
원래 upcall 성능이 kernel thread의 overhead랑 비슷할 줄 알았는데 훨씬 느리다고 한다. signal-wait time은 2.4ms로 Topaz보다 5배나 나쁘다고 한다.
저자들이 변명하기로는 Topaz는 assembly로 잘 짜여져 있는데 우리는 Modula-2 + 로 짜서 그렇다고 한다..
어쨌든 upcall에 의한 overhead에 의해 아래의 application 성능 측정이 production SA 구현보다 약간 느리게 나온다.
Application performance
Topaz + kernel thread, Topaz + FastThreads, Topaz + SA를 비교
kernel service를 최소한으로 사용하는 경우, 원래 FastThread만큼 빠르게 사용할 수 있다.
[I/O가 거의 없고 memory 100% 다 쓸 수 있는 경우]
- 프로세서 하나를 쓰면 3개 다 sequential implementation보다 안 좋다. 병렬화하기 위해 thread를 만들고 동기화하는 overhead가 추가되기 때문
- 프로세서가 추가됨에 따라 kernel thread는 점점 speedup이 없어진다. kernel thread는 contention이 있는 경우 thread가 kernel에서 아예 block되고 사용 불가능해지기 때문에 overhead가 큼.
- user-level thread는 계속 빨라진다.
4, 5개일 때 Topaz에서 주기적으로 깨어나는 daemon 때문에 FastThead에서보다 좀 빠르다고 한다.
[I/O를 수행해서 kernel 개입이 필요한 경우]
- 셋 모두 처음에는 execution time이 천천히 나빠지다가 working set이 memory에 fit되지 않으면 급격히 나빠짐.
- FastThread를 사용한 application이 더 빨리 나빠지는데, user-level thread가 block되면 virtual processor 역할을 하는 kenrel thread도 block되어 IO하는 동안 해당 processor를 못 쓰게 되기 때문
- kernel thread와 SA는 IO와 computation을 overlap할 수 있기 때문에 급격히 나빠지지 않음.
[N-body application에 대한 성능 비교]
SA가 훨씬 좋다. 원래 application이 multiprogramming될 때 OS가 virtual processor 역할을 하는 kernel thread를 시분할한다. SA는 lock이 걸린 thread가 schedule이 안 되는 동안 idle 상태일 수 있기 때문이라고 한다.
Reference
- Thomas E. Anderson, Brian N. Bershad, Edward D. Lazowska, and Henry M. Levy, “Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism,” TOCS, 1992.
