OS) Chapter 4. Threads

Chapter 4. Threads

Motivation

-       대부분의 현대 application이 multithread화되어 있다.

-       Thread는 application과 함께 진행된다.

-       나눠진 thread에 의해 application과 함께 multiple task가 implemented된다.

n  Word processor example

u  Display update

u  Keystroke에 반응

u  background에서 spelling과 grammar 확인

-       Process를 만드는 것은 무겁지만 thread 생성은 가볍다

-       전통적인 process는 single thread만 갖고 있었다.

Multithreaded process는 single-threaded process와 다르게 병렬적으로 thread를 실행한다. (register와 stack을 각각 따로 가지고 있음)

Benefit

-       Responsiveness: 만약 process의 일부분이 block됐다면, execution을 계속 진행하도록 하는데, 이는 user interface에서 매우 중요한 역할을 한다.

-       Resource Sharing: thread는 process의 resource를 공유하기 때문에, shared memory나 message passing 구현이 보다 더 쉽다.

-       Economy: process creation을 만드는 데에 저렴하고, context switching하는 것보다 보다 더 적은 lower overhead이다.

-       Scalability: process는 multiprocessor architecture에 큰 장점을 가지고 있다.

Multicore Programming: Multicore or multiprocessor system은 programmer에게 다음과 같은 점들을 요구한다

ð  Dividing activities

ð  Balance

ð  Data Splitting

ð  Data dependency

ð  Testing and debugging

-       Parallelism은 증진적으로 하나의 task보다 더 많은 것을 소화할 수 있는 system을 의미한다. (multicore processor)

-       Concurrency는 progress를 만들어 하나의 task보다 더 많은 것을 소화할 수 있다. (multiprogramming)

-       Types of parallelism

n  Data parallelism: 같은 data의 subset을 이용하여 multiple core에서 same operation을 수행한다.

n  Task parallelism: core에서 thread를 distribute하는 것으로 각각 unique한 operation을 수행한다.

-       Amdahl’s Law

n  Serial과 parallel한 component를 갖고 있는 application에 additional core를 더하는 것으로 performance gain을 identify할 수 있다.

n  S는 serial portion, N을 Procession Core라고 할 경우,

n  만약 application이 75% parallel, 25% serial이라고 일 경우, single core에서 core를 하나 더 붙이면, 1.6배의 speed up 증가가 있다.

n  N이 무한으로 발산할 경우, speedup 효과는 1/S로 수렴한다.

Thread 종류

-       User thread: user level thread library에 의해 management되는 thread들 (ex) POSIX Pthreads, Windows threads, Java threads

-       Kernel thread: Kernel에 의해 support되는 thread들

Multithreading Models

-       User thread들은 kernel 위에서 support되지만, kernel의 support없이 관리된다.

-       User thread와 kernel thread사이에 반드시 relationship이 나타나야만 한다.

n  Many-to-One

n  One-to-One

n  Many-to-Many

Many-to-One

-       많은 user-level thread가 single kernel thread에 mapping된다.

-       하나의 thread blocking이 모든 thread를 blocking을 초래한다.

-       복수의 thread는 multicore system에서 parallel하게 작동되지 않는데, 그 이유는 반드시 한번에 하나의 thread만이 kernel에 존재하기 때문이다.

-       Solaris Green Threads, GNU Portable Threads에서 사용된다.

One-to-One

-       각각의 user-level thread는 kernel thread에 매칭된다.

-       Kernel thread를 만드는 user-level thread를 만든다.

-       Many-to-one보다 훨씬 더 concurrency하다.

-       process마다 thread의 숫자가 overhead를 촉진할 수 있다.

-       Windows, Linux, Solaris 9 and later

Many-to-Many

-       Many user level thread를 many kernel thread에 매칭시킨다.

-       Kernel thread의 유효한 숫자만큼 만드는 것을 OS에 허락한다.

Two-level Model

-       Many-to-Many Model을 일반적으로 따르나, user-thread에서 kernel-thread로 바로 건너뛰는 경우가 있는 Model

Implicit Threading

-       Threads의 개수가 늘어나는 것이 인기가 높아질수록, explicit thread와 함께 program correctness 보다 더 어려워졌다.

-       Programmer가 아닌 compiler와 run-time libraries를 이용하여 수행되는 thread의 생성과 관리

-       Thread Pool, OpenMP, Grand Central Dispatch

Thread Pools

-       working하길 기다리는 thread를 모아두는 pool에다가 thread를 생성한다.

-       이는 새로운 thread를 만드는 것보다 이미 있는 thread를 요청해 서비스하므로 보통 보다 더 빠르다

-       Application의 thread 숫자를 pool의 size에 bound시킨다.

-       Task를 만드는 mechanic으로부터 수행되는 task를 나누어 running task가 서로 다른 전략을 세울 수 있도록 한다. (Task가 periodically run하게 schedule될 수 있다.)

OpenMP

#pragma omp parallel => 모든 core에 thread를 전달, 한 core가 일을 빨리 처리해버리면 다음 for loop(instruction)을 해당 core가 바로 처리 => Synchronization에 의해 그 core만 계속적으로 thread working이 진행됨

Grand Central Dispatch

Threading Issues

-       Semantics of fork() and exec() system calls: fork() - Some UNIXes have two versions of fork, exec() – usually works as normal

-       Signal handling

n  Synchronous and asynchronous

n  Signal은 보통 UNIX system에서 특정한 event가 일어날 process를 가리킨다.

n  Signal handler는 signal을 process하는 데에 쓰인다.

u  Signal은 특정 event에 의해 생성된다.

u  Process에 signal이 전달된다.

u  Signal은 두 개의 signal handler 중 하나에 의해 조작된다.

l Default

l User-defined

n  모든 signal은 signal을 조작할 때 kernel을 작동시키는 default handler를 가지고 있다.

u  User-defined signal handler가 default(기본값)을 무시할 수 있다.

n  Multi-threaded을 위해 signal이 어디로 운송되어야 하는가?

u  Signal 적용이 되는 thread에 signal을 운송해야 한다.

u  Process의 모든 thread에 signal을 운송해야 한다.

u  process에서 확실한 thread만 운송해야 한다.

u  Process을 위해 모든 signal을 받는 특정한 thread를 assign해야 한다.

-       Thread cancellation of target thread: thread가 종결되기 전에 강제적으로 종료하는 것. 강제적으로 종료되어야 할 thread를 target thread라고 함.

n  Asynchronous or deferred

u Asynchronous cancellation: target thread를 즉시 종결시킨다.

u Deferred cancellation: 만약 그것을 periodically하게 종결시킬 수 있으면 target thread가 종결되도록 한다.

u Thread cancellation을 호출하는 것은 cancellation을 요구하지만, 실제적인 cancellation은 thread의 상태에 달려있다.

u  기본값은 deferred cancellation으로 오직 thread가 cancellation point에 도달했을 때만 cancellation이 일어난다.

-       Thread-local storage: Thread-local storage(TLS)는 각각의 thread에 그것의 data 복사본을 갖도록 한다. 이는 만약 사용자가 thread creation process 생성 권한이 없을 경우 유용하다.

n  이는 thread 생성시 나오는 stack 영역이 아니라 직접 만들 수 있는 area로 local variable과는 다르다.

n  Static data와 매우 유사하다. (TLS는 각각 Thread에 unique하다)

-       Scheduler Activations

n  M:M과 Two-level model 둘 다 application에 할당된 kernel thread의 갯수를 유지하기 위해 communication을 필요로 한다.

n  대표적으로 user와 kernel thread 사이의 중간체 data structure인 lightweight process(LWP)를 사용한다.

u Process가 작동하려는 user thread를 schedule할 때에 가상의 processor로 나타난다.

u 각각의 LWP는 kernel thread에 부착된다.

n  Scheduler의 활성화는 upcall을 제공한다. – upcall: kernel로부터 thread library의 upcall handler까지 향하는 communication mechanism

4.2 User-level thread와 kernel-level thread에서의 두 가지 차이점과, 다른 것들 보다 나은 점은 무엇인가?

1) User-level의 thread는 kernel에서 알지 못한다. kernel에서 user-level은 process만 알아보기 때문이다. 단 kernel-level의 thread의 존재는 kernel이 알고 있다.

2) M:1 이나 M:N mapping을 사용하여, user-level thread는 thread library에 의해 schedule된다. 이렇게 매칭된 일종의 한 segment(kernel이 읽을 땐 process다.)는 process처럼 운영이 되기 때문에 그 내부 segment의 thread들 사이에는 context-switching이 존재하지 않는다.

3) 모든 user-thread는 process에 소속되어 있는 반면, kernel-thread는 그럴 필요가 없다. 그렇기 때문에 kernel thread가 user thread보다 유지하는 데 보다 더 값비싸다. Kernel-thread는 process에 소속되어 있지 않기 때문에 multi-processor system에서 보다 더 유리한 면이 있지만, thread-switching에서 overhead가 발생한다.

4.3 kernel-level thread 사이에서 벌어지는 kernel context-switch가 발생했을 때 어떻게 작동하는 지 설명하시오

참조: http://genesis8.tistory.com/242

User-level thread는 kernel context-switch가 발생하지 않는다.

먼저 kernel에서는 process 단위로 읽기 때문에 user-level thread의 존재를 알지 못하고 그 전체인 process 단위로 보게 된다. 그렇기 때문에 각기 다른 thread끼리 context-switch할 필요 없이 전체 processing을 하는 것이다. 이러한 thread를 user-level에서 스케쥴링하기 때문에 parallism하지 않고 concurrent하다 (multi-processor에서 효율적이지 않음(프로세스 단위로만 배당이 됨))

반면에 kernel context-switch 같은 경우에는 thread를 process취급하여 parallism하게 돌릴 수 있다는 장점이 있다. 하지만, kernel에서 kernel로 넘어갈 때, 쓰케쥴 스케줄러를 다시 불러오거나, system call같은 overhead가 있기 때문에 연산이 길어지면 전체 프로세스의 응답성이 확 떨어진다.

그렇기 때문에 kernel thread에서의 context switch은 CPU의 register를 thread로부터 값을 저장하고, 새로운 thread의 CPU register의 값을 다시 저장하는 과정이 필요하다.

4.4 Thread가 생성될 때 어떠한 자원이 소모되는가? 또한 process가 만들어질 때와는 어떠한 차이점이 있는가?

쓰레드가 process보다 보다 더 작은 단위이기 때문에, process 생성보다 더 적은 자원을 사용한다. Process를 만드는 것은 보다 더 큰 data structure인 PCB를 할당해야 한다. PCB는 memory map, open file의 list, 환경 변수들을 포함하고 있다. Memory map을 할당하고 관리하는 것이 가장 시간 소요가 가장 크다. Thread를 만드는 것은 register set, stack, priority와 같은 작은 data structure 생성만을 요구한다.