Assignment 1

 

Reading - Chapter 1 of the textbook.

Project - Pick a partner and let us know. If you donít know Java or C#, start learning one of them now.

 

This problem is about how the ACID properties are affected by the internal structure and behavior of data management software. It also raises some design considerations that may affect your project.

 

B1 is a transactional block-oriented storage system. A user of B1 identifies each block by its physical address on disk. B1 offers the following five operations. Underlined parameters are output.

 

         /* Start new transaction */

int start()

Returns: -1, if there is an active transaction

tId < -1 (a new Transaction Identifier) otherwise

 

         /* If possible, read block at blockAddr on behalf of transaction tId

from disk into main memory and save a pointer to it in block */

int read(int blockAddr, int tId, int *block)

Returns: 0 if successful, -1 otherwise

 

         /* tell B1 that transaction tId has updated a block at blockAddr */

int write(int blockAddr, int tId)

Returns: 0 if there is no cached entry for blockAddr

1 otherwise

 

         /* Try to commit transaction tId */

int commit(int tId)

Returns: 0 if successful, -1 otherwise

 

         /* Abort transaction tId */

int abort(int tId)

Returns: 0

 

B1 is implemented as follows:

         B1 maintains a cache of blocks in main memory. It organizes this as a collection, called Cache, of cache entries. Each cache entry e is an object Cache(e) with three attributes:

o        int Cache(e).tId, which contains a transaction ID

o        int Cache(e).blockAddr, which contains the identity (i.e. disk address) of the block stored in Cache(e)

o        int Cache(e).oldBlock, which contains the last committed content of the block

o        int Cache(e).newBlock, which contains the last written content of the block

The cache is initially empty. This means that the cache has been allocated, and for all entries e in the cache, Cache(e).tId = 0.

         B1 maintains a variable lastTransId, which is the (sometimes negated) transaction identifier of the last transaction that was started. It is initialized to 1.

         There can be at most one instance of B1 running on a system at a given time. It has exclusive access to the disk drive that it uses.

 

 

B1 is used with a Model Uno disk drive, which supports the operations diskRead and diskWrite

 

         /* Read the value of block at blockAddr from disk and return it in main
memory at address memAddr */

int diskRead(int blockAddr, int memAddr)

 

         /* store the content of the main memory beginning at address memAddr

into block blockAddr on disk */

int diskWrite(int blockAddr, int memAddr)

 

Returns:

For each operation, the disk drive either performs the intended operation and returns 0 or it has no effect and returns -1

 

B1 implements its five operations as follows. It executes operations one-at-a-time. That is, it executes each invoked operation in its entirety before executing the next invoked operation.

 

lastTrans = 1;

...

int start()

{

††††† if (lastTrans < 0) return -1

††††† else

††††† {

††††††††††† lastTrans = -(++lastTrans);

††††††††††† return lastTrans;

††††† }

}

 

int read(int blockAddr, int tId, int *block)

{

/* find the cache element e containing the block whose disk address is blockAddr */

if (there is such a cache element e)

††††† {††††††††††

/* the disk block at blockAddr is in cache */

††††††††††† Cache(e).tId = tId;

††††††††††† block = &Cache(e).newBlock;

/* &Cache(e).newBlock is the address of Cache(e).newBlock */

††††††††††† return 0;

††††† }

††††† else

††††† {††††

††††††††††† /* pick a cache entry e, where Cache(e).tId = 0.

††††††††††† If there is no such entry, then return -1 */

††††† diskRead(blockAddr, &Cache(e).oldBlock);

††††††††††† Cache(e).newBlock = Cache(e).oldBlock;

††††††††††† block = &Cache(e).newBlock;

Cache(e).tId = tId;

††††††††††† return 0;

††††† }

}


/* A transaction should call write(&Cache(e).newBlock, tId) after it updates Cache(e).newBlock. */

int write(int blockAddr, int tId)

{

††††† /* find the cache entry e for block blockAddr */

††††† if (there is no such entry) return 0

††††† else

††††† {

††††††††††† Cache(e).tId = tId;

††††††††††† return 1;

††††† };

}

 

int commit(int tId)

{

††††† for (each cache entry e where Cache(e).tId == tId)

††††† {

††††††††††† status = diskWrite(Cache(e).blockAddr, &Cache(e).newBlock);

††††††††††† Cache(e).tId = - tId;

††††††††††† if (status == -1)

††††††††††† {

††††††††††††††††† Abort(tId);

††††††††††††††††† return -1;

††††††††††† }

††††††††††† Cache(e).oldBlock = Cache(e).newBlock

††††† };

††††† for (each cache entry e where Cache(e).tId == -tId)

Cache(e).tId = 0;

††††† lastTrans = -lastTrans;

†††††

return 0;

}

 

int abort(int tId)

{

††††† for (all cache entries e, where Cache(e).tId == -tId)

††††† {

††††††††††† repeat

††††††††††† {

††††††††††† †† status = diskWrite(Cache(e).blockAddr, &Cache(e).oldBlock)

††††††††††† }until (status == 0);

/* Of course, this will not terminate if diskWrite keeps failing, but ignore that issue */

 

Cache(e).newBlock = Cache(e).oldBlock

††††† };†††

††††† for (all cache entries e)

††††† {

††††††††††† Cache(e).tId = 0

††††† };

††††† lastTrans = -lastTrans;

 

return 0;

}

 


Questions

 

For each of the scenarios below, analyze whether transactions that use B1 satisfy the four ACID properties. In each case, if a property is violated, show a counterexample where it does not satisfy the property. In the latter case, you might want to suggest a way to fix the implementation, but donít lose sleep over it, since it might be pretty hard.

 

a.                   The operating system and B1 never crash. Transactions run serially.

 

b.                   The operating system can crash, in which case main memory is lost. Transactions run serially.

 

c.                   The operating system and B1 never crash. Transactions run serially. DiskWrite(b, addr) always returns 0, but it might corrupt block b on disk.

 

d.                   A variation of (c): The operating system and B1 never crash. Transactions run serially. If DiskWrite(b, addr) returns -1 then it might have corrupted block b on disk (but not if it returns 0).

 

e.                   The operating system and B1 never crash. The specification of Start is modified to allow up to two transactions to run concurrently. So its implementation is modified to keep track of the number of active transactions and return -1 if it is called when two transactions are concurrently active.