Overview of Threads

To let programs run concurrently, the system must perform a series of operations: process creation, process termination, and process switching.
Since a process owns resources, the system pays a considerable cost in time and space when creating, terminating, and switching processes.
How can multiple programs run concurrently more effectively while reducing system overhead?

The concept of a process embodies two characteristics:

• Resource ownership: a process includes a virtual address space holding the process image, and is allocated control or ownership of resources such as memory, I/O channels, I/O devices, and files.
• Scheduling/execution: a process is the entity scheduled by the operating system.

The scheduling and dispatching part is usually called a thread or lightweight process, while the resource-ownership part is usually called a process.

A thread has many characteristics of a traditional process, so it is also called a Light-Weight Process; correspondingly, a traditional process is called a Heavy-Weight Process. A traditional process is equivalent to a task with only one thread.
In an operating system that supports threads, a process usually owns several threads, and at least one.

History

• 1960s: the concept of a process was proposed. In operating systems, the process has always been the basic unit that owns resources and runs independently.
• Mid-1980s: the concept of a thread was proposed. A thread is a basic unit of independent execution smaller than a process, aimed at increasing the degree of concurrent program execution and further raising system throughput.
• 1990s: multiprocessor systems developed rapidly. Threads can improve the degree of parallel execution better than processes, fully exploiting the advantages of multiprocessors.
  

  

Sharing Among Threads

All threads within a process share many of the process’s resources, and this sharing brings synchronization problems.

Shared among threads          Private to each threadProcess instructions          Thread IDGlobal variables              Register set (including PC and stack pointer)Open files                    Stack (for local variables)Signal handlers               Signal maskCurrent working directory     PriorityUser ID

Mutual Exclusion Among Threads

Basic steps for accessing a global variable

• Read the data from the memory cell into a register
• Perform the computation on the value in the register
• Write the value in the register back to the memory cell
  

  

Thread Properties

• Lightweight entity: a thread owns almost no system resources of its own, only a small set of essentials: a TCB, a program counter, a set of registers, and a stack.
• Basic unit of independent scheduling and dispatching: in a multithreaded OS, the thread is the basic unit of independent execution, and thus also the basic unit of independent scheduling and dispatching.
• Concurrent execution: multiple threads within the same process can run concurrently, and one thread can create and terminate another.
• Shared process resources: a thread can share all resources owned by the process with the other threads of that same process.

Thread Control

Create/Terminate Thread

Thread creation:

• In a multithreaded OS environment, when an application starts, usually only one “initial thread” is executing.
• To create a new thread, a thread-creation function (or system call) is used, with the appropriate arguments.
• These include a pointer to the entry of the thread’s main routine, the stack size, the scheduling priority, and so on.
• After the thread-creation function completes, it returns a thread identifier for later use.

Thread termination:

• A thread exits voluntarily after finishing its work;
• Or a thread hits an error while running, or is forcibly terminated by another thread for some reason.

Three ways a thread terminates

• The thread returns from its start routine, and the return value serves as the thread’s exit code
• The thread is canceled by another thread in the same process
• The thread calls pthread_exit in any function to terminate execution

Synchronization and Communication Between Threads

Mutex

A mutex guarantees that only one thread can access a shared resource at a time; other threads must wait until the current thread releases the lock before they can acquire access. The time and space overhead of operating on a mutex is low, so it suits critical shared data and code sections used at high frequency.

• Before accessing the shared resource, a thread must first “acquire the lock”:
  • If the lock is unlocked, the thread acquires it successfully (the lock becomes locked) and may access the resource.
  • If the lock is already locked, the thread is blocked (placed on a wait queue) until the lock is released.
• After finishing with the resource, the thread must “release the lock” (the lock returns to the unlocked state), letting threads on the wait queue compete to acquire it.
• Typical scenario: both reads and writes to the shared resource need exclusive access. For example, in a multithreaded flash sale, the “decrement inventory by 1” operation must be made atomic with a mutex to avoid overselling.

Condition Variable

In multithreaded programming, a condition variable is a synchronization mechanism used to wake one or more threads when a specific condition becomes true. Condition variables are usually used together with a mutex to ensure that no race condition occurs while a thread checks a condition and waits on it.

Here is the general usage of condition variables for thread synchronization:

• Waiting on a condition: when a thread needs to wait for a condition to become true, it first acquires the mutex associated with the condition variable. It then checks whether the condition is already satisfied. If not, the thread calls the condition variable’s wait method (for example, Condition.await() in Java). This releases the mutex and puts the thread to sleep, waiting for the condition to become true.
• Changing the condition: when a thread changes data that may affect the condition, it first acquires the mutex, then modifies the data. After the modification, it calls the condition variable’s wake-up method (for example, Condition.signal() or Condition.signalAll() in Java) to wake all threads waiting on that condition. It then releases the mutex.
• Responding to a wake-up: when a thread is woken (that is, when it returns from the wait method), it re-acquires the mutex and checks the condition again. This is necessary because in a multithreaded environment the condition may change between the moment the thread is woken and the moment it actually runs.

Condition variables let threads avoid busy-waiting (repeatedly checking whether the condition is satisfied) while waiting for a condition. This can greatly improve system efficiency, because a waiting thread consumes no CPU resources.

Semaphore

• Private semaphore.
  When a thread needs a semaphore to synchronize threads within the same process, it can call the semaphore-creation command to create a private semaphore, whose data structure resides in the application’s address space.
  A private semaphore belongs to a specific process, and the OS does not know it exists. So if the semaphore’s holder terminates abnormally, or terminates normally without releasing the space the semaphore occupies, the system cannot restore it to 0 (empty), nor pass it to the next thread that requests it.
• Public semaphore.
  A public semaphore is set up to synchronize different processes, or threads across different processes.
  It has a public name available to all processes, hence the term public semaphore.
  Its data structure resides in a protected system storage area, with space allocated and managed by the OS, so it is also called a system semaphore.
  If the semaphore’s holder terminates without releasing the public semaphore, the OS automatically reclaims the semaphore’s space and notifies the next process. Public semaphores are therefore a relatively safe synchronization mechanism.

ULT & KLT