Software Systems Spring 2008 For today, you should have: 1) had a good break! Outline: 1) the Internet, bottom up. 2) heap implementation (notes14) 3) lock implementation 4) Homework 5 warmup For next time you should: 1) prepare a project progress report (see the handout) 2) read the first half of Chapter 18 of the Cow book 3) start Homework 5 (due Monday 7 April) Benjamin.Fisher Christina.Nguyen samuel.freilich James.Switzer Ilari.Shafer kent.munson allison.weis Jonathan.Inman kiuk.gwak Mary.Germino andrew.tsang jeffrey.dezso 4) Read Tanenbaum pages 379-399. Might seem like a lot, but much of it is familiar. Lock implementation ------------------- We have been taking for granted that we can implement a mutex, but we haven't talked about how. It is possible to do in software; Tanenbaum presents several algorithms in Section 2.3.3 1) disable interrupts con: vulnerable to programmer error 2) simple lock variable con: pure software version doesn't work 3) strict alternation void enter_region(int self, int other) { while (turn != self); // loop } void leave_region(int self, int other) { turn = other; } con: requires strict alternation 4) Peterson's algorithm void enter_region(int self, int other) { interested[self] = TRUE; turn = self; while (turn == self && interested[other]); // loop } void leave_region(int self, int other) { interested[self] = FALSE; } con: hard to generalize to n>2 5) a little help from the hardware One version is called BTS (bit test and set) in some instruction sets and TSL (test and set lock) in others. How does it work? It performs two operations atomically: 1) read the value of the mutex to a register 2) write a 1 to the same mutex Initially, the value of the mutex is 0, indicating that the lock is open or available. If two threads run TSL concurrently, only one of them will read 0 before the other writes 1. So how do you unlock the lock? Homework 5 warmup ----------------- Follow the instructions in the first section. Read Experiment 1 and let's talk about how to measure the rate of sync errors.