Different types of scheduler in operating system

1.   Long Term Scheduler: It is also called job scheduler. Long term scheduler determines which programs are admitted to the system for processing. Job scheduler selects processes from the queue and loads them into memory for execution. Process loads into the memory for CPU scheduler. The primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and processor bound. It also controls the degree of multiprogramming. If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system. On some systems, the long term scheduler may be absent or minimal. Time-sharing operating systems have no long term scheduler. When process changes the state from new to ready, then there is a long term scheduler.
2.  Short Term Scheduler: It is also called CPU scheduler. Main objective is increasing system performance in accordance with the chosen set of criteria. It is the change of ready state to running state of the process. CPU scheduler selects from among the processes that are ready to execute and allocates the CPU to one of them. Short term scheduler also known as dispatcher, execute most frequently and makes the fine grained decision of which process to execute next. Short term scheduler is faster than long term scheduler.
3.   Medium Term Scheduler: Medium term scheduling is part of the swapping function. It removes the processes from the memory. It reduces the degree of multiprogramming. The medium term scheduler is in charge of handling the swapped out-processes.

Running process may become suspended by making an I/O request. Suspended processes cannot make any progress towards completion. In this condition, to remove the process from memory and make space for other process. Suspended process is move to the secondary storage device. Saving the image of a suspended process in secondary storage is called swapping, and the process is said to be swapped out or rolled out. Swapping may be necessary to improve the process mix.

Max HeapSort Algorithm and its Application in implementing Max Prioritiy Queues

Operations supported on Max-Priority Queues are:
1)  Max : Returns maximum element currently in queue in O(1) time
2)  ExtractMax : Returns and removes maximum element currently
                         in queue in O(lg(n)) time
3) Insert: Inserts given element in queue in O(lg(n)) time
4) IncreasePriority : Increases priority of element at given index in
                             O(lg(n)) time
5) IncreasePriority : Decrease priority of element at given index in
                             O(lg(n)) time

All order statistics mentioned above is in worst case

#include <stdio.h>
#include <stdlib.h>

#define LEFT(i) ((i<<1)+1)
#define RIGHT(i) ((i<<1)+2)
#define PARENT(i) (i>>1)

void Swap(int *i,int *j);
void MaintainMaxHeap(int a[],int index,int size);

void BuildMaxHeap(int a[],int size);

void HeapSort(int a[],int size);

int Max(int a[],int numValidElements,int size)
{
    if(numValidElements>0)
        return a[0];
    else
            fprintf(stderr,"Error\n");
}


/*
Number of numValidElements count should be decremented 
by caller itself.
*/
int ExtractMax(int a[],int numValidElements,int size)
{
    if(numValidElements>0)
    {
        Swap(&a[0],&a[--numValidElements]);
        MaintainMaxHeap(a,0,numValidElements);
        return a[numValidElements];
    }
    else
        fprintf(stderr,"Error\n");  
}


void IncreasePriority(int a[],int index,int newPriority,int numValidElements)
{
    if(a[index]<newPriority)
    {
        a[index]=newPriority;
        while(index>0 && a[index]>a[PARENT(index)])
        {
            Swap(&a[index],&a[PARENT(index)]);
            index=PARENT(index);
        }
    }
    else
    {
        fprintf(stderr,"Error in IncreasePriority\n");
    }
}


void DecreasePriority(int a[],int index,int newPriority,int numValidElements)
{
    if(a[index]>newPriority)
    {
        a[index]=newPriority;
        MaintainMaxHeap(a,index,numValidElements);
    }
    else
    {
        fprintf(stderr,"Error in DecreasePriority\n");
    }
}


/*
Its upto caller to increase numValidElements after 
*/
void Insert(int a[],int priority,int numValidElements,int size)
{
    if(numValidElements<size)
    {
        a[numValidElements]=INFINITE;
        IncreasePriority(a,numValidElements,priority,size);
    }
    else
        fprintf(stderr,"Queue Overflow\n");

}


/*
Pre: Subtrees of node at position index are already both max_heaps 
       and size is number of elements in an array 
Post: Element at position index is inserted properly so that tree rooted 
        at index is max_heap 
*/
void MaintainMaxHeap(int a[],int index,int size)
{
        int left=LEFT(index);
        int right=RIGHT(index);
        int max=index;
        if(left < size && a[left]>a[max])
                max=left;
        if(right < size && a[right]>a[max])
                max=right;
        if(max!=index)
       {
                Swap(&a[max],&a[index]);
                MaintainMaxHeap(a,max,size);
       }
}


/*
Post: Elements of array a from index [0,size-1] are 
         arranged so as to form max heap
*/
void BuildMaxHeap(int a[],int size)
{
        int i;
        // Elements from (size/2) to (size-1) are all leaves 
        for(i=size/2-1;i>=0;i--)
        MaintainMaxHeap(a,i,size);
}


void HeapSort(int a[],int size)
{
        int i;
        BuildMaxHeap(a,size);
        for(i=size-1;i>0;i--)
       {
                // Max element in array is at index=0
               Swap(&a[0],&a[i]);
               MaintainMaxHeap(a,0,--size);
       }
}

void Swap(int *i,int *j)
{
        int temp=*i;
        *i=*j;
        *j=temp;
}

NOTES: 
1)Above implementation was for implementing max priority queues, similarly minimum priority queues could also be implemented using min heaps. 
2)Error Handling is done simply by printing message.In any practical application it should be thoroughly done. Thank you.

1) Reversing k elements of a singly linked list at a time (Amazon Test Question) and 2) Finding last kth elements of singly linked list Efficiently

Suppose our linked list contains integer values and is described as:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
and if we want to reverse 2 elements at a time then modified linked list should be:
2 -> 1 -> 4 -> 3 -> 6 -> 5 -> 8 -> 7
and if we want to reverse 3 elements at a time then modified linked list should be:
3 -> 2 -> 1 -> 6 -> 5 -> 4 -> 7 -> 8
Here in case where k=3 last 2 elements are not reversed because 2<3.

We will use recursive algorithm to implement above reversal. Assume List Node's defination as:

//Node Data
typedef struct _DATA
{
int key;

}DATA,*PDATA;

//Node Struct
typedef struct _NODE
{
DATA item;
struct _node *pnext;

}NODE,*PNODE;

//
//Helper functions
//

PNODE NewNode(DATA item);
PNODE InsertAtStart(PNODE phead,DATA item);
PNODE DeleteAtStart(PNODE phead,PDATA pdata);
void Traverse(PNODE phead);
void DeleteList(PNODE phead);

//Reverses linked list pointed by phead
PNODE Reverse(PNODE phead);

//
// First reverse first k nodes then reverse N-k nodes  
// recursively where N=total size of  list
//
PNODE ReverseKNodesAtATime(PNODE phead,int k)
{
PNODE temp=phead;
int count=k;
     
        // Move to kth node from starting
while(temp && --count)
{
temp=temp->pnext;
}
if(temp)
{
                /*remaining list containing N-k  nodes head*/
PNODE nextstart=temp->pnext;
                 
                /* set end of list of first k nodes to NULL*/
temp->pnext=NULL;                                    

                 /* newHead is head of list of first k nodes after reversal*/
                PNODE newHead=Reverse(phead);                
                                                                                            
               /*Now phead points to end of first k nodes list after  reversal*/
               phead->pnext=ReverseKNodesAtATime(nextstart,k);

return newHead;
}
else
{
return phead;
}
}

//
// Finds and returns kth element from end of list if exist else returns NULL
//
PNODE LastKthNode(PNODE phead,int k)
{
PNODE back=phead,
  front=phead;

if(k<1)
return NULL;
else
{
// move front forward till number of nodes between 
                // front and back becomes not equal to k-1
while(front && k--)
{
front=front->pnext;
}

if(k!=-1)
{
if(!front)
printf("Error\n");
else
return NULL;
}
else
{
// when front becomes null, our back points to last kth  
                        // nodes because initial difference of k-1 nodes
while(front)
{
front=front->pnext;
back=back->pnext;
}
return back;
}
}
}

int main(void)
{
PNODE phead=NULL;
DATA d;
int i;
        //insert 10 elements 
for(i=1;i<=10;i++)
{
d.key=i;
phead=InsertAtStart(phead,d);
}
phead=Reverse(phead);
printf("List Reversed\n");
Traverse(phead);
printf("Reversed 2 at a time\n");
phead=ReverseKNodesAtATime(phead,2);
Traverse(phead);
PNODE pLastkthNode=LastKthNode(phead,6);
if(pLastkthNode)
{
printf("Last 6th node: %d\n",pLastkthNode->item.key);
}
else
{
printf("Last 6th node doesn't exist\n");
}

        DeleteList(phead);

        return 0;
}

PNODE Reverse(PNODE phead)
{
PNODE ptail,pmiddle;
ptail=pmiddle=NULL;

while(phead)
{
ptail=pmiddle;
pmiddle=phead;
phead=phead->pnext;
pmiddle->pnext=ptail;
}
return pmiddle;
}

PNODE NewNode(DATA item)
{
PNODE pnode=(PNODE)malloc(sizeof(NODE));
if(pnode)
{
pnode->item=item;
pnode->pnext=NULL;
}
return pnode;
}

PNODE InsertAtStart(PNODE phead,DATA item)
{
if(!phead)
{
PNODE pnode=NewNode(item);
if(!pnode)
printf("Failed to allocate memory\n");
return pnode;
}
else
{
PNODE pnewNode=NewNode(item);
if(pnewNode)
pnewNode->pnext=phead;
else
printf("Failed to allocate memory\n");
}
}

PNODE DeleteAtStart(PNODE phead,PDATA pdata)
{
if(!phead)
return phead;
else
{
PNODE pnext=phead->pnext;
*pdata=phead->item;
free(phead);
return pnext;
}
}

void Traverse(PNODE phead)
{
while(phead)
{
printf("%d\n",phead->item.key);
phead=phead->pnext;
}
}

void DeleteList(PNODE phead)
{
while(phead)
{
PNODE ptemp=phead;
phead=phead->pnext;
free(ptemp);
}
}

Please ask for doubt if any. Thank you.