Implementing Processes, Threads, and Resources

Hard Disk Scheduling

There are several different strategy models to hard disk scheduling. Here are a few simplified ones:

FCFS (First Come First Serve)

• Services requests in the order that they are received
• Some advantages of this model are that it is clean, easy to implement, and fair. The first request that comes in is served first.
• There are many disadvantages to this model, however. Starvation can occur since the most recent requests made will have to wait until all previous requests have been serviced. Additionally, this model does not make any effort to reduce the amount of movements that the hard drive head performs. This causes the model to be very inefficient.

SSTF (Shortest Seek Time First)

• Services the request of memory that is closest to the head of the hard drive
• More efficient than the FCFS model in that it reduces the amount of jumps that the head needs to perform to retrieve the data
• A downfall of this model is that it is possible for some memory requests to run into a starvation situation if more memory requests keep coming in that are closer to the current location of the head. Therefore, this model is considered to not be very fair

CSCAN (Circular Scan)

• Much like the elevator scan model, CSCAN services all memory requests in ascending block order in the queue until it reaches the highest requested block. At this point, it moves backwards servicing requested blocks in descending order. In both cases, it ignores requests that would result in backtracking.
• Advantages of this model are that it is more fair than the SSTF method in that it still maintains somewhat of a order in which the block requests arrive. This method minimizes the starvation that can occur in the SSTF method.
• Since the head of the hard drive doesn't bounce around to serve block requests in different areas of the HD, this method can be considered efficient.

Anticipatory Scheduler

• The current UNIX model is a variation of the elevator model known as an anticipatory scheduler. Once a block request comes in, it doesn't immediately service it. Instead, it waits to see if there is a natural grouping of block requests and then services them all then.

Side Notes

• You can never really achieve perfectly fair scheduling because there is almost always a speed tradeoff
• Write Leveling is a way to virtualize mapping of memory. This is performed to increase the lifetime of the hard disk. If it becomes apparent that a certain block of memory gets read or written frequently, the mapping to this memory block changes to reduce wear and tear

Kernel and User Space Threads

A process can have multiple threads and multiple execution contexts. The CPU implements time slicing which is the allocation of CPU usage to a process or thread. The internal clock periodically causes an interrupt and changes the execution context in order to provide another process or thread with CPU usage.

However, context switching is expensive overhead. It is time spent not performing calculations. The amount of threads that a user can create should be bound since there comes a point where the CPU is just performing context switches to provide each thread with CPU usage instead of actually computing anything. For example, if a user wants to create, 1 000 000 threads, then that means that the time slice that is allocated for the process will be divided into 1 000 000 smaller slices. User space timers are a way to limit the amount of threads that can be created for a process.

It is possible to use threading in systems that do not typically support threading. Essentially, the kernel allocates CPU usage to the process and the user is then responsible for splitting up that usage and allocating it to the threads that the user creates. Creating a custom scheduler is cumbersome and difficult, however, so generally it is best lest to the kernel to deal with CPU usage allocation.

Task_Struct

The Linux model does not distinguish between processes and threads. It simply sees these two things as scheduleable entities. Task_struct is the structure that is used for these entities. It has the following properties associated with it:

• virtual memory (threads are 2 task_structs that share the same vm)
• executable
• process/thread ID
• CPU state
• children, parent
• status
  • running (currently has CPU time and it’s running)
  • ready (just needs CPU time and it’s ready to go)
  • blocked (waiting for I/O)
  • sleep
  • zombie (child’s exit status has not been received by the parent yet. No other statuses are appropriate for this process because execution is complete but the parent does not know about the status yet)

Zombies

A zombie is a process that has completed execution but has not yet had itself removed from the process table. This means that even though the process is finished and its resources deallocated, it's PID still remains reserved and the parent process still has not retrieved its exit status. In order to kill the zombie, the parent should retrieve the exit status by executing a wait call. If the parent is killed without having read the zombie child status, init becomes the new parent of the zombies. Init calls wait every so often to kill any zombies that might be limping along.