Lecture Notes for Operating Systems

Concurrency, 4 October 2000

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

   1. independently executing processes aren't the problem - shared resources

   2. sharing the cpu isn't the problem - uncoordinated sharing

   3. the concurrency problem - uncoordinated resource sharing among concurrent processes

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

         1. safe - good data gets written, good data gets read

         2. high throughput - better than sequential access

         3. timely information - writers aren't starved out

   3. the sleeping barber problem

      1. example problem

         1. a server provides the only access to a device - the disk server

         2. the disk server sleeps if there are no clients

         3. clients arrive and wake the server if necessary

         4. when there are no more clients, the server sleeps again.

         5. the scheduler's the problem here - it may swap executing processes at any time

      2. the problem model

         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-interruptible 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 4 October 2000.