We discussed the solution to the second homework. Points to take away
from the discussion:
- Like a ReaderWriter lock, a Bathroom lock is a new locking
primitive built on top of the basic mutex lock. Below is an example of
how the new locking primitive can be used:
women_start() {
women_enter() /* lock() */
<critical region>
women_leave() /* unlock() */
}
men_start() {
men_enter() /* lock() */
<critical region>
men_leave() /* unlock() */
}
main() {
thread_create(women_start, NULL);
thread_create(men_start, NULL);
}
- To write a new locking primitive, in the beginning of the
"locking" routing, you acquire a mutex lock and release it at the end
of the routine. For example,
women_enter() {
thread_lock(mutex);
.....
thread_unlock(mutex);
}
Mutex lock provides "mutual exclusion".
- Then, you define your condition variables to satisfy the ordering
constraints.
- Make your solution, first, correct and, then, also efficient. For
instance, we discussed when it is "wasteful" to use a broadcast.
- Be careful of when you increment your "counting" variables. Some
cases can lead to a deadlock!
- We discussed whether we can solve the problem using 1 condition
variable. Remeber that a combination of 1 condition variable and a
"signal" (instead of a "broadcast") might get you in trouble (as you
wait up the "wrong" waiting thread. eg., a women when a man should have
received a wakeup call to get into the bathroom)....
- Come by the office hours in case you are not sure if your
solution is correct...
Help with a disk scheduler (building on the pseudo-code from the last
week's discussion).
Remember the producer-consumer problem from the lecture, your disk
scheduler is a consumer and each requester is a producer...
scheduler() {
while() {
while (queue is not sufficiently full)
wait(NEED_WORK) /* look at
the producer-consumer example !*/
do_work();
broadcast/signal() /* let producers
know you have consumed an item */
broadcast/signal() /* don't forget to
let the specific requestor know you've service its item */
}
}
requestor() {
for each track in the input file {
while (queue is full)
wait(QUEUE_IS_FULL)
place_request();
broadcast/signal() /* let the consumer
know you have generated a request */
wait() /* this requester needs to wait
until the scheduler is done servicing this request */
}
}
start() {
.....
thread_create(scheduler, .... );
for number of requestors
thread_create(requestor, ....);
}
main() {
number of requestors = argc - 2;
....
thread_libinit(start, .... , ? (number of locks), ?
(number of cond vars));
/* for the number of locks, recall the 1-st
non-graded question regarding the number of
* threads, resources and maximum
concurrency
* for the number of cond vars: given that you
have a producer-consumer type of problem,
* look at the solution for that problem, you'd
probably wont to have at least that many
* condition variables
*/
We discussion several conditions:
- You need to keep the queue as full as possible. For instance:
1 3
5 /* are the inputs to the requesters */
2 4 6
queue_size = 2
1. 1, 3 gets added to the queue
2. 1 gets serviced.
3. now the scheduler evaluates the condition "is the queue sufficiently
full". at this point there is only 3 in the queue, the scheduler thread
should wait.
4. either 2 or 5 should be added to the queue before the disk scheduler
thread gets to pick its next track to service...
- Another important example, is when a requester thread leaves. For
instance:
1 3
2 4
queue_size = 2
1. as before, 1 and 3 added to the queue
2. 1 gets serviced.
3. 2 gets added to the queue.
4. for the sake of example, say 2 gets serviced now. thread 1 is done
with all its requests (tracks 1 and 2). thread 1 will complete its
"main" function.
5. now, when the disck scheduler evaluates the condition "is the queue
full", it should find the queue full (because the number of active
requestors fell below the size of the queue!). Therefore, I suggest
that you might want to keep track of the number of active requesters in
the system and base the disk scheduler "queue" condition on that count!.