Threads

Terminologies

• Concurrency (동시성 / 병행성) : the ability of two or more threads to execute in interleaving (overlapping) time periods and proceed at same time.
• Parallelism (병렬성) : the ability of two or more threads to execute in overlapping at same time.
• Porcess (Task) : the unit of resource ownership
  • A compound entity (a set of threads + a collection of resource)
• Thread (Lightweight process) : The unit of dispatching (scheduling)
• A thread (called main thread) is bound to a single process but a process can have multiple threads.

 

Multithreaded Process Model

• Address space
  • Every thread in a process share Code, Data, Heap.
  • Each thread has its own execution stack (User / Kernel)
• TCB (Thread Control Block) : Data structure in the operating system kernel which contains thread-specific information needed to manage it.
  • Shared information (related to Resource) : processor info, memory, I/O and file (PCB 중 TCB를 제외한 부분)
  • Private state information (related to CPU) : processor state information, scheduling and state information (TCB)
• LWP (LightWeight Process) : Thread
  • It take less time to create, terminate, switch the thread than the process.
  • Only for additional "execution sequence" : specific information (Stack, TCB)

 

Key Benefits

• Responsiveness (반응성)
  • An application can continue running while it waits for some event in the background.
  • I/O and computation can be overlapped.
• Scalability (확장성) in multi-processor architecture
  • The same application can run on multiple cores.
  • A process can be executed on mulitple CPUs (parallelism)

• Economy of time and space
  • No need to create a new entire PCB.
  • Faster to create and switch between than processes.
• Resource sharing : Synchronization 문제 발생
  • Threads can collaborate by reading and writing the same data in memory.
  • Communication between independent processes requires the intervention of the kernel to provide protection and the mechanisms needed for communication.

 

Implementation of Threads

• Kernel thread
  • Created and destroyed as needed internally by the kernel.
  • Need not be associated with any process.
  • Managed by the operation system.
  • Slow to create, manipulate, synchronize.
• User thread
  • Supported above the kernel.
  • Managed by the thread library
  • Does not involve kernel.
  • Fast to create, manipulate, synchronize.
• Thread libraries
  • To provide a library entirely in user space.
  • To implement a kernel-level library supported directly.
  • Contains code for creating and destroying threads.
• Many-to-One (user-level threads; ULTs)
  • Very fast, small overhead.
  • User thread를 처리하다가 blocking 될 경우 전체 thread가 막히는 병목현상 발생.
  • Parallelism 훼손

• One-to-One (kernel-level threads; KLTs)
  • Guarantee the parallelism.
  • Very big overhead because of mode switch, very slow

• Many-to-Many
  • Multiplexes many user threads to smaller or equal number of kernel threads.
  • Multiplexing by light weight process; LWP (thread)
  • Developers can create as many as user threads as necessary.

• Two level : Many-to-Many model + One-to-One model (Bound thread, high priority)

 

Gang Scheduling

• How to map each thread.
• Dedicated processor assignment
  • Increase cache affinity, easy to implement.
  • Decrease scalability.
• Gang scheduling
  • A scheduling algorithm for parallel systems that schedules related threads or processes to run simultaneously on different processors.
  • Usually these will be threads all belonging to the same process, but they may also be from different processes.
  • Also beneficial for any parallel application

 

Thread API

• Linux / Unix : POSIX Pthreads
• Windows : Win32 Threads
• JVM : Java Threads