Lecture Notes for Operating Systems

Concurrency, 22 September 1999

1. concurrency - more than one processes executing at the same time

2. three representative concurrency problems.

   1. the dining philosophers problem.

      1. example problem

         1. write a program that reads a tape drive, computes a while, and writes another tape - the computation cannot start until the program has both tape drives

         2. five identical copies of the program are to be run on a system with five identical tape drives

         3. commands - get_tape(), compute(), release_tape()

         4. what does the program look like?

      2. model - due to dijkstra

         1. five philosophers, a table, plates of spaghetti, forks

         2. philosophers either think or eat, hungry; eating requires two adjacent forks;

         3. some hungry philosopher eventually gets to eat

         4. every hungry philosopher eventually gets to eat

         5. a hungry philosopher that's eaten n meals has priority over a hungry philosopher that's eaten m meals when n < m

   2. the readers-writers problem

      1. a never-ending stream of readers and writers access a database

      2. only one writer may change the database at a time, and only the writer may access the database while its being changed

      3. any number of readers may access the database at the same time

      4. write an access program for readers and writers - safe and high throughput, timely information

   3. the sleeping barber problem

      1. a barber shop with one barber chair and an n-customer bench.

      2. when the shop is empty the barber is sleeping in the barber chair

      3. a customer enters the store

         1. empty - wake up the barber

         2. bench not full - take a seat

         3. bench full - blow off the hair cut

      4. how many new customers in the shop at once

3. ipc - inter-process communication or coordination

   1. competing access to shared resources

   2. coordinated execution behavior - synchronization

   3. race conditions - unmediated access to shared resources; two threads updating a common counter, interrupts

   4. idea - make shared access non-interruptable or atomic or serial

   5. follow on problem - decreased performance

   6. two-part solution

      1. mutual exclusion to prohibit shared access

      2. critical regions or sections to delimit the scope of mutual exclusion

      3. rules

         1. mutual exclusion only in critical regions

         2. cpu abstracted away - number and speed

         3. processes outside cr may not block entry into the cr

         4. processes attempting to enter the cr eventually will

This page last modified on 27 September 1999.