Truong Than
CS644
HW2: Lock service - Design and Implementation.
---------------------------------------------------

I. External Specification.
   In our package, we provide the set of locking services that are most
important to user programs. They are for creating a lock, locking processes
that wait on the lock, releasing the blocked process one at a time, and
destroying the lock after use. We want our package portable and platform
independent in that it can be compiled and run in both UNIX/Linux and
XINU. To achieve this, we simply use the underlying services provided by
these platforms flexibly. Our task is to create a new API, which adapts both
platforms' specification, appearing uniformly to the user program.

   With this in mind, we need a new struct used to store different pieces of
information retrieved from calling to the semaphore services offered by
different platforms. The user of the package need not worry about
the contents of this structure.

The API of our package is defined as:

   1. struct locker lckcreate():
   - Creates a new mutex. Returns a struct locker, described above. 

   2. int lckwait(struct locker lock):
   - Holds and waits for the mutex referenced by lock. 

   3. int lckunlock(struct locker lock):
   - Releases the lock and unblocks the waiting process on the semaphore
   referenced by lock. Returns success/failure based on what is returned 
   by the underlying syscalls.

   4. int lckkill(struct locker lock, int nusers):
   - Destroys the lock referenced by lock. Returns -1 as failure, 0 as
   success in UNIX/Linux, or what is returned by XINU's sdelete syscall. The
   second argument used to tell XINU the number of lock users, so that the
   parent destroys the lock only if and when all users releasing that lock.

   5. void checkout(struct locker):
   - increment the variable, users, which keeps track of the exited-users.

II. Internal Specification.
   - In our design, for simplicity, we assume that every lock is shared
among the processes, for UNIX/Linux. However, in reality, a semaphore may be
specified to be shared among threads only. Secondly, the destroy of a
current lock is a bit tricky in XINU: XINU doesn't support parent-child
relationship like does UNIX/Linux, calling to lckkill may delete a lock, on
which some processes are waiting. To solve this, we simple use a member
called users of struct locker, to keep track of the number of lock users
who have finished using the lock. Each time a user finishes using a lock,
it calls to checkout() to increment this count. This number is used to 
compare with the number of lock users passed to lckkill by the top-level 
program.

struct locker details:
The syscall creating a new semaphore in XINU simply
returns an integer identifying that semaphore, whereas UNIX/Linux uses a
semaphore struct type, called sem_t, to store all the information about the
semaphore it is creating. So our new struct, called locker, is designed to
hold these different kinds of info of a semaphore. Moreover, an extra
integer field is needed for UNIX/Linux to save the semaphore ID that is 
needed for the segment of shared memory used to store the semaphore and
attaching this shared segment to the processes' VA space.  An extra
integer field is needed for Xinu to hold the lock user count for lckkill.

   - Everything else is just as simple as it appears. Other routines simply
call to the underlying syscalls offered by UNIX/Linux and XINU. Here are
their specifications:  

1. struct locker lckcreate():
   - Calls to XINU's screate(1) to create a new semaphore, of count 1.
   - As discussed above, we assume that locks in UNIX/Linux are shared among
   processes. Thus, we first need to create a segment of shared memory and
   attach it to the processes' VN space by calling to UNIX/Linux's shmget
   and shmat syscalls. Finally, sem_init() is called to initialize the lock.

2. int lckwait(struct locker lock):
   - Calls to XINU's syscall wait() to hold and wait until the
   lock is released.  
   - Calls to UNIX/Linux's syscall sem_wait() to do the same thing.

3. int lckunlock(struct locker lock):
   - Calls to XINU's syscall signal() to unlock the current lock
   and unblock one blocked process waiting on this lock, if any.
   - Calls to UNIX/Linux's sem_post() for the same thing.

4. int lckkill(struct locker lock, int nusers):
   - Calls to XINU's syscall sdelete(lock.mutex) to delete the lock. As
   discussed above, care must be taken to perform this action, because XINU
   doesn't support the parent-child processes relationship. In top-level
   program, we count number of workers and pass this number when we call to
   lckkill so that the parent (main program) know when to kill the
   lock.

5. void checkout(struct locker lock):
   - Called by each worker before they exit. This increment the variable
   users pointed to in struct locker, that keeps track of exited users.
   The indirection through the pointer is needed so that the actual
   count is in shared memory.