For this assignment you will be using a framework I built, you have access to the source code for the framework if you want but you should not need it. The framework can be found here
The framework is a simulator, it simulates a processor working on multiple threads. It creates time slices of approximately 50 microseconds and switches threads in order to simulate process scheduling. You will be responsible for writing the scheduling algorithm, sleep functionality, locking, and priority donation.
You will implement 3 concepts, scheduling, sleep, and priority donation. Each of these concepts will require you to a variety of functions in the framework.
Currently scheduling is a first come first serve implementation. You will have to modify it to be round robin for items of the same priority while allowing those items with high priority to go before those with low priority. The highest priority available is 10, the lowest 1, and the default is 5. You will implement scheduling by implementing nextThreadToRun which is called every tick. By providing the correct thread you can control scheduling.
Currently sleep is not implemented, you will need to implement by writing the scheduling algorithm in such a way that those threads that choose to sleep are chosen on the tick they are supposed to wake up at in priority order. You may not busy wait, you must wake up exactly at the tick that you are scheduled to. It would be best to avoid checking every currently sleeping thread minimizing to only check the minimum number.
Implement priority donation in the simulator. When threads are waiting for a lock,the highest priority waiting thread should be awakened first. A thread may raise or lower its own priority at any time. One issue with priority scheduling is "priority inversion".
Consider high, medium, and low priority threads H, M, and L, respectively. If H needs to wait for L (for instance, for a lock held by L), and M is on the ready list, then H will never get the CPU because the low priority thread will not get any CPU time. A partial fix for this problem is for H to "donate" its priority to L while L is holding the lock, then recall the donation once L releases (and thus H acquires) the lock. Implement priority donation. You will need to account for all different situations in which priority donation is required. Be sure to handle multiple donations, in which multiple priorities are donated to a single thread. You must also handle nested donation: if H is waiting on a lock that M holds and M is waiting on a lock that L holds, then both M and L should be boosted to H's priority. You must implement priority donation for locks.
You are given two data structures a map and a list. Both may come in handy for this assignments. Lists will be needed for your ready and wait lists. The map may come in handy for mapping threads to locks. Instructions on using both classes are in the headers. All lists and maps are represented with UUID's These are unique strings that won't get duplicated.
Using the debugger is challenging if not almost impossible. Since signals are sent every 50 micro seconds and there is multithreading under the covers, running a debugger in the threads as they are working often gets interrupted. You might be able to do it on a small scale and are welcome to try however I cannot guarantee that you will see the same outcome with debugging as you see with running the software.
The better solution is to print data out that you need, unfortunately you cannot simply use printf due to the multithreaded nature of the simulator it often results in deadlocks and frozen programs. You will find a logger that you can use, full functionality of the logger which logs to stdout is located in Logger.h
The simulator is written in C++ and since you must make calls into the C++ library your code is also a C++ project. That having been said you must write your code in the C style, this means you may not use the STL or any C++ features. It also means that you must cast all your pointers to their proper type as you must use C++ syntax. If you are unsure of something you are about to use please ask an instructor.
You will all have a project created for you with the name <username>_project2_threading. This is the project you will be working in. Your repo will be forked automatically at the due date and time. You will also have to sync the include and library repo. Wherever you sync this library will be have to be put into an environment variable SIMULATOR_INC_LIB_DIR in your threading project.
All functions that need to be implemented are labeled in the header files and include the following.