Memo Shared Records: Taking turns.

Memo Prog Tech

• Shared records
• Unordered queues
• Locks and semaphores
• Readers/Writers
  • readers preferred
  • writers preferred
  • taking turns
• Send/Receive
• Ordered Queues
• Barriers
• Job jars / self scheduling
• Implementation
• References

The rules of the taking-turns shared record are these:

• multiple readers may read the record at the same time
• at most one writer may be writing a record at a time
• no writer may be writing the record while any readers are reading it
• if there are no writers present, a reader may gain immediate access to the record
• if there are no readers and no other writers present, a writer may gain immediate access to the record
• if a group of readers finish reading the record and there are writers waiting, a writer must be given the record next
• if a writer finishes writing the record and there are readers waiting, all waiting readers are given the record next.

A solution to this problem in Memo uses the same four folders, extra status record, and data record as are used in the writers-preferred solution.

• The four folders are

1. F[0], read folder 0
2. F[1], read folder 1
3. F[0,1], status folder
4. F[0,2], write folder

(A folder name s[i] means its symbol is s and its X array is {i,0,0}; similarly s[i,j] means its symbol is s and its X array is {i,j,0}.)

• The fields of the status record, (nr,wtr,nw,i), are

1. nr, number of processes reading
2. wtr, number of processes waiting to read
3. nw, number of processes writing and waiting to write
4. i, index of current read folder, either 0 or 1.

The four operations, start reading, end reading, start writing, and end writing, are as follows:

start reading.

get the status memo

if nw=0

add one to nr

get a copy of the data memo from the read folder F[i]

replace the status memo

otherwise

add one to wtr

replace the status memo

get a copy of the data memo from the read folder F[1-i]

   (the other read folder)

end reading

get the status memo

subtract one from nr

if nr=0 and nw>0,

get the data memo from the read folder F[i]

put it into the write folder

replace the status memo

start writing

get the status memo

add one to the number of writers

if nr=0 and nw=1

get the data memo from the read folder F[i]

replace the status memo

otherwise

replace the status memo

get the data memo from the write folder

end writing

get the status memo

subtract one from nw

if wtr>0 or nw=0

assign wtr to nr

assign 0 to wtr

i := 1 - i

replace the status memo

put the data memo into the read folder F[i]

otherwise wtr=0 or nw>0

put the data memo into the write folder

replace the status memo

This page last updated 09/30/97