-
Notifications
You must be signed in to change notification settings - Fork 0
Project1
Operating System
Instructed by Xu Wei
Chen Xiaoqi, Ku Lok Sun, Wu Yijie, Zhang Hanrui
Due on April. 14, 2015
Current thread call thread1.join(), and wait thread1 finish Notice that Current thread != thread1.
- No busy waiting
- Return immediately when finished.
- join() is called at most once for each thread object
We can add waitQueue to hold threads that have to wait until this thread is finished. And move the threads in waitQueue to readyQueue when this thread is done.
Since the threads in waitQueue are in status blocked (by calling sleep()), scheduler will not dispatch them until this thread is finished.
Note that there are some prerequisites:
- This thread can not be currentThread, and
- The waitQueue has been initialized before
join()is called (same as readyQueue). - The interrupt should be disabled before add the current thread to
waitQueue, since all the operations are atomic and the methodsleep()also requires that the interrupt is disabled.
Also note that the tcb will be destroyed by the next thread to run and the priority donation is handled by scheduler.
In KThread.join():
disable interrupt
if(this.status != finished){
add currentThread to waitQueue
currentThread.sleep() //cause it to be blocked
}
restore interrupt
In KThread.finish():
...
//the interrupt has been disabled
while(waitQueue has nextThread){
nextThread.ready()
remove nextThread from waitQueue
}
...//existing code
currentThread.status = finished
sleep()
Implement directly without semaphore. Lock and interrupt disable can be used
- No busy waiting
- Sleeper must no miss the wake up. (No preempt between wake)
We complete the following three functions of Condition2 class: sleep(), wake(), wakeAll().
constructor:
using the queue in scheduler to solve priority inversion problem
sleep(){
release conditional lock
disable interrupt
add this thread to queue
this thread sleep
enable interrupt
acquire conditional lock
}
wake(){
disable interrupt
if(queue not empty){
queue.removeFirst().ready
}
enable interrupt
}
wakeAll(){
while(queue not empty){
queue.removeFirst().ready()
}
}
- How to make sure the sleeper only waked by wake call?
- Will the 'enable machine interrupt' in sleep() crash the OS?
- Do we need to 'disable machine interrupt' in wakeAll()?
Reimplement the waitUntil call without using busy waiting.
- No busy waiting.
- Put the threads in ready queue after they wait AT LEAST (NOT EXACTLY) the right amount of time.
- waitUntil will be called by more than one thread (So we need array / linked list)
The class maintains a list of upcoming threads-to-wake, in time sequence, and add new items in corresponding order.
Upon each timer interrupt arrives, we scan the list to remove and wake up the expired items.
Use heap to maintain the priority queue, to quickly insert and remove.
construct:
Create a heap of pairs (thread, time)
waitUtil:
diable timer interrupt # Tips from tutor
put (thread, waitTime) in the heap;
thread.sleep() # Tutor ask why we don't sleep on conditional variable here
enable timer interrupt # Tips from tutor
timerInerrupt:
# Do we need to disable interrupt?
while(heap is not empty and heap top's waitTime < currentTime)
thread=heap.pop()
thread.ready()
- Do we need to sort the linked list?
- Is it ok without using machine interrupt.disable()
one-word messages.
- No busy waiting
- No message buffer
- Send only return after a reader read the message
This task is similar to the producer-consumer model. The sender will wait upon receiver if message buffer occupied, and wake up a receiver after storing message; the receiver will try waking up a sender if there's no message, then wait upon sender if no message available.
- We should not use wakeAll() to wake receiver, at most one receiver can be running
- There will be starvation. As FIFO property is not guarenteed 1. Sender 1 sent a message. Receiver 1 reading. Sender 2 sleeping on CV. Sender 3 is going to send message. 2. Receiver 1 set buffer to null and wake sender 1 3. Sender 1 release the lock 4. Sender 3 get the lock and find buffer is empty. 5. Sender 3 send message 6. Sender 2 sleep again as it found message is not empty
- Is starvation matter? (No dead lock, but live lock may occur when there are lots of message sending)
Lock lock;
Condition Variable sendCV(lock),receiveCV(lock)
Word buffer;
Send(message):
lock.acquire();
while(buffer != null && no receiver)
receive.signalAll();
send.await();
buffer = message;
receive.signalAll(); # Wake at most one Receiver
lock.release();
# Let receiver to wake sender?
Receive():
lock.acquire();
receiverCnt += 1;
while(buffer == null)
send.signalAll();
receive.await();
tmp=buffer;
buffer=null;
send.signalAll(); # wake the new sender and the previous sender
receiverCnt -= 1;
receive.signalAll(); # make recevierCnt > 0
send.signalAll(); # wake sender for next communication
lock.release();
return tmp;
Implement priority scheduling in Nachos.
- No busy waiting
- Solve priority inversion problem
We use a heap to construct a priority queue of threads sorted by priority, to realise insertion and pop-maximum in log(n) time.
Each time a lock allocates a queue, it is also monitored by the scheduler; we find the lock acquiring relationship between threads by these queue, and calculate the new priority after priority donation.
Use the heap to find the appropriate next thread with highest priority.
Methods that need to be implemented:
-
PriorityScheduler.PriorityQueue:
- acquire:
- nextThread:
- pickNextThread:
-
PriorityScheduler.ThreadState:
- setPriority:
- waitForAccess:
- getEffectivePriority:
PriorityQueue:
constructor:
initialize the heap (Using newThreadQueue(True) to create)
nextThread:
pop the thread on heap top, then
return the popped thread
pickNextThread:
return the thread on heap top
ThreadState:
getEffectivePriority:
scan the thread donation relation tree,
and find the parent element with maximum priority;
return that priority.
wait for access:
insert this thread to the priority queue
if queue.priorityTransfer:
donate the priority to the thread
acquire:
(everytime a thread got a resource,
say lock , samephores or conditional variable)
(this function will be called)
(Tell the scheduler which thread will receive donation)
###Assumptions
First here comes our assumptions on the intelligence of people on the islands. It is reasonable that they should be able to figure out the island they are currently on, whether they are on the boat or not, the state of the boat. They should be able to follow some universal strategy for each child and adult. Also we reasonably assume that everyone on the islands have the ability to do simple arithmetic operations. That is, each one of them is able to:
- Count the number of adults and children on his current island;
- Decrease the corresponding number when seeing people leave his island;
- Increase the corresponding number when seeing people arriving at his island.
All the arithmetic operations above would be implemented through operations on shared variables done by each thread individually.
###Strategies
The strategies are stated as below:
- For children, if they detect that there are more than 1 children on the "source" island, they try to board the boat and be the driver. If there is exactly 1 child, try to board as rider. Each time a boat reaches the "destination" island, they try to board the boat and set off then there is 1 child aboard. If there is only 1 child on the "source" island, he simply board as the driver and set off.
- For adults, if they are on the "destination" island, or there are more than 1 children on the "source" island, they do nothing. Otherwise they try to board the boat and set off immediately.
When the procedure finalizes, the parent thread could be informed by observing that the number of children and adults on the "source" island becomes 0. Note that this is indeed an one-way communication, for that the parent thread never tries to modify that value. In fact, the parent thread do literally nothing except for starting and terminating the whole procedure.
Note that adults should not try to depart before at least two children has departed; otherwise, the boat cannot be driven back; also, when there's only one children, it should yield to adults for boarding.
###Pseudocode
Peudocode comes as below (for convenience, assume that all the operations done to integer variables are atomic, modified blocks has been included in braces):
#Shared variables:
state of the boat
Integer adultsOnSource, childrenOnSource, childrenAboard
lock boarding, childrenUnload
corresponding condition variable bd, cu
Parent:
start adults and children
yield()
while adultsOnSource + childrenOnSource > 0:
yield()
return
Adult:
increase adultsOnSource
{yield()}
while self on source:
boarding.acquire()
while childrenAboard > 0 or childrenOnSource > 1 or boat at dest:
bd.sleep()
decrease adultsOnSource
adultToDest()
bd.wakeAll()
boarding.release()
return
Child:
increase childrenOnSource
{yield()}
while true:
{isDriver = 1}
while self on dest:
boarding.acquire()
while childrenAboard > 0 or boat at source:
bd.sleep()
childDriveToSource()
increase childrenOnSource
bd.wakeAll()
boarding.release()
while self on source:
boarding.acquire()
{while childrenAboard == 2 or boat at dest:
bd.sleep()}
increase childrenAboard
isDriver = 1
{while isDriver == 1 and childrenAboard == 1 and childOnSource + adultOnSource > 0 or boat at dest:
if childrenOnSource == 1 or boat at dest:
decrease childrenAboard
bd.sleep()
increase childrenAboard
else:
isDriver = 0
bd.wakeAll()
bd.sleep()
if childrenOnSource == 1 and isDriver == 1:
decrease childrenAboard}
bd.wakeAll()
boarding.release()
if isDriver == 1:
childrenUnload.acquire()
childDriveToDest()
decrease childrenOnSource
{(decrease childrenAboard) deleted}
cu.wakeAll()
childrenUnload.release()
else:
childrenUnload.acquire()
{(while childrenAboard > 1:)
(cu.wait()) deleted}
childRideToDest()
{(decrease childrenOnSource) deleted}
childDriveToSource()
{(increase childrenOnSource) deleted}
{childrenAboard -= 2}
childrenUnload.release()
return
We added a TestManager class to automate the testing. When a test object is created, it will be added to the TestManager. After all test cases are tested, TestManager will report the result. We can find out how many and which case is fail easily. We also have a python script to parse the output of task VI. It saves lots of time on checking the validity of our solution.
- A traditional thread pool, which creates many thread and joins each of them once.
- An erroneous scheduler who joins a thread twice.
- A chain of thread each joining the subsequent one, until a certain depth, creating a chain of waiting. The last thread exits after some sleep/delay, and all other threads should also quit properly after the delay.
##Task II
- A database reader/writer application similar to the in-class example;
- A bank account transaction model, let teller waiting for deposit, such that no two threads operate on the balance simultaneously and at any time the balance is nonnegative.
- A signal/broadcaster model where the slept process is waken up immediately after a broadcast. Test such that no thread overslept.
##Task III
- Test the offset between expected sleeping time and actual slept time.
- Implement SleepSort in user space.
##Task IV
- 5 Receivers wait and 2 senders came; after the racing condition, only 2 receivers got the message
- 5 senders wait and 2 receivers came; after the racing condition, only 2 senders succeed
- 50 senders and 50 receivers came; no one is left stuck after the racing condition.
##Task V
- Make priority inversion case and the system should not deadlock.
- Make a reader/writer case and cause a livelock, to see the system is properly stucked (i.e. the writer is livelocked)
- Implement PrioritySort in user space.
##Task VI
- Test the scope of information is proper.
- Test the case when there's only many chindren, but no adult.
- Test the case when there's only one children and one adult, and see if they depart simultaneously.
- Test when there's no children and system should deadlock.