Operating Systems 2019W Lecture 17

Video

Video for the lecture given on March 18, 2019 is now available.

Notes

Lecture 17
----------

Wednesday will be "online" (likely)

Concurrency
-----------

First, asynchronous programming (e.g., node)
 - non-blocking I/O
   - so, you use callbacks to continue after long operations (such as I/O)
 - in node, is done in a single-threaded application
   - execution is purely sequential, never parallel (in the program)

Concurrent programming is when you have parallel executions that can interact
 - processes running on separate data, not communicating are NOT concurrent
 - but once they communicate or share resources, they are concurrent

Concurrent programming is hard because the relative speed of programs determines how the system behaves
 - A faster than B != B faster than A

Relational databases were developed to manage concurrent access to data

Regular applications should normally use databases to manage concurrent access to data.  But the operating system can't (because databases depend on the OS!)


Transactions are a way of making sets of non-atomic operations atomic
 - atomic => indivisible

How do you make something that is divisible, indivisible?
 - all operations succeed or none of them do
   - if anything fails in the middle, undo the rest

Airline reservations
 - reserve a seat  (seat map)
 - pay for the seat (payments)
 - get customer information (customers)

Think of these as three tables

A transaction allows us to either update all three tables or none of the tables
 - cancel a transaction, and all parts of it are undone as if they never happened


In the kernel, we can't use ready-made transactions, but we simulate them all the time when we allocate resources
 - we don't want to get into weird states were only some of the resources have been allocated.  That's how you get memory leaks or worse.
 - most common resources we wish to access are data structures

To mediate access to data structures, we use locks

A lock is just a means of enforcing exclusive access of some kind
 - can treat reads and writes differently

Files can have advisory or mandatory locks
 - can you bypass the lock or not

For in-memory data structures, all locks are advisory
 - which makes them painful to debug


Classic locks are semaphores, specifically mutexes
 - a mutex is a binary semaphore (semaphore with a value of 0 or 1)

If you try to get it (down on a mutex), if it succeeds, you own the lock
If you don't get it, you wait until it is free (blocking)
If you don't get it, lock attempt fails (non-blocking)

If you block, you can either
 - busy wait (for in-memory data structures)
 - sleep (for I/O)

Your code should hold onto locks for as little time as possible

A critical section is the part of your code that interacts with the shared resource.  This is the part that should be protected by a lock.
 - critical sections should be short
 - they should release locks always

deadlock
 - parts of system can never get resources they need because they are held by another part of the system
 - Alice has a fork, Bob has a knife, but both Alice and Bob need a fork and knife to eat their food.
 - participants in a deadlock "starve"

How to resolve deadlock?
 - timeouts
 - kill someone
    - doesn't work in the kernel
 - start over
    - reboot