Synchronization

• Related pages
  • Operating Systems
  • Programming
  • Computer Science
  • Software Engineering
  • Computer Architecture

Notes from the Little book of Semaphores .

Shared variables #

• Many applications enforce the constraint that the reader should not read until after the writer writes, this is because the reader may read an old value if the writer hasn’t written to the variable yet
• A thread may also interact as concurrent writes (two or more writers) and concurrent updates (two or more threads performing a read followed by a write)
• Think about what paths (execution paths) are possible and what are the possible effects. Ask yourself if you can you prove that a given (desirable) effect is necessary or that a undesirable effect is impossible

Semaphores #

• A semaphore is like an integer, with three differences
  • A semaphore can have its value initialized to any number, but after that only an increment and decrement operation is allowed, and you are not allowed to read the current value of the semaphore
  • When a thread decrements the semaphore, if the result is negative, the thread blocks itself and cannot continue until another thread increments the semaphore
  • When a thread increments the semaphore, if there are other threads waiting, one of the waiting threads gets unblocked
• If the value of the semaphore is positive, it representes the number of threads that can decrement without blocking. If it is negative, it represents the number of threads that have blocked and are waiting. If the value is zero, it means there are no threads waiting.

Quizzes and exercises #

Shared variables #

1. Imagine that you and your friend Bob live in different cities, and one day, around dinner time, you start to wonder who ate lunch first that day, you or Bob. How would you find out?

   Puzzle: Assuming that Bob is willing to follow simple instructions, is there any way you can guarantee that tomorrow you will eat lunch before Bob?

   • We could call a day before to synchronize our clocks precisely
   • We could call each other before having lunch and start together

2. Given the following threads, and a shared variable x:

   #	Thread A	Thread B
   1	x = 5	x = 7
   2	print(x)

For example, given thread A as a and thread B as b, we could have: a1 < a2 < b1

1. What path yields output 5 and final value 5?
2. What path yields output 7 and final value 7?
3. Is there a path that yields output 7 and final value 5? Can you prove it?

1. a1 < a2 < a1 or a1 < a2
2. b1 < a2 < b1 or b1 < a2
3. Yes, b1 < a2 < a1