OS161 PID Allocation

The quickest way to find a solution to essentially any problem you come across while working on OS161 is to look at the Linux kernel source or other similar resources.
Some useful sites include :

The IBM Technical Library

An IBM article on Linux Process Management 

Some of the Linux kernel read with a text-to-speech synthesizer (including text source) 

Linux Kernel Repository with tagged symbols 

Stack Overflow

How The Linux Kernel Works
Now obviously the Linux Kernel does a lot of optimizations and has many more features than we currently have to deal with in OS161 so I will keep the details light.

For our implementation each process will have a PID. In Linux each process may have many process IDs, thread group IDs, process group IDs, and session IDs, and all of these are included in the task_struct structure. Linux keeps all of these IDs tucked away in hashed doubly linked lists and iterates over them in very weird, very (assumingly) optimized ways.

We do not need a lot of these implementation details. What most of us are looking for is how does Linux keep track of PIDs of any type, how does it reclaim them, etc.

What the Linux kernel does is make an array of bitmaps (explanation to follow) that are the same size as memory pages. It uses these in combination with test and set operations to create a management system that does not use locks, is allocated page-by-page and thus has a low memory over head, and is scalable up to 4 million PIDs (the size of an unsigned int).

So, what is a bitmap. If you have heard of bitfields, same concept. The Linux kernel will initially allocate a single page of memory (probably 4KB) and use each bit to represent a PID. This allows you to determine if PIDs 0-4095 are in use using only 4KB. This is extensible because if the PID is greater than any value on the current page, allocate a new one. If the PID is greater than your defined max_pid, wrap around. To keep track of available PIDs per page, Linux has a counter associated with each page of how many PIDs are available. This is atomically incremented and decremented appropriately. This allows you to quickly identify if there are any PIDs left on a given page.

Once a process has a PID Linux does a few more things with it. It gets attached to the task, added to hashed-doubly-linked lists, etc. Since we do not expose threads to the user, only processes, we don’t have much more to worry about in our allocation scheme. You can even use the existing thread structure and assign the PID to the thread ID. You may need to be able to look up a thread structure (if you use it) by PID for things like parent-child relationships, waiting until a process reaches a certain state. These things can be accomplished other ways but you may want to throw all your processes into a hash table or something.

What should I do for OS161?
For OS161 you are not required to implement exactly what the Linux kernel does but understanding what a large system is useful information. Using this you could decide to make this on a smaller scale. If you only need 4096 PIDs, don’t bother with pages just use a single bit map. Feel free to think of other methods of implementing this, you could create a linked list of reclaimed PIDs and only increment your max PID when this is empty. Remember for an assignment like this simplicity can be your friend as school deadlines are not very flexible.

Hopefully this sheds some lights on the mystery of PID allocation
- FlounderingZ


Edit : Prof. Lie has read this content and feels it lies well within the guidelines of Academic Integrity at U of T. Feel free to share with your friends and check back for more.
Edit 2: Never edit a post after uploading from Windows Live Writer, wow!