Web Security Threat Prediction

Web Security Threat Prediction

By Shritam Bhowmick
Web Application Penetration Tester
LinkedIn: https://www.linkedin.com/profile/view?id=281014248&trk=nav_responsive_tab_profile
Academia: https://independent.academia.edu/ShritamBhowmick
Facebook: https://www.facebook.com/coded32

Abstract

The Web Security scene has been much complex than ever known and its time various industry take a deeper look to it to gain an in-depth gravity of the situation which affects them directly or in-directly. This could come at a blow and wouldn’t let you know until it’s too late. This post will take you mind blown from the recent predictions in terms of Web Security and will let you inform on the latest web attacks in rise and how such attacks are bad for business as well as reputation let alone financial losses. When we talk about industry, this doesn’t have to be the retail industry; it aims at stretch from the medical appliances to the car manufacturing industry and too low down to the Electronic Cigarette industry. That been said, we will look how various industrial assets which have had their presence and continue to have a presence in the web world affects them directly or indirectly and why Web Security for them is an absolute important factor too big a risk to ignore and compromise with the same.

Prediction 2015

I have come across and defined a statistical background check on as many application attack vectors and evidently from the statistical approach have come up to a very conclusive set of industries which could go bankruptcy as well as reputation loss if Web Security part is ignored. Here we have thrown out some of the industries which have a direct impact on business ignoring Web Security at their end.

  • Medical Department
  • Web Retail Department and Business Assets
  • Opensource Platforms
  • Mobile Devices

1ta

Continue reading

C – Practical System Programming for Graphics in C.

Practical System Programming for Graphics in C

By Shritam Bhowmick
Web Application Penetration Tester
LinkedIn: https://www.linkedin.com/profile/view?id=281014248&trk=nav_responsive_tab_profile
Academia: https://independent.academia.edu/ShritamBhowmick
Facebook: https://www.facebook.com/coded32

This is an introduction post for “Graphics and Internet” for WBUT 2014, which includes C as system programming and the underlying source code concepts for drawing basic graphics using C. Earlier in this post, I discussed data-structures in C for WBUT University in details which covered the practical aspects of year 2014. This post in contrary will mention the graphical aspect of the C programming keeping in mind the practical labs. I am glad I could post as far as the syllabus is concerned (which is really outdated as discussed in the last post), but this will help the current students who could have a look here after 2014 passes.

===========================================================================

1.) Draw a Basic Circle:

#include
#include

main()
{
int gd = DETECT, gm;

initgraph(&gd, &gm, "C:TCBGI");

circle(100, 100, 50);

getch();
closegraph();
return 0;
}

===========================================================================

2.) Draw a Rainbow

#include
#include
#include
#include

void main()
{
int gdriver = DETECT,gmode;
int x,y,i;
initgraph(&gdriver,&gmode,"C:TurboC4BGI");
x=getmaxx()/2;
y=getmaxy()/2;
for(i=30;i<200;i++)
{
delay(100);
setcolor(i/10);
arc(x,y,0,180,i-10);
}
getch();
}

===========================================================================

3.) Draw a Smiley

#include
#include
#include
#include

void main()

{
int gd=DETECT,gm;
initgraph(&gd,&gm,"C:BGI");
outtextxy(150,10,"This is a program to draw a Smiley Asshole!");
circle(200,200,80);
circle(160,180,8);
circle(240,180,8);
arc(200,230,180,360,20);
line(190,245,210,260);
line(210,245,210,260)
arc(200,260,180,360,9);
line(200,180,195,210);
arc(202,210,190,10,8);
getch();
closegraph();

}

===========================================================================

4.) Draw a Diagonal Line

#include < stdio.h >
#include < conio.h >
#include < graphics.h >

void main()
{
int gdriver=DETECT,gmode=0;
initgraph(&gdriver, &gmode, "c:tcbgi");
line(0,0,getmaxx(),getmaxy());
getch();
closegraph();

}

===========================================================================

5.) Draw an Eclipse

#include
#include

main()
{
int gd = DETECT, gm;

initgraph(&gd, &gm, "C:TCBGI");

ellipse(100, 100, 0, 360, 50, 25);

getch();
closegraph();
return 0;
}

===========================================================================

5.) Draw a Triangle

#include
#include
#include

void main() {
int gd = DETECT, gm;
initgraph(&gd, &gm, "c:tcbgi");

line(300, 100, 200, 200);
line(300, 100, 400, 200);
line(200, 200, 400, 200);

getch();
closegraph();
}

There are others as well which are related to Web Development. The posts belonging to Web-development could already be accessed from here. The section is for everything related to ‘code’ and working with code in different languages. HTML could be found there. I would appreciate if the readers leave behind a feedback. Roger out./-

Data Structures in C Practicals and Why Colleges with their IDE’s are Outdated. A Wiser Proof of Concept.

Data Structures in C and Why Colleges with their IDE’s are Outdated!

By Shritam Bhowmick
Web Application Penetration Tester
LinkedIn: https://www.linkedin.com/profile/view?id=281014248&trk=nav_responsive_tab_profile
Academia: https://independent.academia.edu/ShritamBhowmick
Facebook: https://www.facebook.com/coded32

The Introduction Preface

Hi, this is about all the practical lab C  for WBUT Winters (Semester 3rd of the University prescribed Syllabus) section data-structures questions solved at once place for a ready reference to the students who might seek help and also on an information as to why colleges now should be moving from the stone age. All the programs are complied under Tubro C++ compiler and would not be/should not be expected to be executed/processed to create an object under GNU C compiler or  any Windows variant compilers (such as Visual C compiler). Since the syllabus itself is too outdated and people had been talking about them in various forums; I came up with a compilation of the code as well as the questions which could help them understand the core with the ready service code to be executed only within from Turbo C++ compiler. This is C code and not C++ code. The source code for each of them had been practically tested on Windows 8.1 platform using DOSBOX as an emulator to run Turbo C.

The Recommendations

It’s recommended to move on with the syllabus and pay less attention there, if anyone really is serious on C and C++ programming. Python, Ruby, Delphi, Lua and Perl are the modern spectacular languages to choose from and Java is really not that friendly as you might think if you have to do a certain task. Java isn’t that flexible in terms that Java would really need long source code for a simple problem. See “Python to other languages – A comparison“. Get to know more at Stackoverflow. To refernce from the original source, here’s is the justification why someone would prefer to code in Python rather than any other older languages in a nutshell:

  1. Speed of development. I can crank out working code before the Java folks have stuff that will compile.
  2. Flexibility. I can refactor and rework a module in an afternoon. The Java folks have to redesign things on paper to be sure they can get some of the bigger refactorings to recompile. In Java, the changes aren’t as small and focused.I should probably blog about some of the nastier refactorings that would be a huge pain — even using the refactoring tools in Eclipse or NetBeans. The most recent example was a major change to the top-most superclass of a class hierarchy that would have invalidated a mountain of Java code. But the method was used in exactly two places, allowing a trivial change to the superclass and those two places. 100’s of unit tests passed, so I’m confident in the change without the compiler overhead.
  3. Simplicity. Python doesn’t need a sophisticated IDE and super-complex WS libraries. Python code can be written in Komodo Edit. A WS interface between your Java front-end and PostgresSQL can be knocked together in Werkzeug in a day. You can plug your transactions into this without much overhead.

The post primarily covered Python against Java, but there are instances why some one could just prefer Python over C which could be referenced from here in this post. This does not at all mean to compare C and Python on basis of what they have to deliver but rather compares them on an average on the end-users opinion perspective. There are other considerations as well into modern computing which is resolved below in the list.

Why Would Python be Slow but equivalently faster ever than C Deployments?

Python is a higher level language than C, which means it abstracts the details of the computer from you – memory management, pointers, etc, and allows you to write programs in a way which is closer to how humans think. It is true that C code usually runs 10 to 100 times faster than Python code if you measure only the execution time. However if you also include the development time Python often beats C. For many projects the development time is far more critical than the run time performance. Longer development time converts directly into extra costs, fewer features and slower time to market.

Why use C contrary to the switching to any other programming languages, a hope out of no-where!?

“If there ever were a quote that described programming with C, it would be this. To many programmers, this makes C scary and evil. It is the Devil, Satan, the trickster Loki come to destroy your productivity with his seductive talk of pointers and direct access to the machine. Then, once this computational Lucifer has you hooked, he destroys your world with the evil “segfault” and laughs as he reveals the trickery in your bargain with him.

But, C is not to blame for this state of affairs. No my friends, your computer and the Operating System controlling it are the real tricksters. They conspire to hide their true inner workings from you so that you can never really know what is going on. The C programming language’s only failing is giving you access to what is really there, and telling you the cold hard raw truth. C gives you the red pill. C pulls the curtain back to show you the wizard. C is truth. Why use C then if it’s so dangerous? Because C gives you power over the false reality of abstraction and liberates you from stupidity.”

The Coverage

Now since we are already hopped into C with Turbo C as a compiler. I’d go writing the source code of the practicals here and try to keep it updated as much as I could to my disposal. Instead this is the responsibility at your side to post back with comments on what else its to be added so this could help others in the process.

Notes

The source code has replaced all the instances of \n to n. Take care of that plus the include headers have not been defined to be kept away from copy/paste practices. This in my opinion will lead to a better coding practices and would lead to a great start with self-research.

The Question Set

The questions I have dug so far follows these:

  1. Doubly Linked List with insertion and deletion.
  2. Priority Queue with addition and deletion of elements.
  3. Dequeue or Double Ended Queue using Linked List.
  4. Dequeue or Double Ended Queue using Circular Array.
  5. Priority Queue Implementation using Arrays.
  6. Circular Queue using Linked List with Circular Queue Concept Notes.
  7. Circular Queue Implementation in C Data-Structures using Arrays.
  8. Stack for PUSH and POP operations in C both via recursive and regular methods.
  9. Linear Search Implementation in C using Arrays.
  10. Binary Search Implementation in C using Arrays.
  11. Insertion Sort Implementation in C using Arrays.
  12. Merge Sort Implementation in C using Arrays.
  13. Quick Sort Implementation in C using Arrays.
  14. Heap Sort Implementation in C using Arrays.

Source Code Solutions

1.) Doubly Linked List with Insertion, Deletion and Reverse Display

Here’s the source code (to avoid copy/paste gimmicks, I have stripped off all the includes. Feel free to add them at your own expense) for Doubly Linked List:

#include
#include
#include
struct node
{
struct node *previous;
int data;
struct node *next;
}*head, *last;

void insert_beginning(int value)
{
struct node *var,*temp;
var=(struct node *)malloc(sizeof(struct node));
var->data=value;
if(head==NULL)
{
head=var;
head->previous=NULL;
head->next=NULL;
last=head;
}
else
{
temp=var;
temp->previous=NULL;
temp->next=head;
head->previous=temp;
head=temp;
}
}

void insert_end(int value)
{
struct node *var,*temp;
var=(struct node *)malloc(sizeof(struct node));
var->data=value;
if(head==NULL)
{
head=var;
head->previous=NULL;
head->next=NULL;
last=head;
}
else
{
last=head;
while(last!=NULL)
{
temp=last;
last=last->next;
}
last=var;
temp->next=last;
last->previous=temp;
last->next=NULL;
}
}

int insert_after(int value, int loc)
{
struct node *temp,*var,*temp1;
var=(struct node *)malloc(sizeof(struct node));
var->data=value;
if(head==NULL)
{
head=var;
head->previous=NULL;
head->next=NULL;
}
else
{
temp=head;
while(temp!=NULL && temp->data!=loc)
{
temp=temp->next;
}
if(temp==NULL)
{
printf("n%d is not present in list ",loc);
}
else
{
temp1=temp->next;
temp->next=var;
var->previous=temp;
var->next=temp1;
temp1->previous=var;
}
}
last=head;
while(last->next!=NULL)
{
last=last->next;
}
}
int delete_from_end()
{
struct node *temp;
temp=last;
if(temp->previous==NULL)
{
free(temp);
head=NULL;
last=NULL;
return 0;
}
printf("nData deleted from list is %d n",last->data);
last=temp->previous;
last->next=NULL;
free(temp);
return 0;
}

int delete_from_middle(int value)
{
struct node *temp,*var,*t, *temp1;
temp=head;
while(temp!=NULL)
{
if(temp->data == value)
{
if(temp->previous==NULL)
{
free(temp);
head=NULL;
last=NULL;
return 0;
}
else
{
var->next=temp1;
temp1->previous=var;
free(temp);
return 0;
}
}
else
{
var=temp;
temp=temp->next;
temp1=temp->next;
}
}
printf("data deleted from list is %d",value);
}

void display()
{
struct node *temp;
temp=head;
if(temp==NULL)
{
printf("List is Empty");
}
while(temp!=NULL)
{
printf("-> %d ",temp->data);
temp=temp->next;
}
}

int main()
{
int value, i, loc;
head=NULL;
printf("Select the choice of operation on link list");
printf("n1.) insert at begningn2.) insert at atn3.) insert at middle");
printf("n4.) delete from endn5.) reverse the link listn6.) display listn7.)exit");
while(1)
{
printf("nnenter the choice of operation you want to do ");
scanf("%d",&i);
switch(i)
{
case 1:
{
printf("enter the value you want to insert in node ");
scanf("%d",&value);
insert_beginning(value);
display();
break;
}
case 2:
{
printf("enter the value you want to insert in node at last ");
scanf("%d",&value);
insert_end(value);
display();
break;
}
case 3:
{
printf("after which data you want to insert data ");
scanf("%d",&loc);
printf("enter the data you want to insert in list ");
scanf("%d",&value);
insert_after(value,loc);
display();
break;
}
case 4:
{
delete_from_end();
display();
break;
}
case 5:
{
printf("enter the value you want to delete");
scanf("%d",value);
delete_from_middle(value);
display();
break;
}
case 6 :
{
display();
break;
}
case 7 :
{
exit(0);
break;
}
}
}
printf("nn%d",last->data);
display();
getch();
}

2.) Priority Queue with Addition and Deletion of Elements

#include
#include
#define MAX 5

void insert_by_priority(int);
void delete_by_priority(int);
void create();
void check(int);
void display_pqueue();

int pri_que[MAX];
int front, rear;

void main()

{

int n, ch;
printf("n1 - Insert an element into queue");
printf("n2 - Delete an element from queue");
printf("n3 - Display queue elements");
printf("n4 - Exit");
create();

while (1)

{

printf("nEnter your choice : ");

scanf("%d", &ch);

switch (ch)

{

case 1:

printf("nEnter value to be inserted : ");

scanf("%d",&n);

insert_by_priority(n);

break;

case 2:

printf("nEnter value to delete : ");

scanf("%d",&n);

delete_by_priority(n);

break;

case 3:

display_pqueue();

break;

case 4:

exit(0);

default:

printf("nChoice is incorrect, Enter a correct choice");

}

}

}

/* Function to create an empty priority queue */

void create()

{

front = rear = -1;

}

/* Function to insert value into priority queue */

void insert_by_priority(int data)

{

if (rear >= MAX - 1)

{

printf("nQueue overflow no more elements can be inserted");

return;

}

if ((front == -1) && (rear == -1))

{

front++;

rear++;

pri_que[rear] = data;

return;

}

else

check(data);

rear++;

}

/* Function to check priority and place element */

void check(int data)

{

int i,j;

for (i = 0; i <= rear; i++) { if (data >= pri_que[i])

{

for (j = rear + 1; j > i; j--)

{

pri_que[j] = pri_que[j - 1];

}

pri_que[i] = data;

return;

}

}

pri_que[i] = data;

}

/* Function to delete an element from queue */

void delete_by_priority(int data)

{

int i;

if ((front==-1) && (rear==-1))

{

printf("nQueue is empty no elements to delete");

return;

}

for (i = 0; i <= rear; i++)

{

if (data == pri_que[i])

{

for (; i < rear; i++)

{

pri_que[i] = pri_que[i + 1];

}

pri_que[i] = -99;

rear--;

if (rear == -1)

front = -1;

return;

}

}

printf("n%d not found in queue to delete", data);

}

/* Function to display queue elements */

void display_pqueue()

{

if ((front == -1) && (rear == -1))

{

printf("nQueue is empty");

return;

}

for (; front <= rear; front++)

{

printf(" %d ", pri_que[front]);

}

front = 0;

}

3.) Dequeue or Double Ended Queue using Linked List

What is Dequeue?

The word dequeue is short form of double ended queue. In a dequeue , insertion as well as deletion can be carried out either at the rear end or the front end. The following diagram illustrates a version of the same concept:

Dequeue Represented Using a Circular Array

The source code is available below:

#define MAX 100
#include
#include

void insert(int);
int delStart();
int delEnd();
int queue[MAX];
int rear =0, front =0;
void display();
void insertEnd(int);
void insertStart(int);

int main()
{
char ch , a='y';
int choice, c, token;
printf("Enter your choice for which deque operation you want to perform operation n");
do
{
printf("n1.Input-restricted deque n");
printf("2.output-restricted deque n");
printf("nEnter your choice for the operation : ");
scanf("%d",&c);
switch(c)
{
case 1:
printf("nDo operation in Input-Restricted c dequen");
printf("1.Insert");
printf("n2.Delete from end");
printf("n3.Delete from begning");
printf("n4.show or display");
do
{
printf("nEnter your choice for the operation in c deque: ");
scanf("%d",&choice);
switch(choice)
{
case 1: insertEnd(token);
display();
break;
case 2: token=delEnd();
printf("nThe token deleted is %d",token);
display();
break;
case 3: token=delStart();
printf("nThe token deleted is %d",token);
display();
break;
case 4: display();
break;
default:printf("Wrong choice");
break;
}
printf("nDo you want to continue(y/n) to do operation in input-restricted c deque: ");
ch=getch();
}
while(ch=='y'||ch=='Y');
getch();
break;

case 2 :
printf("nDo operation in Output-Restricted c dequen");
printf("1.Insert at the End");
printf("n2.Insert at the begning");
printf("n3.Delete the element");
printf("n4.show or display");
do
{
printf("nEnter your choice for the operation: ");
scanf("%d",&choice);
switch(choice)
{
case 1: insertEnd(token);
display();
break;
case 2: insertStart(token);
display();
break;
case 3: token=delStart();
printf("nThe token deleted is %d",token);
display();
break;
case 4: display();
break;
default:printf("Wrong choice");
break;
}
printf("nDo you want to continue(y/n):");
ch=getch();
}
while(ch=='y'||ch=='Y');
getch();
break ;
}

printf("nDo you want to continue(y/n):");
ch=getch();
}
while(ch=='y'||ch=='Y');
getch();
}

void display()
{
int i;
printf("nThe queue elements are:");
for(i=rear;i<front;i++)
{
printf("%d  ",queue[i]);
}
}

void insertEnd(int token)
{
char a;
if(front==MAX/2)
{
printf("nQueue fullnyou cant enter more elements at the end of c queue");
return;
}
do
{
printf("nEnter the token to be inserted:");
scanf("%d",&token);
queue[front]=token;
front=front+1;
printf("do you want to continue insertion Y/N");
a=getch();
}
while(a=='y');
}

void insertStart(int token)
{
char a;
if(front==MAX/2)
{
printf("nQueue fullnyou cant enter more elements at the start of queue");
return;
}
do
{
printf("nEnter the token to be inserted:");
scanf("%d",&token);
rear=rear-1;
queue[rear]=token;
printf("do you want to continue insertion Y/N");
a=getch();
}
while(a=='y');
}
int delEnd()
{
int t;
if(front==rear)
{
printf("nQueue empty");
return 0;
}
front=front-1;
t=queue[front+1];
return t;
}
int delStart()
{
int t;
if(front==rear)
{
printf("nQueue empty");
return 0;
}
rear=rear+1;
t=queue[rear-1];
return t;
}

4.) Dequeue or Double Ended Queue using Circular Array

The available source code is different from the previous one which used linked list. This time the code uses the concept for circular array and implements a Dequeue or Double Ended Queue implementation around circular array. The source code is below as per the references.

#include
#include

#define MAX 30

typedef struct dequeue
{
int data[MAX];
int rear,front;
}dequeue;

void initialize(dequeue *p);
int empty(dequeue *p);
int full(dequeue *p);
void enqueueR(dequeue *p,int x);
void enqueueF(dequeue *p,int x);
int dequeueF(dequeue *p);
int dequeueR(dequeue *p);
void print(dequeue *p);

void main()
{
int i,x,op,n;
dequeue q;
initialize(&q);

do
{
printf("n1.Createn2.Insert(rear)n3.Insert(front)n4.Delete(rear)n5.Delete(front)");
printf("n6.Printn7.ExitnnEnter your choice:");
scanf("%d",&op);

switch(op)
{
case 1: printf("nEnter number of elements:");
scanf("%d",&n);
initialize(&q);
printf("nEnter the data:");

for(i=0;i<n;i++) { scanf("%d",&x); if(full(&q)) { printf("nQueue is full!!"); exit(0); } enqueueR(&q,x); } break; case 2: printf("nEnter element to be inserted:"); scanf("%d",&x); if(full(&q)) { printf("nQueue is full!!"); exit(0); } enqueueR(&q,x); break; case 3: printf("nEnter the element to be inserted:"); scanf("%d",&x); if(full(&q)) { printf("nQueue is full!!"); exit(0); } enqueueF(&q,x); break; case 4: if(empty(&q)) { printf("nQueue is empty!!"); exit(0); } x=dequeueR(&q); printf("nElement deleted is %dn",x); break; case 5: if(empty(&q)) { printf("nQueue is empty!!"); exit(0); } x=dequeueF(&q); printf("nElement deleted is %dn",x); break; case 6: print(&q); break; default: break; } }while(op!=7); } void initialize(dequeue *P) { P->rear=-1;
P->front=-1;
}

int empty(dequeue *P)
{
if(P->rear==-1)
return(1);
return(0);
}

int full(dequeue *P)
{
if((P->rear+1)%MAX==P->front)
return(1);
return(0);
}

void enqueueR(dequeue *P,int x)
{
if(empty(P))
{
P->rear=0;
P->front=0;
P->data[0]=x;
}
else
{
P->rear=(P->rear+1)%MAX;
P->data[P->rear]=x;
}
}

void enqueueF(dequeue *P,int x)
{
if(empty(P))
{
P->rear=0;
P->front=0;
P->data[0]=x;
}
else
{
P->front=(P->front-1+MAX)%MAX;
P->data[P->front]=x;
}
}

int dequeueF(dequeue *P)
{
int x;
x=P->data[P->front];
if(P->rear==P->front)   //delete the last element
initialize(P);
else
P->front=(P->front+1)%MAX;
return(x);
}

int dequeueR(dequeue *P)
{
int x;
x=P->data[P->rear];
if(P->rear==P->front)
initialize(P);
else
P->rear=(P->rear-1+MAX)%MAX;
return(x);
}

void print(dequeue *P)
{
if(empty(P))
{
printf("nQueue is empty!!");
exit(0);
}

int i;
i=P->front;
while(i!=P->rear)
{
printf("n%d",P->data[i]);
i=(i+1)%MAX;
}
printf("n%dn",P->data[P->rear]);
}

5.) Priority Queue using Array

I noticed I didn’t updated a priority queue implementation using arrays. This is the reason the source code is here for a ready reference to the readers of the blog. Here is the original version of the source code which is tested against the terms and conditions posted before which should be able to run via a Turbo C compiler. Any other compiler just won’t work because the syllabus itself is outdated, and people (and universities) must realize this fast.

#include
#include
#define size 5

int queue[5][2] = {0};
int top = -1;
int bottom;

void push(int value, int pr)

{

int i,j,k;

if(top < size-1) { if(queue[top][1] > pr)

{

for(i=0;i<top;i++) { if(queue[i][1] > pr)

{

break;

}

}

for(j=top;j>=i;j--)

{

queue[j+1][0] = queue[j][0];

queue[j+1][1] = queue[j][1];

}

top++;

queue[i][0] = value;

queue[i][1] = pr;

}

else

{

top++;

queue[top][0] = value;

queue[top][1] = pr;

}

}

else

{

printf("queue overflow n");

}

}

void pop()

{

int i;

if(queue[0][0] == 0)

{

printf("n The queue is empty  n");

}

else

{

printf("After , dequeue the following value is erased n  %d n", queue[0][0]);

for(i=0;i<top;i++) { queue[i][0] = queue[i+1][0]; queue[i][1] = queue[i+1][1]; } queue[top][0] = 0; queue[top][1] = 0; top--; } } void display() { int i,j; printf("ElementtPriority n"); for(i=size - 1;i>=0;i--)

{

for(j=0;j<2;j++)

{

printf(" %dt",queue[i][j]);

}

printf("n");

}

}

int main()

{

int i,j, ch=0 ,value = 0,pr=0;

while(1)

{

printf("n Please Enter the choice. n");

printf("1 for Enqueue n 2 for Dequeue n 3 for displayn  5 for exit: t n");

scanf("%d",&ch);

switch(ch)

{

case 1:

printf("n Please Enter the number to be inserted: t ");

scanf("%d", &value);

printf("n Please Enter the priority: t ");

scanf("%d", &pr);

push(value,pr);

break;

case 2:

pop();

break;

case 3:

display();

break;

case 5:

exit(0);

default:

printf("You entered wrong choice!");

}
}
}

6.) Circular Queue using Linked List in C Data-structures with Notes

In a standard queue data structure re-buffering problem occurs for each dequeue operation. To solve this problem by joining the front and rear ends of a queue to make the queue as a circular queue
Circular queue is a linear data structure. It follows FIFO principle.

  • In circular queue the last node is connected back to the first node to make a circle.
  • Circular linked list fallow the First In First Out principle
  • Elements are added at the rear end and the elements are deleted at front end of the queue
  • Both the front and the rear pointers points to the beginning of the array.
  • It is also called as “Ring buffer”.
  • Items can inserted and deleted from a queue in O(1) time.

Circular Queue can be created in three ways. They are:

  • · Using single linked list
  • · Using double linked list
  • · Using arrays

Follow is the source code for implementing a Circular Queue in C using Linked List:

#include
#include
#define max 5
int q[max];
int rear = -1, front = -1;
void insert();
void delet();
void display();

void main()
{
char ch;
int choice;
do
{
clrscr();
printf("n1 -> Insert");
printf("n2 -> Delete");
printf("n3 -> Display");
printf("n0 -> Exit");

printf("nnEnter Your Choice -> ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break;
case 2:
delet();
break;
case 3:
display();
break;
case 0:
exit();
default:
printf("nnInvalid Choice");
}
printf("nnDo u Want to Continue -> ");
ch = getche();
} while (ch == 'y' || ch == 'Y');
}

void insert()
{
int data;
if ((rear == max - 1 && front == 0) || rear == front - 1)
{
printf("nSorry! Q is Full");
}
else
{
printf("nEnter data You want to insert ->");
scanf("%d", &data);
if (front == -1)
{
front++;
rear++;
}
else if (rear == max - 1)
{
rear = 0;
}
else
{
rear++;
}
q[rear] = data;
printf("nnData inserted successfully");
}
}
void delet()
{
if (front == -1)
{
printf("nnSorry! Q is Empty");
}
else
{
if (front == rear)
{
front = rear = -1;
}
else if (front == max - 1)
{
front = 0;
}
else
{
front++;
}
printf("nElement deleted Successfully");
}
}

void display()
{
int i;
if (front == -1)
{
printf("nnSorry! Q is Empty");
}
else
{
printf("nn:: Queue Elements are ::n");
if (front <= rear)
{
for (i = front; i <= rear; i++)
{
printf("n%d", q[i]);
}
}
else
{
for (i = front; i < max; i++)
{
printf("n%d", q[i]);
}
for (i = 0; i <= rear; i++)
{
printf("n%d", q[i]);
}
}
}
}

7.) Circular Queue Implementation in C using Arrays

Earlier in the post, we talked about implementation circular queue using Linked List. This section talks about the same implementation but using arrays. The source code below could be used for the purposes to demonstrate the concepts:

#include
#include
#include
#define MAXSIZE 5
int cq[MAXSIZE];
int front,rear;
void main()
{
void add(int,int);
void del(int);
int will=1,i,num;
front = -1;
rear = -1;
clrscr();
printf("nProgram for Circular Queue demonstration through array");
while(1)
{
printf("nnMAIN MENUn1.INSERTIONn2.DELETIONn3.EXIT");
printf("nnENTER YOUR CHOICE : ");
scanf("%d",&will);
switch(will)
{
case 1:
printf("nnENTER THE QUEUE ELEMENT : ");
scanf("%d",&num);
add(num,MAXSIZE);
break;
case 2:
del(MAXSIZE);
break;
case 3:
exit(0);
default: printf("nnInvalid Choice . ");
}

} //end of  outer while
}               //end of main
void add(int item,int MAX)
{
//rear++;
//rear= (rear%MAX);
if(front ==(rear+1)%MAX)
{
printf("nnCIRCULAR QUEUE IS OVERFLOW");
}
else
{
if(front==-1)
front=rear=0;
else
rear=(rear+1)%MAX;
cq[rear]=item;
printf("nnRear = %d    Front = %d ",rear,front);
}
}
void del(int MAX)
{
int a;
if(front == -1)
{
printf("nnCIRCULAR QUEUE IS UNDERFLOW");
}
else
{
a=cq[front];
if(front==rear)
front=rear=-1;
else
front = (front+1)%MAX;
printf("nnDELETED ELEMENT FROM QUEUE IS : %d ",a);
printf("nnRear = %d    Front = %d ",rear,front);

}
}

Here is a similar implementation of a queue using array. The source code could be referenced from the below:

#include
#include
#define N 6

int queue[N]={0};
int rear=0,front=0;

void insert(void);
void del(void);
void disp(void);
void cre(void);

void main()
{
int user=0;

clrscr();
while(user!=4)
{
clrscr();
printf("nnnttt THE SIZE OF QUEUE IS %d",N);
printf("nt 1.INSERT");
printf("nt 2.DELETE");
printf("nt 3.DISPLAY");
printf("nt 4.EXIT");
printf("nt 5.CREATE");
scanf("%d",&user);
switch(user)
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
disp();
break;
case 4:
printf("nt THANK U");
break;
case 5:
cre();
break;
}
getch();

}
getch();
}

void insert(void)
{
int t;
if(rear<N)
{
printf("nt ENTER A VALUE IN QUEUE");
scanf("%d",&t);
queue[rear]=t;
rear++;
}
else
{
printf("nt Q OVERFLOW!!!!!!!!!!!!!!!");
}
}
void del(void)
{
int i;
printf("nt %d gets deleted.........",queue[front]);
queue[front]=0;
front++;
}
void disp(void)
{
int i;
for(i=front;i<rear;i++)
{
printf("nt %d",queue[i]);
}
}
void cre(void)
{

int t;
printf("nt ENTER A VALUE IN QUEUE");
scanf("%d",&t);
front=0;
queue[front]=t;
rear=front+1;
}

8.) Stack Implementation to perform PUSH and POP Operations

After having gone through the Queue utilities in C and discussing queue with circular based and using Linked List, here is the source code to implement Stack for PUSH and POP operations in C.

#include
#define MAXSIZE 5

struct stack
{
int stk[MAXSIZE];
int top;
};
typedef struct stack STACK;
STACK s;

void push(void);
int  pop(void);
void display(void);

void main ()
{
int choice;
int option = 1;
s.top = -1;

printf ("STACK OPERATIONn");
while (option)
{
printf ("------------------------------------------n");
printf ("      1    -->    PUSH               n");
printf ("      2    -->    POP               n");
printf ("      3    -->    DISPLAY               n");
printf ("      4    -->    EXIT           n");
printf ("------------------------------------------n");

printf ("Enter your choicen");
scanf    ("%d", &choice);
switch (choice)
{
case 1:
push();
break;
case 2:
pop();
break;
case 3:
display();
break;
case 4:
return;
}
fflush (stdin);
printf ("Do you want to continue(Type 0 or 1)?n");
scanf    ("%d", &option);
}
}
/*  Function to add an element to the stack */
void push ()
{
int num;
if (s.top == (MAXSIZE - 1))
{
printf ("Stack is Fulln");
return;
}
else
{
printf ("Enter the element to be pushedn");
scanf ("%d", &num);
s.top = s.top + 1;
s.stk[s.top] = num;
}
return;
}
/*  Function to delete an element from the stack */
int pop ()
{
int num;
if (s.top == - 1)
{
printf ("Stack is Emptyn");
return (s.top);
}
else
{
num = s.stk[s.top];
printf ("poped element is = %dn", s.stk[s.top]);
s.top = s.top - 1;
}
return(num);
}
/*  Function to display the status of the stack */
void display ()
{
int i;
if (s.top == -1)
{
printf ("Stack is emptyn");
return;
}
else
{
printf ("n The status of the stack is n");
for (i = s.top; i >= 0; i--)
{
printf ("%dn", s.stk[i]);
}
}
printf ("n");
}

Here is yet another version of Stack implementation but using recursive method:

#include

#include

struct node

{

int a;

struct node *next;

};

void generate(struct node **);

void display(struct node *);

void stack_reverse(struct node **, struct node **);

void delete(struct node **);

int main()

{

struct node *head = NULL;

generate(&head);

printf("nThe sequence of contents in stackn");

display(head);

printf("nInversing the contents of the stackn");

if (head != NULL)

{

stack_reverse(&head, &(head->next));

}

printf("nThe contents in stack after reversaln");

display(head);

delete(&head);

return 0;

}

void stack_reverse(struct node **head, struct node **head_next)

{

struct node *temp;

if (*head_next != NULL)

{

temp = (*head_next)->next;

(*head_next)->next = (*head);

*head = *head_next;

*head_next = temp;

stack_reverse(head, head_next);

}

}

void display(struct node *head)

{

if (head != NULL)

{

printf("%d  ", head->a);

display(head->next);

}

}

void generate(struct node **head)

{

int num, i;

struct node *temp;

printf("Enter length of list: ");

scanf("%d", &num);

for (i = num; i > 0; i--)

{

temp = (struct node *)malloc(sizeof(struct node));

temp->a = i;

if (*head == NULL)

{

*head = temp;

(*head)->next = NULL;

}

else

{

temp->next = *head;

*head = temp;

}

}

}

void delete(struct node **head)

{

struct node *temp;

while (*head != NULL)

{

temp = *head;

*head = (*head)->next;

free(temp);

}

}

9.) Linear Search Implementation in C

This is an abstract source code of Linear search utility in C. This could be used along in the Turbo C compiler. Others were specifically not tested and not recommended.

#include

int main()
{
int array[100], search, c, n;

printf("Enter the number of elements in arrayn");
scanf("%d",&n);

printf("Enter %d integer(s)n", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

printf("Enter the number to searchn");
scanf("%d", &search);

for (c = 0; c < n; c++)
{
if (array[c] == search)     /* if required element found */
{
printf("%d is present at location %d.n", search, c+1);
break;
}
}
if (c == n)
printf("%d is not present in array.n", search);

return 0;
}

10.) Binary Search using Arrays

The source code below is the implementation of binary search algorithm in C using arrays.

#include
int main(){

int a[10],i,n,m,c=0,l,u,mid;

printf("Enter the size of an array: ");
scanf("%d",&n);

printf("Enter the elements in ascending order: ");
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}

printf("Enter the number to be search: ");
scanf("%d",&m);

l=0,u=n-1;
while(l<=u){
mid=(l+u)/2;
if(m==a[mid]){
c=1;
break;
}
else if(m<a[mid]){
u=mid-1;
}
else
l=mid+1;
}
if(c==0)
printf("The number is not found.");
else
printf("The number is found.");

return 0;
}

11.) Insertion Sort Implementation in C using Arrays.

This is insertion sort in C using Arrays. The source code is available below:

#include

int main()
{
int n, array[1000], c, d, t;

printf("Enter number of elementsn");
scanf("%d", &n);

printf("Enter %d integersn", n);

for (c = 0; c < n; c++) {
scanf("%d", &array[c]);
}

for (c = 1 ; c <= n - 1; c++) { d = c; while ( d > 0 && array[d] < array[d-1]) {
t          = array[d];
array[d]   = array[d-1];
array[d-1] = t;

d--;
}
}

printf("Sorted list in ascending order:n");

for (c = 0; c <= n - 1; c++) {
printf("%dn", array[c]);
}

return 0;
}

12.) Merge Sort in C using Arrays

Here is the source code for Merge sort in C using Arrays:

#include
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){

int merge[MAX],i,n;

printf("Enter the total number of elements: ");
scanf("%d",&n);

printf("Enter the elements which to be sort: ");
for(i=0;i<n;i++){
scanf("%d",&merge[i]);
}

partition(merge,0,n-1);

printf("After merge sorting elements are: ");
for(i=0;i<n;i++){
printf("%d ",merge[i]);
}

return 0;
}

void partition(int arr[],int low,int high){

int mid;

if(low<high){
mid=(low+high)/2;
partition(arr,low,mid);
partition(arr,mid+1,high);
mergeSort(arr,low,mid,high);
}
}

void mergeSort(int arr[],int low,int mid,int high){

int i,m,k,l,temp[MAX];

l=low;
i=low;
m=mid+1;

while((l<=mid)&&(m<=high)){

if(arr[l]<=arr[m]){ temp[i]=arr[l]; l++; } else{ temp[i]=arr[m]; m++; } i++; } if(l>mid){
for(k=m;k<=high;k++){
temp[i]=arr[k];
i++;
}
}
else{
for(k=l;k<=mid;k++){
temp[i]=arr[k];
i++;
}
}

for(k=low;k<=high;k++){
arr[k]=temp[k];
}
}

13.) Quick Sort Implementation in C using Arrays

Below is the raw source code for Quick Sort implementation in C using Arrays:

#include

void quicksort(int [10],int,int);

int main(){
int x[20],size,i;

printf("Enter size of the array: ");
scanf("%d",&size);

printf("Enter %d elements: ",size);
for(i=0;i<size;i++)
scanf("%d",&x[i]);

quicksort(x,0,size-1);

printf("Sorted elements: ");
for(i=0;i<size;i++)
printf(" %d",x[i]);

return 0;
}

void quicksort(int x[10],int first,int last){
int pivot,j,temp,i;

if(first<last){
pivot=first;
i=first;
j=last;

while(i<j){
while(x[i]<=x[pivot]&&i<last) i++; while(x[j]>x[pivot])
j--;
if(i<j){
temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}

temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);

}
}

14.) Heap Sort Implementation in C using Arrays

Below is the source code for Heap Sort in C using Arrays:

#include
void main()

{

int heap[10], no, i, j, c, root, temp;

printf("n Enter no of elements :");

scanf("%d", &no);

printf("n Enter the nos : ");

for (i = 0; i < no; i++)

scanf("%d", &heap[i]);

for (i = 1; i < no; i++)

{

c = i;

do

{

root = (c - 1) / 2;

if (heap[root] < heap[c])   /* to create MAX heap array */

{

temp = heap[root];

heap[root] = heap[c];

heap[c] = temp;

}

c = root;

} while (c != 0);

}

printf("Heap array : ");

for (i = 0; i < no; i++) printf("%dt ", heap[i]); for (j = no - 1; j >= 0; j--)

{

temp = heap[0];

heap[0] = heap[j    /* swap max element with rightmost leaf element */

heap[j] = temp;

root = 0;

do

{

c = 2 * root + 1;    /* left node of root element */

if ((heap[c] < heap[c + 1]) && c < j-1)

c++;

if (heap[root]<heap[c] && c<j)    /* again rearrange to max heap array */

{

temp = heap[root];

heap[root] = heap[c];

heap[c] = temp;

}

root = c;

} while (c < j);

}

printf("n The sorted array is : ");

for (i = 0; i < no; i++)

printf("t %d", heap[i]);

printf("n Complexity : n Best case = Avg case = Worst case = O(n logn) n");

}

15.) Bubble Sort Implementation in C using Arrays

Below is the source code for bubble sort in C using Arrays:

#include

int main()
{
int array[100], n, c, d, swap;

printf("Enter number of elementsn");
scanf("%d", &n);

printf("Enter %d integersn", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

for (c = 0 ; c < ( n - 1 ); c++)
{
for (d = 0 ; d < n - c - 1; d++) { if (array[d] > array[d+1]) /* For decreasing order use < */
{
swap       = array[d];
array[d]   = array[d+1];
array[d+1] = swap;
}
}
}

printf("Sorted list in ascending order:n");

for ( c = 0 ; c < n ; c++ )
printf("%dn", array[c]);

return 0;
}

4. Operating System – Process State Diagram and CPU Scheduling Basics

Operating System – Process State Diagram and CPU Scheduling Basics.

By Shritam Bhowmick
Web Application Penetration Tester
LinkedIn: https://www.linkedin.com/profile/view?id=281014248&trk=nav_responsive_tab_profile
Academia: https://independent.academia.edu/ShritamBhowmick
Facebook: https://www.facebook.com/coded32

Previous post discussed about CPU scheduling and an introduction towards Process Management; This post will take it further to an introduction to the process management which is required for WBUT 3rd Semester BCA candidates. Particularly this post is dedicated to process state diagram and will cover the entire aspect of the same.

To start off with the details, a program when needs to be executed goes through a process. This process has several state changes in the entire operation until termination of the program. Upon successful termination, the program would get useful results to the user. This entire process progression goes through state changes which are mention below in steps:

  1. The process enters a state called NEW STATE.
  2. The process then enters the READY STATE.
  3. The process then goes to an ACTIVE STATE/RUNNING STATE (Execution of the program starts here).
  4. The process ends with the HALT STATE/TERMINATED STATE (after all the program BURST’s are over. The program might be terminated forcibly or else is terminated normally.)

The following PROCESS STATE DIAGRAM would show the entire operation:

Diagram of process state

Note, there is a intermediary state which is known to be the WAITING STATE/BLOCKED STATE.  The program goes through this particular state when the CPU is busy with interaction with the I/O devices during I/O operations (this is called I/O BURST). During I/O BURST, since the CPU time is being wasted, to avoid this; the pending jobs are brought up from the queue by the CPU Scheduler and then this new job is executed with first READY STATE and then after the whole operation is finished, the original Job is picked up and executed from middle-way. This way, the CPU saves significant amount of time and maintains the efficiency. The following describes the process timeline:

 

programterminationdiagramiooperationtimeline

 

CPU SCHEDULING

According to the process timeline, it could be observed that the program initiation starts with a CPU BURST and is terminated with a CPU BURST as well. During the entire process progression, the CPU has to interact with I/O devices and hence the pending jobs are completed during this time. The original job is held with a WAITING STATE/BLOCKED STATE status and upon completion of the pending process, the original job is taken. From the previous post we had discussed about two types of CPU Scheduling:

  • FCFS (First Come First Serve) CPU Scheduling.
  • SJF (Shortest Job First) CPU Scheduling.

SJF CPU Scheduling saves the time and is an efficient way to schedule jobs. This is done by the CPU Scheduler. Contrary to SJF CPU Scheduling, FCFS CPU Scheduling cannot save time and prediction for the next CPU BURST could not be determined (we need to determine or calculate the amount of time the next CPU BURST would be going to take to maintain an efficiency!) cannot be done. FCFS CPU Scheduling has a strict rule to take a Job, process and execute it and only after the termination of the original job, the next job could be taken by the CPU. Hence there is no real time efficiency scheduling been done with FCFS CPU Scheduling; the job which comes first is executed first and therefore prediction for the next CPU BURST could be applied for the SJF Scheduling algorithm. Since, SJF CPU Scheduling algorithm takes time efficiency into consideration, the CPU must predict the amount of time the CPU has to spend it’s time on NEXT CPU BURST.

CPU BURST: The amount of time spent by the CPU for a program in order to execute the program, process it for the execution.
I/O BURST: The amount of time spent by the CPU for a program interacting with I/O devices for I/O operations.

Now, since a calculated prediction of the NEXT CPU BURST could only be determined for SJF CPU Scheduling, the following is considered as the standard process to calculate an estimate of the amount of time spent for the NEXT CPU BURST which would be yet to occur for a program process:

image018image019

 

Now, there is yet another calculated special case of SJF algorithm which could be used for efficiency purposes. This special case of SJF CPU Scheduling algorithm is known as PRIORITY SCHEDULING. In case of priority scheduling, the priority levels could be  set. In that case the job which has the highest priority should be executed first. Low priority jobs will be executed only after high specified priority jobs had been executed. It could be said that PRIORITY SCHEDULING could be considered as the reciprocal of the NEXT CPU BURST.

NON-PREEMPTIVE CPU SCHEDULING

Now, all of these scheduling algorithms, that is:

  1. FCFS
  2. SJF
  3. Priority

are known to be NON-PREEMPTIVE SCHEDULING. The reason it is known to be NON-PREEMPTIVE Scheduling is since the processing of jobs once allocated, the CPU cannot be taken out of the job until that entire CPU BURST is complete. At the end of the current CPU BURST, another Job could be assigned to the CPU by the CPU Scheduler.

PREEMPTIVE CPU SCHEDULING

The situation with PREEMPTIVE CPU SCHEDULING is wherein the job is in it’s CPU BURST but could be made PREEMPTIVE by allocating another JOB (the current job has to be stopped before it’s natural completion). As per the three CPU Scheduling we have seen so far, the FCFS CPU Scheduling cannot be PREEMPTIVE CPU SCHEDULING because  FCFS has to follow the strict rules regarding the jobs which are sent first must be completed first (executed first), and only after the normal completion of the first job execution, other pending jobs should be executed. The remaining two, that is SJF CPU Scheduling and Priority Scheduling algorithm could be modified to get PREEMPTIVE CPU SCHEDULING.

Let’s take an example of jobs which are in the READY Queue with SJF CPU Scheduling modified to suit PREEMPTIVE CPU SCHEDULING that is SHORTEST REMAINING TIME FIRST CPU SCHEDULING (SRT):

J1 – 15
J2 – 9
J3 – 3
J4 – 5

These jobs are in the ready queue with their CPU BURST time. As per the SJF CPU SCHEDULING, the shortest execution time required has to be picked up which in this case would be J3, since J3 has 3 units of time requirement and others have a longer span of time requirement. Let’s consider the execution has been started and the J3 job has spent 1 unit of time with the CPU Processing:

J3

|———–|
1 UNIT

There are remaining 2 UNITS of time completion left for job J3, but another job which is Job J5 arrives which requires an execution CPU BURST time of 1 unit, so, now on the READY Queue we have:

J1 – 15
J2 – 9
J3 – 2 (Since 1 unit has already been completed, the left over is 2 time units.)
J4 – 5
J5 – 1 (new job which has arrived with time unit 1)

Now, the CPU Scheduler has to check the ready queue to find out which job has the minimum of time requirement as per the policy of SJF CPU SCHEDULING algorithm. The CPU Scheduler would find that the new job which has arrived only requires 1 time unit and hence will allocate the job J5 by PREEMPTIVE procedure of job J3 which was in the middle of the execution; the job J5 will be processed for execution:

J3              J5               2 UNIT LEFT

|———–|———–|______________|
1 UNIT     1 UNIT

So, the Job J5 will be executed since it has been scheduled to be executed in the middle of Job J3’s execution. After completion of Job J5, the CPU Scheduler would again check the READY QUEUE to check the status, and the CPU BURST requirement would be:

J1 – 15
J2 – 9
J3 – 2 (This is the minimum time unit)
J4 – 5
J5 – 0 (Since it is finished)

Assuming no new jobs came to the READY QUEUE with lower time unit requirement as compared to that of Job J3 time unit (which was left!), the CPU Scheduler would assign the CPU to execute J3 which requires 2 time units:

J3              J5                        J3

|———–|———–|———————-|
1 UNIT     1 UNIT              2 UNIT

After the completion of the job J3, the CPU Scheduler yet again has to check the READY QUEUE:

J1 – 15
J2 – 9
J3 – 0
J4 – 5
J5 – 0

Now, the modified SJF algorithm will treat Job J4 to be minimum and start executing it assuming no newer jobs were upfront available in the READY QUEUE. This is how the SJF CPU Scheduling algorithm can be used to maintain efficiency in CPU processing with modification which is known to be SRT (SHORTEST REMAINING TIME FIRST) CPU Scheduling.

Now there must be a way to modify the Priority Scheduling algorithm to obtain an efficient result. This could be done using the same logic but using ‘priority’ in mind. The higher priority job must be executed first. But there would be a conflict using priorities since if a job which always have a high priority in the READY QUEUE than the others has to be executed first and this job comes coming over and again to the READY QUEUE, the lower priority jobs will starve for CPU time and hence might not get executed ever. Now, this situation is unwanted, a concept called ‘aging‘ is used. While the job remains in the READY QUEUE, at regular intervals of time, the CPU will go incrementing the priority of the jobs. Now the priority of the job isn’t decided by the user or the administrator, but it’s decided by the time spent by the CPU for a particular job while other incrementing pending jobs were getting higher priority hits since it’s been aging for CPU time. At one point the maximum priority level will be reached by the job(s) pending, and when it reaches this priority level, the CPU will start executing that job leaving the current job to the WAIT/BLOCK status.

The time taken by the CPU Scheduler which has to be executed by the CPU as well program should be negligible compared to the CPU BURST time of the jobs. Now for a brief overview of what we had discussed here were process block diagram where we talked that a process could migrate from READY state to the ACTIVE state and from the ACTIVE state to the WAITING STATE and then again from the WAITING state to the READY state until the job completion. But with new concepts involved such as PREEMPTIVE CPU Scheduling, there is another route of this migration of state, which hence could be also from the ACTIVE state to the READY state. Hence below is something which completes the Process State Diagram:

pathagain

The ‘blue’ color path is the new path which is available because of PREEMPTIVE CPU Scheduling. With respect to the process state diagram; in a system if there are jobs which require more amount of CPU BURST time, such jobs would be called as ‘CPU Bound Jobs‘, another type of CPU BURST time is where a process would require more I/O time and less CPU time, such jobs are referenced as ‘I/O Bound Jobs‘. Hence two types of Jobs are:

  1. CPU Bound Jobs
  2. I/O Bound Jobs

Now, assume, In the READY Queue, all the jobs are CPU Bound Jobs; this means for none of the jobs, I/O operation is much concerned which again means I/O operation in the whole processing is negligible and very less time units are spent in I/O operations whereas much time is spent over CPU processing. So in such cases, the CPU time taken will be quite high and I/O devices will remain inactive. Now contradictory to the past situation where CPU Bound Jobs were in READY QUEUE and I/O operations were negligible, there could be situation where all the jobs in the READY QUEUE are I/O operation jobs and negligible CPU process jobs, which means time spent by the CPU will be negligible for these jobs and the I/O devices will be very busy since all the jobs have I/O operations. None of the previous and the current situation are wanted or desirable. Because the efficiency lies in the point that a system should be always busy with all of it’s components and in these cases either the CPU remains inactive or the I/O devices remains inactive, hence wasting ‘time’ and resources therefore go without proper management scheduling of the jobs in the first place. To avoid this situation, or rather to schedule the jobs efficiently, there are schedulers.

Technically all of this means that there must be some kind of management at the READY QUEUE to avoid situations wherein resource time are being wasted. To address the problem, there are schedulers. There are two kind of schedulers, one which takes the job from the NEW STATE to the READY STATE (shifting the job from NEW to the main memory which is dubbed as READY QUEUE – The state diagram will describe it as the READY STATE) and another which takes the job from the READY STATE to the ACTIVE STATE. Since the procedure where the job has to be taken from the READY STATE (READY Queue) to the ACTIVE STATE is complex because of very low time span  of the CPU BURST. The CPU BURST time span being short, the Scheduler cannot decide which operation (whether the job has to be migrated from the READY STATE to the ACTIVE STATE or ACTIVE STATE to the READY STATE (READY QUEUE) because there are two routes here {see the diagram above which shows the new path in blue because of PREEMPTIVE CPU Scheduling}) to be done. So this scheduler which takes the job from the READY STATE (READY QUEUE) to the ACTIVE STATE is known to be SHORT TERM SCHEDULER. The other scheduler which takes the job from the NEW STATE to the READY STATE (READY QUEUE) is called LONG TERM SCHEDULER. Therefore the two kinds of Schedulers are:

  1. LONG TERM SCHEDULER
  2. SHORT TERM SCHEDULER

Since we discussed that in the READY QUEUE it is  not desirable to have CPU Bound Jobs or I/O Bound jobs, the LONG TERM SCHEDULER would be responsible to decide what jobs should be sent to the READY STATE (READY QUEUE). The duration of the LONG TERM SCHEDULER is quite long since it has plenty of time to decide, but the scope of time involved for SHORT TERM SCHEDULER is quite less which is the reason we can afford a complex LONG TERM SCHEDULER.