Homework 11 Solutions

22C:116, Fall 1998

1. Part A: The transaction can be rewritten as a two-phase transaction as follows:

   	begin example transaction
   	  read x  -- locks x
   	  if x < 10 abort transaction  -- unlocks x
   	  x = x - 10
             -- former position of write x
             read y  -- locks y
   	  y = y + 10
   	  -- boundary between phases
   	  write x  -- unlocks x
   	  write y  -- unlocks y
   	end transaction
   

   Part B: The following set of rewrite rules will convert any transaction to a two-phase transaction; this proves that that all possible transactions can be rewritten to conform to the two-phase model!

   Replace

   	begin transaction
   

   with

   	begin transaction
   	   association = empty set
   

   and replace

   	   read x
   

   with

   	   if association contains ("x",v,t)
                 then x = v
              else
                 read x -- locks x
   	      add element ("x",x,read) to association
   	   endif
   

   and replace

   	   write x
   

   with

   	   if association contains ("x",v,t)
   	      delete this tuple from association
   	   endif
              add element ("x",x,write) to association
   

   and replace

   	end transaction
   

   with

   	   for each tuple ("x",v,t) in association
   	      remove tuple from association
                 if t = read
                    unlock x
                 else if t = write
                    x = v
                    write x  -- unlocks x
                 endif
              endloop
              -- note that association is now empty
   	end transaction
   

   Part C: The two-phase model is useful if we assume that system failure is not an issue, but that deadlocks are detected immediately and resolved by aborting the transactions that caused the deadlock. All such abort operations will occur during phase 1, and therefore, they will occur before the transaciton modifies any values in the shared database.

2. Part A: What security or reliability problems are introduced by If we allow the client to assign the transaction ID, we have no way of assuring ourselves that the client has selected a unique ID. Furthermore, we have no way to assure ourselves that the client will use the ID that the client has selected. If the server selects the ID, the server can guarantee that it is a unique ID (from the point of view of that server), but there is no way for the server to force the client to use the same ID that the server just issued.

   Part B: In a multiple-server interaction, there is not a single server, so there is no way for the server to assign the transaction ID. There is, however, only one ultimate client, at the root of the client-server tree involved in the transaction, so the client is the obvious logical choice for the job of assigning the transaction ID.

3. We can allow our example thread package to offer a separate logical file position to each thread that manipulates some file in two distinct ways.

   First, each thread that needs to use the file can open the file separately. This gives each thread its own UNIX file descriptor for that file, and each descriptor will have its own logical position, maintained by the operating system.

   Second, each thread can maintain its own logical position in the file, pos. Thus, we replace:

   	read(d,buf,len)
   

   with

   	lseek(d,pos,SEEK_SET)
   	pos = pos + read(d,buf,len)