In this task you will implement two synchronization primitives: mutex and condition variable (although I cannot see any requirement of implementing condition variable).

Please start with your PA2 code. If your PA2 code is not working, you will not be able to run the test here and you won't get any credit for this assignment (since you have to pass tests to get credit).

Please read about mutexes and condition variables in POSIX, preferably before you begin coding for this part of the assignment. Your implementation will emulate the behavior and API of pthread_mutex and pthread_cond. A nice tutorial is provided by Lawrence Livermore National Laboratory. Read it carefully and give yourself some time to digest it. You will have a far easier time with the rest of the assignment if you do so.

Please examine the implementation of spinlocks in xv6's kernel (for example the scheduler uses a spinlock). Please also read Chapter 4 of the xv6 book about locking. Spinlocks are used in xv6 in order to synchronize kernel code. Your task is to implement the required synchronization primitives as a kernel service to applications, via system calls. Locking and releasing can be based on the implementation of spinlocks to synchronize access to the data structures which you will create to support mutexes and condition variables.

Quoting from the pthreads tutorial by Lawrence Livermore National Laboratory:

Mutex is an abbreviation for "mutual exclusion". Mutex variables are one of the primary means of implementing thread synchronization and for protecting shared data when multiple writes occur. A mutex variable acts like a "lock" protecting access to a shared data resource. The basic concept of a mutex, as used in pthreads, is that only one thread can lock (or own) a mutex variable at any given time. Thus, even if several threads try to lock a mutex only one thread will be successful, and all other threads will get blocked until the mutex becomes available. Mutex differs from a binary semaphore in its unlock semantics - only the thread which locked the mutex is allowed to unlock it, unlike binary semaphores on which any thread can perform up.

Make sure you watch the lecture that covers the PA3 slides.

Examine pthreads' implementation and define the type kthread_mutex_t inside the xv6 kernel to represent a mutex object. You can use a global static array to hold all the mutex objects in the system. The size of the array should be defined by the macro MAX_MUTEXES=64.

The API for thread system calls is as follows: int kthread_mutex_alloc();

Allocates a mutex object and initializes it; the initial state should be unlocked. The function should return the ID of the initialized mutex, or -1 upon failure.

int kthread_mutex_dealloc(int mutex_id);

De-allocates a mutex object which is no longer needed. The function should return 0 upon success and -1 upon failure (for example, if the given mutex is currently locked).

int kthread_mutex_lock(int mutex_id);

This function is used by a thread to lock the mutex specified by the argument mutex_id. If the mutex is already locked by another thread, this call will block the calling thread until the mutex is unlocked.

int kthread_mutex_unlock(int mutex_id);

This function unlocks the mutex specified by the argument mutex_id if called by the owning thread, and if there are any blocked threads, one of the threads will acquire the mutex. An error will be returned if the mutex was already unlocked. The mutex may be owned by one thread and unlocked by another!

Please note the following:

• In all the above functions, the value 0 should be returned upon success, and a negative value upon failure.
• No busy waiting should be used whatsoever, except for synchronizing access to the mutex array using short-time waiting in spinlock.

The code distribution contains 2 test files: mutextest1.c and mutextest2.c. Most of the points on this assignment will be based on your code matching the expected outputs provided below.

mutextest1.c

    $ mutextest1
    ~~~~~~~~~~~~~~~~~~ mutex test 1 ~~~~~~~~~~~~~~~~~~
    joining on thread 4
    thread 4 said hi
    finished join
    joining on thread 5
    thread 5 said hi
    finished join
    joining on thread 6
    thread 6 said hi
    finished join
    joining on thread 7
    thread 7 said hi
    finished join
    joining on thread 8
    thread 8 said hi
    finished join
    joining on thread 9
    thread 9 said hi
    finished join
    joining on thread 10
    thread 10 said hi
    finished join
    joining on thread 11
    thread 11 said hi
    finished join
    joining on thread 12
    thread 12 said hi
    finished join
    joining on thread 13
    thread 13 said hi
    finished join
    joining on thread 14
    thread 14 said hi
    finished join
    joining on thread 15
    thread 15 said hi
    finished join
    joining on thread 16
    thread 16 said hi
    finished join
    joining on thread 17
    thread 17 said hi
    finished join
    joining on thread 18
    thread 18 said hi
    finished join
    Finished.
    $ 

mutextest2.c

    $ mutextest2
    ~~~~~~~~~~~~~~~~~~ mutex test 2 ~~~~~~~~~~~~~~~~~~
    test passed
    $ 

The grading guidelines has been made available. Please run the commands in the grading guidelines on a standard 32-bit Ubuntu 16.04 system. It is possible that there are bugs in the guidelines. If you find bugs, please let the instructor know as soon as possible. (Note: if I change the grading guidelines, I will make an announcement in the class Piazza. Please remember that you are required to read my posts in the class Piazza.)

The grading guidelines is the only grading procedure we will use to grade your program. No other grading procedure will be used. Please note that the grader may use a different set of test programs and commandline arguments when grading your submission. (We may make minor changes if we discover bugs in the script or things that we forgot to test.) It is strongly recommended that you run your code through the commands in the grading guidelines.

• Please read the general programming FAQ if you need a refresher on file I/O and bit/byte manipulications in C.

If you have made all your code changes in-place (which you are requied to do), it will be very easy to create a gzipped tarfile for submission using the Bistro system. To create your submission file, just do the following:

    make pa3-submit

and the following command should run:

    tar cvzf pa3-submit.tar.gz \
            Makefile \
            pa3-README.txt \
            proc.c \
            proc.h \
            syscall.c \
            sysproc.c \
            kthread.h \
            exec.c

Please note that you are not permitted to change any other existing files. If you submit another existing file, it will be deleted before grading. If you give instructions to the grader to modify another existing file (other than Config.mk), it will disregarded.

A pa3-README.txt template file is provided here. You must save it as your pa3-README.txt file and follow the instructions in it to fill it out with appropriate information and include it in your submission. You must not delete a single line from w1-README.txt. Please make sure that you satisfy all the README requirements.

To check the content of pa3-submit.tar.gz, you can use the following command:

    tar tvzf pa3-submit.tar.gz

Please read the output of the above command carefully to see what files were included in pa3-submit.tar.gz and what are their file sizes and make sure that they make sense.

Please enter your USC e-mail address and your submission PIN below. Then click on the Browse button and locate and select your submission file (i.e., pa3-submit.tar.gz). Then click on the Upload button to submit your pa3-submit.tar.gz. (Be careful what you click! Do NOT submit the wrong file!) If you see an error message, please read the dialogbox carefully and fix what needs to be fixed and repeat the procedure. If you don't know your submission PIN, please visit this web site to have your PIN e-mailed to your USC e-mail address.

When this web page was last loaded, the time at the submission server (merlot.usc.edu) was 28Nov2025-01:56:12. Reload this web page to see the current time on merlot.usc.edu.

USC Email:

 @usc.edu

Submission PIN:

Event ID (read-only):

Submission File Full Path:

 

 
If the command is executed successfully and if everything checks out, a ticket will be issued to you to let you know "what" and "when" your submission made it to the Bistro server. The next web page you see would display such a ticket and the ticket should look like the sample shown in the submission web page (of course, the actual text would be different, but the format should be similar). Make sure you follow the Verify Your Ticket instructions to verify the SHA1 hash of your submission to make sure what you did not accidentally submit the wrong file. Also, an e-mail (showing the ticket) will be sent to your USC e-mail address. Please read the ticket carefully to know exactly "what" and "when" your submission made it to the Bistro server. If there are problems, please contact the instructor.

It is extreme important that you also verify your submission after you have submitted pa3-submit.tar.gz electronically to make sure that every you have submitted is everything you wanted us to grade. If you don't verify your submission and you ended up submit the wrong files, please understand that due to our fairness policy, there's absolutely nothing we can do.

Finally, please be familiar with the Electronic Submission Guidelines and information on the bsubmit web page.