States of a process

States of a process are as following:

• New (Create) – In this step process is about to create but not yet created, it is the program which is present in secondary memory that will be picked up by OS to create the process.
• Ready – New -> Ready to run. After creation of process, the process enters the ready state i.e. into the main memory. The process here is ready to run and is waiting to get the CPU time for its execution.
• Run – The process is running in the main memory.
• Blocked or wait – Whenever the process requests the I/O it enters the blocked or wait state. It is executed in the main memory and it doesn’t require CPU. Once the I/O operation is completed the process goes to ready state.
• Terminated or completed – Process is killed as well as PCB is deleted.
• Suspend ready – Set of process that were initially in ready state but lack of main memory caused them to go to suspend ready, it is a secondary memory.
• Suspend wait or suspend blocked – Similar to suspend ready but uses the process which was performing I/O operation and lack of main memory caused them to move to secondary memory.
  When work is finished it may go to suspend ready.

CPU and IO Bound Processes:
If process is having lots of CPU operation then it is called CPU bound process. Similarly, If process is having lots of IO operation then it is called IO bound process.

Types of schedulers:

1. Long term – performance – Makes decision about how many processes should be made to stay in the ready state this decides the degree of multiprogramming. Once decision is taken it lasts for long time hence called long term scheduler.
2. Short term – Context switching time – Short term scheduler will decide which process to be executed next and then it will call dispatcher. Dispatcher is a software that moves process from ready to run and vice versa. In other words, it is context switching.
3. Medium term – Swapping time – Suspension decision is taken by medium term scheduler. Medium term scheduler is used for swapping that is moving the process from main memory to secondary and vice versa.

Multiprogramming – We have many processes ready to run. There are two types of multiprogramming:

1. Pre-emption – Process is forcefully removed from CPU. Pre-emption is also called as time sharing or multitasking.
2. Non pre-emption – Processes are not removed until they complete the execution.

Degree of multiprogramming –
The number of process that can reside in the ready state at maximum decides the degree of multiprogramming, e.g., if degree of programming = 100 means 100 processes can reside in the ready state at maximum.

RAM and ROM

Types of computer memory (RAM and ROM)

Memory is the best essential element of a computer because computer can’t perform simple tasks. Computer memory is of two basic type – Primary memory / Volatile memory and Secondary memory / non-volatile memory. Random Access Memory (RAM) is volatile memory and Read Only Memory (ROM) is non-volatile memory.

1. Random Access Memory (RAM) –

• It is also called as read write memory or the main memory or the primary memory.
• The programs and data that the CPU requires during execution of a program are stored in this memory.
• It is a volatile memory as the data loses when the power is turned off.
• RAM is further classified into two types- SRAM (Static Random Access Memory) and DRAM (Dynamic Random Access Memory).

2. Read Only Memory (ROM) –

• Stores crucial information essential to operate the system, like the program essential to boot the computer.
• It is not volatile.
• Always retains its data.
• Used in embedded systems or where the programming needs no change.
• Used in calculators and peripheral devices.
• ROM is further classified into 4 types- ROM, PROM, EPROM, and EEPROM.

Types of Read Only Memory (ROM) –

1. PROM (Programmable read-only memory) – It can be programmed by user. Once programmed, the data and instructions in it cannot be changed.
2. EPROM (Erasable Programmable read only memory) – It can be reprogrammed. To erase data from it, expose it to ultra violet light. To reprogram it, erase all the previous data.
3. EEPROM (Electrically erasable programmable read only memory) – The data can be erased by applying electric field, no need of ultra violet light. We can erase only portions of the chip.

Types of Operating Systems

Types of Operating Systems: Some of the widely used operating systems are as follows-

1. Batch Operating System –
This type of operating system do not interact with the computer directly. There is an operator which takes similar jobs having same requirement and group them into batches. It is the responsibility of operator to sort the jobs with similar needs.

Advantages of Batch Operating System:

• It is very difficult to guess or know the time required by any job to complete. Processors of the batch systems knows how long the job would be when it is in queue
• Multiple users can share the batch systems
• The idle time batch system is very less
• It is easy to manage large work repeatedly in batch systems

Disadvantages of Batch Operating System:

• The computer operators should be well known with batch systems
• Batch systems are hard to debug
• It is sometime costly
• The other jobs will have to wait for an unknown time if any job fails

Examples of Batch based Operating System: Payroll System, Bank Statements etc.

2. Time-Sharing Operating Systems –
Each task has given some time to execute, so that all the tasks work smoothly. Each user gets time of CPU as they use single system. These systems are also known as Multitasking Systems. The task can be from single user or from different users also. The time that each task gets to execute is called quantum. After this time interval is over OS switches over to next task.

Advantages of Time-Sharing OS:

• Each task gets an equal opportunity
• Less chances of duplication of software
• CPU idle time can be reduced

Disadvantages of Time-Sharing OS:

• Reliability problem
• One must have to take care of security and integrity of user programs and data
• Data communication problem

Examples of Time-Sharing OSs are: Multics, Unix etc.

3. Distributed Operating System –
These types of operating system is a recent advancement in the world of computer technology and are being widely accepted all-over the world and, that too, with a great pace. Various autonomous interconnected computers communicate each other using a shared communication network. Independent systems possess their own memory unit and CPU. These are referred as loosely coupled systems or distributed systems. These systems processors differ in sizes and functions. The major benefit of working with these types of operating system is that it is always possible that one user can access the files or software which are not actually present on his system but on some other system connected within this network i.e., remote access is enabled within the devices connected in that network.

Advantages of Distributed Operating System:

• Failure of one will not affect the other network communication, as all systems are independent from each other
• Electronic mail increases the data exchange speed
• Since resources are being shared, computation is highly fast and durable
• Load on host computer reduces
• These systems are easily scalable as many systems can be easily added to the network
• Delay in data processing reduces

Disadvantages of Distributed Operating System:

• Failure of the main network will stop the entire communication
• To establish distributed systems the language which are used are not well defined yet
• These types of systems are not readily available as they are very expensive. Not only that the underlying software is highly complex and not understood well yet

Examples of Distributed Operating System are- LOCUS etc.

4. Network Operating System –
These systems runs on a server and provides the capability to manage data, users, groups, security, applications, and other networking functions. These type of operating systems allows shared access of files, printers, security, applications, and other networking functions over a small private network. One more important aspect of Network Operating Systems is that all the users are well aware of the underlying configuration, of all other users within the network, their individual connections etc. and that’s why these computers are popularly known as tightly coupled systems.

Advantages of Network Operating System:

• Highly stable centralized servers
• Security concerns are handled through servers
• New technologies and hardware up-gradation are easily integrated to the system
• Server access are possible remotely from different locations and types of systems

Disadvantages of Network Operating System:

• Servers are costly
• User has to depend on central location for most operations
• Maintenance and updates are required regularly

Examples of Network Operating System are: Microsoft Windows Server 2003, Microsoft Windows Server 2008, UNIX, Linux, Mac OS X, Novell NetWare, and BSD etc.

5. Real-Time Operating System –
These types of OSs serves the real-time systems. The time interval required to process and respond to inputs is very small. This time interval is called response time.

Real-time systems are used when there are time requirements are very strict like missile systems, air traffic control systems, robots etc.

Two types of Real-Time Operating System which are as follows:

• Hard Real-Time Systems:
  These OSs are meant for the applications where time constraints are very strict and even the shortest possible delay is not acceptable. These systems are built for saving life like automatic parachutes or air bags which are required to be readily available in case of any accident. Virtual memory is almost never found in these systems.
• Soft Real-Time Systems:
  These OSs are for applications where for time-constraint is less strict.

Advantages of RTOS:

• Maximum Consumption: Maximum utilization of devices and system,thus more output from all the resources
• Task Shifting: Time assigned for shifting tasks in these systems are very less. For example in older systems it takes about 10 micro seconds in shifting one task to another and in latest systems it takes 3 micro seconds.
• Focus on Application: Focus on running applications and less importance to applications which are in queue.
• Real time operating system in embedded system: Since size of programs are small, RTOS can also be used in embedded systems like in transport and others.
• Error Free: These types of systems are error free.
• Memory Allocation: Memory allocation is best managed in these type of systems.

Disadvantages of RTOS:

• Limited Tasks: Very few task run at the same time and their concentration is very less on few applications to avoid errors.
• Use heavy system resources: Sometimes the system resources are not so good and they are expensive as well.
• Complex Algorithms: The algorithms are very complex and difficult for the designer to write on.
• Device driver and interrupt signals: It needs specific device drivers and interrupt signals to response earliest to interrupts.
• Thread Priority: It is not good to set thread priority as these systems are very less pron to switching tasks.
Examples of Real-Time Operating Systems are: Scientific experiments, medical imaging systems, industrial control systems, weapon systems, robots, air traffic control systems, etc.

introduction to operating system

Functions of Operating system – Operating system performs three functions:

1. Convenience: An OS makes a computer more convenient to use.
2. Efficiency: An OS allows the computer system resources to be used in an efficient manner.
3. Ability to Evolve: An OS should be constructed in such a way as to permit the effective development, testing and introduction of new system functions without at the same time interfering with service.

Operating system as User Interface –

1. User
2. System and application programs
3. Operating system
4. Hardware

Every general purpose computer consists of the hardware, operating system, system programs, and application programs. The hardware consists of memory, CPU, ALU, and I/O devices, peripheral device and storage device. System program consists of compilers, loaders, editors, OS etc. The application program consists of business programs, database programs.

Sort a stack using a temporary stack

Sort a stack using a temporary stack

Given a stack of integers, sort it in ascending order using another temporary stack.

Examples:

Input : [34, 3, 31, 98, 92, 23]
Output : [3, 23, 31, 34, 92, 98]

Input : [3, 5, 1, 4, 2, 8]
Output : [1, 2, 3, 4, 5, 8]

We follow this algorithm.

1. Create a temporary stack say tmpStack.
2. While input stack is empty do this:
   • Pop an element from input stack call it x
   • while temporary stack is not empty and top of stack is greater than x,
     pop from temporary stack and push it to the input stack
   • push temp in tempory of stack
3. The sorted numbers are in tmpStack

Here is a dry run of above pseudo code.

input: [34, 3, 31, 98, 92, 23]

Element taken out: 23
input: [34, 3, 31, 98, 92]
tmpStack: [23]

Element taken out: 92
input: [34, 3, 31, 98]
tmpStack: [23, 92]

Element taken out: 98
input: [34, 3, 31]
tmpStack: [23, 92, 98]

Element taken out: 31
input: [34, 3, 98, 92]
tmpStack: [23, 31]

Element taken out: 92
input: [34, 3, 98]
tmpStack: [23, 31, 92]

Element taken out: 98
input: [34, 3]
tmpStack: [23, 31, 92, 98]

Element taken out: 3
input: [34, 98, 92, 31, 23]
tmpStack: [3]

Element taken out: 23
input: [34, 98, 92, 31]
tmpStack: [3, 23]

Element taken out: 31
input: [34, 98, 92]
tmpStack: [3, 23, 31]

Element taken out: 92
input: [34, 98]
tmpStack: [3, 23, 31, 92]

Element taken out: 98
input: [34]
tmpStack: [3, 23, 31, 92, 98]

Element taken out: 34
input: [98, 92]
tmpStack: [3, 23, 31, 34]

Element taken out: 92
input: [98]
tmpStack: [3, 23, 31, 34, 92]

Element taken out: 98
input: []
tmpStack: [3, 23, 31, 34, 92, 98]

final sorted list: [3, 23, 31, 34, 92, 98]

Output:

Sorted numbers are:
98 92 34 31 23 3 

Applications of Queue

Applications of Queue

Queue, as the name suggests is used whenever we need to manage any group of objects in an order in which the first one coming in, also gets out first while the others wait for their turn, like in the following scenarios :

1. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
2. In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e First come first served.
4. Queue is used in BFS(Breadth First Search) algorithm. It helps in traversing a tree or graph.

A real-world example of queue can be a single-lane one-way road, where the vehicle enters first, exits first. More real-world examples can be seen as queues at the ticket windows and bus-stops.

Vehicle on Road

Program to Implement Two Stacks in an Array

• Write a program to implement two stacks using a single array supporting push and pop operations for both stacks.

Given an integer array of size N. We have to implement two stacks in given array. Both stacks must support push and pop operations. We should be able to push an element in any stack until there is a empty slot in given array.

Algorithm to implement two stacks in a array

• We will start two stacks from two extreme end of input array. Both these stacks will grow towards each other.
• Left stack will start index 0 and grow towards right end of array.
• Right array will start from index N-1 and grow towards left end of array.
• We will use stack number to differentiate between these two arrays. 0 and 1 will be used for left and right array respectively.
• When both stacks meet each other then we won't be able to push any element in any stack.

Here is the prototype of push and pop operations.
PUSH

• void push(int stack, int num);
• It will take stack number and integer to be pushed in stack as input.

POP

• int pop(int stack)
• It takes stack number as input. It removes the top element from stack corresponding to passed stack number.

NOTE : Here we are using same push and pop method for both stacks. We will select appropriate stacks based on stack number.

---

C program to implement two stacks in using one array

Output

Pop from left stack 6
Pop from right stack 5

---

By dividing array into two equal parts.

• We will divide the input array into two equal sub arrays. Left stack from index 0 to N/2-1 and right stack from index N/2 to N-1.
• Left stack will start from index 0 and can grow till index N/2-1 whereas right start will start from index N/2 and can grow till index N-1.
• Any stack cannot hold more than N/2 elements.

Print Binary Tree levels in sorted order

Given a Binary tree, the task is to print its all level in sorted order

Examples:

Input :     7
          /    \
        6       5
       / \     / \
      4  3    2   1
Output : 
7
5 6
1 2 3 4 

Input :     7
          /    \
        16       1
       / \      
      4   13    
Output :
7 
1 16
4 13

Here we can use two Priority queue for print in sorted order. We create an empty queue q and two priority queues, current_level and next_level. We use NULL as a separator between two levels. Whenever we encounter NULL in normal level order traversal, we swap current_level and next_level.

Output:

Level Order traversal of binary tree is 
7 
5 6 
1 2 3 4