Threads and Dispatching

Threads #

Definition: a thread is a sequential execution stream (i.e., executes instructions sequentially, one after another)

Virtualization #

Concept: one thing can behave like another - indistinguishably so

Why? Because modern computer hardware deals with threads in a complex, parallel (rather than serial) way, but we can treat threads as single units without having to worry about complex hardware interactions

Execution state #

Definition: Everything that can affect a thread, or be affected by it


  • Variables
  • Memory
  • Interrupts
  • Call stack (private)
  • Registers (private)
  • Cache
  • Open files
  • Network connection
  • Clock

Process #

Definition: One or more threads and their execution state

Process model #

  • Earliest OSes: single-tasking (1 process, 1 thread)
  • By the late 1970s: multitasking (many processes, 1 thread per process)
    • First on server/mainframe OSes, quickly spread to PC OSes
  • 1990s: multithreading (many threads per process)
    • Why? Uses multiprocessors well
    • Also, as structuring tool to separate out independent tasks of a program

Processors #

Today: Processors have multiple cores, each running a thread; some cores can run two threads (hyperthreading)

Tpyical server: 2 chips, 12 cores, 2-way hyperthreading: 48 simultaneous threads

Dispatching #

  • Every thread can run a process (fair scheduling)
  • Threads don’t change each other’s state (protection)

Process control block (per process) #

  • Saved state for threads
  • Scheduling information
  • Memory for process
  • Open files
  • Accounting

Thread states #

Thread states

Why no arrow from ready to blocked? Because the thread needs to run in order to wait on a resource, which is what blocked denotes.

Dispatchers #

  1. Let thread run
  2. Save state
  3. Load state of new thread
  4. See step 1

Context switch #

What: Change core’s current thread


  1. Save registers on stack
  2. Save stack pointer in process control block (PCB)
  3. Load stack pointer for new thread
  4. Pop register from stack
  5. Return

What makes the dispatcher run?

  • Interrupt (generated by hardware timer, disk I/O or keyboard input)
  • Traps: Code written in the thread that forces it to run OS code
    • System calls
    • Errors
    • Page fault

Picking which thread to run #

Simple approach:

  • Take all ready threads and put them in a ready queue (linked list)
  • When thread becomes ready, put it in the back of a queue
  • Pick first off the thread to run

In practice:

  • Most scheduling systems have some notion of priority
  • Queue structure organized according to priority
  • Dispatcher does not make priority decisions; it only physically stops and starts the threads
  • Scheduler is what makes decisions

Process creation #

  • Create a PCB
  • Load process’s code and data into memory
  • Create first thread
    • Allocate stack memory
    • Initialize thread state
      • Make it look like thread had just been blocked before first instruction
    • Add thread to ready queue

Kernel calls #

  • Similar to calling a method in a local process
  • User program invokes method inside the OS

Unix/Linux kernel calls #

// code is the same in parent and child
// fork() returns different value for parent or child
int pid = fork();
if (pid == 0) { // denotes child process
    // execute something on the child process via the shell
    // typically, child will change something in inherited state before calling exec()
    execv("/bin/ls", argv); 
} else { // denotes parent process
    // wait for child process to finish
    // child PID is second value returned by fork()
    waitpid(pid, &status, options);

Windows kernel calls #

BOOL CreateProcess(
    LPCTSTR lpApplicationName,
    LPTSTR lpCommandLine,
    LPSECURITY_ATTRIBUTES lpProcessAttributes,
    LPSECURITY_ATTRIBUTES lpThreadAttributes,
    BOOL bInheritHandles,
    DWORD dwCreationFlags,
    PVOID lpEnvironment,
    LPCTSTR lpCurrentDirectory,
    LPSTARTUPINFO lpStartupInfo,
    LPPROCESS_INFORMATION lpProcessInformation