PintOS Implementation
I decided to write this post as it took me considerable time to understand what was needed for implementing project1 of PintOS and implementing a proper solution that would handle all test cases.
I would still suggest you all to do the same, but if you feel that you are stuck and need some food for thought please do read ahead. I wanted to make it a bit easier for all of you out there by giving you hints, but not provide you with the whole solution so that you can try implementing the solution yourself. Trust me, there is no better joy than writing your own code and watching it work exactly as intended.
Ok so here goes.......
For those of you doing the PintOs project1 here is a short overview of what you need to do:
There are basically three parts of the project that you need to implement properly:
1) Avoid busy waiting for threads
2) Implement priority scheduling considering cases such as priority donation, priority lowering and so on
3) Implement a Multilevel Feedback Queue Scheduler(MLFQS) based on the FreeBsd schedule calculating the thread priority, recent load average, the niceness of the thread and recent CPU time that has been taken by the thread.
1) For the first part we must first understand what busy waiting is:
Busy waiting occurs when a thread that has been scheduled to run, just runs in loop waiting for a condition to change. As a result it performs no useful work but uses the CPU time nevertheless. In PintOs, busy waiting occurs when timer_sleep() is called. You need to change the implementation so that the thread is put on a waiting list for a particular amount of time and then put back on the ready_list after the amount of time that it wanted to sleep for has passed. You can use semaphores for this, or you can use thread_block(), thread_unblock() and related functions to properly put the thread into a waiting list. If you are using semaphores you will need to order the list of waiters in a particular way.
Hint: For this, you need to consider the time after which a thread needs to be awakened and insert
those threads in a particular order.
2) For the second part, I would suggest debugging the main test case program(priority-donate-one) and watch what happens when lock_acquire() and lock_release() are called. You will then get a better understanding of what needs to be done here. Changes will be needed to file synch.c to modify locks and semaphores. You will also need to think of a data structure which needs to be used to track the priority donators and a way in which the priority of the thread should return to its original priority, or that priority of another thread if it is holding another lock that a higher priority thread is waiting on.
Hint: For priority-donate-chain ensure that the priority donation by a thread occurs for every thread above it(lower priority) that is holding a lock.
For priority-donate-multiple you will need to bump up priority of the lock holder(Main which holds locks A and B) as other threads may want to acquire B when A has been released. For the test priority-condvar, you will need to find a way to order the list of (lists)semaphores that contain threads of different priority. For priority-donate-lower you will need to make changes to thread_set_priority( ) to handle the case where a thread that has a bumped up priority by priority donation,wants to lower its priority.
3) Implement a Multilevel Feedback Queue Scheduler(MLFQS) based on the FreeBsd schedule
calculating the thread priority, recent load average, the niceness of the thread and recent CPU time
that has been taken by the thread. This final part is actually easier than it looks. You have to implement a multilevel feedback queue scheduling algorithm based on the FreeBSD scheduler. The formulas for calculating recent_cpu_average, the niceness of threads and the load average is given.
As the Pintos Kernel does not implement floating point calculations you will need to simulate them using integer values itself. In a 32-bit Int, 17 bits will be used to store the value, 14 bits will be used to store the decimal point values and one bit is the sign bit. The manual explains how to simulate floating point calculations pretty straight forward. You can also refer to the table given in the manual for your calculations.You can create a new header file and implement the various calculating functions that you will need when you calculate load_average and recent_cpu which need to be stored as floating point numbers. You can actually do the calculations in functions like thread_get_recent_cpu() itself but this is a neater and more modular way of writing code.
Ok so once you are done writing the functions that will be used for calculations you need to just calculate the priority, recent_cpu and load_average at the right instances of time.Note: Do not forget to increment recent_cpu every clock tick. Also ensure that these values are instantiated right, or else your calculations will go haywire at the start itself.
Hint: Instead of 64 queues you can use one queue also. This is already available in the existing
code itself. You only need to decide which queue to use.
Note: Remember to implement thread_get_recent_cpu() and related functions by multiplying by100 and then returning the rounded integer value. You will know you have gotten your calculations right when load-one and load-60 and the other load cases pass. After that it is a simple process of implementing thread_set_nice() and you are all set!
Happy Coding.....
I decided to write this post as it took me considerable time to understand what was needed for implementing project1 of PintOS and implementing a proper solution that would handle all test cases.
I would still suggest you all to do the same, but if you feel that you are stuck and need some food for thought please do read ahead. I wanted to make it a bit easier for all of you out there by giving you hints, but not provide you with the whole solution so that you can try implementing the solution yourself. Trust me, there is no better joy than writing your own code and watching it work exactly as intended.
Ok so here goes.......
For those of you doing the PintOs project1 here is a short overview of what you need to do:
There are basically three parts of the project that you need to implement properly:
1) Avoid busy waiting for threads
2) Implement priority scheduling considering cases such as priority donation, priority lowering and so on
3) Implement a Multilevel Feedback Queue Scheduler(MLFQS) based on the FreeBsd schedule calculating the thread priority, recent load average, the niceness of the thread and recent CPU time that has been taken by the thread.
1) For the first part we must first understand what busy waiting is:
Busy waiting occurs when a thread that has been scheduled to run, just runs in loop waiting for a condition to change. As a result it performs no useful work but uses the CPU time nevertheless. In PintOs, busy waiting occurs when timer_sleep() is called. You need to change the implementation so that the thread is put on a waiting list for a particular amount of time and then put back on the ready_list after the amount of time that it wanted to sleep for has passed. You can use semaphores for this, or you can use thread_block(), thread_unblock() and related functions to properly put the thread into a waiting list. If you are using semaphores you will need to order the list of waiters in a particular way.
Hint: For this, you need to consider the time after which a thread needs to be awakened and insert
those threads in a particular order.
2) For the second part, I would suggest debugging the main test case program(priority-donate-one) and watch what happens when lock_acquire() and lock_release() are called. You will then get a better understanding of what needs to be done here. Changes will be needed to file synch.c to modify locks and semaphores. You will also need to think of a data structure which needs to be used to track the priority donators and a way in which the priority of the thread should return to its original priority, or that priority of another thread if it is holding another lock that a higher priority thread is waiting on.
Hint: For priority-donate-chain ensure that the priority donation by a thread occurs for every thread above it(lower priority) that is holding a lock.
For priority-donate-multiple you will need to bump up priority of the lock holder(Main which holds locks A and B) as other threads may want to acquire B when A has been released. For the test priority-condvar, you will need to find a way to order the list of (lists)semaphores that contain threads of different priority. For priority-donate-lower you will need to make changes to thread_set_priority( ) to handle the case where a thread that has a bumped up priority by priority donation,wants to lower its priority.
3) Implement a Multilevel Feedback Queue Scheduler(MLFQS) based on the FreeBsd schedule
calculating the thread priority, recent load average, the niceness of the thread and recent CPU time
that has been taken by the thread. This final part is actually easier than it looks. You have to implement a multilevel feedback queue scheduling algorithm based on the FreeBSD scheduler. The formulas for calculating recent_cpu_average, the niceness of threads and the load average is given.
As the Pintos Kernel does not implement floating point calculations you will need to simulate them using integer values itself. In a 32-bit Int, 17 bits will be used to store the value, 14 bits will be used to store the decimal point values and one bit is the sign bit. The manual explains how to simulate floating point calculations pretty straight forward. You can also refer to the table given in the manual for your calculations.You can create a new header file and implement the various calculating functions that you will need when you calculate load_average and recent_cpu which need to be stored as floating point numbers. You can actually do the calculations in functions like thread_get_recent_cpu() itself but this is a neater and more modular way of writing code.
Ok so once you are done writing the functions that will be used for calculations you need to just calculate the priority, recent_cpu and load_average at the right instances of time.Note: Do not forget to increment recent_cpu every clock tick. Also ensure that these values are instantiated right, or else your calculations will go haywire at the start itself.
Hint: Instead of 64 queues you can use one queue also. This is already available in the existing
code itself. You only need to decide which queue to use.
Note: Remember to implement thread_get_recent_cpu() and related functions by multiplying by100 and then returning the rounded integer value. You will know you have gotten your calculations right when load-one and load-60 and the other load cases pass. After that it is a simple process of implementing thread_set_nice() and you are all set!
Happy Coding.....
