ECS150 FQ20
March 27, 2020
Lecture Notes 4 Concurrency and Threads
• Concurrency – Multiple activities that can happen at same time (all continue to make progress over time)
• Parallelism – Multiple activities happen simultaneously Thread Use Cases
• •
Single Threaded – Single sequential execution context Multithreaded – Multiple concurrent execution contexts
Text Data Files
Regs Stack
Text Data Files
Regs Stack
Regs Stack
Regs Stack
•
Reasons for using threads
• Program Structure – Expressing logically concurrent tasks
• Responsiveness – Shifting work to run in the background
• Performance – Exploiting multiple processors
• Performance – Managing I/O devices
Thread Abstraction
• Thread – A single execution sequence that represents a separately schedulable task
• Single execution sequence – Each thread executes a sequence of instructions
• Separately schedulable task – The OS can run, suspend or result a thread at any time
• Threads vs. Processes
• One thread per process – Simple application that has only one sequence of
instructions
• Many threads per process – Several concurrent sequences of instructions only one is
running at a time
• Many single-threaded process – OS supports multiple processes that are each single
threaded, they appear as multiple-threads to the OS
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 4
1 of 4
ECS150 FQ20 March 27, 2020
• Many kernel threads – Kernel has multiple threads to exploit parallelism
• Cooperative – Threads run without interruption until explicitly relinquish control
• Preemptive – Thread can be switched out at any time
• Unpredictable Speed – Many factors play into the scheduling of threads, is unpredictable
at design time
• Amdahl’s Law – Formula for potential speedup of multiple processing cores.
𝑠𝑝𝑒𝑒𝑑𝑢𝑝 ≤ ! “#(“#$)
&
S – portion of application that must be performed serially N – Number of processing cores
Simple Thread API
• Asynchronous Procedure Call – Separates the procedure call from the return
• Fork-join Parallelism – Create children threads to perform work, and wait for their results
• thread_create() – Creates a thread
• thread_yield() – Relinquishes the CPU to another thread
• thread_join() – Waits for another thread to exit, gets exit value of that thread
• thread_exit() – Termination of a thread, can pass return value to thread waiting on join
Thread Data Structures and Life Cycle
• Thread Control Block (TCB) – Holds per thread information, analogous to PCB
• Per-thread Computation State
• Stack – Each thread has own stack
• Stack Frame – Local variables/return address, etc. for a procedure call
• Copy of processor registers – Includes more than just general purpose, but also CPU
flags, instruction pointer and stack pointer
• Per-thread Metadata – Information for managing the thread
• Thread ID – Used to identify the thread
• Scheduling Priority – Used to determine scheduling of the thread
• Status – Is the thread waiting, ready, running, etc.
• Shared State – Data, text, and heap, are shared by all threads within a process Thread Life Cycle
• Process or Thread State
• New – Process/thread being created
• Running – Process/thread is executing instructions
• Waiting – Process/thread is blocked waiting for I/O, signal, or a resource
• Ready – Process/thread is able to run when assigned a CPU
• Terminated – Process/thread has finished executing
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 4
2 of 4
ECS150 FQ20
March 27, 2020
Ready New 5
3
2
Waiting
Running 6
4 Terminated
1. Process/thread created
2. Scheduler selects process/thread
3. Scheduler selects another process/thread 4. Process/thread blocks for I/O or resource 5. I/O completes or resource released
6. Process/thread terminates
1
• Ready List – Set of runnable threads waiting to run
• Waiting List – Set of threads waiting for an associated event
• Finished List – Set of threads that have terminated possibly waiting to pass return value
Implementing Kernel Threads
• Multithreading Models
• Heavy Weight Threads (Kernel Threads)– Kernel space, visible to the OS, can
concurrently execute on independent cores
• Light Weight Threads (User Threads) – User space only, scheduled by application, all
share a core
• Fibers – Light Weight Threads that are cooperatively scheduled (non-preemptive
threads)
• Many-to-One Model – Many user space threads to one kernel space thread
• One-to-One Model – One user space thread to one kernel space thread
• Many-to-Many Model – Multiple user space threads to multiple (usually fewer)
kernel space threads
• Two-level Model – Many-to-Many that also allows user space to kernel space
binding
• Creating a Thread
• Allocate per-thread state
• Initialize per-thread state
• Put TCB on ready list
• Deleting a Thread
• Remove thread from ready list
• Free the per-state allocated to the thread
• Thread Context Switch – Switching from one thread to another
• Store current threads registers in TCB and stack
• Restore next threads registers from TCB and stack
• Voluntary Switching – Calling yield, join, exit or similar functions that can relinquish
control
• Involuntary Switching – Interrupt handler preempts the current running thread
• Zero-threaded Kernel – Kernel does not actually have a running thread, but only responds to interrupts
Implementing Multi-Threaded Processes
• Multi-threaded Process – Processes with multiple threads
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 4
3 of 4
ECS150 FQ20
• Kernel Thread State
• User level stack for executing code
• Kernel level interrupt stack
• Kernel TCB
• Green Threads – A pure user-level implementation of threads
• Scheduler Activations – User level thread scheduler is notified for every kernel event
• Increase the number of virtual processors
• Decrease the number of virtual processors
• Transition to Waiting
• Transition from Waiting to Ready
• Transition from Running to Idle Alternative Abstractions
• Asynchronous I/O – Allow single threaded processes to issue multiple concurrent I/O requests
• Event-Driven Programming – Thread spins in loop processing one I/O event each loop
• Continuation – A data structure that keeps track of each task’s current state
• Data Parallel Programming – Program can be parallelized because it needs to be applied
to multiple pieces of data
• Single Instruction Multiple Data (SIMD) – Data parallel at instruction level (model of
GPU and other vector machines)
• Bulk Synchronous Parallel Programming – Idealized machine with uniform compute
nodes and communication costs, separates communication and computation, synchronization is global
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 4
4 of 4
March 27, 2020