Task Basics

Task: A task is an execution unit where CPU can dispatch, execute and suspend. This task can be called in different operating system as a Process, Thread, Fork and other names. All program execution should happen within a task.

A task is a combination of two parts:

  1. Task Execution Space: This consists of a Code segment, Stack segment and Data segments. If operating system uses processor privilege level protection, the task execution space provides a separate stack for each privilege level (SS0, SS1 and SS2).
  2. Task State Segment (TSS): This provides a space for storing the task state information. This is mainly used in multitasking system.
  3. TSS Descriptor: Like other segments, TSS is defined by a segment descriptor. TSS descriptor should be placed only in GDT (Global Descriptor Table). This cannot be placed either in IDT (Interrupt Descriptor Table) or LDT (Local Descriptor Table). Refer following Figure.

Busy Flag (B) in descriptor indicates whether a task is busy or not. This should be maintained (Setting/Clearing) by operating system while running multiple tasks. If this flag is 0, then task is not busy or else it is busy.

When flag G is 0 in a TSS descriptor limit field must have value equal to or greater then 67H, even if there is 1 byte less than 67h during task switch will generate Invalid-TSS exception. Size can be more if Operating system add’s extra field or if it’s included I/O permission bitmap in TSS. Processor will not check the max limit by default, checks only minimum limit of 67h. During I/O operation it’s going to check the maximum limit field.

Each CPU should have 1 task minimum. All these descriptor is stored only in GDT and GDT size is 2^16=65536 bytes. Each GDT size is 8 bytes. So, GDT can store maximum 65536/8=8192 descriptors. So, we can create maximum tasks using hardware method only 8192 tasks. This is actually a limitation. Although we cannot create even this many tasks and maintain due to various reasons like non-portable, might saves state of current task more then what we require, difficult to debug, etc…

If paging is enabled (most enables) for a task, base address of Page directory used by the task is loaded into CR3 register (Control Register 3). In WinNT, after switching to new thread and if the current executing and new thread is part of different process, then it updates CR3 register where new thread is going to access its process address space. In this way, it can give protection for not accessing other process address space. Updating CR3 register is costly since it flushes CPU internal cache.

Creating more number of Hardware Task Switching is left to choice of Operating System and it should create at least one Hardware Task. Most of the modern operating system will use stack based switching to switch between different tasks by re-using the same hardware TSS by updating manually required fields. This software based task switching will give greater control to operating system to deal with many situations.

Before running task using LTR (Load Task Register)/STR (Store Task Register) instruction we need to load current task in this register. This has visible field for software and Non-visible field which are accessible only from processor.

Following field will be present in currently executing task (Check following Figure):

  1. Segment registers CS, DS, SS, ES, FS and GS
  2. State of the general purpose registers- State of EFLAGS register
  3. State of EIP (Instruction Pointer)
  4. State of control register CR3
  5. State of Task register
  6. State of LDTR register
  7. I/O Map base address and I/O Map
  8. Stack pointers of all Privileges SS0, SS1, SS2.
  9. Link to previously executed task

Task switch happens either using JMP or CALL instructions and return will be initiated using IRET instruction. There are methods for using INT instructions also.

Using multi-task method as explained above, we can create many tasks to execute concurrently even though we cannot execute concurrently on single physical CPU. Using the stack based task switch it will make operating system looks like executing more than 1 task at a time using Preemptive multitasking method. This has done by assigning time slice for each thread, after completing executing for that much time Operating system will suspend the currently executing task and dispatches new task for execution.

When we have multiple tasks and if these tasks are sharing the same global data structure, then we need to synchronize data or else tasks might corrupt data by updating from more than 1 task.

Take example of the following structure:

type struct _DUMBSTRUCT
{
int iIndex;
char cValue;
}DUMBSTRUCT;

DUMBSTRUCT strData ; // Global variable

TASK1()
{
strData.iIndex = 10 ;
strData.cValue = ‘A’ ;
}

TASK2()
{
strData.iIndex = 20 ;
strData.cValue = ‘B’ ;
}

Here there are 2 Tasks where OS can switch between them. During executing TASK1 and while updating value of first field of structure time slice might get over and operating system will suspend this task and schedules TASK2.

Current value of struct is :

strData.iIndex = 10 ;
strData.cValue = 0 ;

Even in this task TASK2 it is updating same variable and it will update both fields. Now the current value ‘strData’ is as follow:

strData.iIndex = 20 ; ( Overwritten value which is written by TASK1 )
strData.cValue = ‘B’;

After suspending TASK2, variable ‘strData’ has wrong values. To avoid this, we need to have some use Synchronization methods where we can prevent data corruption

Modified code:

TASK1()
{
WaitForLock();
strData.iIndex = 10 ;
strData.cValue = ‘A’ ;
ReleaseLock();
}

TASK2()
{
WaitForLock();
strData.iIndex = 20 ;
strData.cValue = ‘B’ ;
ReleaseLock();
}

In this way, till TASK1 completes the updating of global variable, second TASK2 will not get lock and will not update the variable. It will wait till it gets lock to touch the global structure.

Now, do we need to Synchronize if we use global variable (of Basic data type) like following:

int Index = 0 ;

TASK1()
{
Index ++ ;
}

TASK2()
{
Index ++ ;
}

Let’s say compiler will generate code like following:

Index ++ ;

TO

[Generate code of compiler in 3 steps, this is not actual instructions]

STEP-1: move Index value to register
STEP-2: add 1 to register value
STEP-3: move register value back to Index

During executing TASK1 and after executing STEP-1, Operating system will suspend TASK1 for executing other task.

Current fetched value of Index is 0

When it starts executing TASK2, it will perform above 3 steps like:

STEP-1: Register <- Index (Value is 0)
STEP-2: Register = Register + 1 (Value of Register is 1)
STEP-3: Index <- Register (stores value of 1 into Index)

Current value of Index is 1.

After this Operating system will switch back to TASK1 and continue executing from STEP-2(earlier it was suspended after expecting STEP-1). Current value of Register is 0 and continues further:

STEP-2: Register = Register + 1 (Value of Register is 1)
STEP-3: Index <- Register (stores value of 1 into Index)

Here, you can clearly observe total value of variable ‘Index’ should be 2. But, due to accessing wrongly from multiple tasks value got corrupted. In most modern compilers they will not generate 2 steps for incrementing variable; they will do by one instruction itself. However, in multiple physical CPU there is still a chance of accessing the same variable from multiple tasks at a time. Here, if there are 2 physical processor we can execute 2 tasks parallel. To synchronize in this situation hardware itself provides LOCK instruction where it guarantees only 1 can modify variable.

In WinNT, Win32 function for this purpose like:


InterlockedCompareExchange(),InterlockedCompareExchangePointer(), InterlockedDecrement(), InterlockedExchange(), InterlockedExchangeAdd(), InterlockedExchangePointer() and InterlockedIncrement().

WinNT Process

Process is a data structure which has several information to control the running program. This will have following fields:

  1. Info about physical memory used by this process.
  2. Info about code, data and stack segment used by this process.
  3. Info about each thread created by this process.
  4. Info about memory allocation is done by different threads.
  5. Info about file handles from different threads.
  6. Info about various objects created or opened by this process.
  7. There are lot of other info is stored in this data structure to keep track of what is happening in each process.

WinNT Threads

Thread is a data structure which controls execution unit. This data structure is used to store all Task info during suspending the Task. This has fields like:

  1. Info about Context registers (like TSS)
  2. 2 Stack pointers for both UserMode and KernelMode
  3. Private storage info for using by subsystems, run time libraries and DLL’s
  4. It has security context info related to thread. There are lot of other info is stored to control the execution unit.

Task scheduling: In a preemptive multi-tasking system, it will generally have multiple queues along with priority assigned. Each time users create any Task, he will also mention priority for the Task. Based on this Operating system will select the task and dispatch for executing. During running low priority task, if there is any high priority task arrives, it will suspend current task and run’s high priority task. Operating system also makes sure that all the tasks in all level of priority will get a fair chance to use CPU time.

This preemptive multi-tasking is implemented using timer, like timer ISR(Interrupt Service Routine) will get control for each millisecond and here operating system will get a chance to check time slice of the current running thread, if need it will switch to new thread and continues executing the new thread.

Note: Hyper threading will have 2 logical CPU’s within same Physical CPU. This will run 2 tasks at a time. Synchronization should be applied like we do it for multi-processor.