CSE Roadmap

Core tier · about 5 hours · 8 parts

Part 3 of 8 · 2 min read

Sharing

In plain words: If no resource were ever held by one thread alone, no thread would ever have to wait. For data that is only read, this is easy: read-only data can be shared by any number of threads with no lock. Level 4, page 7, used a read-write lock for this reason. Readers share, and only the rare writer takes exclusive hold.

Many resources cannot be shared. Two threads cannot write to a printer at the same moment without mixing their output. One trick is spooling: threads write their output into files on disk, and a single helper program, the printer daemon, sends the files to the printer one at a time. Only the daemon ever asks for the printer. It asks for nothing else, so no cycle can include the printer.

Spooling moves the problem and does not always remove it. If two jobs each fill half of the spool disk with part of their output, and neither can finish, they wait for space that the other holds. This is a deadlock again, now over disk space. For this reason, the lesson is general: give out an exclusive resource only when it is really necessary, and let as few threads as possible ask for it.

In code, the same idea appears as a rule to reduce the sharing. Give each thread its own copy of a counter and add the copies at the end (Level 4, page 9). Use a lock-free queue. Pass messages to one owner thread instead of sharing the data. Each removes the lock, and a lock that does not exist cannot take part in a cycle.

Spooling

Spooling is a technique in which jobs write their output to a queue on disk, and a single helper process later sends it to a device that cannot be shared, so that only the helper ever holds the device.

Example: ten programs print at once; each writes a file to the print queue, and one daemon prints them one after another.

Check yourself: 1. Why can read-only data be shared without a lock? 2. In spooling, which thread asks for the printer, and why does that remove the deadlock risk for the printer? 3. How can spooling create a deadlock over disk space?