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.