Scheduling Criteria of CPU

Scheduling Criteria of CPU for a scheduler varies from one scheduler to another. There are many scheduling algorithms. Different scheduling algorithms have different properties. The selection of a proper scheduling algorithm may improve the system performance. We must consider the properties of various scheduling algorithm and the computer system for selecting a particular scheduling algorithm.

Many criteria have been suggested for evaluating the scheduling algorithm. Some commonly used scheduling criteria are described below.

1.      CPU Utilization Scheduling Criteria:

The CPU must be busy as much as possible to perform different activities. The percentage of time, the CPU is executing a process may range from 0 to 100 percent. CPU utilization is very important in real time and multiprogramming system. In a real time system the CPI utilization should be 50 percent (lightly loaded system) to 95 percent (heavily loaded system). It means that load on a system affects the CPU utilization. The high CPU utilization is achieved on heavily loaded system.

2.      Balanced Utilization Scheduling Criteria:

Balanced utilization represents the percentage of the time al the resource utilized. In addition to considering he CPU utilization the utilization of memory, I/O devices and other system resources are also considered.

3.      Through Put Scheduling Criteria:

The number of process executed by the system in a specific period of time this time unit is called through put. For long process this rate may be one process per minute. Similarly for short process, it may be 100 processes per minute. The evaluation of through must be considered on the basis of average length.

4.      Turnaround  Time Scheduling Criteria:

Turnaround time represents the average period of time taken by a process executes. The turnaround time is computed by subtracting the time, when the process was created from the time is terminated. The turnaround time is inversely proportional to through put.

5.      Waiting Time Scheduling Criteria:

Waiting time represents the average period of time, a process spends waiting in the ready queue to get a chance for execution. It does not include the time, a prcess is executing on the CPU or performing I/O. waiting time is also very important factor to measure the performance of the system.

6.      Response Time Scheduling Criteria:

Response time represents the average time take by the system to start responding to user request. The response time is considered in interactive systems. For example, ATM is an interactive system, which is used in banks for withdrawal of money. The user expects that the system should response quickly. In interactive system the turnaround time is not a best criterion and this mostly depends on the speed of the users responses to the turnaround time in interactive system has no importance. Therefore the response time in an interactive system should be very less.

7.      Predictability Scheduling Criteria:

Predictability represents the consistency in the average response time in interactive system. It is another measure of performance of a system because users prefer consistency. Suppose an interactive system that normally responds within a microsecond, but on some occasions, it takes 5 to 15 milliseconds or more. In this case the user may be confused. Mostly the users prefer the system with reasonable and predicable response time, than a system that is faster but is highly variable is response time.

8.      Fairness Scheduling Criteria:

Fairness represents the degree to which all processes are given equal opportunity of execution. This criterion is codified in time shared system.

9.      Priorities Scheduling Criteria:

The process with higher priorities must be given preference for execution.

Types of CPU schedulers

Several types of schedulers may be used in operating systems there are three fundamental types of schedulers

·         Long term scheduler

·         Short term scheduler

·         Medium term scheduler

Long term scheduler

Long term scheduler is also known as job scheduler. It selects jobs or user programs from job poolon the disk and loads them into main memory. Once a job or user program is loaded into memory, it becomes the process and added to the ready queue.  The long term scheduler controls the number of process in memory. It means that it controls the degree of multiprogramming.

Short term scheduler

The short term scheduler is also known as dispatcher. It retrieves a process from the ready queue and CPU is allocated to it. The process state is changed from ready to running. If an interrupt or time out occurs the scheduler places the running process back into the ready queue and marks it as ready. Typically the dispatcher gives the control of CPU for a fixed amount of time. A Process may execute for only a few milliseconds, and then the next process is selected form ready queue for execution and so on. The time taken by the dispatcher to stop the execution of one process and then to start the execution of another process is known as the dispatcher latency.

Medium term scheduler

The medium term scheduling is also known as swapping. In this scheduling swapper is used to exchange process between main memory and secondary storage (disk). Typically multiprocessing system use swapping technique, Sometimes a process that  is in job queue on disk is too long and cannot be fit in memory, then swapper removes another process from ready queue to make room for it. Later the same process is re-loaded into memory, which is added to ready queue and its execution is continued where it left off if a process is waiting for completion of a short term I/O operation than it is not swapped out.

What is CPU Scheduling

The processes entered into the computer system are put into the job queue. Similarly, the processes that are in main memory and are ready to execute are kept in a ready queue. In a multiprogramming and timesharing systems, multiple processes is used to determine which process to run first and how much times.  The method or procedure for switching the CPU among multiple processors is called CPU scheduling or process scheduling. The part of operating system which schedules the process is called the CPU scheduler.

In single precursors system one process can run at a time and other processes have wait. In multiprocessing system some processes may be running in this cases schedules the execution of processes on the CPU.

In multiprogramming system some processes may be running at all times. Similarly timesharing system must switch from one process to another so frequently that users can interact with their programs. The CPU scheduler plays the main role in multiprogramming and timesharing system.

CPU scheduling increase the CPU utilization.  Whenever CPU becomes idle the CPU scheduler selects a process from the ready queue and sends it to the CPU for execution.

Preemptive and None preemptive scheduling:

The earlier computer systems used the non preemptive scheduling. It means that a process retained control of the CPU until the process blocked or terminated. This approach was used in batch systems. In modern computer systems preemptive scheduling is used. The scheduler may preemptive a process before it blocks or terminated in order to allocate the CPU to another process.

For example, the non preemptive scheduling was used by Microsoft windows 3.x product. The preemptive scheduling was introduced in Windows 95 operating system. To day all operating systems used this method. Non preemptive scheduling is used only on certain hardware platform.

What is Thread

A thread is a sequence of instruction within a process. A thread also represents the sequential flow of execution of the task of a process. A process may consist of one of many threads. Therefore a thread is sometimes called a lightweight process. Each thread has its own information of program counter, CPU register and stack. In a process, threads are typically used for dividing a task in a web browser are divided into multiple threads such as,

• Task to download the images
• Task to download the text
• Task to display images and text etc

You have observed that downloading images take more time than text. In this case one thread remains busy for downloading images, while other threads download and display the text. It must be noted that each process occupies an independent address space in memory. But all threads of the process share the same address space. On the basis of process execution, the Operating System can be classified as,

1.      Single-Process single-thread

2.      Single-Process multiple-threads

3.      Multi-Process single-thread

4.      Multi-Process multi-threads

The simplest arrangement is single-process single-thread. Where only one task can be perform at a time. MS DOS is an example of a single-process single-thread operating system. For example in a word processor program only one process can execute at a time. The user cannot simultaneously type text and run the spell checker within the same process.

To day modern systems allow a process to have multiple threads per process. A Java run-time environment is an example of a system of one process with multiple threads.

The multiprogramming system allows the CPU to be shared by multiple processes, for example UNIX supports multiple users’ processes but each process has only one thread.

Some operating system allows multiple process and multiple threads per process like Windows, Linux and OS/2 etc.

User level and kernel level threads

The support for thread may be provided either at user level or by kernel level. Therefore threads may be divided into two categories.

1. User-level Threads
2. Kernel-level Threads

User-level Threads

In user level threads all work of threads management is done by the application without kernel support. Any application can be programmed to be multithreaded by using a threads library, which has a collection of routines that can be sued for user level threads management. For example threads library contains the routines for

• Creating and destroying threads
• Passing data between threads
• Scheduling threads
• Saving and restoring states of threads etc.

Once and application is loaded into user space, all the threads are created and managed within the user space of a process, by default an application begins with a single thread and continuously running in that thread. This application and its thread are managed by the Kernel. At any time the application may create many threads within the same process. A separate data structure for each thread also created. Some scheduling algorithm is also used to pass control to one thread to another within the process; when control is switched from one thread to another that state of the currently executed is saved and then restored which control returns back.

Kernel-level thread

In kernel level thread all work of threads management is done by the kernel of operating system. There is no thread management code in user space of the process. In this approach when control is switched form one thread to another within the same process then control also has to switch form user mode to kernel mode. So this approach affects the performance of the system. Scheduling by the kernel is done on a thread basis. Most of the operating system support kernel threads. These systems are windows XP, Linux and Solaris etc.

Multithreading Models

There must exist a relationship between user threads and kernel threads. These relationships can be established by using the following models.

1. Many to One model
2. One to One model
3. Many to Many model

Many to one model

In many to one model a user space is allocated to single process and multiply threads may be created and executed within that process. The application and its threads are managed by the kernel. The many to one model maps many user level threads to one kernel thread. Thread management is done by the thread library in user space. In this model the entire process will be block if a thread makes a blocking system call. Only one thread can access the kernel at a time so it is impossible to run multiple threads in parallel on multiprocessors system.

One to One model

The one to one model maps each user level thread to one kernel thread. This modl provides more concurrency than many to one model, because it allows another thread to run when a thread makes a blocking system call. This model also allows multiple threads to run in parallel on multiprocessors system.

Many to Many models

The Many to Many models multiplexes many user level threads to smaller equal number of kernel threads. The number of kernel threads may be specific to either a paruvullar application or a particular machine.

 

Inter-Process Communication

A mechanism through which data is shared among the process in the system is referred to as Inter-process communication. Multiple processes communicate with each other to share data and resources. A set of functions is required for the communication of process with each other. In multiprogramming systems, some common storage is used where process can share data. The shared storage may be the main memory or it may be a shared file. Files are the most commonly used mechanism for data sharing between processes. One process can write in the file while another process cam read the data for the same file.

Various techniques can be used to implement the Inter-Process Communication. There are two fundamental models of Inter-Process communication that are commonly used, these are:

1. Shared Memory Model

2. Message Passing Model

·        Shared Memory Model

In shared memory model. The co operating process shares a region of memory for sharing of information. Some operating systems use the supervisor call to create a share memory space. Similarly, Some operating system use file system to create RAM disk, which is a virtual disk created in the RAM. The shared files are stored in RAM disk to share the information between processes. The shared files in RAM disk are actually stored in the memory. The Process can share information by writing and reading data to the shared memory location or RAM disk.

·        Message Passing Model

In this model, data is shared between process by passing and receiving messages between co-operating process. Message passing mechanism is easier to implement than shared memory but it is useful for exchanging smaller amount of data. In message passing mechanism data is exchange between processes through kernel of operating system using system calls. Message passing mechanism is particularly useful in a distributed environment where the communicating processes may reside on different components connected by the network. For example, A data program used on the internet could be designed so that chat participants communicate with each other by exchanging messages. It must be noted that passing message technique is slower than shared memory technique.

• A message contains the following information:
• Header of message that identifies the sending and receiving processes
• Block of data
• Pointer to block of data
• Some control information about the process

Typically Inter-Process Communication is based on the ports associated with process. A port represent a queue of processes. Ports are controlled and managed by the kernel. The processes communicate with each other through kernel.

In message passing mechanism, two operations are performed. Theses are sending message and receiving message. The function send() and receive() are used to implement these operations. Supposed P1 and P2 want to communicate with each other. A communication link must be created between them to send and receive messages. The communication link can be created using different ways. The most important methods are:

1. Direct model
2. Indirect model
3. Buffering   

Process Control Block

The data structure that stores information about a process is called a Process Control Block (PCB). In a computer system, each process is represented by a Process Control Block (PCB). It is also referred to as Task Control Block. The PCB contain the information about the process. It is the central store of information that allows the operating system to locate all the key information about a process. When CPU switches from one process to another, the operating system uses the Process Control Block (PCB) to save the state of process and uses these information when control returns back process is terminated, the Process Control Block (PCB) released from the memory. The information stored in the Process Control Block in given below

Process State

It indicates the information about the state of process such as blocked ready running etc.

Process ID

Each process is assigned a unique identification number, when it is entered into the system.

Program Counter

It indicates the address of the next instruction to be executed.

CPU Registers

It indicates the information about the contents of the CPU registers. The information of CPU registers must be saved when an interrupt occurs, so that the process can be continued correctly afterward. Registers hold the processed the result of calculations or addresses pointing to the memory locations of desired data.

CPU Scheduling Information

It indicates the information needed for CPU scheduling such as process priority, pointers to scheduling queues and other scheduling parameters.

Memory Management Information

It indicates the information needed for memory management such as value of the base and limit registers, page tables or segment tables, amount of memory units allocated to the process etc.

Accounting Information

It indicates the information about process number, CPU used by the process time limits etc.

I/O Status Information

It indicates the information about I/O devices allocated to the process a list of open files access rights of files opened and so on,

Link to Parent Process

A new process can be created from existing process; the existing process is called the parent process of the newly created process. The address of the PCB of parent process is stored.

Link to Child Process

The addresses of the PCBs of the child processes in the main memory are stored.

What is Process?

A process is just an executing program. In other words, a program in execution is called a process. The term process was first used by the designers of multics system in 1960s. since that time a process was considered as an activity to perform a task. A process also includes:

• Current activity, which is represented by current values of program counter, CPU registers and variables.
• Process stack, which contains temporary data such as parameters of procedure, return address and local variables.
• Heap, which is memory that is dynamically allocated during program execution time.
• Operating resources allocated to it.

It must be noted that a program is not a process itself. It is static entity stored in a file on the disk. A process is an active entity, with a program counter specifying the next instruction to execute and a set of associated resources. A program becomes a process, when it is loaded into the memory for execution.

There may be multiple process for the same program. The process are controlled and scheduled by the operating system conceptually. Each process has its own virtual cpu, but in reality a single CPU switches from process to process in a cycle. This switching form process to process is called multiprogramming.

Process States:

In computer system, a process changes states during execution. Various events can cause a process to change states. A process exists in one of the five states. These are

• New: this star of process indicated that the process has just been created.
• Blocked: in this state the process is blocked and is waiting for some event to occur before it can continue executing.
• Ready: in this state the process is not allocated to the processor for running but it is ready to run.
• Running: the process is executing on processor, if a system has one CPU then only one process can be in the running state.
• Terminated: the process has finished its execution on the cpu but the record of the process is still maintained by the operating system.

Transition between process states:

Five transitions are possible among these four states as shown below

• Running- Blocked: This transition occurs, when a running process must executes a system call such as for performing I/O operation, communicating with other processes etc. in such cases, continuing execution of the process must be blocked.
• Running- Ready: This transition occurs when the scheduler decides that the running process has used its time slice ( time allocated the process) it moves the process form running state to ready stare and runs another process.
• Ready- Running transition: This transition occurs when CPU scheduler selects a process for running from the ready queue and sent to the CPU for execution.
• Blocked- Ready: This transition occurs when a process is moved form blocked state to ready state. If no other process is running at that instant, transition 3 will be triggered immediately.
• Running- Terminated: This transition occurs, when a running process is terminated. A process may be terminated by either performing some illegal action or by completing the execution of its code.

Traps And interrupts

Traps and interrupts are events that break down the normal execution of the program.

Trap: A trap is and abnormal condition detected by the CPU, which indicates an unknown I/O device is accessed, etc.

Interrupt: An interrupt in an interruption in the normal execution of the program. When the CPU is interrupt, then it stops its current activities like execution of the program. And transfer the control to interrupting device to check the interrupt. The CPU responds interrupt. By saving the current value of the program counter and resetting the program to a new address. The new address is the starting address where procedure for handling interrupt is located. Similarly, other state information is also saved when an interrupt occurs. In many computer systems this information is stored in a special program status word register. After saving the necessary information, the interrupt service routine is executed on completion; the CPU resumes the interrupted program. Thus the application program does not have to contain any special code to accommodate the interrupts. The CPU and the operating system are responsible for suspending the program and then resuming it at the end of interrupt processing.

Difference:

1. A trap will occur at exactly the same point f the program execution, each time a program runs.

2. An interrupt is dependent on the relative timing between the interrupting device and the CPU.

An interrupt is signal sent to the CPU by an external hardware device such as I/O device. The software can also send interrupt signal to the CPU. Hardware may trigger an interrupt at any time sending a signal to the CPU through system bus. It also called a monitor call or supervisor call.

Interrupt are the important part of computer architecture. Each machine has its own interrupt mechanism, bur most of the function are common. The interrupt must transfer control to the appropriate interrupt service routine. Similarly, interrupts must be handled quickly. In a computer system only a predefined interrupts can be occurred, so the array of pointer is used to store the address of interrupt routines. This array of pointer is called the interrupt vector. Each trap and interrupt is associated with an index into that vector. The index values are the unique device number that provides the address of the interrupt service routine for interrupting device. The early computer systems stored the interrupt address in a fixed location or in a location indexed by the device number but the modern computer use the stack for this purpose.

Classes of interrupts:

There are many classes of interrupts, but the most common classes of interrupts are

·                    Program check interrupts

·                    Supervisor call interrupts

·                    Timer interrupts

·                    I/O interrupts

·                    External interrupts

·                    Machine check interrupts

Program check interrupts:

These are caused by some problems that may occur during program execution such as division by zero, arithmetic overflow or underflow, data read in correct format, attempt to reference a memory location beyond the limits of real memory, attempt to reference a protected resource etc. many systems allow users to specify their own routines to be executed when a program check interrupt occurs.

Supervisor call interrupts:

These are initiated by a running process that executes the supervisor call instruction. This type of interrupt is a user generated request for a particular system service such as for I/O operation etc.

Timer interrupts:

These are generated by timer within the CPU. Timer interrupt allows the operating system to perform certain function on regular intervals of time.

I/O interrupts:

These are generated by I/O controller. The i/o interrupts signal to the cpu that the status of device has changed. I/O interrupts are caused due to three resigns.

1. Input/output operation completes.

2. Input/output error occurs.
3. Input/output device is made ready.

External interrupts:

These are caused by pressing of the console’s interrupt key by the operation or the receipt of a signal from another processor on a multiprocessor system.

Machine check interrupts:

These are caused by hardware failure such as memory parity error.

Basic concept of computer

A computer system consists of various hardware components that play certain roles in computer systems. These components are interconnected to each other in such a way so that the computer can perform its desired functions. The main components of the computer systems are:

   1. C.P.U
   2. Main memory
   3. I/O module
   4. System bus
   5. C.P.U registers

Processor

Processor is the main component of the computer system. It controls the operations of the computer and co-ordinate the other components of the computer. It performs all the function according to program instruction. It consider as the brain of the computer. Many new systems have more than one processor.

Main memory

The program and data must be loaded into main memory of the computer before execution. So it is known as the working area of the computer. The main part (Kernal) of the operating systems also loaded into the memory during the booting process of the computer and performs different type of function residing in the main memory. It’s also known as temporary memory. If the computer system shut down or power cut-off all the data is cleared from the memory.

I/O Module

I/O module is an electronic component. It is also known as I/O (input/output) controller or controller deceives. The data and programs instruction moved between the computer and its external device through I/O modules. Each I/O device have its own I/O module to communicate with processor.

System Buses

A system bus is the electronic path through which data and command signals are communicated between the computer components, such as between main memory, processor, and I/O modules. Systems buses further divided into

   1. Data Bus
   2. Address Bus
   3. Control Bus

C.P.U Registers

It is the most important part of C.P.U. Each register performs a specific function.

   1. M.A.R (Memory Address Register)
   2. M.B.R (Memory Buffer Register)
   3. I/O AR (I/O Address Register)
   4. I/O BR (I/O Buffer Register)
   5. P.C (Program Counter)
   6. I.R (Instruction Register)
   7. Flag register
   8. Stack control register 

Computer system architecture

Computer architecture means design or construction of a computer. A computer sustem may be organized in different ways. Some computer systems have single processor and other have multiprocessors. So computer systems categorized in these ways.

1.      Single Processor Systems

2.      Multiprocessor Systems

3.      Clustered Systems

Single processor

Some computers use only one processor such as microcomputers. On a single processor system, there is only one CPU that perform all the activities in the computer system, However, most of these systems have  other special purpose processors, such as I/O Processor that move data rapidly among different components of the computer system. These processors execute only a limited system programs and do not run the user program. So we define single processor systems as “ A system that has only one general purpose CPU, is considered as single processor system.

Multiprocessor systems

Some systems have two or more processors. These systems are also known as parallel systems or tightly coupled systems. Mostly the processors of these systems share the common system bus (electronic path) memory and peripheral (input/output) devices. These systems are fast in data processing and have capability to execute more than one program simultaneously on different processors. This type of processing is known as multiprogramming or multiprocessing. Multiple processors further divided in two types.

                                     i.            Asymmetric Multiprocessing Systems (AMS)

                                   ii.            Symmetric Multiprocessing Systems (SYS)

Asymmetric multiprocessing systems

The multiprocessing system, in which each processor is assigned a specific task, is known as Asymmetric Multiprocessing Systems. In this system there exists master slave relationship like one processor defined as master and others are slave. The master processor controls the system and other processor executes predefined tasks. The master processor also defined the task of slave processors.      

Symmetric multiprocessing system

The multiprocessing system in each processor performs all types of task within the operating system. All processors are peers and no master slave relationship exits. In SMP systems many programs can run simultaneously. But I/O must control to ensure that data reach the appropriate processor because all the processor shares the same memory.

Clustered systems

Clustered systems are another form of multiprocessor system. This system also contains multiple processors but it differs from multiprocessor system. The clustered system is composed of multiple individual systems that connected together. In clustered system, also individual systems or computers share the same storage and liked to gather via local area network. A special type of software is known as cluster to control the node the systems.

Other form of clustered system includes parallel clusters and clustering over a wide area network. In parallel cluster multiple hosts can access the same data on the shared storage. So many operating systems provide this facility but some special software are also designed to run on a parallel cluster to share data.    

Intro to Operating System

Operating System Introduction

A computer is an electronic machine, which can store, process and retrieve information trough software, which are divided into two kinds

           I.      System software

           II.      Application software

The system software is used to control and manage the operation of the computer. While the application software’s are used to control or solve the particular problems of the users.

The systems software is further divided into different categories. The most important is operating system. It controls all the computer resources, application programs and provides the services to the systems users; it also provides the platform through which the computer programs are developed.

A usual computer system consists of five major elements.

Hardware: it includes the CPU, memory and input/output deceives and provides the basic computing resources for the system.

Operating System: it manages hardware and provides the services to the application programs and system users.

System Program: these programs are set of programs that use to provide the basic services for hardware and software such as disk scanner program, backup utility program and Antivirus.

Application Programs: the programs are used to solve the problems of user. Like word processor, and web browser.

Users: the user interact with the operating system indirectly though the application programs.

Components of operating systems

The operating system is divided into various components or parts and each component performs its own role in computer operation. The components of a typical operation system are:

    * Process management
    * Memory management
    * Secondary storage management
    * I/O system
    * File system
    * Protection system
    * Command interpreter system

Process management

The most important task of operating system is to manage and monitor different processes executing in the computer (The program in execution is called a process). A system consists of a collection of processes, some of which are operating systems processes and the rest of which are user processes. The process management component of the operating system schedules the processes for execution.

The operating system also performs following major activities for process management.

v     Creates and deletes both user and system processes.

v     Suspends and resumes process

v     Provides mechanisms for process synchronization

v     Provides mechanism for processes communication between them.

Memory management

The memory unit has very important role for data processing. The processor takes data and program instruction from memory, executes them, and store results in the main memory. In some advanced computer systems, memory can share by multiple processes. The operating systems must manage the allocation memory to these processes.

The operating system performs the following major memory management tasks.

v     Manages the memory space used by different processes or user programs

v     Loads new process into memory and allocates memory space for them

v     De-allocate memory space allocated to a process when it is terminated.

v     Swaps out and swaps in process if required.

Secondary storage management

The information and programs are permanently stored on the secondary devices such as hard disk, floppy disk, tape drive etc. the programs are loaded by operating system from secondary storage in main memory before to execute.

The operating system performs the following major secondary management tasks.

v     Manages free space

v     Allocates storage area for storing information and programs

v     Manages the disk scheduling

File system management

The processed data must be stored in the form of files on storage medium and can be retrieved when required for use (a file is a storage unit and it is a collection of information or it may be a set of programs instruction). The files are stored permanently on the storage device and are organized in folders or directories so that a particular file can be easily accessed.

File management is the most visible components of an operating system. It performs the following major file management tasks.

v     File operations such as creating, deleting, closing a file.

v     Directory operation such as creating new directory or removing directory

v     File organization such as arrangement of records into files and the ways for accessing these records

v     File protection to control access the files etc

I/O system

A computer communicates information through its input and output devices. The application programs access these devices through operating system supervisor calls provided for this purpose.

The OS perform these I/O related task

v     Issues commands to various I/O devices

v     Handles I/O interrupts

v     Handles I/O errors that occur to reading and writing operation.

Protection system

The operating system provides protection to various resources of the computer against unauthorized users so that only authorized users can access the system. The operating systems use various mechanisms for the protection of the computer system.

Command interpreter system

It is the basic interface between the computer and user the user interacts with the computer by giving command to the operating system. The command interpreter is also known as command line interpreter or the shell. It gets the commend from user and executes them