Process Management

Draft Version

Goals

1. Providing interface to start/terminate task/threads

2. Mechanism for communication between threads/task

Design

Task, Thread Management

This subsystem should provide some interface/function to create task. Task is collection of one or more threads. Task can’t run it self. Thread is the core of execution and it stores the execution snapshot. Each thread has kernel and user stack.

Thread States:

1. Running

2. Ready

3. Terminating

4. Waiting

Running state

A thread state is in running state, when it’s running on one of the processors. This state can be reached only from ready state when the scheduler selects it for running.

Ready state

A thread state is in ready state when it’s ready to run and waiting for scheduler to allot it a processor.

Waiting State

A thread state is in waiting state when the thread blocks voluntarily. This state can be reached only from running state.

State Transition	Ready	Running	Waiting	Terminating
Ready	NA	Scheduler moves the thread to run queue	NA	The task is terminating prematurely, so all the threads are getting terminated.
Running	Thread gets preempted because quantum expired	NA	Thread blocks because IO, mutex, sleep etc	Thread finished its work.
Waiting	Kernel finds the condition on which thread is waiting is signaled so it puts the thread back into the run queue.	NA	NA	The task is terminating prematurely, so all the threads are getting terminated.
Terminating	NA	NA	NA	NA

Task States

State of a task is the state of that of it’s most active thread.

Swap-out state

If the process is swapped out, it is in this state.

Swap-in state

This is a transient state when the process is in the context of moving from swap to memory.

Active state

When at least one of it’s threads are running, process is in active state.

Waiting state

If all the threads of a process are in wait state, then the process is in wait state.

Zombie State

A process state is in zombie state when one of it’s thread is terminating and finds that it’s the last thread in the process and that it’s parent is not waiting for it’s status. It is the responsibility of the parent to do the last rites (freeing task structure and kernel stack) for it’s dead children. So if the parent has not issued a wait call, it won’t be able to get the status of it’s child and hence some valuable cpu resources will go unused. Hence the state of the process switches to zombie when such a condition arises and a Housekeeping thread from kernel, periodically flushes all such threads in zombie state. Note that state of the thread in such a process will be terminating and will not change to zombie.
Scheduling

Scheduler exposes nothing to other systems. If exposed, then each system can have its own variant and will result in an inconsistent system. Also the scheduling activity happens for every clock tick. Hence it's unreasonable to expose scheduler functionality to other systems.

Scheduler is affected only by the PM (process/thread) structures.

Round Robin Policy with Priority Queues is chosen as scheduler policy.

Scheduler defines the following fields which should be included in the thread structure. Based on the state of a thread, it can be either in RunQueue or OtherQueue.

A scheduler sub system has its own array’s for maintaining the run queues called priority queues. Scheduler uses this array to select a thread to run.

Every thread is associated with a scheduler_data structure. This structure represents the thread inside scheduler and has enough information like: pointer to thread, priority level, etc..

When a thread is created, this structure is also created and passed onto scheduler to add into it’s internal database.

1. AddThreadToSchedulerQueue()
This function adds the given thread to the RunQueue. Kernel calls this function when it creates a thread and wants to put it in the run queue or when thread becomes runnable.

2. RemoveThreadFromSchedulerQueue()
This function removes a thread from the RunQueue. Kernel calls this function when a thread is blocking or when it is terminating.

3. SetThreadPriorityInfo()
Sets the given thread’s priority information like class, level etc

4. GetThreadPriorityInfo()
Gets the given thread’s priority information like class, level etc

5. Schedule()
Selects and returns a new thread to run. It is the responsibility of the kernel to run the thread.

Scheduler Algorithm

Scheduler maintains an array of priority queues (PQ). The scheduler maintains 5 different priority classes; inside each priority class there are 5 different priority levels. So the number of elements in the priority queue array is 5*5 = 25.

Scheduler priority classes:

· Very low

· Low

· Medium

· High

· Very High

Scheduler priority levels:

· Very low

· Low

· Medium

· High

· Very High

Threads are put into one of these queues and it can be reassigned to any of the queues at any time during it’s lifetime. Threads at level n are preferred over threads of level n+1.

Scheduler exposes priority classes to user; priority levels are not exposed. So the administrator can select any of these 5 different classes of priority. User can decide to give more/less priority to the thread by selecting suitable classes.

By default a user process inherits the priority of it’s parent and the threads of the same process can have different priorities. This is useful in situations where we design a process to have one thread to handle I/O operations.

Main objective of ACE scheduler is fair execution. So it tries it’s best to not let any thread starve for long time. This is done by moving threads between priority queues. So if a thread is found starving in a priority queue at level n, then it’s automatically moved to level n-1. However movement of any thread is restrained to it’s class.
TimeSlice quota expiry:

After thread’s time quantum expires, scheduler is called by the kernel to schedule a new thread.

Procedure to select a new thread:

The order of search for a new thread begins from current level and ends at level n where n is the least level(25). So threads from lower priority level are not run, until all threads from higher priority level are done with execution.

When a thread finishes it’s timeslice quota, processor is unhappy that the thread utilized it’s full quota without relinquishing control over the CPU. Hence it revaluates the sched_bonus value of the priority queue in which the thread resides:

If the value is equal to -5. Then the priority queue is moved to lower(n+1) priority queue slot and sched_bonus value is reinitialized to 0. This is called depromotion. Note that we only swap the priority queue pointers.

Else the sched_bonus value is decremented.

Whenever timeslice expires, sched_bonus value of each priority queue(5 queues) in the same class is recalculated.

Preemption:

While a thread is running, if a new thread is added to the ready queue, following steps are performed:If the new thread has got a lesser priority than the running thread, it keeps waiting in the ready queue.Else if the new thread has got a greater priority than the running thread, following steps are performed:The currently running thread is moved back to it’s ready queue and the priority queue in which the thread resides is recalculated.The new higher priority thread is selected to run..

Priority recalculation:

When a thread X is preempted by a higher priority thread Y, scheduler denies thread X of it’s cpu quota. Hence it is adjusted by increasing the sched_bonus value of the corresponding priority queue. If this value reaches +5, then we move the thread from level n to higher level n-1. This is called promotion.

Note: A scenario where a new thread is added to the ready queue is:

A thread has issued an I/O and hence it’s on wait queue. When the I/O is completed, I/O device raises an interrupt and the ISR puts the corresponding thread in ready queue. So if this is a high priority thread, then it will preempt the currently running thread on that cpu.

Key points on this scheduling policy

1. A thread in low priority queue will starve for sometime, only if multiple threads at higher priority queue keep executing. This will not happen for a long time, because the sched_bonus value will be decremented for the higher priority queue whenever the timeslice expires on one of it’s threads. Hence an entire priority queue is depromoted if it is CPU hungry.

2. Similarly if threads in a priority queue are I/O bound, then the priority queue is promoted.

3. Note that promotion and depromotion happens only within a class.

4. A thread from lower priority queue can starve forever, if threads in higher priority queue keep on executing and move between waiting and ready state. But this is highly unpredictable and impossible to program from user, because a user cannot predict when the scheduler selects a particular thread to run. Hence the scheduling policy is false proof.

5. During promotion and depromotion, if the value of sched_bonus reaches maximum or minimum, it is left at that extreme value itself without any alteration.

Context Switch

Things to be done on context switch:

1. Call processor dependent code to do the following:

a. Save registers of running thread.

b. Load registers of newly selected thread.

c. Change the processor structure fields to reflect newly selected thread credentials.

d. Invalidate TLB and cache.

2. Call MM to switch the virtual memory layout.

IPC

Communication between kernel-threads and user-threads happens only through signal mechanism. Threads inside a process will not need any explicit mechanism and hence for communication between user threads of different process, shared memory or message passing has to be used.

Task (To share bulk data, shared memory option should be given.)

Since this form of communication is common for all threads of a process, all information/data structures are maintained per process.

1. Message Passing

All task has a queue to store messages where kernel posts all the messages from other task's thread into this message queue. It is the responsibility of the task to clear the message queue, to avoid overflow.

2. Shared Memory

Only access permission and statistics are maintained in PM; all other details are maintained in VM.

Data Structures:

struct Process

{

/*process management fields*/

UINT32 Id; //Unique id for the process

UINT32 ParentId; //Parent id

TIME CreationTime; //Creation date time of the process

UINT32 State; //Current state of the process

UINT32 Flag;

UINT16 ReferenceCount; //number of objects referring

LOCK Lock; //synchronization mech for process

/*thread management*/

THREAD ThreadRunQueue; //threads in the run queue

THREAD ThreadOtherQueue; //threads in the state != run

/*vm related fields*/

V_MAP VirtualMap; //virtual_map for this process

/*scheduler related fields*/

UINT16 MaxPriority;

UINT16 CurrentPriority;

THREAD RunQueue; //threads in the run state

THREAD OtherQueue; //threads in the other than run state

LOCK SchedulerLock;

/*IPC related fields*/

MESSAGE MessageQueue; //message box for this process

LOCK MessageLock;

};

struct Thread

{

/*management fields*/

LOCK Lock;

UINT32 State; //state of the thread

UINT32 Flag;

UINT16 ReferenceCount; //number of objects referring

/*queue management*/

THREAD NextThreadProcess; //next thread in the same process

THREAD NextThreadCPU; //next thread in the CPU

/*process related fields*/

PROCESS Process;

/*scheduler related fields*/

UINT16 MaxPriority;

UINT16 CurrentPriority;

TIME LastRun; //when the thread last removed from runq

LOCK SchedulerLock;

/*execution context*/

CHAR* Stack;

CPU RunningCpu;

/*ipc related fields*/

UINT32 Signal; //bit mask for signal

/*synchronization related*/

EVENT WaitEvent; //event for which this thread is waiting

TIME TimeOut; //time when a panic should called

};
Functions/Macros:

Macros/inline functions:

inline GetCurrentProcess()

Returns current running process structure.

inline GetCurrentThread()

Returns current running thread structure

inline GetCurrentCpu()

Returns current running CPU structure

Process related:

CreateProcess()

Creates a new process and starts a single thread and returns process structure.

Arguments:

· ProgramName – Path and name of the program to start

· EntryPoint – Symbol name to start execution of the first thread

TerminateProcess()

Terminates execution of a process and removes all associated data structures.

Arguments:

· ProcessId

GetProcess()

Returns process structure for a given process id.

Argument:

· ProcessId

SetProcessPriority()

Sets the priority of a process

Arguments:

· ProcessId

· Priority

Thread Related:

CreateThread()

Creates a new thread and returns its address

Arguments:

· EntryPoint

PauseThread()

Pauses execution of a thread.

Arguments:

· Thread

ResumeThread()

Starts/resumes execution of a thread.

Arguments:

· Thread

TerminateThread()

Terminates execution of a thread and removes all datastructures associated with it.

Arguments:

· Thread

IPC Related:

PostMessage()

Adds the given message in a process’s message queue.

Arguments:

· ProcessId

· Message

ReteriveMessage()

Removes a message from the current process message queue and returns it.

Signal()

Sets the signal bit for a thread.

Arguments:

· Thread

WaitForEvent()

Puts the given thread in the pause state and waits for the given event to occur.

Arguments:

· Thread

· Event

EventOccured()

Wakes one or more threads waiting for the particular event.

Arguments:

· Event

· NumberOfThreadsToWakeup