CU-BCA-SEM-III-System software and operating system-Second draft

Ordinary Files: Ordinary files are the one, with which we all are familiar. They may contain executable programs, text or databases. You can add, modify or delete them or remove the file entirely. Directory Files: Directory files, as discussed earlier also, represent a group of files. They contain a list of file names and other information related to these files. Some of the commands that manipulate these directory files differ from those for ordinary files. Special Files: Special files are also referred to as device files. These files represent physical devices such as terminals, disks, printers and tape-drives etc. These files are read from or written into just like ordinary files, except that operation on these files activates some physical devices. These files can be of two types: Character device files and block device files. In character device files, data is handled character by character, as in case of terminals and printers. In block device files, data is handled in large chunks of blocks, as in the case of disks and tapes. FIFO Files: FIFO (first-in-first-out) are the files that allow unrelated processes to communicate with each other. They are generally used in applications where the communication path is in only one direction, and several processes need to communicate with a single process. For an example of FIFO file, take the pipe in UNIX. This allows transfer of data between processes in a first-in-first-out manner. A pipe takes the output of the first process as the input to the next process, and so on. 5.3 FILE PROTECTION The original motivation for protection mechanisms came with the advent of multiprogramming. The intent was to confine each user's program to its assigned area of memory and thus, prevent programs from trespassing and harming each other. With the increased desire for sharing of objects in primary and secondary memory, more complex mechanisms for access control were devised. 5.3.1 Protection in Computer System Protection in primary storage is usually adjunct to address translation. Its objective is to allow concurrent aabc:bcd:cdend potentially mutually suspicious resident process to share the common physical address space, primary memory. In systems with contiguous allocation of memory, protection is usually accomplished with the aid of some sort of limit registers. When 101 CU IDOL SELF LEARNING MATERIAL (SLM)

the program is loaded, the limit or the bound registers are set to delineate the extent of its legitimate address space. At run time, each memory reference is prechecked to verify that it is within the bounds. Otherwise, access to memory is denied, and an exception is raised to activate the protection mechanism. Protection is ensured by making modification of the limit registers, a privileged operation that can be executed only when the machine is running in the privileged, supervisor state. The supervisor state is usually reserved for the operating system and for trusted system programs. User programs, by default, run in the less privileged user mode. In paging systems, a page-map table lists all pages that the related program can access. In addition, the table stores access rights – such as read, write, or execute – for each individual page. Each process has a separate page-map table. At run-time, the hardware address translation mechanism translates virtual addresses to physical addresses. Before allowing access to memory, the hardware verifies that (1) the target page exists in the program's address space and (2) that the intended mode of access is permitted. Any discrepancy causes an exception that invokes the protection mechanism. Loading and modification of page-map tables are privileged operations. The page-map tables themselves are usually kept in the operating system's private address space. Virtual-memory systems based on paging operate in much the same way, with the additional provision of handling legitimate references to pages that are not resident in main memory. Systems based on segmentation use the segment descriptor tables for address translation and protection. There is one segment-map table per process. Each entry of the table defines the base address, the length (size), and the access rights to the related segment. For each memory reference, the run-time address translation mechanism verifies that 11. The segment is within the program's address space, The offset is valid, and The intended mode of access is permitted. As discussed earlier, protection in secondary storage is usually affected by means of user- defined access rights that are associated with files and managed by the file system. Typically, the file owner- which is usually its creator – has the discretion to designate the access rights for all users of the file. The owner may subsequently modify the access rights in lists consisting of user IDs and their specific rights. The access list is usually stored in association with the file. For efficiency, some systems use abbreviated access lists. 102 CU IDOL SELF LEARNING MATERIAL (SLM)

5.3.2 Access-Matrix Model of Protection The use of seemingly quite different protection mechanisms for primary and secondary memory can sometimes obscure the basic underlying issues and principles. This section introduces the access-matrix model of protection, which serves as a useful abstraction for reasoning about protection mechanisms in computer systems. A computer system may be viewed as consisting of a set of subjects, such as processes, that operate on and manipulate a set of objects. Objects include both hardware, such as peripheral devices and memory segments, and software objects, such as files and arrays. From the software point of view, each object is an abstract data type. Operations on an object amount to applications of functions that may transform the state of the object. In principle, the specific subset of functions that can be meaningfully applied to an individual object is object-specific. The protection mechanism should ensure that (1) no process is allowed to apply a function inappropriate to a given object type and (2) each process is permitted to apply only those functions that it is explicitly authorized for a specific object. For any given object, the latter set is a subset of the object-specific legitimate operations. The authority to execute an operation on an object is often called the access right. Some of these relationships may be expressed by means of an abstraction called protection domain, which specifies a set of objects and the types of operations that may be performed on each object. A protection domain is a collection of access rights, each of which is a pair <object identifier, rights set>. In general, domains need not be static; their elements can change as objects are deleted or created and the access rights are modified. Domains may overlap; a single object can participate in multiple domains, possibly with different access rights defined therein. A simple illustration of the protection domain concept is provided by the dual, user/supervisor mode of operation found in many computer systems. A more elaborate example, provided by the IBM/360 type of hardware, uses 4-bit memory protection keys and thus, supports up to 15 user domains. In multi-user systems, each user typically has a protected set of programs and files, which amounts to as many protection domains as there are users. A process executes in a protection domain at a given point in time. This binding is not static, and a process may switch between different protection domains in the course of its execution. In a flexible protection system, not all parts and phases of a program need be given equal and 103 CU IDOL SELF LEARNING MATERIAL (SLM)

unrestricted access to all objects that the program has access rights to. For example, a procedure may have private data that it wants to have exclusive access rights to. The need to control access rights is especially pronounced in situations, where some common utilities, such as editors and compilers, are shared. In order for a process to use a shared utility, some of the user's access rights must be conveyed to it. For example, the compiler must be granted at least read access to the user's source file and, optionally, may have created and write-file access to the user program's home directory for object and listing files. However, it is unwise and dangerous to affect this transfer of rights by allowing the shared utility to assume all of the invoking user's access rights. Such promiscuous behaviour, not unusual in real systems, provides a fertile ground for planning of Trojan horses and for spreading of computer viruses. These relationships may be represented by means of an access matrix, which is a representation of all access rights of all subjects to all objects in a computer system. It is usually depicted as a two-dimensional matrix, with protection domains as rows and system objects as columns. Both hardware and software objects are included in the access matrix. Blank entries indicate no access rights. Thus, for example, a process executing in domain D2 can access only one object-File 2, in read-only mode. File 3 is presumably, a shared utility that is maintained by domain D3 and is also executable in domain D1. Object Domain File 1 File 2 File 3 Printer Execute Output Read D1 Write D2 Read Read D3 Write Output Execute Copy Figure 5.2: Access Matrix Although a useful model, access matrices are inefficient for storage of access rights in a computer system because they tend to be large and sparse. The actual forms of representation of access rights, captured and expressed by the access matrix, differ in practice in accordance with the access-control mechanism in use. The common access-control mechanisms are: 104 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Access hierarchies, such as levels of execution privilege and block-structured programming languages. 2. Access lists of all subjects having access rights to a particular object. 3. Capabilities or tickets for objects that specify all access rights of a particular subject. 5.3.3 Access Hierarchies A simple form of access hierarchy is provided by the dual, user/supervisor, mode of operation found in many computer systems. In that model, a restricted range of operations is available in the user mode, which is a default for program execution. The supervisor mode is a superset that, in addition to user-mode instructions, allows execution of instructions that can adversely affect the system's integrity. These include certain I/O functions, halting of the machine, and updating of the address translation tables. The supervisor mode is reserved for the operating system and for trusted programs, usually various system utilities. Thus, user programs execute in the user domain, and the operating system executes in the supervisor domain. Instruction-level domain switching is allowed only in the privileged mode. When a user program needs to perform an operation outside its protection domain, it calls the operating system. At the control-transfer-point, such as the supervisor-call instruction, the operating system can check the user's authority and grant or deny execution accordingly. Some systems extend this mode of operation to multiple levels of protection. For example, some DEC minicomputers have three modes: kernel (most privileged), supervisor and user. The kernel mode is used in some designs to run the security kernel, supervisor for the rest of the operating system, and user mode is for application programs. The protection rings, introduced in Multics, are a generalization of the concept of a supervisor state. Each protection ring defines a domain of access. At any given time, each process runs in a specific protection ring, whose number is specified in the processor-status word as an integer in the range [0, r–1]. The access privileges of ring j are a subset of those for ring i, for all 0 < i < j < r–1. Protection rings are illustrated in Figure 9.6. Inner rings (lower numbers) have higher access rights. Protection barriers, in the form of call gates, are invoked by hardware when a lesser- privileged outer ring needs to call on a service running in an inner, more privileged, ring. 105 CU IDOL SELF LEARNING MATERIAL (SLM)

Intel's 80286 and higher-numbered processors in that family, implement a reduced, four-ring version of the multics ring-protection scheme. decreasing 0 12 r-1 pri vilege Figure 5.3: Protection Rings in Multics The concept of access hierarchy is not unique to hardware. It can also be used in software. For instance, the scope rules of block-structured programming languages, such as Pascal and C, represent a hierarchy of access domains. In that approach, the scope of an identifier encompasses the block x in which it is declared, and all blocks defined in x. As illustrated in Figure 5.4, identifiers declared in block A (outermost, level 0) are accessible in all of A's nested blocks. A statement contained in inner block D (level 2) may legally reference all identifiers declared in D's outer blocks – blocks A and B in the example - but not the identifiers declared in the disjoint block C. However, outer blocks cannot reference identifiers declared in their enclosed, inner-level blocks. For example, statements in block A do not have access to variables declared in blocks B and D, and variables declared in block D cannot be accessed from block B. A B D C 106 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 5.4: Scope in a Block-structured Language In general, access hierarchies violate the design principle of least privilege. They usually grant too many access rights to privileged programs. For example, a process running at ring 0 has full access to the whole system. A bug or a Trojan horse in such a program can easily corrupt the entire system. Moreover, the linearity of the ring-based protection mechanism imposes too strict ordering of objects and access-right classes. This makes it difficult or impossible to represent arbitrary constraints, such as a cyclic graph. 5.3.4 Access Lists Access lists are one way of recording access rights in a computer system. They are frequently used in file systems. In principle, an access list is an exhaustive enumeration of the specific access rights of all entities (domains or subjects) that are authorized access to a given object. In effect, an access list for a specific object is a list that contains all nonempty cells of a column of the access matrix associated with a given object. In systems that employ access lists, a separate list is maintained for each object. Usually, the owner has the exclusive right to define and modify the related access list. The owner of the object can revoke the access rights granted to a particular subject or a domain by simply modifying or deleting the related entry in the access list. Many variations of the access-list scheme are used to store access information in file systems. Typically, the access list or a pointer to it is stored in the file directory. Access lists may be combined with other schemes to strengthen protection. In multics, for example, access lists are combined with a ring-based protection scheme to control access to segments that reside on secondary storage. The primary drawback of access lists is the search overhead, imposed by the need to verify the authority of a subject to access a requested object. According to the principle of complete mediation, every request to access a file should be checked. In order to improve efficiency, some systems check the requestor's authority only when the file is opened. This weakens protection by opening the door for penetration after the file is opened and by making revocations of privilege ineffective as long as the user has the file open-which may be indefinitely in some systems 107 CU IDOL SELF LEARNING MATERIAL (SLM)

5.4 NETWORKING MANAGEMENT COMPONENT Network management is the process of administering and managing computer networks. It includes performance management, fault analysis, provisioning of networks, and maintaining the quality of service. A distributed system is a collection of computers/processors that never share their own memory or a clock. In this type of system, all the processors have their local Memory, and the processors communicate with each other using different communication lines, like fiber optics or telephone lines. The computers in the network are connected through a communication network, which can be configured in a number of different ways. With the help of network management, the network can be fully or partially connected, which helps users to design routing and connection strategies that overcome connection and security issues. Functions of Network management:  Distributed systems help you to various computing resources in size and function. They may involve microprocessors, minicomputers, and many general-purpose computer systems.  A distributed system also offers the user access to the various resources the network shares.  It helps to access shared resources that help computation to speed-up or offers data availability and reliability. Often built on top of file system 1. TCP/IP, IPX, IPng 2. Connection/Routing strategies 3. Circuit management - circuit, message, packet switching 4. Communication mechanism 5. Data/Process migration 108 CU IDOL SELF LEARNING MATERIAL (SLM)

Networking can be defined as when the processor interacts with each other through communication lines. The design of communication-network must consider routing, connection methods, safety, the problems of opinion & security. Presently most of the operating systems maintain different networking techniques, hardware, & applications. This involves that computers that run on different operating systems could be included in a general network to share resources like data, computing, scanners, printers, which uses the connections of either wired otherwise wireless. 5.5 COMMAND INTERPRETER Some operating systems include the command interpreter in the kernel. Others, such as Windows and UNIX, treat the command interpreter as a special program that is running when a job is initiated or when a user first logs on (on interactive systems). On systems with multiple command interpreters to choose from, the interpreters are known as shells. For example, on UNIX and Linux systems, a user may choose among several different shells, including the Bourne shell, C shell, Bourne-Again shell, Korn shell, and others. Third-party shells and free user-written shells are also available. Most shells provide similar functionality, and a user’s choice of which shell to use is generally based on personal preference. Figure 2.2 shows the Bourne shell command interpreter being used on Solaris 10. The main function of the command interpreter is to get and execute the next user-specified command. Many of the commands given at this level manipulate files: create, delete, list, print, copy, execute, and so on. The MS-DOS and UNIX shells operate in this way. These commands can be implemented in two general ways. In one approach, the command interpreter itself contains the code to execute the command. For example, a command to delete a file may cause the command interpreter to jump to a section of its code that sets up the parameters and makes the appropriate system call. In this case, the number of commands that can be given determines the size of the command interpreter, since each command requires its own implementing code. An alternative approach used by UNIX, among other operating systems implements most commands through system programs. In this case, the command interpreter does not understand the command in any way; it merely uses the command to identify a file to be loaded into memory and executed. 109 CU IDOL SELF LEARNING MATERIAL (SLM)

Thus, the UNIX command to delete a file rm file.txt would search for a file called rm, load the file into memory, and execute it with the parameter file.txt. The function associated with the rm command would be defined completely by the code in the file rm. In this way, programmers can add new commands to the system easily by creating new files with the proper names. Figure 5.5: The Bourne shell command interpreter in Solaris 10. 5.6 SUMMARY  A file is a collection of letters, numbers and special characters: it may be a program, a database, a dissertation, a reading list, a simple letter etc. Sometimes you may import a file from elsewhere, for example from another computer. If you want to enter your own text or data, you will start by creating a file. A file system is a method for storing and organizing computer files and the data they contain to make it easy to find and access them.  Disks provide the bulk of secondary storage on which a file system is maintained. To improve I/O efficiency, I/O transfer between memory and disk are performed in units of blocks. Each block is one or more sectors. Depending on the disk drive, sectors vary from 32 bytes to 4096 bytes; usually, they are 512 bytes. The file system provides the mechanism for online storage and access to both data and programs. 110 CU IDOL SELF LEARNING MATERIAL (SLM)

 The file system resides permanently on secondary storage, which has the main requirement that it must be able to hold a large amount of data, permanently. In a multi-user environment, a file is required to be shared among more than one user. There are several techniques and approaches to affect this operation.  The file systems of computers can be extensive. Some systems store thousands of files on hundreds of gigabytes of disk. The direct-access nature of disks allows flexibility in the implementation of files. In almost every case, many files will be stored on the same disk. Security policies specify what is desired in terms of protection and security. Security mechanisms specify how to affect the security policies and enforce them in a given system. 5.7 KEYWORDS  Distributed system: A distributed system is a collection of processors that do not share memory, peripheral devices, or a clock.  Monitors: A monitor is software synchronization tool with high-level of abstraction that provides a convenient and effective mechanism for process synchronization.  Multiprocessor System: It is a computer system that has an array of a number of processors.  Multiprogramming: The rapid switching back and forth of CPU among processes is called multiprogramming.  Batch Processing: A mode of data processing in which a number of tasks are lines up and the entire task set is submitted to the computer in one go 5.8 LEARNING ACTIVITY 1. Explain why Java programs running on Android systems do not use the standard Java API and virtual machine. ___________________________________________________________________________ ____________________________________________________________________ 5.9 UNIT END QUESTIONS A. Descriptive Questions Short Questions 111 CU IDOL SELF LEARNING MATERIAL (SLM)

1. Name different types of access methods used in file operations. 2. How can we protect a file? 3. What are different types of File Systems available? 4. Define Acyclic-graph directories. 5. What is the difference between sequential and direct access? Long Questions 1. Explain the file system architecture and functions. 2. What is file sharing and file allocation? 3. Briefly explain the access matrix model of protection. 4. What does the general graph directory contain? 5. Do you think the file system provides the mechanism for online storage and access to both data and programs? Why or why not? B. Multiple Choice Questions 1. Reliability of files can be increased by: a. keeping the files safely in the memory b. making a different partition for the files c. by keeping them in external storage d. by keeping duplicate copies of the file 2. Protection is only provided at the _____ level. 112 a. lower b. central c. higher d. None of these CU IDOL SELF LEARNING MATERIAL (SLM)

3. The main problem with access control lists is: a. their maintenance b. their length c. their permissions d. All of these 4. Many systems recognize three classifications of users in connection with each file (to condense the access control list): a. Owner b. Group c. Sub-owner d. Universe 5. All users in a group get _______ access to a file. a. different b. similar c. write d. None of these 6. Universe consists of: 113 a. all users that aren’t included in the group or owners b. all users that are not owners c. all users in the system CU IDOL SELF LEARNING MATERIAL (SLM)

d. None of these 7. In UNIX, groups can be created and modified by: a. super user b. any user c. a programmer only d. the people in the group only 8. To control access the three bits used in UNIX are represented by: a. r b. w c. ex d. x 9. If each access to a file is controlled by a password, then the disadvantage is that: a. user will need to remember a lot of passwords b. it is not reliable c. it is not efficient d. All of these 10. In a multilevel directory structure: 114 a. the same previous techniques will be used as in the other structures b. a mechanism for directory protection will have to applied c. the subdirectories do not need protection once the directory is protected CU IDOL SELF LEARNING MATERIAL (SLM)

d. None of these Answers 1 d,2 a, 3 b, 4 a, 5 b, 6 c, 7 a, 8 a, 9 a, 10 b. 5.10 REFERENCES  A. Silberschatz P.B. Galvin, Gange (2002). Operating System Concepts, 6th Ed., Addison Wesley Publishing Co., Boston.  H.M. Deitel (1990). An Introduction to Operating Systems, Addison Wesley Publishing Co., Boston.  D.M. Dhamdhare (2002). Operating System. Tata McGraw Hill, New Delhi.  A.S. Tanenbaum (2000). Operating Systems: Design and Implementation, Prentice Hall of India, New Delhi.  Nutt (2005). Operating Systems, 3rd Edition, Pearson Education, Delhi. 115 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 6: PROCESSES 116 Structure 6.0 Learning Objectives 6.1 Introduction 6.2 Process Management 6.3 Process Concept 6.3.1 Primary Process States 6.3.2 Additional Process States 6.3.3 Process Control Block 6.3.4 Process State Transitions 6.3.5 Thread 6.4 Concurrent Process 6.4.1 Processes Creation 6.4.2 Process Hierarchy: Children and Parent Processes 6.4.3 Process Termination 6.5 Scheduling Concepts 6.5.1 General Goals 6.6 Operation on Process 6.7 Summary 6.8 Keywords 6.9 Learning Activity 6.10 Unit End Questions 6.11 References 6.0 LEARNING OBJECTIVES After studying this unit, you will be able to: CU IDOL SELF LEARNING MATERIAL (SLM)

 Describe process concept  Explain concurrent process  Define scheduling concepts  Perform CPU scheduling  Exercise scheduling algorithms  Define multiple processor scheduling 6.1 INTRODUCTION One definition of a process is that it has an address space and a single thread of execution. Sometimes it would be beneficial if two (or more) processes could share the same address space and run parts of the process in parallel. This is what threads do. Firstly, let us consider why we might need to use threads. Assume we have a server application running. Its purpose is to accept messages and then act upon those messages. Consider the situation where the server receives a message and, in processing that message, it has to issue an I/O request. Whilst waiting for the I/O request to be satisfied it goes to a blocked state. If new messages are received, whilst the process is blocked, they cannot be processed until the process has finished processing the last request. One way we could achieve our objective is to have two processes running. One process deals with incoming messages and another process deals with the requests that are raised. However, this approach gives us two problems:  We still have the problem, in that either of the processes could still become blocked (although there is way around this by issuing child processes) and  The two processes will have to update shared variables. This is far easier if they share the same address space. The answer to these types of problems is to use threads. 6.2 PROCESS MANAGEMENT Process management is an operating system's way of dealing with running multiple processes at once. Since most computers contain one processor with one core, multi-tasking is done by simply switching processes quickly. Depending on the operating system, as more processes 117 CU IDOL SELF LEARNING MATERIAL (SLM)

run, either each time slice will become smaller or there will be a longer delay before each process given a chance to run. Process management involves computing and distributing CPU time as well as other resources. Most operating systems allow a process to be assigned a priority, which affects its allocation of CPU time. Interactive operating systems also employ some level of feedback in which the task with which the user is working receives higher priority. Interrupt driven processes will normally run at a very high priority. In many systems, there is a background process such as the System Idle Process in Windows, which will run when no other process is waiting for the CPU. 6.3 PROCESS CONCEPT The term \"process\" was first used by the designers of the MULTICS in 1960s. Since then, the term \"process\" is used somewhat interchangeably with 'task' or 'job'. The process has been given many definitions for instance 1 A program in Execution. 2 An asynchronous activity. 3 The 'animated sprit' of a procedure in execution. 4 The entity to which processors are assigned. 5 The 'dispatchable' unit. As we can see from above that there is no universally agreed upon definition, but the definition \"Program in Execution\" seem to be most frequently used. And this is a concept are will use in the present study of operating systems. Now that we agreed upon the definition of process, the question is - what is the relation between process and program. It is same beast with different name or when this beast is sleeping (not executing) it is called program and when it is executing becomes process. Well, to be very precise. Process is not the same as program. In the following discussion we point out some of the difference between process and program. As we have mentioned earlier. Process is not the same as program. A process is more than a program code. A process is an 'active' entity as opposed to program which is considered to be a 'passive' entity. As we all know that a program is an algorithm expressed in some suitable notation, (e.g., programming 118 CU IDOL SELF LEARNING MATERIAL (SLM)

language). Being a passive, a program is only a part of process. Process, on the other hand, includes: 1 Current value of Program Counter (PC) 2 Contents of the processor’s registers 3 Value of the variables The process stacks (SP) which typically contains temporary data such as subroutine parameter, return address, and temporary variables. 1 A data section that contains global variables. 2 A process is the unit of work in a system. In process model, all software on the computer is organized into a number of sequential processes. A process includes PC, registers, and variables. Conceptually, each process has its own virtual CPU. In reality, the CPU switches back and forth among processes. (The rapid switching back and forth is called multiprogramming). A process includes, besides instructions to be executed, the temporary data such as subroutine parameters, return addresses and variables (stored on the stack), data section having global variables (if any), program counter value, register values and other associated resources. Although two processes may be associated with the same program, yet they are treated as two separate processes having their respective set of resources. Code Data Resources Process Status Abstract Machine Environment (OS) Figure 6.1: A Schematic Representation of a Process 6.3.1 Primary Process States The following typical process states are possible on computer systems of all kinds. In most of these states, processes are \"stored\" on main memory: 119 CU IDOL SELF LEARNING MATERIAL (SLM)

Created: It is also called new. When a process is first created, it occupies the \"created\" or \"new\" state. In this state, the process awaits admission to the \"ready\" state. This admission will be approved or delayed by a long-term, or admission, scheduler. Ready: It is also called waiting or runnable. A \"ready\" or \"waiting\" process has been loaded into main memory and is awaiting execution on a CPU (to be context switched onto the CPU by the dispatcher, or short-term scheduler). Running: It is also called active or executing. A \"running\", \"executing\" or \"active\" process is a process which is currently executing on a CPU. From this state the process may exceed its allocated time slice and be context switched out and back to \"ready\" by the operating system, it may indicate that it has finished and be terminated or it may block on some needed resource (such as an input / output resource) and be moved to a \"blocked\" state. Blocked: It is also called sleeping. Should a process \"block\" on a resource (such as a file, a semaphore or a device), it will be removed from the CPU (as a blocked process cannot continue execution) and will be in the blocked state. The process will remain \"blocked\" until its resource becomes available, which can unfortunately lead to deadlock. Terminated: A process may be terminated, either from the \"running\" state by completing its execution or by explicitly being killed. In either of these cases, the process moves to the \"terminated\" state. If a process is not removed from memory after entering this state, this state may also be called zombie. 6.3.2 Additional Process States Two additional states are available for processes in systems that support virtual memory. In both of these states, processes are \"stored\" on secondary memory (typically a hard disk). Swapped out and waiting: It is also called suspended and waiting. In systems that support virtual memory, a process may be swapped out, that is removed from main memory and placed in virtual memory by the mid-term scheduler. From here the process may be swapped back into the waiting state. Swapped out and blocked: It is also called suspended and blocked. Processes that are blocked may also be swapped out. In this event the process is both swapped out and blocked, and may be swapped back in again under the same circumstances as a swapped out and waiting process (although in this case, the process will move to the blocked state, and may still be waiting for a resource to become available). 120 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 6.2: A Process Life Cycle 6.3.3 Process control block A process control block or PCB is a data structure (a table) that holds information about a process. Every process or program that runs needs a PCB. When a user requests to run a particular program, the operating system constructs a process control block for that program. Typical information that is stored in a process control block is: 1. The location the process in memory 2. The priority of the process 3. A unique process identification number (called PID) 4. The current process state (ready, running, blocked) 5. Associated data for the process. The PCB is a certain store that allows the operating systems to locate key information about a process. Thus, the PCB is the data structure that defines a process to the operating systems. Process state Process number Parent process number Program counter Register Memory limits 121 CU IDOL SELF LEARNING MATERIAL (SLM)

List of open files Figure 6.3: Process Control Block or PCB 6.3.4 Process State Transitions Blocking: It occurs when process discovers that it cannot continue. If running process initiates an I/O operation before its allotted time expires, the running process voluntarily relinquishes the CPU. Time-Run-Out: It occurs when the scheduler decides that the running process has run long enough and it is time to let another process have CPU time. Dispatch: It occurs when all other processes have had their share and it is time for the first process to run again. Wakeup: It occurs when the external event for which a process was waiting (such as arrival of input) hTaeprmpiennaste.d. Admitted: It occurs when the process is created. Exit: It occurs when the process has finished execution. Fig Figure 6.4: (a): Process State Transitions 122 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 6.4: (b): Process State Transitions 6.3.5 Thread Threads are a way for a program to fork (or split) itself into two or more simultaneously (or pseudo-simultaneously) running tasks. A thread is a single sequence stream within a process. Because threads have some of the properties of processes, they are sometimes called lightweight processes. In a process, threads allow multiple executions of streams. In many respects, threads are popular way to improve application through parallelism. The CPU switches rapidly back and forth among the threads giving illusion that the threads are running in parallel. Processes vs Threads As we mentioned earlier that in many respect threads operate in the same way as that of processes. Some of the similarities and differences are: Similarities: 1. Like processes threads share CPU and only one thread active (running) at a time. 2. Like processes, threads within processes, threads within processes execute sequentially. 3. Like processes, thread can create children. 4. And like process, if one thread is blocked, another thread can run. 123 CU IDOL SELF LEARNING MATERIAL (SLM)

Differences: 1. Unlike processes, threads are not independent of one another. 2. Unlike processes, all threads can access every address in the task. 3. Processes might or might not assist one another because processes may originate from different users, but threads are design to assist one other. Benefits of Threads 4. Following are some reasons why threads are used in designing operating systems: 5. A process with multiple threads makes a great server for example printer server. 6. Because threads can share common data, they do not need to use interprocess communication. 7. Because of the very nature, threads can take advantage of multiprocessors. Figure 6.5: A Process with Two Threads of Execution 6.4 CONCURRENT PROCESS In a multi-programming environment, more than one process exists in the system competing for the resources. Based on criteria and algorithms employed by the system, one of them is selected at a time, is granted requisite resources and is executed while other candidate processes wait for their turn. The processes can execute in two different modes – sequential and concurrent. In sequential mode of execution, processes do not interfere with each other. A process, in this mode is executed only when the currently executing process has finished its execution. While a 124 CU IDOL SELF LEARNING MATERIAL (SLM)

process is executing, it is allocated all the available resources and therefore there is no resource contention between the processes. Process-1 Execution CPU Instruction-1.1 Instruction-1.1 Instruction-1.2 Instruction-1.1 Instruction-1.3 Instruction-1.2 Instruction-1.4 Instruction-1.3 Instruction-1.5 Instruction-1.2 Instruction-1.6 Instruction-1.4 Process-2 Instruction-2.1 Instruction-2.1 Instruction-2.2 Instruction-2.2 Instruction-2.3 Instruction-2.3 Instruction-2.3 Instruction-2.4 Figure 6.6: Sequential Mode of Execution Process-1 Execution Instruction-1.1 Instruction-1.1 CPU Instruction-1.2 Instruction-2.1 Instruction-1.3 Instruction-1.2 Instruction-1.4 Instruction-2.2 Instruction-1.5 Instruction-1.3 Instruction-1.6 Instruction-1.4 Instruction-2.3 Process-2 Instruction-1.5 Instruction-1.6 Instruction-2.1 Instruction-2.4 Instruction-2.2 Instruction-2.3 Instruction-2.4 Figure 6.7: Concurrent Mode of Execution If concurrency is not controlled adequately, it may turn into a condition in which no process makes any headway. Such a condition is called deadlock. The situation is very different in case of concurrent mode of execution. In this case, each of the processes, try to acquire required resources and therefore, a lot of control is required on the part of the operating system to ensure a smooth operation. The processes in the system can execute concurrently, and they must be created and deleted dynamically. Thus, the operating system must provide a mechanism (or facility) for process creation and termination. 125 CU IDOL SELF LEARNING MATERIAL (SLM)

6.4.1 Processes Creation The creation of a process requires the following steps. The order in which they are carried out is not necessarily the same in all cases. 1. Name: The name of the program which is to run as the new process must be known. 2. Process ID and Process Control Block: The system creates a new process control block, or locates an unused block in an array. This block is used to follow the execution of the program through its course, keeping track of its resources and priority. Each process control block is labelled by its PID or process identifier. 3. Locate the program to be executed on disk and allocate memory for the code segment in RAM. 4. Load the program into the code segment and initialize the registers of the PCB with the start address of the program and appropriate starting values for resources. 5. Priority: A priority must be computed for the process, using a default for the type of process and any value which the user specified as a ‘nice’ value. 6. Schedule the process for execution. 6.4.2 Process Hierarchy: Children and Parent Processes In a democratic system anyone can choose to start a new process, but it is never users which create processes but other processes! That is because anyone using the system must already be running a shell or command interpreter in order to be able to talk to the system, and the command interpreter is itself a process. When a user creates a process using the command interpreter, the new process becomes a child of the command interpreter. Similarly, the command interpreter process becomes the parent for the child. Processes therefore form a hierarchy. 126 CU IDOL SELF LEARNING MATERIAL (SLM)

d Root Node Level 0 Child # 1 Child # 2 Child # 3 Level 1 Level 2 d Figure 6.8: Process Hierarchies The processes are linked by a tree structure. If a parent is signalled or killed, usually all its children receive the same signal or are destroyed with the parent. This doesn't have to be the case–it is possible to detach children from their parents–but in many cases it is useful for processes to be linked in this way. When a child is created it may do one of two things. 1. Duplicate the parent process. 2. Load a completely new program. Similarly, the parent may do one of two things: 1. Continue executing alongside its children. 2. Wait for some or all of its children to finish before proceeding. The specific attributes of the child process that differ from the parent process are: 1. The child process has its own unique process ID. 2. The parent process ID of the child process is the process ID of its parent process. The child process gets its own copies of the parent process's open file descriptors. Subsequently changing attributes of the file descriptors in the parent process won't affect the file descriptors in the child, and vice versa. However, the file position associated with each descriptor is shared by both processes. 1. The elapsed processor times for the child process are set to zero. 2. The child doesn't inherit file locks set by the parent process. 3. The child doesn't inherit alarms set by the parent process. 127 CU IDOL SELF LEARNING MATERIAL (SLM)

The set of pending signals for the child process is cleared. (The child process inherits its mask of blocked signals and signal actions from the parent process.) 6.4.3 Process Termination Processes terminate in one of two ways: 1. Normal Termination occurs by a return from main or when requested by an explicit call to exit. 2. Abnormal Termination occurs as the default action of a signal or when requested by abort. On receiving a signal, a process looks for a signal-handling function. Failure to find a signal- handling function forces the process to call exit, and therefore to terminate. A parent may terminate the execution of one of its children for a variety of reasons, such as these: 1. The child has exceeded its usage of some of the resources that it has been allocated. This requires the parent to have a mechanism to inspect the state of its children. 2. The task assigned to the child is no longer required. The parent is exiting, and the operating system does not allow a child to continue if its parent terminates. On such systems, if a process terminates (either normally or abnormally), then all its children must also be terminated. This phenomenon, referred to as cascading termination, is normally initiated by the operating system 6.5 SCHEDULING CONCEPTS The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization. The objective of time sharing is to switch the CPU among processes so frequently that users can interact with each program while it is running. To meet these objectives, the process scheduler selects an available process (possibly from a set of several available processes) for program execution on the CPU. For a single-processor system, there will never be more than one running process. If there are more processes, the rest will have to wait until the CPU is free and can be rescheduled. 128 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 6.9: The ready queue and various I/O device queues. Scheduling Queues  All processes, upon entering into the system, are stored in the Job Queue.  Processes in the Ready state are placed in the Ready Queue.  Processes waiting for a device to become available are placed in Device Queues. There are unique device queues available for each I/O device. A new process is initially put in the Ready queue. It waits in the ready queue until it is selected for execution (or dispatched). Once the process is assigned to the CPU and is executing, one of the following several events can occur:  The process could issue an I/O request, and then be placed in the I/O queue.  The process could create a new sub process and wait for its termination.  The process could be removed forcibly from the CPU, as a result of an interrupt, and be put back in the ready queue. 129 CU IDOL SELF LEARNING MATERIAL (SLM)

In the first two cases, the process eventually switches from the waiting state to the ready state, and is then put back in the ready queue. A process continues this cycle until it terminates, at which time it is removed from all queues and has its PCB and resources deallocated. Figure 6.10: Queueing-diagram representation of process scheduling. Types of Schedulers There are three types of schedulers available: 1. Long Term Scheduler 2. Short Term Scheduler 3. Medium Term Scheduler Many objectives must be considered in the design of a scheduling discipline. In particular, a scheduler should consider fairness, efficiency, response time, turnaround time, throughput, etc. Some of these goals depend on the system one is using for example batch system, interactive system or real-time system, etc. but there are also some goals that are desirable in all systems. 6.5.1 General Goals Fairness 130 CU IDOL SELF LEARNING MATERIAL (SLM)

Fairness is important under all circumstances. A scheduler makes sure that each process gets its fair share of the CPU and no process can suffer indefinite postponement. Note that giving equivalent or equal time is not fair. Think of safety control and payroll at a nuclear plant. Policy Enforcement The scheduler has to make sure that system's policy is enforced. For example, if the local policy is safety than the safety control processes must be able to run whenever they want to, even if it means delay in payroll processes. Efficiency Scheduler should keep the system (or in particular CPU) busy cent percent of the time when possible. If the CPU and all the Input/Output devices can be kept running all the time, more work gets done per second than if some components are idle. Response Time A scheduler should minimize the response time for interactive user. Turnaround A scheduler should minimize the time for which users must wait for an output. Throughput A scheduler should maximize the number of jobs processed per unit time. A little thought will show that some of these goals are contradictory. It can be shown that any scheduling algorithm that favours some class of jobs hurts another class of jobs. The amount of CPU time available is finite, after all. Different methods of scheduling are appropriate for different kinds of execution. A queue is one form of scheduling in which each program waits its turn and is executed serially. This is not very useful for handling multitasking, but it is necessary for scheduling devices which cannot be shared by nature. An example of the latter is the printer. Each print job has to be completed before the next one can begin; otherwise, all the print jobs would be mixed up and interleaved resulting in nonsense. We shall make a broad distinction between two types of scheduling, one is non-preemptive scheduling and another is preemptive scheduling. 131 CU IDOL SELF LEARNING MATERIAL (SLM)

The Scheduling algorithms can be divided into two categories with respect to how they deal with clock interrupts. 6.6 OPERATION ON PROCESS Operations on Processes A process is an activity of executing a program. Basically, it is a program under execution. Every process needs certain resources to complete its task. Figure 6.11: Resources for Process Operation on a Process: The execution of a process is a complex activity. It involves various operations. Following are the operations that are performed while execution of a process: 132 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 6.12: Process States 1. Creation: This initial step of process execution activity. Process creation means the construction of a new process for the execution. This might be performed by system, user or old process itself. There are several events that lead to the process creation. Some of such events are following:  When we start the computer, system creates several background processes.  A user may request to create a new process.  A process can create a new process itself while executing.  Batch system takes initiation of a batch job. 2. Scheduling/Dispatching: The event or activity in which the state of the process is changed from ready to running. It means the operating system puts the process from ready state into the running state. Dispatching is done by operating system when the resources are free or the process has higher priority than the ongoing process. There are various other cases in which the process in running state is pre-empted and process in ready state is dispatched by the operating system. 3. Blocking: When a process invokes an input-output system call that blocks the process and operating system put in block mode. Block mode is basically a mode where process waits for input-output. Hence on the demand of process itself, operating system blocks the process and dispatches another process to the processor. Hence, in process blocking operation, the operating system puts the process in ‘waiting’ state. 133 CU IDOL SELF LEARNING MATERIAL (SLM)

4. Pre-emption: When a timeout occurs that means the process hadn’t been terminated in the allotted time interval and next process is ready to execute, then the operating system pre- empts the process. This operation is only valid where CPU scheduling supports pre-emption. Basically, this happens in priority scheduling where on the incoming of high priority process the ongoing process is pre-empted. Hence, in process pre-emption operation, the operating system puts the process in ‘ready’ state. 5. Termination: Process termination is the activity of ending the process. In other words, process termination is the relaxation of computer resources taken by the process for the execution. Like creation, in termination also there may be several events that may lead to the process termination. Some of them are:  Process completes its execution fully and it indicates to the OS that it has finished.  Operating system itself terminates the process due to service errors.  There may be problem in hardware that terminates the process.  One process can be terminated by another process. 6.7 SUMMARY  Process management is an operating system's way of dealing with running multiple processes at once. A multitasking operating system may just switch between processes to give the appearance of many processes executing concurrently or simultaneously, though in fact only one process can be executing at any one time on a single-core CPU (unless using multi-threading or other similar technology). Processes are often called tasks in embedded operating systems.  Process is the entity to which processors are assigned. The rapid switching back and forth of CPU among processes is called multiprogramming.  CPU scheduling is the basics of multiprogramming. In both situations, a system with a single CPU or a multi-processor system with fewer CPU's than processes have to divide CPU time among the different processes/threads that are competing to use it. This process is called CPU scheduling. There are many scheduling algorithms and various criteria to judge their performance.  Process is a unit of program execution that enables the systems to implement multi- tasking behaviour. An operating system provides an environment, which presents each hardware resource in its abstract form. 134 CU IDOL SELF LEARNING MATERIAL (SLM)

 In the direct-communication discipline, each process that wants to communicate must explicitly name the recipient or sender of the communication. Multitasking and multiprogramming, the two techniques that intend to use the computing resources optimally. A thread is a basic unit of resource utilization, and consists of a program counter, a register set, and a stack. 6.8 KEYWORDS  Thread: A thread is a single sequence stream within in a process.  Process Control Block (PCB): It is a data structure (a table) that holds information about a process.  Process Management: It is an operating system's way of dealing with running multiple processes at once.  Process: It is the entity to which processors are assigned.  Access Hierarchy: A simple form of access hierarchy is provided by the dual, user/supervisor, mode of operation found in many computer systems.  Access Lists: Access lists are one way of recording access rights in a computer system. 6.9 LEARNING ACTIVITY 1. Explain why Java programs running on Android systems do not use the standard Java API and virtual machine. ___________________________________________________________________________ ____________________________________________________________________ 6.10 UNIT END QUESTIONS A. Descriptive Questions Short Questions 1. What resources are used when a thread created? How do they differ from those when a process is created? 2. What are the different process states? What is the state of the processor, when a process is waiting for some event to occur? 3. Write a brief description on process state transition. 135 CU IDOL SELF LEARNING MATERIAL (SLM)

4. What is PCB? What is the function of PCB? 5. Explain context switching. Long Questions 1. Explain the process with its state diagram. 2. Do you think a process migrates between the various scheduling queues throughout its lifetime? 3. What is the difference between response time and waiting time? 4. Describe how processes help achieve multiprogramming. 5. Explain various operations on a process. B. Multiple Choice Questions 1. Which module gives control of the CPU to the process selected by the short-term scheduler? a. dispatcher b. interrupt c. scheduler d. None of these 2. The processes that are residing in main memory and are ready and waiting to execute are kept on a list called a. job queue b. ready queue c. execution queue d. process queue 136 CU IDOL SELF LEARNING MATERIAL (SLM)

3. The interval from the time of submission of a process to the time of completion is termed as a. waiting time b. turnaround time c. response time d. throughput 4. Which scheduling algorithm allocates the CPU first to the process that requests the CPU first? a. first-come, first-served scheduling b. shortest job scheduling c. priority scheduling d. None of these 5. In priority scheduling algorithm a. CPU is allocated to the process with highest priority b. CPU is allocated to the process with lowest priority c. equal priority processes cannot be scheduled d. None of these 6. In priority scheduling algorithm, when a process arrives at the ready queue, its priority is compared with the priority of a. all process b. currently running process c. parent process 137 CU IDOL SELF LEARNING MATERIAL (SLM)

d. in it process 138 7. Time quantum is defined in a. shortest job scheduling algorithm b. round robin scheduling algorithm c. priority scheduling algorithm d. multilevel queue scheduling algorithm 8. Process is classified into different groups in a. shortest job scheduling algorithm b. round robin scheduling algorithm c. priority scheduling algorithm d. multilevel queue scheduling algorithm 9. In multilevel feedback scheduling algorithm a. a process can move to a different classified ready queue b. classification of ready queue is permanent c. processes are not classified into groups d. None of these 10. Which one of the following cannot be scheduled by the kernel? a. kernel level thread b. user level thread c. process CU IDOL SELF LEARNING MATERIAL (SLM)

d. None of these Answers 1 a, 2 b, 3 b, 4 a, 5 a, 6 b, 7 b, 8 b, 9 a, 10 b 6.11 REFERENCES  A. Silberschatz P.B. Galvin, Gange (2002). Operating System Concepts, 6th Ed., Addison Wesley Publishing Co., Boston.  H.M. Deitel (1990). An Introduction to Operating Systems, Addison Wesley Publishing Co., Boston.  D.M. Dhamdhare (2002). Operating System. Tata McGraw Hill, New Delhi.  A.S. Tanenbaum (2000). Operating Systems: Design and Implementation, Prentice Hall of India, New Delhi.  Nutt (2005). Operating Systems, 3rd Edition, Pearson Education, Delhi. 139 CU IDOL SELF LEARNING MATERIAL (SLM)

UNIT - 7: CPU SCHEDULING 140 Structure 7.0 Learning Objectives 7.1 Introduction 7.2 CPU Scheduling 7.2.1 Context Switch 7.2.2 Scheduling Criteria 7.3 Scheduling Algorithm 7.3.1 Non-preemptive Scheduling 7.3.2 Preemptive Scheduling 7.3.3 Multi-level Feedback Queues (MLF) 7.4 Multiple Processor Scheduling 7.5 Summary 7.6 Keywords 7.7 Learning Activity 7.8 Unit End Questions 7.9 References 7.0 LEARNING OBJECTIVES After studying this unit, you will be able to:  Explain scheduling concepts  Define scheduling criteria  Perform CPU scheduling  Exercise scheduling algorithms  Define multiple processor scheduling CU IDOL SELF LEARNING MATERIAL (SLM)

7.1 INTRODUCTION The process scheduling is the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process on the basis of a particular strategy. Process scheduling is an essential part of Multiprogramming operating systems. Such operating systems allow more than one process to be loaded into the executable memory at a time and the loaded process shares the CPU using time multiplexing. Process Scheduling Queues The OS maintains all PCBs in Process Scheduling Queues. The OS maintains a separate queue for each of the process states and PCBs of all processes in the same execution state are placed in the same queue. When the state of a process is changed, its PCB is unlinked from its current queue and moved to its new state queue. The Operating System maintains the following important process scheduling queues −  Job queue − this queue keeps all the processes in the system.  Ready queue − this queue keeps a set of all processes residing in main memory, ready and waiting to execute. A new process is always put in this queue.  Device queues − the processes which are blocked due to unavailability of an I/O device constitute this queue. Two-State Process Model S.No. State & Description 1 Running When a new process is created, it enters into the system as in the running state. 2 Not Running Processes that are not running are kept in queue, waiting for their turn to execute. Each entry in the queue is a pointer to a particular process. Queue is implemented by using linked list. Use of dispatcher is as follows. When a process is interrupted, that 141 CU IDOL SELF LEARNING MATERIAL (SLM)

process is transferred in the waiting queue. If the process has completed or aborted, the process is discarded. In either case, the dispatcher then selects a process from the queue to execute. Schedulers Schedulers are special system software which handles process scheduling in various ways. Their main task is to select the jobs to be submitted into the system and to decide which process to run. Schedulers are of three types −  Long-Term Scheduler  Short-Term Scheduler  Medium-Term Scheduler Comparison among Scheduler S.N. Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler 1 It is a job scheduler It is a CPU scheduler It is a process swapping scheduler. 2 Speed is lesser than short Speed is fastest among Speed is in between both term scheduler other two short- and long-term scheduler. 3 It controls the degree of It provides lesser control It reduces the degree of multiprogramming over degree of multiprogramming. multiprogramming 4 It is almost absent or It is also minimal in time It is a part of Time-sharing minimal in time sharing system sharing system systems. 5 It selects processes from It selects those processes It can re-introduce the 142 CU IDOL SELF LEARNING MATERIAL (SLM)

pool and loads them into which are ready to process into memory and memory for execution execute execution can be continued. 7.2 CPU SCHEDULING CPU scheduling is the basics of multiprogramming. By switching the CPU among several processes, the operating systems can make the computer more productive. The objective of multiprogramming is to have some process running at all times, in order to maximize CPU utilization. On systems with 1 processor, only one process may run at a time; any other processes must wait until CPU is free to be rescheduled. In multiprogramming, a process executes until it must wait (either interrupted, or doing IO), at which point, the CPU is assigned to another process, which again, executes until it must wait, at which point another process gets the CPU, and so on. Processes generally execute a CPU burst, followed by an IO burst, followed by the CPU burst, etc. This cycle is central to all processes. Every process must have CPU bursts, and every process must do some IO. The operating system maintains what is known as a ready- queue. Processes on this queue are ready to be executed. Whenever a currently executing process needs to wait, the operating system picks a process from the ready queue and assigns the CPU to that process. The cycle then continues. There are many scheduling algorithms, ranging in complexity and robustness: First-Come, First-Serve scheduling; Shortest Job First scheduling; Round-Robin scheduling; etc. The objective of time-sharing system is to switch the CPU among processes so frequently that users can interact with each program while it is running. For a uniprocessor system, there will never be more than one running process. If there are more processes, the rest will have to wait until the CPU is free and can be rescheduled. As processes enter the system, they are put into a job queue. This queue consists of all processes in the system. The processes that are residing in main memory and are ready and waiting to execute are kept on a list called the ready queue. This queue is generally stored as a linked list. A ready-queue header will contain pointers to the first and last PCBs in the list. Each PCB has a pointer field that points to the next process in the ready queue. There are also other queues in the system. When a process is allocated the CPU, it executes for a while and eventually quits, is interrupted, or waits for the occurrence of a particular 143 CU IDOL SELF LEARNING MATERIAL (SLM)

event, such as the completion of an I/O request. In the case of an I/O request, such a request may be to a dedicated tape drive, or to a shared device, such as a disk. Since there are many processes in the system, the disk may be busy with the I/O request of some other process. The process therefore may have to wait for the disk. The list of processes waiting for a particular I/O device is called a device queue. Each device has its own device queue. Figure 7.1 (a): CPU Scheduling A common representation for a discussion of process scheduling is a queuing diagram, such as that in the Figure 3.9. Each rectangular box represents a queue. Three types of queues are present: the waiting queue ready queue and a set of device queues. The circles represent the resources that serve the queues, and the arrows indicate the flow of processes in the system. new Preempted exit terminated Interrupt Admitted CPU Resources R1 Ready Queue running Scheduler R2 dispatch Device Queues Device 1 I/O event completion Device 2 waiting Device n I/O or event Rn Figure 7.1(b): State Conversion of a Process 144 CU IDOL SELF LEARNING MATERIAL (SLM)

Figure 7.2 (a): Process Scheduling with Queues and (b) The ready queue and various I/O device queues Scheduling Queues: As processes enter the system, they are put into a job queue, which consists of all processes in the system. The processes that are residing in main memory and are ready and waiting to execute are kept on a list called the ready queue. This queue is generally stored as a linked list. A ready-queue header contains pointers to the first and final PCBs in the list. Each PCB includes a pointer field that points to the next PCB in the ready queue. The system also includes other queues. When a process is allocated the CPU, it executes for a while and eventually quits, is interrupted, or waits for the occurrence of a particular event, such as the completion of an I/O request. Suppose the process makes an I/O request to a shared device, such as a disk. Since there are many processes in the system, the disk may be busy with the I/O request of some other process. The process therefore may have to wait for the disk. The list of processes waiting for a particular I/O device is called a device queue. Each device has its own device queue (Figure 3.10(a) and 3.10(b)) A common representation for a discussion of process scheduling is a queueing diagram, such as that in Figure 3.7. Each rectangular box represents a queue. Two types of queues are present: the ready queue and a set of device queues. The circles represent the resources that serve the queues, and the arrows indicate the flow of processes in the system. 145 CU IDOL SELF LEARNING MATERIAL (SLM)

A new process is initially put in the ready queue. It waits there tmtil it is selected for execution, or is dispatched. Once the process is allocated the CPU and is executing, one of several events could occur: 1. The process could issue an I/O request and then be placed in an I/O queue. 2. The process could create a new sub process and wait for the sub process’s termination. 3. The process could be removed forcibly from the CPU, as a result of an interrupt, and be put back in the ready queue. In the first two cases, the process eventually switches from the waiting state to the ready state and is then put back in the ready queue. A process continues this cycle until it terminates, at which time it is removed from all queues and has its PCB and resources deallocated. 7.2.1 Context Switch Switching the CPU to another process requires saving the state of the old process and loading the saved state for the new process. This task is known as a context switch. Context-switch time is pure overhead, because the system does no useful work while switching. Its speed varies from machine to machine, depending on the memory-speed, the number of registers that must be copied, and the existence of special instructions (such as a single instruction to load or store all registers). Typically, the speed ranges from 1 to 1,000 microseconds. Context-switch times are highly dependent on hardware support. For instance, some provide multiple sets of registers. A context switch simply includes changing the pointer to the current register set. Of course, if there are more active processes than there are register sets, the system resorts to copying register data to and from memory, as before. Also, the more complex the operating system, the more work must be done during a context switch. Advanced memory-management techniques may require extra data to be switched with each context. For instance, the address space of the current process must be preserved as the space of the next task is prepared for use. How the address space is preserved, and the amount of work needed to do it, depend on the memory-management method of the operating system. Context switching has become such a performance bottleneck that new structures (threads) are being used to avoid it whenever possible. 146 CU IDOL SELF LEARNING MATERIAL (SLM)

In order that resources are utilized optimally and systematically, the resources must be allocated and deallocated according to algorithms. 7.2.2 Scheduling Criteria There are many scheduling algorithms and various criteria to judge their performance. Different algorithms may favour different types of processes. Some criteria are as follows: 1. CPU utilization: CPU must be as busy as possible in performing different tasks. CPU utilization is more important in real-time system and multi-programmed systems. 2. Throughput: The number of processes executed in a specified time period is called throughput. The throughput increases for short processes. It decreases if the size of processes is huge. 3. Turnaround Time: The amount of time that is needed to execute a process is called turnaround time. It is the actual job time plus the waiting time. 4. Waiting Time: The amount of time the process has waited is called waiting time. It is the turnaround time minus actual job time. 5. Response Time: The amount of time between a request is Submitted and the first response is produced is called response time 7.3 SCHEDULING ALGORITHM Different methods of scheduling are appropriate for different kinds of execution. A queue is one form of scheduling in which each program waits its turn and is executed serially. This is not very useful for handling multitasking, but it is necessary for scheduling devices which cannot be shared by nature. An example of the latter is the printer. Each print job has to be completed before the next one can begin; otherwise, all the print jobs would be mixed up and interleaved resulting in nonsense. We shall make a broad distinction between two types of scheduling; one is non-pre-emptive scheduling and another is pre-emptive scheduling. The Scheduling algorithms can be divided into two categories with respect to how they deal with clock interrupts. 147 CU IDOL SELF LEARNING MATERIAL (SLM)

7.3.1 Non-preemptive Scheduling A scheduling discipline is non-preemptive if, once a process has been given the CPU; the CPU cannot be taken away from that process. Following are some characteristics of non-preemptive scheduling: 6. In non-preemptive system, short jobs are made to wait by longer jobs but the overall treatment of all processes is fair. In non-preemptive system, response times are more predictable because incoming high priority jobs cannot displace waiting jobs. In non-preemptive scheduling, a scheduler executes jobs in the following two situations: When a process switches from running state to the waiting state. When a process terminates. 7.3.2 Pre-emptive Scheduling A scheduling discipline is preemptive if, once a process has been given the CPU can take away. The strategy of allowing processes that are logically runnable to be temporarily suspended is called Preemptive Scheduling and it is contrast to the “run to completion” method. First-Come-First-Served Scheduling (FCFS) A FCFS queue is a list of available processes awaiting execution by the processor. New processes arrive and are placed at the end of the queue. The process at the start of the queue is assigned the processor when it next becomes available and all other processes move up one slot in the queue. Other names of this algorithm are First-In-First-Out (FIFO), Run-to-Completion, Run-Until- Done. First-Come-First-Served algorithm is the simplest scheduling algorithm. Processes are dispatched according to their arrival time on the ready queue. Being a non-preemptive discipline, once a process has a CPU, it runs to completion. The FCFS scheduling is fair in the formal sense or human sense of fairness but it is unfair in the sense that long jobs make short jobs wait and unimportant jobs make important jobs wait. FCFS is more predictable than most of other schemes since it offers time. FCFS scheme is not useful in scheduling interactive users because it cannot guarantee good response time. 148 CU IDOL SELF LEARNING MATERIAL (SLM)

The code for FCFS scheduling is simple to write and understand. One of the major drawbacks of this scheme is that the average time is often quite long. The First-Come-First-Served algorithm is rarely used as a master scheme in modern operating systems but it is often embedded within other schemes. The CPU, in this scheme, is scheduled to the processes in the order of arrival at the ready queue. This scheme can be easily implemented using a queue data structure. The processes are queued up by enqueuer (software component of operating system), in the order of their arrival at the tail of the queue. Whenever, the CPU is available, the dispatcher (software component of operating system), removes a process from the head of the queue and schedules it to the CPU. Although simple, the scheme is often characterized by relatively longer wait time. Let us consider an example of the following processes with their respective CPU time requests. Assume P1 to be at the head of the queue: Process: P1 P2 P3 P4 Burst time (CPU time): 6 8 7 3 Turnaround time is the time taken by a process between it getting into the ready queue and finishing execution. Wait time is the time a process must wait before it starts executing. The following Gantt chart depicts the schedule under this scheme: P1 P2 P3 P4 6 14 21 24 Turnaround time for process P1 = 6 Turnaround time for process P2 = 6 + 8 = 14 Turnaround time for process P3 = 14 + 7 = 21 Turnaround time for process P4 = 21 + 3 = 24 Average turnaround time = (6 + 14 + 21 + 24)/4 = 16.25 milliseconds. Wait time for process P1 = 0 Wait time for process P2 = 0 + 6 = 6 Wait time for process P3 = 6 + 8 = 14 149 CU IDOL SELF LEARNING MATERIAL (SLM)

Wait time for process P4 = 14 + 7 = 21 Average wait time = (0 + 6 + 14 + 21)/4 = 10.25 milliseconds. Shortest-Job-First Scheduling (SJF) Another name of this algorithm is Shortest-Process-Next (SPN). Like FCFS, SJF is non- preemptive therefore; it is not useful in timesharing environment in which reasonable response time must be guaranteed. Shortest-Job-First (SJF) is a non-preemptive discipline in which waiting job (or process) with the smallest estimated run-time-to-completion is run next. In other words, when CPU is available, it is assigned to the process that has smallest next CPU burst. The SJF scheduling is especially appropriate for batch jobs for which the run times are known in advance. Since the SJF scheduling algorithm gives the minimum average time for a given set of processes, it is probably optimal. The SJF algorithm favours short jobs (or processors) at the expense of longer ones. The obvious problem with SJF scheme is that it requires precise knowledge of how long a job or process will run, and this information is not usually available. The best SJF algorithm can do is to rely on user estimates of run times. Shortest job next is advantageous because of its simplicity and because it maximizes process throughput (in terms of the number of processes run to completion in a given amount of time). However, it has the potential for process starvation for processes which will require a long time to complete if short processes are continually added. Highest response ratio next is similar but provides a solution to this problem. Shortest job next scheduling is rarely used outside of specialized environments because it requires accurate estimations of the runtime of all processes that are waiting to execute. The basic idea is straightforward: each process is assigned a priority, and priority is allowed to run. Equal-Priority processes are scheduled in FCFS order. The shortest-Job-First (SJF) algorithm is a special case of general priority scheduling algorithm. An SJF algorithm is simply a priority algorithm where the priority is the inverse of the (predicted) next CPU burst. That is, the longer the CPU burst, the lower the priority and vice versa. This algorithm associates with each process the length of the number of CPU bursts needed by it for its execution. The process having the smallest next CPU burst is allocated the 150 CU IDOL SELF LEARNING MATERIAL (SLM)