Operating Systems 2020W Lecture 14
Jump to navigation Jump to search
The video from the lecture given on March 4, 2020 is now available.
Lecture 14 ---------- Topics * midterm * tutorials (meta) * concurrency * producer/consumer * pipes * shared memory with mmap * Tutorial 6 * pattern matching versus model building Concurrency - doing multiple things "in parallel" that interact - note signal handlers add a kind of concurrency - we really can't do it well, can only do it in limited circumstances We see concurrency issues when there are multiple computations that have to communicate & coordinate - multiple threads - multiple processes - processes running on different systems - single process that gets interrupted by signal handlers Key task with concurrency is managing interactions Two basic strategies - messages - shared data structures (memory) Networking is messaging-based concurrency So is pipes We can use messages to simulate shared state - think google docs But where we can, shared state is more efficient, but is much more dangerous Pipes are a weird kernel thing - we are pausing the process doing writes when the reader isn't ready for them Pausing writes is easy - just make the write system call take a long time - writes block after all Note that the same is true for reads, they can block We coordinate by using a shared buffer - buffer is in kernel space - writes put data into the buffer - reads take data out - when buffer is full, writer is paused on write - when buffer is empty, reader is paused on read A pipe is an example of the producer-consumer problem - classic design pattern for concurrency pipes show the line between message passing and shared state isn't always so clear So, are pipes the way to go for IPC on a single host? - well, there is significant overhead - the overhead is in the system calls (switching back and forth to the kernel) and copying data - (high performance communication makes use of "zero copy" mechanisms) So, we can just share memory right? Note that child processes get a copy of a parent's memory - NOT shared You get shared memory with either - making a thread (all memory is shared) - shared memory ranges using mmap - do an anonymous mmap that is shared - will be shared from parent to child, won't be duplicated So we have shared memory, are we done? NO - shared memory is WEIRD on modern systems - changes to memory made by one process won't necessarily be seen immediately by other processes When we share memory, we are fighting the memory hierarchy - caches get in the way! Memory hierarchy - registers - L1 cache - L2 cache - L3 cache volatile, fast - main memory (DRAM) -------------------- - SSD - hard drives persistent, slow - tapes L1 caches are normally per core If CPU cores A and B both try modifying X A will have one version of X, B will have another version and they won't necessarily be the same You can only share memory safely between processes by using special hardware mechanisms which makes sure data is consistent - not all data, just selected data What do we need? special CPU instructions that make sure changes to memory are instantly shared across all CPUs - need hardware-provided atomic operations But we don't want to use such mechanisms directly need special language support (just like with system calls) semaphores are an abstraction of this sort of coordination mechanism, using shared memory that is changed atomically atomic operation - indivisible operation Semaphores come from railroad signals - want to make sure shared track is never occupied by two trains - semaphore indicates when the track is "taken" Basic algorithm for accessing shared state - try to grab semaphore (check if zero, if zero, make one) - if taken, wait until it becomes available, then take it (watch semaphore until it turns to zero, then make it one) - when finished, release semaphore (set semaphore to zero) (this describes a binary semaphore, also known as a mutex) (can also have counting semaphores) You can't implement a semaphore safely with a simple byte or integer variable, using standard programming constructs Need to be able to do test and set (check value and change it) as ONE instruction