Operating Systems 2017F Lecture 10
Video
Video from the lecture given on October 10, 2017 is now available. (The audio worked!)
Notes
In-Class
Lecture 10
----------
Concurrency
- more than one thing happening at the same time
challenge with concurrency is keeping shared state consistent
* files that are written to by multiple processes
* two or more processes communicating
* multiple threads within a process
concurrency leads to race conditions
- order of interleaved actions affects output
- ex. did process A or B modify the file first?
We want deterministic behavior from concurrent computations
To get consistent computation, we need to coordinate
- but you can't interact via regular variables
Regular variables are subject to the memory hierarchy
- variables are stored in registers, L1 cache, L2 cache, L3 cache, main memory
- can be deeper in some contexts
- so what if coordination variable is in L1 cache for one thread and in main memory for another?
- hardware maintains consistency...eventually
mechanisms for coordinating concurrent computations must bypass the memory hierachy
Instead use
- filesystem locking primitives (kernel)
- special machine language instructions
Operating systems - kernels in particular - are highly concurrent
- makes them painful to code
- have to always worry about having exclusive (or safe) access to data, resources
Abstractions for managing concurrency
- atomic variables guarantee strict ordering of operations
Example
Variable X: ***** <- range of memory locations
To modify X, you...
- load X into a register
- modify the register
- save the register to X
What if two cores try to modify X at the same time?
- both could have X in a register at the same time
X is 5
core A increments by 1
core B decrements by 1
What's X after both have run?
If B changes X but doesn't see A's change...you get 4
If A changes X but doesn't see B's change...you get 6
For X to be atomic, ^^^ shouldn't be possible
- has to make sure only one core accesses X at a time
Atomic variables are typically used to build semaphores...
But what we really want is mutual exclusion
- only one thread/process/CPU can access the resource at a time
Want mutual exclusion for larger resources, e.g. data structures, devices
Higher-level languages directly support mutual exclusion, e.g.
Java synchronized methods
Semaphores are an analogy to a railroad control mechanism
- only one train on the track!
When a train enters the shared track
- grab the semaphore (increment atomic variable)
- if not available, wait (check first to see if it is 0)
When a train leaves the shared track
- release the semaphore (decrement atomic variable)
Lesson: don't implement semaphores yourself, please!
In the Linux kernel
- locks using semaphores of various types are associated with all kinds
of data structures
e.g. inodes
When you can't get the lock, what do you do?
- sleep (tell the scheduler to wake you up when the lock is available)
- deal with not getting the resource
- spin (do a null loop)
If the wait time is short, spinning is the fastest thing you can do
Where possible, everything should be exclusive, minimize sharing
But in userspace...
- shared memory...NOOOOOOO
- unless you use atomic variable, or something higher level
like a semaphore
- messages
- series of messages can be used to synchronize state
3-way handshakes, e.g. opening a TCP connection
- SYN (synchronize) client->server
- SYN-ACK (acknowledge SYN) server->client
- ACK (acknowledge) client->server
Can send messages between processes
- signals!
- other ways too
concurrency pattern: producer/consumer
* two processes P and C
* P "makes" things, C "consumes" them
* want to coordinate P and C
- P shouldn't produce too much (C gets too far behind)
- C shouldn't waste time waiting for P
* shared circular buffer for storing output of P and input of C
* when buffer is empty, C should sleep
* when buffer is full, P should sleep
For those who have used Mutexes before, a mutex is essentially a binary semaphore (hence the name, mutual exclusion).
A mutex allows only a single thread to access a resource, whereas a semaphore allows, and can keep count of how many threads are accessing a certain resource at once.
Mutexes are more common in practice, for some examples of when to use a semaphore, please see:
http://www.freertos.org/Real-time-embedded-RTOS-Counting-Semaphores.html
When using a semaphore, you wait on it using sem_wait(), an analogy is waiting for a key to go to the washroom.
When youre finished with the resource, you return the key using sem_post() for someone else to use.