Thread and Concurrency 스레드와 병행성

Concurrency in Process Model

• 프로세스 모델에서의 동시성
  (+) 다중 CPU를 제공하는 최신 다중 코어 시스템에서 스레드 사용을 통한 병렬 처리의 기회를 식별하는 것이 점차 중요

• Use of concurrency within an application has several advantages.

  • 응용 프로그램 내에서 동시성을 사용하면 몇 가지 이점 존재함

• Concurrency can be implemented by structuring an application as a set of concurrent processes (e.g., using fork()).

  • Concurrency(동시성) 은 애플리케이션을 동시 프로세스 집합으로 구성하여 구현 가능

Overhead in Process Model

• Each process is completely independent (need IPC via kernel).
• 각 프로세스는 완전히 독립적 (커널을 통한 IPC 필요).
  => BAD !! : Too heavy for process creation, context switching.

What is Thread ?

• A flow of control within a process that consists of a PC, a register set and a stack space (similar to process – sub-process).
  An individual thread has at least its own register state, and usually its own stack.
• 스레드(Thread)는 CPU 이용의 기본 단위이다.
• 개별적인 스레드는 ID, PC(Program Counter), 자신만의 레지스터 집합, 스택으로 구성
• 스레드는 ID, PC, stack, 레지스터 집합으로 구성되어 있다.
  
  
• A basic unit of CPU scheduling.
• CPU 스케줄링의 기본 단위.
  
  
• Multiple threads can be created within a same process and share code, address space, and operating resources for the process.
• 또한 스레드는 같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 그리고 열린 파일이나 신호와 같은 운영체제 자원들을 공유
  
  
• Thread makes creation and switching inexpensive (use small context).
  
  
• The environment in which a thread executes is called task, and a traditional (heavyweight) process is equal to a task with one thread.
• 스레드가 실행되는 환경을 task !
• (올드한) 기존의(heavyweight) 프로세스는 스레드가 하나 있는 작업과 동일
  
  

• 보면 각 쓰레드는 공유자원은 공유하되, 레지스터 / 스택 공간은 각각 지닌다.

(+) 전통적인 프로세스는 하나의 제어 스레드를 가지고 있지만, 현대 프로세스는 다수의 제어 스레드를 가지고 있기 때문에 해당 프로세스는 동시에 하나 이상의 작업을 수행할 수 있다.

Multithreading (Multiple Cores or Processors)

Achieve parallelism 병렬성

- Two tasks are parallel if they are performed at the same time. - 두 작업이 동시에 수행되는 경우 두 작업은 병렬 - Threads of a process can even execute in parallel on different processors or cores (multicore). - 프로세스의 스레드는 서로 다른 프로세서 또는 코어에서 병렬로 실행될 수도 - Parallelism = no. of CPUs (cores) 병렬성의 갯수는 cpu 갯수

Multithreading (Single Core or Processor)

Achieve concurrency (illusion of parallelism) 동시성

- Two tasks are concurrent if there is an illusion that they are being performed in parallel, whereas, in reality, only one of them may be performed at any time. - 두 개의 작업이 동시에 수행된다는 착각이 있는 경우, 실제로는 두 작업 중 하나만 수행되고 있지만, 두 개의 작업이 동시에 수행되는 경우 concurrent 하다고 두 task 를 명명

• Provide computation speed-up even on a single processor system because if an I/O bound thread blocks, the kernel can switch to another thread of the same process.
• I/O가 바인딩된 스레드가 차단하면, 커널이 동일한 프로세스의 다른 스레드로 전환할 수 있으므로 단일 프로세서 시스템에서도 계산 속도를 높일 수 있습니다.

---

(+) 병렬성(Parallelism), 동시성(Concurrency) 차이

• 동시성은 모든 작업이 진행되게 하여 둘 이상의 작업을 지원

• 병렬성은 둘 이상의 작업을 동시에 수행

• 따라서 병렬성 없이 병행성을 가질 수 있다. (단일 프로세서의 멀티 태스킹)

---

< Multithreading Benefits >

• ① Scalability 확장성
  (+) 규모 적응성(scalability): 멀티 프로세서 구조에서 각각의 스레드가 다른 프로세서에서 병렬로 수행될 수 있기 때문에 규모 적응성이 뛰어나다.
  • Achieve concurrency and parallelism : 동시성 & 병렬성 달성
  • Throughput (overlap computation and I/O) : 처리량 up
  • Utilization of MP Architectures

• ② Responsiveness

(+) 대화형 어플리케이션을 다중 스레드화하면 어플리케이션의 일부분이 봉쇄되거나, 긴 작업을 수행하더라도 프로그램의 수행이 계속되는 것을 허용함으로써, 사용자에 대한 응답성을 증가

• ③ Resource Sharing

(+) 스레드는 자동으로 그들이 속한 프로세스의 자원들과 메모리를 공유하기 때문에 스레드간의 통신 기법 없이 협업이 가능하다. (프로세스는 공유메모리 or IPC 기법등이 필요)

• ④ Economy

(+) 프로세스 생성보다 스레드를 활용 하는 것이 훨씬 경제적

• If all operations are CPU intensive do not go far on multithreading
  Thread creation is very cheap, it is not free
  Thread that has only five lines of code would not be useful

< Example (Multithreaded Program-1) >

< Example (Multithreaded Program-2) >

Multithreading Models

User-level threads (커널 위에서 커널 지원 없이) vs Kernel-level thread (운영체제 직접 지원)

• User-level threads run at the user level and are managed via thread library.

  • User-level threads는 사용자 수준에서 실행되며, 스레드 라이브러리를 통해 관리
  • 사용자 스레드는 커널 위에서 커널의 지원없이 관리

• Kernel-level threads run at the kernel level and are managed directly by kernel (This kernel is called multithreaded kernel).

  • Kernel-level threads는 커널 수준에서 실행되며 운영체제,커널에 의해 직접 관리
  • Most contemporary operating systems (e.g., Windows XP, Linux, Solaris, Mac OS X, etc.) are multithreaded kernels.

• Mapping between user-level threads and kernel-level threads.

  • In non-multithreaded kernels, (e.g., MS-DOS etc.) user-level threads run on a processor like a regular process
    (no mapping: kernel doesn’t aware threads).

  • In multithreaded kernels, there must exists a relationship between user and kernel threads.

  • 사용자 응용 프로그램은 사용자 수준 스레드를 생성하며, 이 스레드는 궁극적으로 CPU에서 실행되도록 커널 스레드에 매핑되어야 한다.

< 사용자 스레드와 커널 스레드의 연관 관계>

(1) 다대일 모델 (Many to One Model)

• Map many user-level threads to one kernel-level thread.
  • 많은 사용자 수준 스레드를 하나의 커널 스레드로 맵핑 (하나의 스레드는 하나의 커널에만 접근 가능)
• Mapped kernel-level threads will block if user-level threads
  make blocking system calls.
  • 한 스레드가 blocking 시스템 콜을 할 경우, 전체 프로세스가 봉쇄된다.
• Cannot fully utilize multi-cores or processors
  • 또한 한 번에 하나의 스레드만이 커널에 접근할 수 있기 때문에, 다중 스레드가 다중 코어 시스템에서 병렬로 실행될 수 없다.

---

(2) 일대일 모델 (One to One Model)

• Map one user-level thread to one kernel-level thread.

  • 각 사용자 스레드를 각각 하나의 커널 스레드로 맵핑

• No blocking problem and can utilize multi-processors.

  • 이 모델은 다중 프로세서에서 다중 스레드가 병렬로 수행되는 것을 허용

• Creating a user-level thread requires creating a kernel-level thread. -> can cause performance problem when the number of kernel-level threads is large.

• 사용자 레벨 만들려면 커널 레벨도 만들어야 함

• 사용자 레벨 만들려면 커널 레벨도 만들어야 해서 비용 up

• 하나의 스레드가 blocking 시스템 콜을 호출하더라도 다른 스레드가 실행될 수 있기 떄문에 다대일 모델보다 더 많은 병렬성을 제공

---

(3) 다대다 모델 (Many to Many Model)

• Map many user-level threads to a smaller or equal number of kernel-level thread.

  • 여러 개의 사용자 수준 스레드를 그 보다 작은 수, 혹은 같은 수의 커널 스레드로 멀티플렉스

• The number of kernel-level threads may be specific to either a particular application or a particular machine.

  • 커널 수준 스레드의 수는 특정 응용 프로그램 또는 특정 시스템에 한정될 수 있다.

• No blocking problem and can utilize multi-processors.

  • 차단 문제가 없으며 멀티 프로세서를 활용할 수 있습니다.

< Effect on concurrency and parallelism >

Many to one model :

• Creates as many threads as possible for concurrency
• but no parallelism.

병렬성 X 동시성을 위해 가능한 많은 스레드를 만듦

One to one model :

• Allows concurrency and parallelism but should be careful not to create so many threads within an application.
  -> Some systems limit the number of threads.

동시성과 병렬성을 허용, BUT 응용프로그램 내에 너무 많은 스레드가 생성되지 않도록 주의

Many to many model :

• Allows concurrency and parallelism. Developers can create as many
  user threads as possible and kernel threads can run in parallel.

• Most flexible but hard to implement (Q 이게 M 2 M 말하는 것인지? : )
  => Most operating systems prefer one to one model.

Thread Mapping and Scheduling

• 유저 레벨은 스레드 라이브러리에 의해 MAPPING
• 커널 레벨은 커널에 의해 MAPPING

---

• Parallel Execution due to
  • Concurrency of threads on Virtual Processors 가상 프로세서에서 스레드의 동시성
  • Concurrency of threads on Physical Cores 물리적 코어의 스레드 동시성
• True Parallelism
  • Single Thread : Single Core = 1:1

Thread Libraries

• Thread library provides the programmer with an API for managing threads.
• 스레드 라이브러리는 프로그래머에게 스레드 관리를 위한 API를 제공

< Thread library 구현 두가지 방법 >

(1) User-level thread library : 커널 지원 X

커널의 지원 없이 완전히 사용자 공간에서만 라이브러리를 제공하는 것

• Provides a library entirely in user space with no kernel support (i.e., no mapping).

  • 커널 지원 없이 전체 사용자 공간에 라이브러리를 제공
  • => 커널과 유저 사이의 맵핑이 필요 없음

• All code and data structures for the library exist in user space.

  • 라이브러리에 대한 모든 코드와 데이터 구조가 사용자 공간에 존재
  • 오직 라이브러리 통해서만 가능

• Usually used in a non-multithreaded kernel.

  • 일반적으로 멀티스레드되지 않은 커널에서 사용

• However, we can use it over a multithreaded kernel.

-> In this case, the outcome will be the same as running over a non-multithreaded kernel.

• 멀티스레드 커널에서 사용할 수 있습니다.
  -> 이 경우 결과는 비 멀티스레드 커널에서 실행되는 것과 같습니다.

(2) Kernel-level thread library : 커널 지원 O

운영체제에 의해 지원되는 커널 수준 라이브러리를 구현하는 것

• Provides a library supported directly by the kernel (i.e., mapping).
  • 커널에서 직접 지원하는 라이브러리(예: 매핑)를 제공
• Code and data structures for the library exist in kernel space.
  • 커널 공간에 라이브러리의 코드와 데이터 구조가 존재
• Invoking an API function typically results in a system call to the kernel.
  • API 함수를 호출하면 일반적으로 커널에 대한 시스템 호출이 발생
• Multithreading model (mapping model) depends on the OS types.
  • 멀티스레딩 모델(매핑 모델)은 OS 유형에 따라 다릅니다.

---

• Three main thread libraries : POSIX Pthreads, Windows and Java threads

• (1) POSIX Pthreads may be provided as either a user-level or a kernel-level library.

  • 사용자 레벨 또는 커널 레벨 라이브러리로 제공

• (2) Windows provides a kernel-level library.

  • 커널 수준 라이브러리를 제공

• (3) Java threads are generally implemented using a thread library available on the host system.

  • 일반적으로 호스트 시스템에서 사용 가능한 스레드 라이브러리를 사용하여 구현

Process and Threaded Models

Threading Issues 스레드와 관련된 문제들

① Semantics of fork() and exec() system calls
② Signal handling
③ Thread cancellation
④ Thread pools
⑤ Thread Local Storage (TLS)

① Semantics of fork() and exec() system calls

Fork() 및 Exec() 시스템 콜 (The fork() and exec() System Calls)

• Does fork() duplicate only the calling thread or all threads?

• 만일 한 프로그램의 스레드가 fork()를 호출하면 ,새로운 프로세스는 모든 스레드를 복제해야 하는가 아니면 한 개의 스레드만 가지는 프로세스여야 하는가?

  • If exec() is called immediately after forking, duplicating all threads is unnecessary (since exec() replaces the entire process including all threads).
  • 보통 어떤 스레드가 exec() 시스템 콜을 부르면 exec()의 매개변수로 지정된 프로그램이 모든 스레드를 포함한 전체 프로세스를 대체시킨다.
  • 따라서 forking 이후에 exec() 을 부른다면, exec()은 모든 스레드 포함한 전체 프로세스 대체시키기에 모든 쓰레드를 복제하는 것은 불필요하다.
  • If not, the process should duplicate all threads.
  • 반면, forking 이후에 exec() 이 불린 것이 아니라면 모든 쓰레드를 복제한다.
  • Some UNIX systems have chosen to have two versions of fork()
  • UNIX 시스템은 fork() API로써 이 둘의 기능을 다 지원한다.

② Signal handling 신호 처리

신호 처리

• Signals are used in UNIX systems to notify a process that a particular event has occurred.
  : 신호는 UNIX에서 프로세스에 어떤 이벤트가 일어났음을 알려주기 위해 사용

• Received depending on the source and the reason for the signal:

  • Synchronous signals 동기적
    : 신호를 발생시킨 작업을 수행한 동일한 프로세스에 전달
    : 동기식 신호는 그 신호를 야기한 스레드에 전달되어야 하고 다른 스레드에 전달되면 안 된다.

• Asynchronous signals 비동기적
  : 실행 중인 프로세스 외부의 이벤트에 의해 생성
  : 비동기 신호의 경우에는 그 프로세스 내 모든 스레드에 전달되어야 한다.
  

• Signal handling in single threaded programs (c.f. process)
  < 모든 신호는 다음과 같은 형태로 전달되어야 한다. >

  • Signal is generated by particular event.
  • 신호는 특정 이벤트가 일어나야 생성된다.
  • Signal is delivered to a process.
  • 생성된 신호가 프로세스에 전달된다.
  • Signal is handled
  • 신호가 전달되면 반드시 처리되어야 한다.
  • (either by default signal handler or user-defined signal handler).

• Signal handling in multithreaded programs (options)

  • (1) Deliver the signal to the thread to which the signal applies
    • (e.g. synchronous signals).
  • 신호가 적용되는 thread에 신호를 전달합니다.
    • (예: 동기식 신호).
  • (2) Deliver the signal to every thread in the process
    • (e.g. process termination signal).
  • 프로세스의 모든 thread에 신호를 전달합니다.
    • (예: 프로세스 종료 신호).
  • (3) Deliver the signal to certain threads in the process
    • (e.g. some asynchronous signals to non-blocking threads).
  • 프로세스 중 특정 thread에 신호를 전달합니다.
    • (예: 비동기 스레드로의 일부 비동기 신호).
  • (4) Assign a specific thread to receive all signals for the process.
  • 프로세스에 대한 모든 신호를 수신할 특정 스레드를 할당합니다.

③ Thread cancellation 스레드 취소

스레드가 끝나기 전에 그것을 강제 종료시키는 작업

• Terminating a thread before it has finished.

< Two general approaches >

③-① 비동기식 취소 (asynchronous cancellation):

• synchronous cancellation terminates the target thread immediately.
• 한 스레드가 즉시 목적 스레드를 강제 종료
  

③-② 지연 취소 (deferred cancellation):

• allows the target thread to periodically check if it should be cancelled
• 목적 스레드가 주기적으로 자신이 강제 종료 되어야 할지를 점검
  (cf. cancellation points in Pthreads – pthread_testcancel() function).

• (+) Pthreads에서는 pthread_cancel() 함수를 사용하여 스레드를 취소할 수 있다.
• (+) pthread_cancel()을 호출하면 대상 스레드를 취소하라는 요청만 표시된다.
• (+) 그러나 실제 취소는 요청을 처리하기 위해 대상 스레드가 설정되는 방식에 달림
• (+) 대상 스레드가 최종적으로 취소되면 취소 스레드의 pthread_join() 호출이 반환

④ Thread pools

Create a number of threads in a pool where they await work.
작업이 대기 중인 풀에 여러 개의 스레드를 작성
(언젠간 쓰이겠지, 일정 갯수의 thread 만들어놓기)

< Advantages >

• Usually slightly faster to service a request with an existing thread than create a new thread.

• 일반적으로 새 스레드를 만드는 것보다 기존 스레드로 요청을 처리하는 것이 약간 빠릅니다.

• Allows the number of threads in the application(s) to be bound to the size of the pool.

• 응용 프로그램의 스레드 수를 풀 크기에 바인딩할 수 있습니다.

⑤ Thread Local Storage (TLS) 스레드-로컬 저장장치

• 한 프로세스에 속한 스레드들은 그 프로세스의 데이터를 스레드간에 모두 공유한다.
• 하지만 상황에 따라서는 각 스레드가 자기만 액세스할 수 있는 데이터를 가져야 할 필요도 있다. => 자기만 액세스하는 데이터 : thread-local storage : TLS

• Allows each thread to have its own copy of data.

• 각 스레드가 고유한 데이터 복사본을 가질 수 있습니다.

• Most thread libraries and compilers provide support for TLS.

• 대부분의 스레드 라이브러리와 컴파일러는 TLS를 지원합니다.

• For example, the gcc compiler provides TLS via "static __thread int threadID;"