Comparative Analysis of O(1) and CFS Schedulers of Linux

Given below are the links to the two documents that you need to read and understand. The first is a very detailed paper that allows you to understand the concerns that drive the scheduler design based on the market being targeted by the OS. It explains the O(1) scheduler introduced by Ingo Molnar to take care of the issues with the introduction of Linux into multiple markets. It also describes the earlier scheduler of Linux (the 2.4.* kernel scheduler). The second link gives the state-of-the-art scheduler (to my knowledge) of Linux. The primary driving force here being the SMP becoming a common platform of every user in the world.

WHAT TO SUBMIT: A one to two page summary of your understanding of the schedulers in your handwriting.

NOTE: You are allowed to discuss the papers with each other and understand the papers. You are also allowed to analyze the papers together. You are NOT ALLOWED to copy the final summary from each other.

CAUTION: ALL ASSIGNMENTS FOUND TO BE COPIES OF EACH OTHER WILL BE GIVEN ZERO regardless of who copied from whom.

Write your own Basic Shell

Write a basic shell program, which when run, prints its prompt and waits for input from the user. When the user types something and presses ENTER, it accepts the input and tries to execute whatever the command given. If the command cannot be found, it prints the error Command Not Found. This will require parsing the PATH environment variable and looking for the command in the directories of the PATH.

Otherwise, it executes and prints the output of the command. Remember that a shell does a fork() and exec() to execute the command given. You need to do the same. You need to be able to accept any command line arguments given for the command and pass them to exec(), just as a shell program does.

NOTE: Remember that the cd command has to be implemented differently.

Grading Policy: If the program segment faults or results in zombie processes or hangs, you will lose marks accordingly.

Please refer to the previous page on Assignment submission policy. Also, read the coding guidelines given below and follow them. Any code which does not follow the coding guidelines is likely to lose marks.

Please read the Coding Guidelines and make sure you follow these guidelines.

Use gcc -Wall as the compile command in your Makefiles.

CAUTION: Make your code as modular as you can get it to. You will be adding features to the shell, esp. once IPC is done.

Extend your own Basic Shell

Handling Background Processes: You should be able to handle putting a process into background. This will mean parsing the command and if there is an "&" at the end, you need to disconnect the child process from the terminal. Read up on the net and Stevens' APUE to understand how to do this.
Handling Piped Commands: Parsing must be extended to check for the pipe character "|". If found, the characters before this character form one command and all others after it are part of another command(s). You can initially do with only one pipe. However, your parsing must be general and modular. Fork processes as required after opening pipes as required. For one piped command, the parent can open a pipe. For multiple piped commands, check if it is easier for you to fork from the child after opening a pipe in the child. This is one design model. The other is that the parent shell process forks all children. This may be more difficult to handle.

Build your own partial ps command

Read The /proc filesysem documentation or The /proc filesystem. Or, alternately you can use the man pages with the command 'man 5 proc'.

Understand the entries and the contents of various files in this directory /proc.

Write a program to read the /proc filesystem and print the following for all the processes listed there:

PID, PPID, STATE, COMMAND, No. of Files open

Since for all the root or privileged processes, you are not allowed to read the no. of files open, print NA for those. For all user processes, print the no. of files open.

Below are some Hints for the assignment.

Use the systems calls - opendir, chdir, readdir for opening, changing to and reading the contents of a directory. If you do not change to the directory you are opening, make sure the path is correctly set by concatenating the path to the file/directory you are trying to open.
Remember to check the return value of every system call you are using. This is most important for system calls. In fact, without this, you will find yourselves in a lot of trouble to debug or understand what is happening.
Typically, system calls only return -1 when there is an error. They set a global error number variable called errno which is defined in errno.h. Since it is difficult to understand the number itself, Unix/Linux provides the function strerror(errno) to print a human-readable string which gives the error encountered. Use this to debug your code.
Use fopen and fgets calls to read the contents of a directory. Then use either strchr, strtok or sscanf to parse the contents of the file and read the pid, ppid etc. values.
Make sure your code is modular with different functions doing different logical pieces of work and unit test these functions as you build them to enable fewer bugs. If you write the complete program and only then try to debug, you may find yourself bogged down.