Operating Systems CMPSC 473
Concurrency: Threads
March 30, 2021 – Lecture 19 Instructor: Bhuvan Urgaonkar
Quiz 19.1
• Identifyreasonabletimescalesforeachofthefollowing (choose from: a few cycles, 100s-1000s of cycles, 100s of microseconds to a few milliseconds, longer):
• Inter-arrivaltimeoftimerinterrupts
• Durationofaprocess
• InterruptfromanIOdevice
• Flushing the TLB
• Running the CPU scheduler
• Runningthepagefaulthandler
• Time a process spends in the blocked state after issuing a disk read
Quiz 19.2
• Identifyreasonablecapacity/sizeranges(choosefrom:afew dozens to low 100s; 10s of KBs; 100s of KBs; low MBs; high MBs; …) for a laptop/desktop:
• Registers (per core)
• TLB (per core)
• L1 cache (per-core)
• L2 cache (per-core or shared)
• L3 cache (shared)
• Main memory
• Swap
• Diskforfilesystems,databases,etc.
Quiz 19.2
• Identifyreasonablecapacity/sizeranges(choosefrom:afew dozens to low 100s; 10s of KBs; 100s of KBs; low MBs; high MBs; …) for a laptop/desktop:
• /proc/cpuinfo
• Registers (per core) – low 100 words
• TLB(percore)–lowdozenstolow100softranslations
• L1cache(per-core)–10sofKBs
• L2cache(per-coreorshared)–100sofKBs
• L3cache(shared)–fewto10sofMBs
• /proc/meminfo,/proc/swaps,free,swapon-s
• Main memory – low GBs
• Swap – low GBs
• df,du
• Diskforfilesystems,databases,etc.
Quiz 19.3
• Consider a system with two processes A and B. A does not issue any loads and stores once its code is paged in. It simply executes a compute- intensive loop without raising any traps. Suppose B is running and issues a load instruction that results in a page fault. Assume the content needed by B is on the swap device. What will be the scheduling state of the two processes after the page fault handler has executed and the CPU scheduler is called:
• Both will be blocked till a disk interrupt arrives
• B will be blocked till a disk interrupt arrives; A will be ready
• A will be blocked till a disk interrupt arrives; B will be ready
• Both will be ready
Quiz 19.4
• In the last lecture we said that on a CPU such as x86, the TLB must be flushed if switching from process A to a different process B so B may not access physical pages assigned to A. Strictly speaking, however, there may be some entries in the TLB that can be left intact and won’t cause violation of virtual memory protection guarantees. What do you think these entries might be?
• Recently Intel has introduced ASID in its TLB entries!
• Whatever I was describing in Lecture 18 re. Intel TLBs was a bit dated
Quiz 19.5
• We studied the page replacement problem with the objective being minimization of page fault rate. Consider an alternative objective analogous to proportional fairness for CPU scheduling. Which of the following do you like best?
• Process with weight w_i should get fraction w_i / sum_j w_j of DRAM
• Divide DRAM among processes so their page hit rates are proportional to their weights
• DivideDRAMamongprocessessotheirpagefaultratesareproportionaltotheir weights
Concurrent Programming
• Why?
• Interleave CPU and IO devices
• Exploit multiple CPUs
• Maybecrucialtomeetperformanceneeds
• Sometimes natural as a programming style
• Downsidesoftheprocessasaunitofconcurrency:
• Context switches across address spaces are expensive • Competition even between processes meant to cooperate!
• Wastageofphysicalmemory • Specifically,what?
(Old) Process Address Space
2^32-1 stack
SP
heap
data
code 0 PC
(New) Address Space with Threads
2^32-1 stack
SP for thread 1 SP for thread 2
SP for thread 3
heap
data code 0
PC for thread 3 PC for thread 2 PC for thread 1
All threads in a process share the same address space
Types of threads
• Kernel-level threads
• OS manages per-thread state
• Threads can exploit multiple CPUs
• When a thread gets blocked another ready thread in the same process may run
• User-level threads
• User application manages per-thread state
• Implements TCBs, context switching, scheduling • Emulates timer interrupt via timer signals
• When a thread gets blocked, so does the entire process
OS data structures for kernel-level threads
• Processcontrolblockforanaddressspace
• Thread control block for a thread
• Holdsthread-specificinformation,e.g.,identifier,signalspending, resource usage, …
• Threadshaveschedulingstatessimilartothoseforaprocess • New, ready/runnable, running, blocked, terminated
• CPU scheduler considers threads as the schedulable entities
• Natural to take a “hierarchical” scheduling approach
• First determine eligible process, then pick a thread within it
• POSIX threads
• sidenote:POSIXstandsforThePortableOperatingSystem Interface, a family of standards specified by the IEEE computer society for maintaining compatibility between operating systems
• Defines a set of C language types, functions, and macros
• Implemented with a pthread.h header file and a library
• About 100 functions, all prefixed with pthread_
• We will be interested in a small subset
Pthreads
Pthreads data types of interest
• #include
• pthread_attr_t
Thread creation
Thread creation: C revision/learning
• Keyword const:
• tells the compiler that this is a read-only variable • outcomeofwritingtoitimplementation-specific
• Keyword restrict: (from Wikipedia):
• keyword that can be used in pointer declarations
• byaddingthistypequalifier,aprogrammerhintstothecompilerthatforthe lifetime of the pointer, only the pointer itself or a value directly derived from it (such as pointer + 1) will be used to access the object to which it points
• limitstheeffectsofpointeraliasing,aidingcompileroptimizations
• if the declaration of intent is not followed and the object is accessed by an independent pointer, this will result in undefined behavior
Thread creation
• Understanding the arguments to pthread_create:
• #1: pthread_t *restrict thread
• #2: const pthread_attr_t *restrict attr
• #3: void *(*start_routine) (void *)
• #4: void *restrict arg
Thread termination
Thread termination
• Keywordnoreturn:Specifiesthatthefunctiondoesnot return to its point of invocation
• Argument: returns a value via “retval” that is available to another thread in the same process the calls pthread_join
Thread join
Thread join
• Argument #1: the thread whose termination we want to wait for
• Argument#2:ifretvalisnotNULL,copiestheexitstatusof the target thread (argument to pthread_exit) into the location pointed to by retval
• Return value: 0 on success else error number
Thread self identification