OS Notes - B.Sc CISIT 3rd Sem - Aberdeen Int’l College

OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Chapter 1 Operating System Concepts What is an Operating System? If we just build a computer, using its basic physic...

OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Chapter 1 Operating System Concepts What is an Operating System? If we just build a computer, using its basic physical components, then we end up with a lot of assembled metal, plastic and silicon. In this state the computer is useless. To turn it into one of the most useful tools we need software. We need applications that allow us to write letters, write software, perform numerical modeling, calculate cash flow forecasts etc etc. But, if all we have are just the applications, then each programmer has to deal with the complexities of the hardware. If a program requires data from a disc, the programmer would need to know how every type of disc worked and then be able to program at a low level in order to extract the data. In addition, the programmer would have to deal with all the error conditions that could arise. For example, it is a lot easier for a programmer to say READ NEXT RECORD than have to worry about: spinning the motor up, moving the read/write heads, waiting for the correct sector to come around and then reading the data. It was clear, from an early stage in the development of computers, that there needed to be a “layer of software” that sat between the hardware and the software, to hide the user from such complexities, and to hide the ‘breakable’ parts of the computer from human error or stupidity. Thus we can define operating system as “It is the system software that acts as a interface between computer hardware and users and provides easy interface to the users by hiding underlying complexities of computer hardware “ Two views of an operating system Now we are going to look at two views of an operating system. In another word we can categorize functions of an operating system into two catagories OS as Resource Manager: One view considers the operating system as a resource manager. In this view the operating system is seen as a way of providing the users of the computer with the resources they need at any given time. Some of these resource requests may not be able to be met (memory, CPU usage etc.) but, the operating system is able to deal with problems such as these. For example consider the situation where more than one process is requesting CPU. If we have single CPU it can be assigned to only one process at a time. OS is responsible for when to provide CPU to which process called CPU scheduling. Similarly other resources are also managed by CPU. Prepared By: Arjun Singh Saud 1 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem OS as Extended Machine: Another view of an operating system sees it as a way of not having to deal with the complexity of the hardware. If we have operating system, we can read data easily from disc by issuing a command such as READ. But, if we don’t have OS we have to deal with low level complexities f disc to read data from it. We should know whether the floppy disc is spinning, what type of recording method we should use, What error codes are used etc etc. Operating system hides all these complexities from us simple minded users and provides convenient interface. So in this view of the machine, the operating system can be seen as an extended machine or a virtual machine. History of Operating Systems In this section we take a brief look at the history of operating systems which is almost the same as looking at the history of computers. You are probably aware that Charles Babbage is attributed with designing the first digital computer, which he called the Analytical Engine. It is unfortunate that he never managed to build the computer as, being of a mechanical design; the technology of the day could not produce the components to the needed precision. Of course, Babbage’s machine did not have an operating system, but would have been incredibly useful all the same for it’s era for generating nautical navigation tables. First Generation (1945-1955) : Like many developments, the first digital computer was developed due to the motivation of war. During the Second World War many people were developing automatic calculating machines. These first generation computers filled entire rooms with thousands of vacuum tubes. Like the analytical engine they did not have an operating system, they did not even have programming languages and programmers had to physically wire the computer to carry out their intended instructions. The programmers also had to book time on the computer as a programmer had to have dedicated use of the machine. Second Generation (1955-1965): Vacuum tubes proved very unreliable and a programmer, wishing to run his program, could quite easily spend all his/her time searching for and replacing tubes that had blown. The mid fifties saw the development of the transistor which, as well as being smaller than vacuum tubes, was much more reliable. It now became feasible to manufacture computers that could be sold to customers willing to part with their money. Of course, the only people who could afford computers were large organizations who needed large air conditioned rooms in which to place them. Now, instead of programmers booking time on the machine, the Prepared By: Arjun Singh Saud 2 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem computers were under the control of computer operators. Programs were submitted on punched cards that were placed onto a magnetic tape. This tape was given to the operators who ran the job through the computer and delivered the output to the expectant programmer. As computers were so expensive methods were developed that allowed the computer to be as productive as possible. One method of doing this (which is still in use today) is the concept of batch jobs. Instead of submitting one job at a time, many jobs were placed onto a single tape and these were processed one after another by the computer. The ability to do this can be seen as the first real operating system. Third Generation (1965-1980): The third generation of computers is characterized by the use of Integrated Circuits as a replacement for transistors. This allowed computer manufacturers to build systems that users could upgrade as necessary. Up until this time, computers were single tasking. The third generation saw the start of multiprogramming. That is, the computer could give the illusion of running more than one task at a time. Being able to do this allowed the CPU to be used much more effectively. When one job had to wait for an I/O request, another program could use the CPU. The concept of multiprogramming led to a need for a more complex operating system. One was now needed that could schedule tasks and deal with all the problems that this brings. In implementing multiprogramming, the system was confined by the amount of physical memory that was available (unlike today where we have the concept of virtual memory). Another feature of third generation machines was that they implemented spooling. This allowed reading of punch cards onto disc as soon as they were brought into the computer room. This eliminated the need to store the jobs on tape, with all the problems this brings. Similarly, the output from jobs could also be stored to disc, thus allowing programs that produced output to run at the speed of the disc, and not the printer. Although, compared to first and second generation machines, third generation machines were far superior but they did have a downside. Up until these point programmers were used to giving their job to an operator and watching it run. This problem led to the concept of time sharing. This allowed programmers to access the computer from a terminal and work in an interactive manner. Obviously, with the advent of multiprogramming, spooling and time sharing, operating systems had to become a lot more complex in order to deal with all these issues. Prepared By: Arjun Singh Saud 3 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Fourth Generation (1980-present): The late seventies saw the development of Large Scale Integration (LSI). This led directly to the development of the personal computer (PC). These computers were (originally) designed to be single user, highly interactive and provide graphics capability. One of the requirements for the original PC produced by IBM was an operating system and, Bill Gates supplied MS-DOS on which he made his fortune. In addition, mainly on non-Intel processors, the UNIX operating system was being used. It is still (largely) true today that there are “mainframe” operating systems (such as VME which runs on ICL mainframes) and “PC” operating systems (such as MS-Windows and UNIX), although the distinctions are starting to blur. Mainly, we can say that Graphical User Interface (GUI) became popular in 3rd generation computers. Fifth Generation (Sometime in the future): If you look through the descriptions of the computer generations you will notice that each have been influenced by new hardware that was developed (vacuum tubes, transistors, integrated circuits and LSI). The fifth generation of computers may be the first that breaks with this tradition and the advances in software will be as important as advances in hardware. One view of what will define a fifth generation computer is one that is able to interact with humans in a way that is natural to us. No longer will we use mice and keyboards but we will be able to talk to computers in the same way that we communicate with each other. In addition, we will be able to talk in any language and the computer will have the ability to convert to any other language. Computers will also be able to reason in a way that imitates humans. Just being able to accept (and understand!) the spoken word and carry out reasoning on that data requires many things to come together before we have a fifth generation computer. For example, advances need to be made in AI (Artificial Intelligence) so that the computer can mimic human reasoning. It is also likely that computers will need to be more powerful. Maybe parallel processing will be required. Maybe a computer based on a non-silicon substance may be needed to fulfill that requirement (as silicon has a theoretical limit as to how fast it can go). This is one view of what will make a fifth generation computer. At the moment, as we do not have any, it is difficult to provide a reliable definition. Types of Operating systems All of this history and development has left us with a wide variety of operating systems, not all of which are widely known. Prepared By: Arjun Singh Saud 4 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Mainframe Operating Systems: A mainframe with 1000 disks and thousands of gigabytes of data is not unusual. Mainframes are normally used as web servers, servers for large-scale electronic commerce sites, and servers for business-to-business transactions. The operating systems for mainframes are heavily oriented toward processing many jobs at once, most of which need heavy amounts of I/O. They typically offer three kinds of services: batch, transaction processing, and timesharing. A batch system is one that processes routine jobs without any interactive user present. A claim processing in an insurance company or sales reporting for a chain of stores is typically done in batch mode. Transaction processing systems handle large numbers of small requests; for example, check processing at a bank or airline reservations. Each unit of work is small, but the system must handle hundreds or thousands per second. Timesharing systems allow multiple remote users to run jobs on the computer at once, such as querying a big database. These functions are closely related: mainframe operating systems often perform all of them. An example mainframe operating system is OS/390, a descendant of OS/360 Real-Time Operating Systems: Another type of operating system is the real-time system. These systems are characterized by having time as a key parameter. For example, in industrial process control systems, real-time computers have to collect data about the production process and use it to control machines in the factory. Often there are hard deadlines that must be met. For example, if a car is moving down an assembly line, certain actions must take place at certain instants of time, if a welding robot welds too early or too late, the car will be ruined. If the action absolutely must occur at a certain moment (or within a certain range), we have a hard real-time system. Another kind of real-time system is a soft real-time system, in which missing an occasional deadline is acceptable. Digital audio or multimedia systems fall in this category. Personal Computer Operating Systems: Job of personal computer operating system is to provide a good interface to a single user. They are widely used for word processing, spreadsheets, Internet access etc. Personal computer operating systems are so widely known to the people who use computers but only few computer users knows about other types of operating systems. Common examples of PC operating systems are Windows 2008, Windows 2007, the Macintosh operating system, Linux, Ubuntu etc. Prepared By: Arjun Singh Saud 5 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Server Operating Systems: Server operating systems run on servers, which are very large personal computers, workstations, or even mainframes. They serve multiple users at once over a network and allow the users to share hardware and software resources. Servers can provide print service, file service, or Web service. Internet providers run many server machines to support their customers and Web sites use servers to store the Web pages and handle the incoming requests. Some Examples of typical server operating systems are UNIX and Windows 2007 server, Sun Solaris etc. Review of Computer Hardware An operating system is closely related to the hardware of the computer it runs on. It extends the computer’s instruction set and manages its resources. To work, it must be well known about the hardware, at least, about how the hardware appears to the programmer. Processors: The “brain” of the computer is the CPU. It fetches instructions from memory and executes them. The basic cycle of every CPU is given below:  Fetch  Decode  Execute Fetching loads instruction from memory that is pointed by program counter. Decoding determines type of instruction, operations, and operands. Execution carried out the specified operation on operands. And then fetch, decode, and execute subsequent instructions. Each CPU has a specific set of instructions that it can execute. Thus a Pentium cannot execute SPARC programs and a SPARC cannot execute Pentium programs. Because reading an instruction or data word from memory takes much longer than executing an instruction, all CPUs contain some registers inside it to store currently used variables and temporary results. Most computers have several special registers that are visible to the programmer. One of these is the program counter, which contains the memory address of the next instruction to be fetched. Another register is the stack pointer, which points to the top of the current stack in memory. The stack contains one frame for each procedure that has been entered but not yet exited. A procedure’s stack frame holds input parameters, local variables, and temporary variables that are not kept in registers. Yet another register is the PSW (Program Status Word). This register contains the condition code bits, which are set by comparison instructions, the CPU priority, the mode (user or kernel), and various other control bits. The PSW plays an important role in system calls and I/O. The operating system must be aware of all the registers. In timesharing Prepared By: Arjun Singh Saud 6 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem systems, the operating system will often stop the running program to (re)start another one. Every time it stops a running program, the operating system must save all the registers so they can be restored when the program runs later. Many modern CPUs have facilities for executing more than one instruction at the same time. For example, a CPU might have separate fetch, decode, and execute units, so that while it was executing instruction n , it could also be decoding instruction n + 1 and fetching instruction n + 2. Such an organization is called a pipeline. Instruction n Fetch Decode Execute Fetch Decode Execute Instruction n+1 Fetch Decode Execute Instruction n+2 Figure: Three Stage Pipelining Pipelines cause compiler writers and operating system writers great headaches because they expose the complexities of the underlying machine to them. Even more advanced than a pipeline design is a superscalar CPU. In this design, multiple execution units are present, for example, one for integer arithmetic, one for floating-point arithmetic, and one for Boolean operations. Two or more instructions are fetched at once, decoded, and dumped into a holding buffer until they can be executed. As soon as an execution unit is free, it looks in the holding buffer to see if there is an instruction it can handle, and if so, it removes the instruction from the buffer and executes it. Figure: Superscalar CPU Prepared By: Arjun Singh Saud 7 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Most CPUs have two operating modes, kernel mode and user mode. Usually a bit in the PSW controls the mode. When running in kernel mode, the CPU can execute every instruction in its instruction set and use every feature of the hardware. In contrast, user programs run in user mode, which permits only a subset of the instructions to be executed and a subset of the features to be accessed. Generally, all instructions involving I/O and memory protection are disallowed in user mode. Setting the PSW mode bit to kernel mode-is also forbidden, of course. Memory: The second major component in any computer is the memory. Ideally, a memory should be extremely faster so that CPU is not held up by the memory and should be large enough. No current technology satisfies these goals, so the memory system is designed as hierarchy. Register Cache Main Memory Magnetic Disk Magnetic Tape The top layer consists of the registers internal to the CPU. They are made of the same material as the CPU and are thus just as fast as the CPU. The storage capacity available in them is typically 32 x 32-bits on a 32-bit CPU and 64 x 64-bits on a 64-bit CPU. Generally size of registers is less than 1 KB. Next layer in the hierarchy is the cache memory, which is mostly controlled by the hardware. When the program needs to read a memory word, the cache hardware checks to see if the data needed is in the cache. If it is, called a cache hit, the request is satisfied from the cache and no memory request is sent over the bus to the main memory. Cache hits normally take about two clock cycles. Cache misses have to go to memory, with a substantial time penalty. Cache memory is limited in size due to its high cost. Some machines have two or even three levels of cache, each one slower and bigger than the one before it. Prepared By: Arjun Singh Saud 8 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Main memory comes next. This is the workhorse of the memory system. Main memory is often called RAM (Random Access Memory). All CPU requests that cannot be satisfied out of the cache go to main memory. Next in the hierarchy is magnetic disk (hard disk). Disk storage is two orders of magnitude cheaper than RAM per bit and often two orders of magnitude larger as well. The only problem is that the time to randomly access data on it is close to three orders of magnitude slower. This low speed is due to the fact that a disk is a mechanical device. A disk consists of one or more metal platters that rotate at 5400, 7200, or 10,800 rpm. A mechanical arm is pivoted over the platters. Information is written onto the disk in a series of concentric circles. At any given arm position, each of the heads can read an annular region called a track. Together, all the tracks for a given arm position form a cylinder. Each track is divided into some number of sectors, typically 512 bytes per sector. The arm can move from one cylinder to another cylinder which takes some time in msec. Once the arm is on the correct track, the drive must wait for the needed sector to rotate under the head, an additional delay of 5 msec to 10 msec, depending on the drive’s rpm. Once the sector is under the head, reading or writing occurs at a rate of 5 MB/sec on low-end disks to 160 MB/sec on faster ones. The final layer in the memory hierarchy is magnetic tape. This medium is often used as a backup for disk storage and for holding very large data sets. To access a tape, it must first be put into a tape reader. Then the tape may have to be spooled forwarded to get to the requested block. The big plus of tape is that it is exceedingly cheap per bit and removable, which is important for backup tapes that must be stored off-site in order to survive fires, floods, earthquakes, etc. Prepared By: Arjun Singh Saud 9 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Bus: Physically, bus is a set of wires used for moving data, instruction, and control signals from one component of a computer system to another component. Each component of the computer is connected to these buses. Broadly we can divide buses into following categories:  Address Bus  Data Bus  Control Bus a) Address bus: Address bus is used to specify the address of the memory location to be accessed. CPU reads data or instructions from memory locations by specifying the address of its location or CPU write data to the memory locations by specifying the memory address. Address bus is unidirectional. This means, address bus carries memory location in only one direction, from CPU to memory, both for read and write operation. The width of address bus determines the maximum possible memory of the system. b) Data Bus: Actual data is transferred via the data bus. In case of read operations, CPU sends an address to memory; the memory will send data via the data bus in return to the CPU. But In case of write operation, CPU sends an address via address bus and data via data bus and then specified data is written in specified memory location. Therefore data bus is bidirectional. c) Control Bus: Path for sending the control signals generated by Control Unit is called control bus. Data and Address bus is shared by all the components of the system through the control bus. If CPU needs to perform write operation on memory it sends ‘write’ signal via control bus but if CPU needs to perform read operation on memory ‘read’ signal is sent via control bus. Control bus is also unidirectional because only CPU sends control signals to other devices. System Calls System calls are the interface between the operating system and the user programs. Access to the operating system is done through system calls. Each system call has a procedure associated with it so that calls to the operating system can be done in a similar way as that of normal procedure call. When we call one of these procedures it places the parameters into registers and informs the operating system that there is some Prepared By: Arjun Singh Saud 10 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem work to be done. When a system call is made TRAP instruction (sometimes known as a kernel call or a supervisor call) is executed. This instruction switches the CPU from user mode to kernel (or supervisor) mode. The operating system now carries out the work, which includes validating the parameters. Eventually, the operating system will have completed the work and will return a result in the same way as a user written function written in a high level language. Making a system call is like making a special kind of procedure call, only system calls enter the kernel and procedure calls do not. Since the actual mechanics of issuing a system call are highly machine dependent and often must be expressed in assembly code, a procedure library is provided to make it possible to make system calls from C programs and often from other languages as well. An example of an operating system call (via a procedure) is count = read(file, buffer, nbytes); Prepared By: Arjun Singh Saud 11 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem System calls are performed in a series of steps. To make this concept clearer, let us examine the read call written above. Calling program first pushes the parameters onto the stack, as shown in steps 1-3 before calling the read library procedure, which actually makes the read system call. Then the actual call to the library procedure (step 4) is made. This instruction is the normal procedure call instruction used to call all procedures. The library procedure, possibly written in assembly language, typically puts the system call number in specified register (step 5). Then it executes a TRAP instruction to switch from user mode to kernel mode and start execution at a fixed address within the kernel (step 6). The kernel code examines the system call number and then dispatches to the correct system call handler (step 7). At that point the system call handler runs (step 8). Once the system call handler has completed its work, control may be returned to the user-space library procedure at the instruction following the TRAP instruction (step 9). This procedure then returns to the user program in the usual way procedure calls return (step 10). To finish the job, the user program has to clean up the stack, as it does after any procedure call (step 11). Since, normally the system stack grows downward, stack pointer is incremented exactly enough to remove the parameters pushed before the call to read. The Shell The operating system is the mechanism that carries out the system calls requested by the various parts of the system. Tools such as compilers, Linkers, Loaders, editors etc are not part of the operating system. Similarly, the shell is not part of the operating system. The shell is the part of operating systems such as UNIX and MS-DOS where we can type commands to the operating system and receive a response. Shell is also called the Command Line Interpreter (CLI) or the “C” prompt. Shell is the primary interface between a user sitting at his terminal and the operating system, unless the user is using a graphical user interface. Many shells exist, including sh, csh, ksh, and bash. The shell makes heavy use of operating system features and thus serves as a good example of how the system calls can be used. When any user logs in, a shell is started up. The shell has the terminal as standard input and standard output. It starts out by typing the prompt, a character such as a dollar sign, which tells the user that the shell is waiting to accept a command. If the user now types “date” command, the shell creates a child process and runs the date program as the child. While the child process is running, the shell waits for it to terminate. When the child finishes, the shell types the prompt again and tries to read the next input line. A more complicated command is Prepared By: Arjun Singh Saud 12 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem cat file1 file2 file3 | sort > /dev/lp & This command concatenates three files and pipes them to the sort program. It then redirects the sorted file to a line printer. The ampersand “&” at the end of the command instructs UNIX to issue the command as a background job. This results in the command prompt being returned immediately, whilst another process carries out the requested work. Above command makes a series of system calls to the operating system in order to satisfy the whole request. Operating System Structure Monolithic Systems: One possible approach is to have no structure to the operating system at all i.e. it is simply a collection of procedures. Each procedure has a well defined interface and any procedure is able to call any other procedure. The operating system is constructed by compiling all the procedures into one huge monolithic system. There is no concept of encapsulation, data hiding or structure amongst the procedures. This organization suggests a basic structure for the operating system: A main program that invokes the requested service procedure, A set of service procedures that carry out the system calls, and A set of utility procedures that help the service procedures. In this model, for each system call there is one service procedure that takes care of it. The utility procedures do things that are needed by several service procedures, such as fetching data from user programs. Layered Systems: In 1968 E. W. Dijkstra (Holland) and his students built the “THE” operating system that was structured into layers. It can be viewed as a generalization of the model shown above, but this model had six layers.  Layer 0 was responsible for the multiprogramming aspects of the operating system. It decided which process was allocated to the CPU. It dealt with interrupts and performed the context switches when a process change was required. Prepared By: Arjun Singh Saud 13 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem  Layer 1 was concerned with allocating memory to processes.  Layer 2 deals with inter-process communication and communication between the operating system and the console.  Layer 3 manages all I/O between the devices attached to the computer. This included buffering information from the various devices.  Layer 4 was where the user programs were stored.  Layer 5 was the overall control of the system (called the system operator). As you move through this hierarchy (from 0 to 5) you do not need to worry about the aspects you have “left behind.” For example, high level user programs (level 4) do not have to worry about where they are stored in memory or if they are currently allocated to the processor or not, as these are handled in low level 0-1. Virtual Machines: Virtual machines mean different things to different people. For example, if you run an MS-DOS prompt from with Windows 2008 you are running, what Microsoft call, a virtual machine. It is given this name as the MS-DOS program is fooled into thinking that it is running on a machine that it has sole use of. ICL’s mainframe operating system is called VME (Virtual Machine Environment). The idea is that when you log onto the machine a VM (Virtual Machine) is built and it looks as if you have the computer all to yourself. One of the first operating system (VM/370) was able to provide a virtual machine to each user. In addition, each user was able to run different operating systems if they so desired. Main concept of the system was that the bare hardware was “protected” by VM/370 (called a virtual machine monitor). This provided access to the hardware when needed by the various processes running on the computer. Unlike other operating systems, instead of simply providing an extension of the hardware that hides the complexities of the hardware, VM/370 provided an exact copy of the hardware, which included I/O, interrupts and user/kernel mode. Because each virtual machine is identical to the true hardware, each one can run any operating system that will run directly on the bare hardware. Any instructions to the hardware are trapped by VM/370, which carried out the instructions on the physical hardware and the results returned to the calling process. The diagram below shows a model of the VM/370 computer. Note that CMS is a “Conversational Monitor System” and is just one of the many operating systems that can be run – in this case it CMS is a single user OS intended for interactive time sharing. Prepared By: Arjun Singh Saud 14 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Client-Server Model: One of the recent advances in computing is the idea of a client/server model. A server provides services to any client that requests it. This model is heavily used in distributed systems where a central computer acts as a server to many other computers. The server may be something as simple as a print server, which handles print requests from clients. Or, it could be relatively complex, and the server could provide access to a database which only it is allowed to access directly. Operating systems can be designed along similar lines. Take, for example, the part of the operating system that deals with file management. This could be written as a server so that any process which requires access to any part of the filing system asks the file management server to carry out a request, which presents the calling client with the results. Similarly, there could be servers which deal with memory management, process scheduling etc. The benefits of this approach include  It can result in a minimal kernel. This results in easier maintenance as not so many processes are running in kernel mode. All the kernel does is providing the communication between the clients and the servers.  As each server is managing one part of the operating system, the procedures can be better structured and more easily maintained.  If a server crashes it is less likely to bring the entire machine down as it will not be running in kernel mode. Only the service that has crashed will be affected. Prepared By: Arjun Singh Saud 15 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Chapter 2 Process Management Processes Process is a program that is ready for execution in CPU. When a program is loaded into memory, it becomes ready for execution and competes with other processes to access CPU. Thus when a program is loaded into memory it becomes process. Computers nowadays can do many things at the same time. They can be writing to a printer, reading from a disc and scanning an image. Operating system is responsible for running many processes, usually, on the same CPU. In fact, only one process can be run at a time so the operating system has to share the CPU between the processes that are available to be run, while giving the illusion that the computer is doing many things at the same time. This approach can be directly contrasted with the first computers. They could only run one program at a time. Now, the main point of this part is to consider how an operating system deals with processes when we allow many to run. To achieve true parallelism we must have multiprocessor system where n processors can execute n programs simultaneously. True parallelism cannot be achieved with single CPU. In single processor CPU switched from one process to another process rapidly. In 1 sec CPU can serve 100’s of processes giving the illusion of parallelism to a user which is called pseudo-parallelism. The Process Model All the runnable programs on the computer including the operating system, is organized into a number of sequential processes. Every process includes the current values of the program counter, registers, and variables. Conceptually, each process has its own virtual CPU. In reality, of course, the real CPU switches back and forth from process to process. To understand the system of CPU switching from program to program and execution of programs, consider four processes each with its own flow of control (i.e., its own logical program counter), and each one running independently of the other ones. Of course, there is only one physical program counter, so when each process runs, its logical program counter is loaded into the real program counter. When it has finished its turn on CPU, the physical program counter is saved in the process logical program counter in memory. Same process is also repeated for another process. Prepared By: Arjun Singh Saud 16 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Process States A process may be in one of three states. A state transition diagram can be used to represent the various states and the transition between those states.  Running: Only one process can be running sate at any one time (assuming a single processor machine). Running process is the process that is actually using the CPU at that time.  Ready: A process that is ready is runnable but cannot get access to the CPU due to another process using it. Any number of processes can be in ready state at the same time.  Blocked: A blocked process is unable to run until some external event has taken place. For example, it may be waiting for data to be retrieved from a disc. Blocked process cannot use CPU even if CPU has to do nothing. We can see from above transition diagram that a running process can either move to blocked sate or ready state. Running process is moved to blocked state when it needs to wait for an external event such as input from keyboard or it can go to a ready state when the scheduler allows another process to use the CPU. A ready process can only move to a running state when scheduler decides to provide CPU to that process. But, a Prepared By: Arjun Singh Saud 17 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem blocked process can only move to a ready state when the external event for which it is waiting occurs. Implementation of Processes Assuming we have a computer with one processor, it is obvious that the computer can only execute one process at a time. However, when a process moves from a running state to a ready or blocked state it must store certain information so that it can remember where it was up to when it moves back to a running state. For example, it needs to know which instruction it was about to execute (Value of PC), which record it was about to read from its input file (position of input file pointer) and the values of various variables that it was using as working storage. To implement the process model each process is associated with data structure called process table of Process Control Block (PCB). Thus PCB is a data structure used to hold all the information that a process needs in order to restart from where it left off when it moves from a ready state to a running state. Different systems will hold different information in the process block. This table shows a typical set of data We can notice that, as well as information to ensure the process can start again (e.g. Program Counter), the process control block also holds accounting information such as the time the process started and how much CPU time has been used. This is only a sample of the information held. There will be other information, at least all process entries must also include files being used and the memory the process is using. Threads One definition of a process is that it has an address space and a single thread of execution. Processes are based on two independent concepts: resource grouping and execution. Sometimes it would be beneficial if two (or more) processes could share the same address space (i.e. same variables and registers etc) and run parts of the process in Prepared By: Arjun Singh Saud 18 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem parallel. This is what threads do. Multithreading is one of the technique for achieving multitasking. Threads are like mini-processes that operate within a single process. Each thread has its own program counter and stack so that it knows where it is. Apart from this they can be considered the same as processes, with the exception that they share the same address space. This means that all threads from the same process have access to the same global variables and the same files. Threads are also called light weight processes. The table given below shows the various items that a process has, compared to the items that each thread has. Per Thread Items Per Process Items  Program Counter  Address Space  Stack  Global Variables  Register Set  Open Files  Child Thread  Child Process  State  Timers  Signals  Semaphores  Accounting Information Thread Usage  Some application needs to perform multiple activities at once that share common data and files. Thus reason behind need of multiple threads can be listed as below:  Ability of parallel entities, within a process, to all share common variables and data.  Since threads do not have their own address space, it is easier to create and destroy threads than processes. In fact thread creation is around 100 times faster than process creation  Thread switching has much less overhead than process switching because threads have few information attached with them.  Performance gain when there is a lot of computing and a lot of I/O as tasks can overlap. Pure CPU bound thread application no advantage though  Threads very effective on multiple CPU systems for concurrent processing because with multiple CPUs true parallelism can be achieved Prepared By: Arjun Singh Saud 19 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem For example, 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 such as I/O. However, this approach gives us two problems  We still have the problem, in that either of the processes could become blocked.  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. Now consider yet another example of where threads are useful: a server for a World Wide Web site. Requests for pages come in and the requested page is sent back to the client. One way to organize the Web server is to use a process with dispatcher thread and worker thread. The dispatcher thread reads incoming requests for work from the network. After examining the request, the dispatcher wakes up the sleeping worker, moving it from blocked state to ready state. When the worker wakes up, it checks to see if the request can be satisfied from the Web page cache, to which all threads have access. If not, it starts a read operation to get the page from the disk and blocks until the disk operation completes. When the thread blocks on the disk operation, another thread is chosen to run, possibly the dispatcher, in order to acquire more work, or possibly another worker that is now ready to run. Prepared By: Arjun Singh Saud 20 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Implementation of threads in User Space There are two main ways to implement a threads package: in user space and in the kernel. The choice is moderately controversial, and a hybrid implementation is also possible. One method is to put the threads package entirely in user space.. If we put threads entirely in user space, the kernel knows nothing about them rather it just thinks that it is serving single threaded processes. User level threads run on top of a run-time system, which is a collection of procedures that manage threads. Some of the procedures are thread_create , thread_exit , thread_wait , thread_yield etc. When threads are implemented in user space Each process needs to maintain its own thread table and are analogous to the kernel’s process table. A thread table contains thread program counter, thread stack pointer, thread registers, thread state i.e. ready, blocked etc. Unlike processes though, when a thread_yield is called it saves the thread information in the thread table itself and can instruct the thread scheduler to call another thread. Just local procedures used, so more efficient/faster than a kernel call. Prepared By: Arjun Singh Saud 21 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Advantages of implementing threads in user space  User-level threads package can be implemented on an operating system that does not support threads.  Threads permit each process to have its own scheduler. This means processes can customize scheduling algorithm.  With user level threads no trap is needed, no context switch is needed, the memory cache need not be flushed, and so on. This makes thread scheduling very fast. Disadvantages of implementing threads in user space  Allowing threads to use blocking system calls causes other threads in the same address space to be blocked.  If a thread causes a page fault, the kernel blocks the entire process until the disk I/O is complete, even though other threads might be runnable. This is because kernel doesn’t know anything about threads in user space.  Within a single process, there are no clock interrupts, making it impossible to schedule threads in the fashion that takes turns. No other thread in that process will ever run unless the first thread voluntarily gives up the CPU One possible solution to the problem of threads running forever is to have the run-time system request a clock signal (interrupt) once a second to give it control, but periodic clock interrupts at a higher frequency are not always possible, and even if they are, the total overhead may be substantial. Prepared By: Arjun Singh Saud 22 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Interprocess Communication The mechanism of passing information from one process to another process is called IPC. Processes frequently need to communicate with other processes. For example, in a shell pipeline, the output of the first process must be passed to the second process, and so on down the line. Thus there is a need for communication between processes, preferably in a well-structured way not using interrupts. Race Conditions It is sometimes necessary for two processes to communicate with one another. This can either be done via shared memory or via a file on disc. We are not discussing the situation where a process can write some data to a file that is read by another process at a later time e.g. days, weeks or months. We are talking about two processes that need to communicate at the time they are running. Race conditions are situations where two or more processes reads or writes some shared data at the same time and the final result is incorrect. Final result may be different according to order of completion of competing processes. To see how interprocess communication works in practice, let us consider a simple but common example: a print spooler. When a process wants to print a file, it enters the file name in a special spooler directory. Another process, the printer daemon, periodically checks to see if there are any files to be printed, and if there are, it prints them and then removes their names from the directory. Consider the situation given in figure below, where in and out are two shared variables. Prepared By: Arjun Singh Saud 23 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Process A reads value of in (i.e. 7) but before inserting the name of the document to be printed in index 7, a clock interrupt occurs and the CPU decides to schedule process B. Now, process B also reads in, and also gets a 7. At this instant both processes think that the next available slot is 7. Process B now continues to run and stores the name of its file in slot 7 and updates in to be an 8. After some time process A runs again, starting from the place it left off. It looks at value of in stored in its local variable and finds a 7 there, and writes its file name in slot 7, erasing the name that process B just put there. Then it increments value of in cached by (which is 8) it and sets in to 8. The printer daemon will not notice anything wrong, but process B will never receive any output. Situations like this are called race conditions. Critical Sections One way to avoid race conditions is not to allow two processes to be in their critical sections at the same time. Critical section is the part of the process that accesses a shared variable. That is, we need a mechanism of mutual exclusion. Mutual exclusion is the way of ensuring that one process, while using the shared variable, does not allow another process to access that variable. In fact, to provide a good solution to the problem of race conditions we need four conditions to hold.  No two processes may be simultaneously inside their critical sections.  No assumptions may be made about the speed or the number of processors.  No process running outside its critical section may block other processes  No process should have to wait forever to enter its critical section. Prepared By: Arjun Singh Saud 24 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Implementing Mutual Exclusion Mutual Exclusion with Busy Waiting Busy waiting means if the process is not allowed to enter its critical section it sits in a tight loop waiting for a condition to be met. This is obviously wasteful in terms of CPU usage. Busy waiting is useful in systems where CPU have to do no other things busy waiting. a) Disabling Interrupts: Perhaps the most obvious way of achieving mutual exclusion is to allow a process to disable interrupts before it enters its critical section and then enable interrupts after it leaves its critical section. By disabling interrupts the CPU will be unable to switch processes. This guarantees that the process can use the shared variable without another process accessing it. But, it is unwise to give user processes the power to turn off interrupts. At best, the computer will not be able to service interrupts for the time period a process is in its critical section. At worst, the process may never enable interrupts, thus crashing the computer. Although disabling interrupts might seem a good solution its disadvantages overshadow the advantages. b) Lock Variables: Lock variable is software solution to achieve mutual exclusion. It is a binary variable whose value is either zero or 1. Initially zero is assigned to lock variable. Value 0 indicates no process is in critical region and value 1 indicates that some process is doing processing inside the critical region. When a process wants to enter critical region it tests lock variable. If it is 1, it waits for lock to be 0 by sitting in tight loop otherwise it sets lock to 1 and enter into critical section. And process resets lock to zero when it exits from its critical region. This scheme simply moves the problem from the shared variable to the lock variable. It again suffers from race condition problem. Suppose that one process reads the lock and sees that it is 0. Before it can set the lock to 1, another process is scheduled, runs, and sets the lock to 1. When the first process runs again, it will also set the lock to 1, and two processes will be in their critical regions at the same time Prepared By: Arjun Singh Saud 25 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem c) Strict alternation Process 0 Process 1 While (TRUE) While (TRUE) { { while (turn != 0); // wait while (turn != 1); // wait critical_section(); critical_section(); turn = 1; turn = 0; noncritical_section(); noncritical_section(); } } These above code fragments offer a solution to the mutual exclusion problem. Assume the variable turn is initially set to zero. Process 0 is allowed to run. It finds that turn is zero and is allowed to enter its critical region. If process 1 tries to run, it will also find that turn is zero and will have to wait (the while statement) until turn becomes equal to 1. When process 0 exits its critical region it sets turn to 1, which allows process 1 to enter its critical region. If process 0 tries to enter its critical region again it will be blocked as turn is no longer zero. This approach also suffers from one major flaw. Consider following sequence of events:  Process 0 runs, enters its critical section and exits; setting turns to 1. Process 0 is now in its noncritical section. Assume this non-critical procedure takes a long time.  Process 1, which is a much faster process, now runs and once it has left its critical section turn is set to zero.  Process 1 executes its non-critical section very quickly and returns to the top of the procedure.  The situation is now that process 0 is in its non-critical section and process 1 is waiting for turn to be set to zero. In fact, there is no reason why process 1 cannot enter its critical region as process 0 is not in its critical region. From this observation we can see that strict alteration violates the condition “No process running outside its critical section may block other processes” d) Peterson’s Solution: It is a solution to the mutual exclusion problem that does not require strict alternation, but still uses the idea of lock variables together with the concept of taking turns. The solution consists of two procedures, shown below: Prepared By: Arjun Singh Saud 26 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem #define N 2 // Number of processes int turn; // Whose turn is it? int interested[N]; // All values initially FALSE void enter_region(int process) { other = 1 – process; // the opposite process interested[process] = TRUE; // this process is interested turn = process; // set flag while(turn == process && interested[other] == TRUE); // wait } void leave_region(int process) { interested[process] = FALSE; // process leaves critical region } Initially, both processes are not in their critical region and the array interested has all its elements set to false. Assume that process 0 calls enter_region. The variable other is set to one (the other process number) and it indicates its interest by setting the relevant element of interested to true. Next it sets the turn variable, before coming across the while loop. In this instance, the process will be allowed to enter its critical region, as process 1 is not interested in running. Now process 1 could call enter_region. It will be forced to wait as the other process (i.e process 0) is still interested. Process 1 will only be allowed to continue when interested is set to false which is possible only when process 0 calls leave_region. If we ever arrive at the situation where both processes call enter region at the same time, one of the processes will set the turn variable, but it will be immediately overwritten. Assume that process 0 sets turn to zero and then process 1 immediately sets it to 1. Under these conditions process 0 will be allowed to enter its critical region and process 1 will be forced to wait. e) Test and Set Lock (TSL) If we are given assistance from the instruction set of the processor we can implement a solution to the mutual exclusion problem. The assembly (machine code) instruction we require is called test and set lock (TSL). This instruction reads the contents of a memory location, stores it in a register and then stores a non-zero value at the address. This operation is guaranteed to be atomic. That is, no other process Prepared By: Arjun Singh Saud 27 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem can access that memory location until the TSL instruction has finished. This assembly (like) code shows how we can make use of the TSL instruction to solve the mutual exclusion problem. enter_region: tsl register, flag // copy flag to register and set flag to 1 cmp register, #0 //was flag zero? jnz enter_region //if flag was non zero, lock was set , so loop ret //return (and enter critical region) leave_region: mov flag, #0 //store zero in flag ret //return Assume, again, two processes. Process 0 calls enter_region. The tsl instruction copies the flag to a register and sets flag to a non-zero value. The flag is now compared to zero and if found to be non-zero the routine loops back to the top. Only when process 1 has set the flag to zero (or under initial conditions), by calling leave_region, process 0 will be allowed to enter into critical region. Comments on Busy Waiting Solutions Of all the solutions we have looked at, both Peterson’s and the TSL solutions solve the mutual exclusion problem. However, both of these solutions suffers from following two problems:  Busy Waiting Problem: If the process is not allowed to enter its critical section it sits in a tight lop waiting for a condition to be met. This is obviously wasteful in terms of CPU usage.  Priority Inversion Problem: Suppose we have two processes, one of high priority h, and one of low priority l. Scheduler is set so that whenever h is in ready state it must be run. If l is in its critical section when h becomes ready to run, l will be placed in a ready state so that h can be run. However, if h tries to enter its critical section then it will be blocked by l, which will never be given the opportunity of running and leaving its critical section. Meantime, h will simply sit in a loop forever. This is sometimes called the priority inversion problem. Sleep and Wakeup One of the simplest solutions to achieve mutual exclusion without busy waiting is the pair sleep and wakeup system calls. Sleep is a system call that causes the caller to block, that is, be suspended until another process wakes it up. Prepared By: Arjun Singh Saud 28 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem The Producer-Consumer Problem Producer-consumer problem is also known as the bounded-buffer problem. Two processes called producer and consumer share a common, fixed size buffer. Producer puts information into the buffer, and consumer, takes it out. Trouble arises when the producer wants to put a new item in the buffer, but it is already full. The solution is for the producer to go to sleep until consumer has removed one or more items and wakes up it. Similarly, if the consumer wants to remove an item from the buffer and sees that the buffer is empty, it goes to sleep until the producer puts something in the buffer and wakes it up. This approach sounds simple enough, but it leads to the race conditions. Consider the following code fragment: #define N 100 int count = 0; void producer (void) { int item; while (TRUE) { item = produce_item(); if (count == N) sleep(); insert_item(item); count = count + 1; if (count == 1) wakeup(consumer); } } void consumer(void) { int item; while (TRUE) { if (count == 0) sleep(); item = remove_item(); count = count - 1; if (count == N - 1) wakeup(producer); consume_item(item); } } Prepared By: Arjun Singh Saud 29 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem This seems logically correct but we have the problem of race conditions with count. The following situation could arise.  The buffer is empty and the consumer has just read count to see if it is equal to zero.  Scheduler stops running the consumer and starts running the producer. The producer places an item in the buffer and increments count.  The producer checks to see if count is equal to one. If it is zero, it assumes that it was previously zero which implies that the consumer is sleeping – so it sends a wakeup.  In fact, the consumer is not asleep so the call to wakeup is lost. The consumer eventually gets switched back in and now runs – continuing from where it left off – it checks the value of count. Finding that it is zero it goes to sleep. As the wakeup call has already been issued the consumer will sleep forever.  Eventually the buffer will become full and the producer will send itself to sleep. Both producer and consumer will sleep forever. Semaphore Concept of semaphore was devised by Dijkstra in 1965. Semaphore is an integer variable that is used to record number of wakeups that had been saved. If it is equal to zero it indicates that no wakeup’s are saved. A positive value shows that one or more wakeup’s are pending. The DOWN operation (equivalent to sleep) checks the semaphore to see if it is greater than zero. If it is, it decrements the value (using up a stored wakeup) and continues. If the semaphore is zero the process sleeps. The UP operation(Equivalent to wakeup) increments the value of the semaphore. If one or more processes were sleeping on that semaphore then one of the processes is chosen and allowed to complete its DOWN. Checking and updating the semaphore must be done as an atomic action to avoid race conditions. Producer Consumer problem can be solved by using semaphore as below: #define N 100 typedef int semaphore; semaphore mutex = 1; semaphore empty = N; semaphore full = 0; void producer(void) { int item; Prepared By: Arjun Singh Saud 30 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem while (TRUE) { item = produce_item(); down(&empty); down(&mutex); insert_item(item); up(&mutex); up(&full); } } void consumer(void) { int item; while (TRUE) { down(&full); down(&mutex); item a= remove_item(); up(&mutex); up(&empty); consume_item(item); } } This solution uses three semaphores: one called full for counting the number of slots that are full, one called empty for counting the number of slots that are empty, and one called mutex to make sure the producer and consumer do not access the buffer at the same time. Full is initially 0, empty is initially equal to the number of slots in the buffer, and mutex is initially 1. Semaphores that are initialized to 1 and used by two or more processes to ensure that only one of them can enter its critical region at the same time are called binary semaphores. The mutex semaphore is used for mutual exclusion. It is designed to guarantee that only one process at a time will be reading or writing the buffer and the associated variables. If each process does a down just before entering its critical region and an up just after leaving it, mutual exclusion is guaranteed. The full and empty semaphores are needed to Prepared By: Arjun Singh Saud 31 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem guarantee synchronization. In this case, they ensure that the producer stops running when the buffer is full, and the consumer stops running when it is empty. Monitors With semaphores interprocess communication looks easy in first sight. But we should be too much careful about order of down operation. Suppose that the two downs in the producer’s code were reversed in order, so mutex was decremented before empty. If the buffer were completely full, the producer would block, with mutex set to 0. Consequently, the next time the consumer tried to access the buffer, it would do a down on mutex. Since mutex is already 0, consumer is also blocked too. Both processes would stay blocked forever and no more work would ever be done. This unfortunate situation is called a deadlock. Above problem shows that one subtle error causes everything to come to a grinding halt. To make it easier to write correct programs, Hoare and Brinch Hansen proposed a higher-level synchronization primitive called a monitor. A monitor is a collection of procedures, variables, and data structures that are all grouped together in a special kind of module or package. Processes may call the procedures in a monitor whenever they want to, but they cannot directly access the monitor’s internal data structures from procedures declared outside the monitor. Only one process can be active in a monitor at any instant. Monitors are a programming language construct, so the compiler knows they are special and can handle calls to monitor procedures differently from other procedure calls. When a process calls a monitor procedure, the first few instructions of the procedure will check to see, if any other process is currently active within the monitor. If so, the calling process will be suspended until the other process has left the monitor. If no other process is using the monitor, the calling process may enter. A skeleton of the producer-consumer problem with monitors is given below: monitor ProducerConsumer.. function insert (item : integer );.. Prepared By: Arjun Singh Saud 32 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem function remove : integer ;.. end monitor ; procedure producer ; begin while true do begin item = produce_item ; ProducerConsumer.insert (item ) end; end ; procedure consumer ; begin while true do begin item = ProducerConsumer.remove ; consume_item (item ) end; end ; Operations wait and signal are very similar to sleep and wakeup, but with one crucial difference: sleep and wakeup failed because while one process was trying to go to sleep, the other one was trying to wake it up. With monitors, that cannot happen. The automatic mutual exclusion on monitor procedures guarantees that if, say, the producer inside a monitor procedure discovers that the buffer is full, it will be able to complete the wait operation without having to worry about the possibility that the scheduler may switch to the consumer just before the wait completes. The consumer will not even be let into the monitor at all until the wait is finished and the producer has been marked as no longer runnable. Message Passing This method of interprocess communication uses two primitives, send and receive , which, like semaphores and unlike monitors, are system calls rather than language constructs.  send(destination, &message): It sends a message to a given destination Prepared By: Arjun Singh Saud 33 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem  receive (source, &message): It receives a message from a given source. If no message is available, the receiver can block until one arrives. Design Issues for Message Passing Systems Message passing systems have many challenging problems and design issues that do not arise with semaphores or monitors, especially if the communicating processes are on different machines connected by a network. For example  Messages can be lost by the network. To guard against lost messages, the sender and receiver can agree that as soon as a message has been received, the receiver will send back a special acknowledgement message. If the sender has not received the acknowledgement within a certain time interval, it retransmits the message.  If the message itself is received correctly but the acknowledgement is lost, the sender will retransmit the message, so the receiver will get it twice. Usually, his problem is solved by putting consecutive sequence numbers in each original message. If the receiver gets a message bearing the same sequence number as the previous message, it knows that the message is a duplicate that can be ignored.  Message systems also have to deal with the question of how processes are named, so that the process specified in a send or receive call is unambiguous.  Authentication is also an issue in message systems: how can the client tell that he is communicating with the real file server, and not with an imposter?  When the sender and receiver are on the same machine, copying messages from one process to another is always slower than doing a semaphore operation or entering a monitor. The Producer-Consumer Problem with Message Passing We assume that all messages are the same size and that messages sent but not yet received are buffered automatically by the operating system. In this solution, a total of N messages are used. The consumer starts out by sending N empty messages to the producer. Whenever the producer has an item to give to the consumer, it takes an empty message and sends back a full one. If the producer works faster than the consumer, all the messages will be filled up, and the producer will be blocked, waiting for an empty message to come back. If the consumer works faster, then the reverse happens: all the messages will be empties and the consumer will be blocked, waiting for a full message. #define N 100 void producer(void) Prepared By: Arjun Singh Saud 34 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem { int item; message m; // message buffer while (TRUE) { item = produce_item( ); // generate something to put in buffer receive(consumer, &m); // Receive an empty message, if any build_message (&m, item); // construct a message to send send(consumer, &m); // send item to consumer } } void consumer(void) { int item, i; message m; for (i = 0; i < N; i++) send(producer, &m); // send N empty messages while (TRUE) { receive(producer, &m); //get message containing item item = extract_item(&m); // extract item from message send(producer, &m); // send back empty reply consume_item(tem); // do something with the item } } Classical IPC Problems The Producer-Consumer Problem: Assume there are a producer (which produces goods) and a consumer (which consumes goods). The producer produces goods and places them in a fixed size buffer. The consumer takes the goods from the buffer. The buffer has a finite capacity so that if it is full, the producer must stop producing. Similarly, if the buffer is empty, the consumer must stop consuming. This problem is also referred to as the bounded buffer problem. The type of situations we must cater for are when the buffer is full, so the producer cannot place new items into it. Another potential problem is when the buffer is empty, so the consumer cannot take from the buffer. The Dining Philosophers Problem: This problem was posed by (Dijkstra, 1965). Five philosophers are sat around a circular table. In front of each of them is a bowl of Prepared By: Arjun Singh Saud 35 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem food. In between each bowl there is a fork. That is there are five forks in all. Philosophers spend their time either eating or thinking. When they are thinking they are not using a fork. When they want to eat they need to use two forks. They must pick up one of the forks to their right or left. Once they have acquired one fork they must acquire the other one. They may acquire the forks in any order. Once a philosopher has two forks they can eat. When finished eating they return both forks to the table. The question is, can a program be written, for each philosopher, that never gets stuck, that is, a philosopher is waiting for a fork forever. The Readers Writers Problem: This problem was devised by. It models a number of processes requiring access to a database. Any number of processes may read the database but only one can write to the database. The problem is to write a program that ensures this happens. The Sleeping Barber Problem: A barber shop consists of a waiting room with n chairs. There is another room that contains the barber’s chair. The following situations can happen.  If there are no customers the barber goes to sleep.  If a customer enters and the barber is asleep (indicating there are no other customers waiting) he wakes the barber and has a haircut.  If a customer enters and the barber is busy and there are spare chairs in the waiting room, the customer sits in one of the chairs.  If a customer enters and all the chairs in the waiting room are occupied, the customer leaves. The problem is to program the barber and the customers without getting into race conditions. Scheduling When a computer is multiprogrammed, it frequently has multiple processes competing for the CPU at the same time. This situation occurs whenever two or more processes are simultaneously in the ready state. If only one CPU is available, a choice has to be made which process to run next. The part of the operating system that makes the choice is called the scheduler and the algorithm it uses is called the scheduling algorithm. Compute-Bound Vs I/O-Bound Processes Some processes spend most of their time in computing. Such processes are called compute-bound processes. But some spend most of their time waiting for I/O. such processes are called I/O bound processes. Compute-bound processes typically have Prepared By: Arjun Singh Saud 36 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem long CPU bursts and thus infrequent I/O waits, whereas I/O-bound processes have short CPU bursts and thus frequent I/O waits. As CPUs get faster, processes tend to get more I/O bound. This effect occurs because CPUs are improving much faster than disks. As a consequence, the scheduling of I/O-bound processes is likely to become a more important subject in the future. The basic idea here is that if an I/O-bound process wants to run, it should get a chance quickly so it can issue its disk request and keep the disk busy. Preemptive vs Non-preemptive Scheduling A nonpreemptive scheduling algorithm picks a process to run and then just lets it run until it blocks or until it voluntarily releases the CPU. Even if it runs for hours, it will not be forceably suspended. Scheduling the next process to run would simply be a case of taking the highest priority job or using some other algorithm, such as FIFO algorithm. In contrast, a preemptive scheduling algorithm picks a process and lets it run for a maximum of some fixed time. If it is still running at the end of the time interval, it is suspended and the scheduler picks another process to run (if one is available). If no clock is available, nonpreemptive scheduling is the only option. Categories of Scheduling Algorithms In different environments different scheduling algorithms are needed. This situation arises because different application areas have different goals. The scheduler optimized for one may not be optimal for another area. Three environments worth distinguishing are  Batch: In batch systems, there are no users impatiently waiting at their terminals for a quick response. Consequently, nonpreemptive algorithms, or preemptive algorithms with long time periods for each process are often acceptable. This approach reduces process switches and thus improves performance.  Interactive: In an environment with interactive users, preemption is essential to keep one process from monopolizing the CPU and denying service to the others. Preemption is needed to prevent this behavior.  Real time: In real time systems normally preemption is not needed because the processes know that they may not run for long periods of time and usually do their work and block quickly. The difference with interactive systems is that real- time systems run only programs that are intended to further the application at hand. Prepared By: Arjun Singh Saud 37 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Scheduling Algorithm Goals All systems  Fairness - Under all circumstances, fairness is important. Processes having similar priority should get should get comparable service. Giving one process much more CPU time than an equivalent one is not fair.  Policy enforcement - seeing that stated policy is carried out  Balance – All parts of the system must be busy when possible. If the CPU and all the I/O devices can be kept running all the time, more work gets done per second than if some of the components are idle, Batch systems  Throughput - Throughput is the number of jobs per hour that the system completes. All things considered, finishing 50 jobs per hour is better than finishing 40 jobs per hour.  Turnaround time – Turnaround time is the statistically average time from the moment that a batch job is submitted until the moment it is completed. It measures how long the average user has to wait for the output. Here the rule is: Small is Beautiful.  CPU utilization - On the big mainframes where batch systems run, the CPU is still a major expense. Thus computer center managers feel guilty when it is not running all the time therefore one goal of batch system is to keep the CPU busy all the time Interactive systems  Response time - Response time is the time between issuing a command and getting the result. One main goal of interactive systems is to minimize response time.  Proportionality – When a request that is perceived as complex takes a long time, users accept that, but when a request that is perceived as simple takes a long time, users get irritated. Proportionality measures how well the users’ expectations are met. Real-time systems  Meeting deadlines - avoid losing data  Predictability - avoid quality degradation in multimedia systems Prepared By: Arjun Singh Saud 38 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Scheduling Algorithms First Come – First Served Scheduling (FCFS) An obvious nonpreemptve scheduling algorithm is to execute the processes in the order they arrive and to execute them to completion. It is an easy algorithm to implement. When a process becomes ready it is added to the tail of ready queue and when the CPU becomes free the process at the head of the queue is removed, moved to a running state and allowed to use the CPU until it is completed. The problem with FCFS is that the average waiting time can be long. Consider the following processes Process Burst Time Arrival time P1 27 1 P2 9 2 P3 2 4 Gantt chart P1 P2 P3 0 27 36 38 Average waiting =( (0 + 27 +36) /3 )=21 Average turnaround time = ((27+ 36 +38) /3 )= 33.66 FCFS algorithm has some undesirable effects. A CPU bound job may make the I/O bound (once they have finished the I/O) wait for the processor. At this point the I/O devices are sitting idle. Again, when the CPU bound job finally does some I/O, the I/O- bound processes use the CPU quickly and now the CPU sits idle waiting for the CPU bound job to complete its I/O. Thus FCFS can lead to I/O devices and the CPU both being idle for long periods. Shortest Job First SJF is another non-preemptive batch algorithm that assumes the run times are known in advance. When several equally important jobs are sitting in the input queue waiting to be started, the scheduler picks the shortest job first. SJF is the optimal scheduling algorithm that gives minimum average waiting time. The problem of SJF is we do not know the burst time of a process before it starts. For some systems (notably batch Prepared By: Arjun Singh Saud 39 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem systems) we can make fairly accurate estimates but for interactive processes it is not so easy. Consider the following processes. Process Burst Time Arrival Time P1 12 0 P2 19 0 P3 4 0 P4 7 0 Gantt chart P3 P4 P1 P2 0 4 11 23 42 Average waiting =( (0 + 4 + 11 + 23 ) /4 )= 9.5 Average turnaround time = ((4+ 11 + 23 + 42) /4 )= 20 Challenge!!! Construct Gantt chart and then calculate average waiting time and average turnaround time for processes given in table below. Process Burst Time Arrival Time P1 8 0 P2 19 0 P3 4 3 P4 7 5 Shortest Remaining Time Next (SRTF) A preemptive version of shortest job first is shortest remaining time next. With this algorithm, the scheduler always chooses the process whose remaining run time is the shortest. Again here, the run time has to be known in advance. When a new job arrives, its total time is compared to the current process’ remaining time. If the new job needs less time to finish than the current process, the current process is suspended and the new job started. This scheme allows new short jobs to get good service. Round-Robin Scheduling One of the oldest, simplest, fairest, and most widely used algorithms is round robin. Each process is assigned a time interval, called its quantum, which it is allowed to run. If the process is still running at the end of the quantum, the CPU is preempted and Prepared By: Arjun Singh Saud 40 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem given to another process. If the process has blocked or finished before the quantum has elapsed, the CPU switching is done when the process blocks, of course. Round robin is easy to implement. All the scheduler needs to do is maintain a list of runnable processes. When the process uses up its quantum, it is put on the end of the list. The interesting issue with round robin is the length of the quantum. Switching from one process to another requires a certain amount of time. Setting the quantum too short causes too many process switches and lowers the CPU efficiency, but setting it too long may cause poor response to short interactive requests. Large value of quantum may cause Round Robin scheduler may cause it to behave like FCFS. Typically RR gives higher average turnaround time, but better response time. Consider the following processes with time quantum set to 20. Process Burst Time Arrival Time P1 53 0 P2 17 0 P3 68 0 P4 24 0 Gantt chart Avg. turnaround time= (134+37+162+121)/4 = 113.5 Avg. waiting time=(81+20+94+97)/4=73 Prepared By: Arjun Singh Saud 41 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Challenge!!! Construct Gantt chart and then calculate average waiting time and average turnaround time for processes given in table below. {Assume Quantum size=5} Process Burst Time Arrival Time P1 9 0 P2 17 1 P3 23 2 P4 12 16 Priority Scheduling Round robin scheduling makes the implicit assumption that all processes are equally important. On a PC, there may be multiple processes, some more important than others. For example, a daemon process sending electronic mail in the background should be assigned a lower priority than a process displaying a video film on the screen in real time. The need to take external factors into account leads to priority scheduling. The basic idea is straightforward: each process is assigned a priority, and the runnable process with the highest priority is allowed to run. One of the problems with priority scheduling is that some processes may never run. There may always be higher priority jobs that get assigned the CPU. This is known as indefinite blocking or starvation. One solution to this problem is scheduler may decrease the priority of the currently running process at each clock tick. If this action causes its priority to drop below that of the next highest process, a process switch occurs. Alternatively, each process may be assigned a maximum time quantum that it is allowed to run. When this quantum is used up, the next highest priority process is given a chance to run. Multiple Queue Scheduling There are two typical processes in a system, interactive jobs which tend to be shorter and batch jobs which tend to be longer. We can set up different queues to cater for different process types. Each queue may have its own scheduling algorithm – the background queue will typically use the FCFS algorithm while the interactive queue may use the RR algorithm. The scheduler has to decide which queue to run. Either higher priority queues can be processed until they are empty before the lower priority queues are executed or each queue can be given a certain amount of the CPU. There could be other Prepared By: Arjun Singh Saud 42 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem queues in addition to the two mentioned. Multilevel Queue Scheduling assigns a process to a queue and it remains in that queue. It may be advantageous to move processes between queues (multilevel feedback queue scheduling). If we consider processes with different CPU burst characteristics, a process which uses too much of the CPU will be moved to a lower priority queue. We would leave I/O bound and (fast) interactive processes in the higher priority queues. Working Assume three queues (Q0, Q1 and Q2)  Scheduler executes Q0 and only considers Q1 and Q2 when Q0 is empty  A Q1 process is preempted if a Q0 process arrives  New jobs are placed in Q0  Q0 runs with a quantum of 8ms  If a process Q0 uses full quantum it is placed at the end of the Q1 queue  Q1 has a time quantum of 16ms associated with it  Any processes preempted in Q1 are moved to Q2, which is FCFS Figure: A scheduling algorithm with four priority classes Prepared By: Arjun Singh Saud 43 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Chapter 1 Process Deadlocks Deadlock Introduction In a multiprogramming environment, several processes may compete for a finite number of resources. A process requests resources; if the resources are not available at that time, the process enters a wait state. Waiting processes may never again change state, because the resources they have requested are held by other waiting processes. This situation is called a deadlock. System is deadlocked if there is a set of processes such that every process in the set is waiting for another process in the set. Or “A set of procedures is deadlocked if each process in the set is waiting for an event that only another process in the set can cause” for example:  Process A makes a request to use the scanner  Process A given the scanner  Process B requests the CD writer  Process B given the CD writer  Now A requests the CD writer  A is denied permission until B releases the CD writer  Alas now B asks for the scanner  Result a DEADLOCK! A system consists of a finite number of resources to be distributed among a number of processes. These resources are partitioned into several types, each of which consists of some number of identical resources. A process must request a resource before using it, and must release the resource after using it. A process may request as many resources as it requires to carry out its designated task. Under the normal mode of operation, a process may utilize a resource in only the following sequence:  Request: If the request cannot be granted immediately, then the requesting process must wait until it can acquire the resource.  Use: The process can operate on the resource.  Release: The process releases the resource. Prepared By: Arjun Singh Saud 44 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Deadlock Characterization Necessary Condition: According to Coffman, a deadlock can arise if the following four conditions hold simultaneously.  Mutual exclusion: Only one process at time can use the resource. If a process requests the recourse that is used by another process, the requesting process must be delayed until the resource has been released.  Hold and wait: A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.  No preemption: A resource can be released only voluntarily by the process holding it, after that process has completed its task.  Circular wait: A set {P0, P1, …, P0} of waiting processes must exist such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0. Resource – Allocation Graph: Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph. This graph consists of a set of vertices V and a set of edges E. The set of vertices V is partitioned two different types of nodes:  P = {P1, P2, …, Pn}, the set consisting of all the processes in the system.  R = {R1, R2, …, Rm}, the set consisting of all resource types in the system. A directed edge from process Pi to resource type Rj is denoted by Pi Rj and it signifies that process Pi requested an instance of resource type Rj and is currently waiting for that resource. This directed edge is called request edge. A directed edge from resource type Rj to process Pi is denoted by Rj Pi and it signifies that an instance of resource type Rj has been allocated to process Pi. This directed edge is called an assignment edge. Pictorially, we represent each process as a circle, and each resource type as a square. Since resource type may have more than one instance, we represent each such instance as a dot within the square. A request edge points to only the square, whereas an assignment edge must also designate one of the dots in the square. The figure below shows resource-allocation graph. Prepared By: Arjun Singh Saud 45 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem This resource-allocation graph depicts the following situation.  The set P, R, and E  P = {P1, P2, P3}  R = {R1, R2, R3, R4}  E = {P1 R1, P2 R3, R1 P2, R2 P2, R2 P1, R3 P3}  Resource instances:  One instance of resource type R1  Two instances of resource type R2  One instance of resource type R3  Three instances of resource type R4  Process states:  Process p1 is holding an instance of resource type R2, and is waiting for an instance of resource type R1  Process P2 is holding an instance of R1 and R2, and is waiting for an resource type R3  Process P3 is holding an instance of R3 If graph contains no cycles, no deadlock occurs. But, if the graph contains a cycle and only one instance per resource is available, then deadlock occurs. Also, if the graph contains a cycle and there are several instances per resource type, then there is possibility of deadlock. The figure (a) below shows the resource allocation graph with a deadlock and the figure (b) shows the resource allocation graph with a cycle but no deadlock. Prepared By: Arjun Singh Saud 46 OS Handouts Aberdeen Int’l College B.Sc CISIT 3rd Sem Figure (a):Deadlock Figure(b):No Deadlock Handling Deadlocks We can deal with deadlock problems in one of the four ways: a. Ignore the Problem (Ostrich Algorithm): We can ignore the deadlock problem altogethe