MP2 Extra Credit - Priority Inheritance and Priority Ceiling Protocols:

Due March 1st before class

 

This MP is optional. There is no penalty for not submitting it. It is merely for optional extra credit.

 

The goal of the MP2 extra credit assignment is to implement the priority inheritance and/or priority ceiling protocols (PIP and PCP from now on) in your thread and lock library.

 

PIP Extra credit = 1/7 of MP2

PCP Extra credit = 2/7 of MP2

Both together = 3/7 of MP2

 

 

API Changes

 

In order to easily implement PIP and PCP in the thread library, one new API is added to the thread library.

 

int thread_uselock(unsigned int lock, unsigned int priority);

 

The API specifies which locks can be acquired by threads of which priority. The test application will make these API calls at the beginning of its execution, upon initialization. For example, if a thread with priority 1 can acquire locks 12 and 13, the test application will call:

 

thread_uselock(12, 1);

thread_uselock(13, 1);

 

Also:

 

thread_lock_policy() should be changed such that it can take integer as a parameter:

 

int thread_lock_policy(int lock_policy);

 

lock_policy can have four values: THR_LOCK_DEFAULT, THR_LOCK_DFREE, THR_LOCK_PRIORITY_CEILING, or THR_LOCK_PRIORITY_INHERITANCE.

 

THR_LOCK_DEFAULT is for the previous default lock semantics and THR_LOCK_DFREE is for the previous deadlock free semantics. In this extra credit project, you will only use THR_LOCK_PRIORITY_CEILING and/or THR_LOCK_PRIORITY_INHERITANCE semantics, which represents the priority ceiling and priority inheritance protocols, respectively. THR_LOCK_DEFAULT and THR_LOCK_DFREE are for backport purpose and will NOT be tested by extra credit applications.

 

Here is the file "thread.h". The copy is located in /home/class/sp10/cs423/mp2-extra/thread.h in csil-vmserv1.

 

Finally, and most importantly, you have to change the implementation of thread_lock() and thread_unlock() properly to support the PIP and/or PCP in your thread library.

I found a document useful for implementing the PCP (http://www.cs.lth.se/DAT040/HT/lecture/RTP-F6b.pdf). It has simple examples that may help you understand how the PCP works .

 

-------------------------------------------------------------------------------
/*

 * * thread.h ? public interface to thread library

 * *

 * * This file should be included in both the thread library and application

 * * programs that use the thread library.

 * */

 

#ifndef _THREAD_H

#define _THREAD_H

#define STACK_SIZE 262144 /* size of each thread's stack */

 

#define THR_SCHED_FIFO 0

#define THR_SCHED_PRIORITY 1

 

#define THR_LOCK_DEFAULT 0

#define THR_LOCK_DFREE 1

#define THR_LOCK_PRIORITY_CEILING 2

#define THR_LOCK_PRIORITY_INHERITANCE 3

 

typedef void (*thread_startfunc_t) (void *);

 

extern int thread_libinit(thread_startfunc_t func, void *arg, unsigned int priority = 0);

extern int thread_set_sched_policy(int sched_policy);

extern int thread_create(thread_startfunc_t func, void *arg, unsigned int priority = 0);

extern int thread_yield(void);

extern int thread_lock_policy(int lock_policy);

extern int thread_initlock(unsigned int lock);

extern int thread_uselock(unsigned int lock, unsigned int priority);

extern int thread_lock(unsigned int lock);

extern int thread_unlock(unsigned int lock);

 

/*

 * start_preemptions() can be used in testing to configure the generation

 * of interrupts (which in turn lead to preemptions).

 *

 * It generate asynchronous preemptions every 10 ms using

 *         SIGALRM.  These are non-deterministic.

 *

 * start_preemptions() should be called (at most once) in the application

 * function started by thread_libinit().  Make sure this is after the thread

 * system is done being initialized.

 *

 * If start_preemptions() is not called, no interrupts will be generated.

 */

 

extern void start_preemptions(void);

 

#endif /* _THREAD_H */

-------------------------------------------------------------------------------

 

Since there are some changes in APIs (hence thread.h), it'd be best to create a separate folder for this project for example, cs423-mp2-extra-<groupid>. You can copy the exiting files for MP2 to the new folder and start working in the new folder.

 

NOTE that in our thread library, a higher priority thread will have a lower priority value. So please be careful when calculating the ceilings.

 

 

Test Cases

 

An example test case (test-ext1.cc) and Makefile are placed in mp2-extra folder in the server.

 

There are two threads: Thread 1 tries to acquire lock2 followed by lock1. Thread 0 tries to acquire lock1 and then lock2:

 

* Thread 1 - priority 1

lock(2) lock(1) ... unlock(1) unlock(2)

 

* Thread 0 - priority 0

lock(1) lock(2) ... unlock(2) unlock(1)

 

Here is the output for the provided test case (test-ext1)

 

-------------------------------------------------------------------------------

 [jinheo@csil-vmserv1 mp2-extra]$ ./test-ext1

main thread called with arg 1

thread starts  with prio: 1

thread with prio 1 is trying to acquire lock 2

thread with prio 1 successfully acquired lock 2

thread starts  with prio: 0

thread with prio 0 is trying to acquire lock 1

thread with prio 1 is trying to acquire lock 1

thread with prio 1 successfully acquired lock 1

thread with prio 1: 0            0

thread with prio 1: 1            1

thread with prio 1: 2            2

thread with prio 1: 3            3

thread with prio 1: 4            4

thread with prio 1 released lock 1

thread with prio 1 released lock 2

thread with prio 0 successfully acquired lock 1

thread with prio 0 is trying to acquire lock 2

thread with prio 0 successfully acquired lock 2

thread with prio 0: 0            5

thread with prio 0: 1            6

thread with prio 0: 2            7

thread with prio 0: 3            8

thread with prio 0: 4            9

thread with prio 0 released lock 2

thread with prio 0 released lock 1

thread with prio 0 last statement

thread with prio 1 last statement

Thread library exiting.

-------------------------------------------------------------------------------

 

NOTE: interrupt will not be used for this project. But for a smooth transition from the previous code to this project, interrupt.cc is still added to the Makefile.

 

Creating your own test cases and testing against them are important to successfully finish this MP. This MP is for extra credit. Your code will be tested with examples NOT presented to you above. You are responsible for code correctness (and not simply matching the above example output correctly).

 

Deliverables / Grading

 

We need the following files:

 

thread.cc, C source code for implementing your thread library

README, described below

 

Writing a README file

 

Create a text file that briefly describes how your thread library APIs are implemented (Focus on the PIP and/or PCP implementation part). If there are any known bugs in your implementation that you were unable to fix, or you could not fully complete the assignment, please describe what does and doesn't work correctly in this file as well.

 

This file should include, at the very top, the names and NetIDs of all group members.

 

 

Submitting your work

 

Copy the files you wish to hand in to a directory named cs423-mp2-extra-<groupid>, replacing <groupid> by the net id of one of your group members followed by the group size. An example <groupid> for a group with 3 members: jinheo3. You will use this group id throughout the semester.

Tar and gzip the files (tar zcf cs423-mp2-extra-<groupid>.tar.gz cs423-mp2-extra<groupid>).

Send an email with the gzipped file to the TA. The subject line should include "CS423 SP10 MP2 EXTRA"

You can resubmit your work anytime before the deadline.