2. Kernel and Thread, Event-driven approach

[Study/OS] - 1. μ-Kernel, Interrupt handling

1. Concurrency를 위한 Approach

Processes

실행시 프로그램의 instance

Threads

프로그램에서 실행되고 있는 일련의 instruction들

• code, data, file들은 공유
• register와 stack은 각자 보유   

Events

프로그램에서 요구되는 모듈화된 각 작업들

• 기존의 process나 thread와는 다른 새로운 방식
• FSM과 같은 기능을 제공 (event가 들어올 경우 해당하는 handler가 일을 처리)

2. Thread 종류 

Kernel Threads (One-to-one model)

커널이 직접 커널 공간에서 threads 생성, 스케줄링, 관리

장점

• process 보다 cheaper
• I/O overlap 가능
• 멀티코어에서도 실행 가능

단점

• User therad 보다 expensive (느리다)
• 모든 요구에 충족되어야 되기 때문에 일반화 되어야 함

User Threads (Many-to-one model)

커널의 지원없이 유저 공간에서 threads 생성, 스케줄링, 관리

thread 라이브러리에 의해 구현

• Asynchronous I/O : block 해놓으면 다른 threads 가 resource를 사용하지 못한다

장점

• Thread간 전환 할 때 커널 스케줄러를 호출할 필요가 없어 context switch가 적다
• 유연성있다
• 이식성이 있다

단점

• 프로세스내의 한 thread가 kernel로 진입하는 순간 나머지 thread 들도 전부 정지 (OS는 인식하지 못한다) ~ 프로세스 단위
• CPU가 아무리 많더라도 커널 모드에서 thread 단위로 스케줄이 안되므로 각 CPU에 효율적으로 thread를 배당 할 수 없다

관련자료

• thread에 대한 공방전.... http://kldp.org/node/295 ... 좋은 공부가 되었습니다 :D~ 
• p.s. thread vs event 해주실 분 없으신지?
  

3. 참고 논문

Schedule activation: Effective Kernel Support for the User-Level Management of Parallelism, TOCS (1992)

1. Motivation  

기존 Thread 방식에 각자 문제점이 존재

Many-to-one Models

• 장점 : threads 관리는 사용자 공간에서 행해지므로 효율적
• 단점 : threads 가 blocking system call 할 경우 전체가 다 block

One-to-one Models

장점 : 하나의 thread가 blocking system call을 하더라도 다른 thread 동작

• 단점 : 사용자 thread를 생성할 때 마다 kernel thread 생성 (성능 저하)

2. Objective

두 가지 장점을 합친 thread 방식 필요 (M:N threads - M kernel threads and N user-level threads)

• 여러 개의 User-level threads를 그보다 작거나 같은 수의 kernel threads와 연결
• 필요한 만큼 많은 사용자 threads 생성 ~ 상응하는 kernel thread 가 멀티코어에서 병렬로 수행

3. 기본 approach

Upcall 과 system call을 사용하여 쌍방간의 communication이 월활할 수 있도록 도와줌  

• Upcall : 커널 함수에서 사용자 함수를 호출 with user-level stack
• System call : 사용자 함수에서 커널 함수를 호출 with kernel-level stack
   

4. Problem

M:N model은 너무 복잡하다

Signal handling

concurrency 관리

User-level scheduler에서 internal lock으로 인한 확장성 저해

Linux threads 에선 NPTL(1:1) vs. NGPT(M:N) 경쟁을 하다 NGPT 프로젝트가 끝나면서 NPTL로 통일  

Threads vs. Events

SEDA : An Architecture for Well-Conditioned, Scalable Internet Services, SOSP (2001)

(Event-based 입장)

1. Motivation

• 최근 인터넷 서비스 제공 측면에서 대규모의 concurrency를 요구
• 서비스 페이지들이 동적이고 유연성이 필요하도록 바뀌고 있음
• 하지만 기존 thread 기반의 방법으로는 대규모의 concurrency를 처리하는데 한계가 있음

2. Objective

Event 기반의 방법을 사용한 새로운 framework가 필요 - SEDA (Staged Event Driven Architecture)

3. SEDA design principle

독립적인 Stage들이 존재

• Event queue를 통해 작업을 받아 Event handler에서 event를 fetch
• Stage에 속한 controller에서 thread pool에서 동작할 thread 수를 동적으로 조정 및 queue에 입력된 event 확인
• 해당 stage에서 처리할 작업만 하고 다른 stage로 위임
  

4. 주장하고 있는 장점

• 대규모의 concurrency 처리가 가능 (graceful degradation)
• Apache는 대규모의 요청이 들어올 경우 급격한 성능저하를 보여줌 (실험결과)
• 개념상의 modularity 향상

5. Problem

• 구현하기 어렵다 (code modularity 가 떨어짐)
• 실험에서 사용된 환경에 일관싱이 없음
• 다른 논문에서 반박 ~ 새로운 환경에서의 실험 결과 없음 (eg. Capriccio)

Capriccio : Scalable Threads for Internet Services, SOSP (2003)

(Thread-based 입장)

1. Motivation

• SEDA와 같은 event 기반의 서버는 thread 기반의 서버보다 좋다는 편견이 존재
• Event 기반의 서버는 thread 기반에 비해 단점이 많다.

2. Objective

향상된 thread 기반의 framework를 제시하여 event 기반의 서버가 더 효율적이라는 주장에 반박

3. Capriccio design principle

• Cooperative user-level thread 사용 (thread 기능의 확장을 위해)
• Linked stack 사용 (Stack 낭비를 줄이기 위해 동적 스택 적용)
• Resource-aware 스케줄러 (프로그램의 제어 흐름에 대한 정보를 사용

이 기술들을 사용하여, event 기반의 시스템보다 더 큰 concurrency를 제공한다고 주장

4. Problem

• wrapper layer에서의 오버헤드와 SMP 환경에서의 비효율성 극복하지 못함
• Resource-aware 스케줄러의 경우 event 기반의 시스템과 유사

이후, SEDA 홈페이지 (http://www.eecs.harvard.edu/~mdw/proj/seda/) 에서 보여주는 바와 같이 결과를 향상시키기 위해 다른 환경에서도 실험을 많이 하였고, approach 도 수정하였다고 언급

These performance issues are not fundamental to the architecture

결국, 아직 thead 기반이 좋은지 event 기반이 좋은지 확신 할 수 없다. (연구가 필요한 부분)