Introducing Threads
- show create.c
- Discuss how threads change the virtual memory story.
Using Semaphores
- Sem-queue example
- This is way less safe than just using locks. Requires careful analysis.
Insufficiently careful analaysis of sem-queue
Initial model: queue array has infinite size
- qii stores the index where we will insert the next item
- isem stores the number of logically free slots in the queue
- Inserting is safe: qii is atomicly incremented after each insert, so
it always points to a never-before-used slot.
- qjj stores the index where we will extract the next item
- qjj is incremented after each extract, so it will always point to the next
item that hasn't been extracted
- osem stores the number of full slots; initially zero
- osem is incremented only after an insert, so decrementing it is guaranteed
to provide access to a slot that has been written its single time
Modification: Queue is finite size.
- qii and qjj are used MOD(size). This causes slots to be reused both for writing
and for reading as the counter wraps around.
- We need to guarantee that reuses never overlap with the previous use.
- At most (size) items can be in the queue at once. This guarantees that no
matter where the queue data starts in the buffer, it can never overfill by
wrapping around.
- A read can never wrap around either, since that would require an osem value
greater than size.
- We have an invariant that isem + osem <= size. Why?
- Does that demonstrate that a read can never wrap around to a write?
Modification: Integers are finite size.
- Unsigned integers wrap on overflow.
- As long as the buffer size evenly divides into the integer range, then
this isn't a problem.
- Why?
More with Threads
Now we have two ways to support parallel execution on a Linux system:
- We can spawn multiple processes with fork()
- We can execute multiple threads within a single process.
Key difference: With threads, all memory is shared by default.
- Advantage: Allocating shared memory post-spawn.
- Disadvantage: 100% data races
With threads, we can get broken behavior even easier than before.
- Show thread sum101 examples.