PintOS System Call Handling
I finished Project 2 of PintOS, and hoped to write a blog, but this has taken more time than imagined. Here are my thoughts and suggestions to help you in your project. So project 2 is supposed to be significantly longer and harder than project 1, but not to worry :D, it does involve more coding and better understanding of how system calls function but that will not be too hard for you guys if you have finished with project 1. I was able to complete all but 2 cases(, Sync-read and Sync-write, Still dont know how to complete these).

Project 2 is all about system call handling. I think you might have a decent idea about system calls as this must have been taught in class. I will shed some light about what you must do to implement system call handling in PintOS.
First with the statistics:
There are about 76 test cases which will test the functionality of the system, out of which a lot of them will also try to break your OS. You need to implement proper handling to ensure that faulty user programs are terminated by the kernel. Other than that there are also a few cases which will try to break the VM of the OS, as well as some which checks to see the extent to which file handling is implemented.

Let me break this down into a few main steps:
1) Argument passing
2) System calls
3) Executing and waiting for child processes(Included in system calls but is the hardest to implement and hence you should carefully decide the data structures and functionality related to this problem)

Do go through the code in userprog/ and filesys/ folder. For the latter, you only need to use functions defined here, without the need to modify anything here.
You will need to make minor change in the exception.c file to handler user errors.
go through the pagedir.c file as you will be needing functions like pagedir_get_page and the like. This will also help you gain a better understanding as to how memory is allocated.
Alright so lets begin!
The OS at this initial state is absolutely useless. It even does not print to output(From a user program perspective). The first thing that you need to implement is argument passing, so that functions can at least pass arguments to other functions(In the user to the kernel context).
The first step to solve this is to break your arguments using strtok_r. Store the original command line arguments in another variable. You will be needing this when you start pushing these arguments into the stack. This will have to be done once in process_execute and start_process.
Refer to the manual which states how the stack must look at the end.

For system calls, you need to first check whether the pointer passed to you by the user program is valid or not. Check whether it is null or not and also use thread_get_pagedir() to check if the pointer points to the memory of a user process. Once that is done, we can figure out which system call is being called. For filesystem calls, we have the filesystem interfaces in filesys. and file.h. Use that to open, close, read and write to files. Remember to acquire and release locks for implementing file system calls. For the specical case of write to STOUT_FILENO(1), just use the system call to write to console.

For implementing exec and wait system calls, a thread needs to maintain a list of child processes so that you can call wait on those processes. Also children need to have a pointer to a parent so that they can signal to the parent once they have exited. Remember childs may exit prematurely or, in some cases the parent must have already finished execution, so you need to handle that case properly.
That is about it.
You should have now have an OS that is able to run a lot of user programs, atleast the ones that need at least less than 4KB of memory.
In Project 3, we will be implementing features such as paging so that the OS can run user programs which need more than 4KB of memory.









  

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.....