Operating Systems (Third Edition): Chapter 4

OS3e_Chapter_04

Operating Systems (Third Edition)
Harvey M. Deitel, Paul J. Deitel, David R. Choffnes

-------------------------------------------------------------------------------
CHAPTER 4: Thread Concepts
-------------------------------------------------------------------------------

# Introduction
    - Applications contain threads of execution, each thread being designated a
      portion of a program that may execute concurrently with other threads.
    - Threads known as Light-Weight Processes (LWP). They normally belong to
      processes which are refereed to as Heavy-Weight Processes (HWP).
    - Threads within a process can execute concurrently and cooperate to attain
      a common goal.
    - Local resources for each thread: processor registers, stack,
      Thread-Specific Data (TSD) such as signal masks.
    - Global resources for each thread: address space of process, open files.
    - Popular multithreading libraries
        * Win32 threads: Microsoft 32-bit Windows OS
        * C-threads: Mach Microkernel, supported in Mac OS X, Solaris, Win NT
        * POSIX threads: POSIX specification provides Pthreads standard. Goal
          is to allow multithreading applications to be portable.
    - Performance with LWPs approach is often much better than HWPs approach
      because a process's threads can communicate using a shared address
      space. Multiple HWPs need to establish IPC channels via kernel.

# Thread States
    - Born state
    - Ready state (runnable state)
    - Running state
    - Dead state (job complete)
    - Blocked state (wait for I/O completion)
    - Waiting state (wait for an event)
    - Sleeping state (sleep for a specified interval)

# Thread Operations
    - create
    - exit (terminate)
    - suspend
    - resume
    - sleep
    - wake
    - cancel
        * terminate a thread prematurely
        * threads can mask the cancellation signal
    - join
        * A joining thread blocks until the thread it joined exits.
        * When a process is initialized, it spawns a primary thread. If a
          primary thread terminates, the process terminates. The primary
          thread 'joins' all the threads to ensure that the process
          terminates only after all the threads have finished execution.

# Threading Models
    - User-level threads
    - Kernel-level threads
    - Combination of user-level and kernel-level threads

# User-level Threads
    - User-level threads perform threading operations in user space
    - Threads are created by runtime libraries that cannot execute privileged
      instructions or access kernel primitives directly.
    - Many-to-one thread mappings
    - OS maps all threads in a multithreaded process to single execution 
      context.
    - Advantages
        * User-level libraries have the liberty to tune the scheduling
          algorithm in order to meet needs of a specific application.
        * Portable, since it doesn't rely on a particular OS's threading API.
        * Can be used even in OS which doesn't support threads.
        * User-level threads do not invoke the kernel for scheduling or
          synchronization decisions, avoiding overhead due to context
          switches.
    - Disadvantages
        * Kernel views a multithreaded process as a single thread of control.
          Can result in suboptimal performance in multiprocessor systems.
        * Entire process blocks if any of its threads requests a blocking I/O
          operation.
        * Cannot be scheduled on multiple processors at once.

# Kernel-level Threads
    - One-to-one thread mapping
    - Each user thread is provided with a kernel thread that the OS can
      dispatch.
    - OS can dispatch a ready thread even if any other thread is blocked.
    - Individual threads can be scheduled on the basis of priority if the OS
      implements a priority based scheduling algorithm.
    - Overhead due to context switching and reduced portability due to OS
      specific API. POSIX threads aim to minimize this problem.

# Combining User and Kernel-level Threads
    - Many-to-many thread mapping, or m-to-n mapping.
    - Number of user and kernel threads may not be equal.
    - m-to-n mapping reduces overhead caused by one-to-one mapping by
      implementing thread pooling. This technique allows an application to
      specify the number of kernel level threads it requires.
    - Application developers are encouraged to use many-to-one mappings for
      threads that exhibit a low degree of parallelism.
    - Worker threads
        * Persistent kernel threads that occupy the thread pool.
        * Improves performance in environments where threads are frequently
          created and destroyed.
    - Scheduler activation
        * Technique that enables user-level library to schedule its threads.
        * Occurs when the OS calls a user-level threading library that
          determines if any of its threads need rescheduling.
        * Scheduler activation is actually a kernel thread that notifies a
          user-level threading library of events like thread has blocked, or
          processor is available, etc.

# Thread Signal Delivery
    - Synchronous signals are those that occur as a direct result of program
      execution. If a signal is synchronous, it is delivered to the thread
      which initiated it.
    - Asynchronous signals are those that occur due to an event typically
      unrelated to the current instruction.
    - Each thread is usually associated with a set of pending signals to be
      delivered when it enters the running state.
    - If a process employs user-level thread library, the OS cannot determine
      which thread should receive the signal. Particularly difficult if the
      signal is asynchronous. One solution is to require that the sender
      specify a thread ID.
    - According to the POSIX specification, processes send signals by
      specifying a process identifier, and not a thread identifier. To solve
      the thread signal delivery problem, POSIX uses signal masking.
    - A thread can mask all signals except those that it wishes to receive.
    - One way to implement pending signals for a many-to-many threading model
      is to create a kernel thread for each multithreaded process that
      monitors and delivers asynchronous signals to the appropriate thread,
      even if that thread was not running at the time of the signal. In
      Solaris, this thread is called Asynchronous Signal Lightweight Process
      (ASLWP).

# Thread Termination
    - Prematurely terminating a thread can cause subtle errors in processes
      because multiple threads share the same address space.
    - A thread can be terminated by completing execution, raising a fatal
      exception, or receiving a cancellation signal. A thread can mask a
      cancellation signal.

# POSIX and Pthreads
    - Threads that use the POSIX threading API are called Pthreads.
    - POSIX states that processor registers, stack and signal masks should be
      maintained individually for each thread. Other resources must be globally
      accessible to all threads.
    - According to POSIX, when a thread generates a synchronous signal due to
      an exception, such as illegal memory operation, the signal is delivered
      only to that thread.
    - If the signal is not specific to a thread, such as a signal to kill a
      process, then the threading library delivers that signal to a thread that
      does not mask it.
    - POSIX states that one should not use the kill signal to terminate a
      particular thread, i.e. if a thread acts upon a kill signal, the entire
      process, including all of its threads will terminate.
    - Although signal masks are stored individually in each thread, signal
      handlers are global to all of a process's threads.
    - To terminate a particular thread POSIX suggests using thread-cancellation
      modes.
        * Asynchronous cancellation: thread can be terminated at any point
          during the its execution.
        * Deferred cancellation: thread is cancelled only after it explicitly
          checks for a cancellation request. This allows threads to complete a
          series of operations before being abruptly terminated.

# Linux Threads
    - Many Linux kernel subsystems do not distinguish between threads and
      processes. Linux allocates the same type of process descriptor to threads
      and processes, both of which are called tasks.
    - Linux uses the UNIX based fork() system call to spawn child tasks. fork()
      creates a new task that contains a copy of all its parent's resources.
    - To enable threading, Linux provides a modified version of fork(), called
      clone(). Unlike fork(), clone() accepts arguments that specify which
      resources to share with the child task.
    - Linux provides one-to-one thread mapping that supports an arbitrary number
      of threads in the system. All tasks are managed by the same scheduler,
      meaning that processes and threads with equal priority receive the same
      level of service.

# Windows XP Threads
    - Threads are the actual unit of execution dispatched to a processor
    - Threads execute a piece of the process's code in the process's context,
      using the process's resources.
    - In addition to its process's context, a thread contains its own execution
      context which includes:
        * runtime stack
        * state of machine's registers
        * several attributes like scheduling priority
    - When the system initializes a process, the process creates a primary
      thread. If the primary thread returns, the process terminates.
    - All threads belonging to the same process share that process's virtual
      address space.
    - Threads can maintain their own private data in Thread Local Storage (TLS).
    - Windows XP threads can create fibres.
    - A fibre is scheduled for execution by the thread that creates it, rather
      than the scheduler.
    - A thread stores state information for each fibre. Windows API forces a
      thread to convert itself into a fibre before creating or scheduling other
      fibres.
    - Fibres have their own Fiber Local Storage (FLS). A fibre can access its
      thread's TLS.
    - If a fibre deletes itself, its thread terminates.
    - Windows XP provides each process with a thread pool that consists of a
      number of worker threads, which are kernel threads that execute functions
      specified by user threads.

# Introduction to Java Threads
    - Java allows the application programmer to create threads that can port to
      many computing platforms.
    - Threads
        * created by class Thread
        * execute code specified in a Runnable object's run() method.
    - Java supports operations such as naming, starting, and joining threads.

    /* ThreadTester.java
     * Multiple threads printing at different intervals
     */
    
    public class ThreadTester {
        public static void main(String[] args)
        {
            // create and name each thread
            PrintThread thread1 = new PrintThread("thread1");
            PrintThread thread2 = new PrintThread("thread2");
            PrintThread thread3 = new PrintThread("thread3");
    
            // System.err is unbuffered, hence printing is done immediately
            System.err.println("Starting threads");
    
            thread1.start();
            thread2.start();
            thread3.start();
    
            System.err.println("Threads started, main ends");
        }
    }
    
    // class PrintThread controls thread execution
    class PrintThread extends Thread {
        private int sleepTime;
    
        // assign name to thread by calling super class constructor
        public PrintThread(String name)
        {
            super(name);
    
            // pick random sleep time between 0 and 5000 milliseconds
            sleepTime = (int) (Math.random() * 5001);
        }
    
        public void run()
        {
            // put thread to sleep for sleepTime amount of time
            try {
                System.err.println(getName() + " going to sleep for " + sleepTime
                    + " milliseconds");
                Thread.sleep(sleepTime);
            }
            // if thread interrupted during sleep, print stack trace
            catch(InterruptedException exception) {
                exception.printStackTrace();
            }
    
            System.err.println(getName() + " done sleeping");
        }
    }
    
    Sample output 1:
        Starting threads
        Threads started, main ends
        thread1 going to sleep for 3476 milliseconds
        thread2 going to sleep for 1043 milliseconds
        thread3 going to sleep for 3090 milliseconds
        thread2 done sleeping
        thread3 done sleeping
        thread1 done sleeping
    
    Sample output 2:
        Starting threads
        Threads started, main ends
        thread1 going to sleep for 3104 milliseconds
        thread2 going to sleep for 3917 milliseconds
        thread3 going to sleep for 1812 milliseconds
        thread3 done sleeping
        thread1 done sleeping
        thread2 done sleeping