CPE 308 Operating System.docx

**CPE 308** **PRINCIPLES OF OPERATING SYSTEMS** 1. Introduction =============== The operating system is an essential part of a computer system; it is an intermediary component between the application programs and the hardware. The ultimate purpose of an operating system is two folds: 1. To prov...

**CPE 308** **PRINCIPLES OF OPERATING SYSTEMS** 1. Introduction =============== The operating system is an essential part of a computer system; it is an intermediary component between the application programs and the hardware. The ultimate purpose of an operating system is two folds: 1. To provide various services to users\' programs and 2. To control the functioning of the computer system hardware in an efficient and effective manner. Software Components =================== A program is a sequence of instructions that enables a computer to execute a specific task. Before a program executes, it has to be translated from its original text form (source program) into a machine language program. The program then needs to be linked and loaded into memory. The software components are the collection of programs that execute in the computer. These programs perform computations and control, manage, and carry out other important tasks. There are two general types of software components: - System software - Application software System software is the set of programs that control the activities and functions of the various hardware components, programming tools and abstractions, and other utilities to monitor the state of the computer system. This software forms an environment for the programmers to develop and execute their programs (collectively known as application software). There are actually two types of users: application programmers and end users. Common system software, in particular, is very general and covers a broad spectrum of functionalities. It mainly comprises three major subsystems: (i) language translators (compilers, interpreters, assemblers) and runtime systems (linkers, loaders, etc.) for a programming language, (ii) utility systems, and (iii) operating systems (OSs). Numerous input/output (I/O) devices also require device-dependent programs that control and monitor their smooth operation during an I/O operation. These programs are essentially system software known as device drivers, sometimes called input--output control systems (IOCSs). All these programs are mostly written in low‑level languages, such as Assembly language, binary language, and so on, which are very close to the machine's (hardware's) own language or have patterns so that machine resources can be directly accessed from the user level. Nowadays, they are also often developed with the high-level language C. The most important part of system software is the operating system (OS) that directly controls and manages the hardware resources of the computer. The OS also provides a set of services to the user programs. The most common examples of operating systems are Linux, Unix, Windows, MacOS, and OS/2. Application software is the user programs and consists of those programs that solve specific problems for the users and execute under the control of the operating system. Application programs are developed by individuals and organizations for solving specific problems. Operating Systems ================= An operating system (OS) is a large and complex set of system programs that control the various operations of a computer system and provide a collection of services to other (user) programs. The purpose of an operating system involves two key goals: - Availability of a convenient, easy-to-use, and powerful set of services that are provided to the users and the application programs in the computer system - Management of the computer resources in the most efficient manner Application and system programmers directly or indirectly communicate with the operating system in order to request some of these services. The services provided by an operating system are implemented as a large set of system functions that include scheduling of programs, memory management, device management, file management, network management, and other more advanced services related to protection and security. The operating system is also considered a huge resource manager and performs a variety of services as efficiently as possible to ensure the desired performance of the system. Figure 1 shows an external view of a computer system. It illustrates the programmers and end users communicating with the operating system and other system software. The most important active resource in the computer system is the CPU. Other important resources are memory and I/O devices. Allocation and de-allocation of all resources in the system are handled by various resource managers of the operating system. Figure 1: An external view of a computer system. **Operating system performs the following functions:** 1. Booting: Booting is a process of starting the computer. Operating system starts the computer to work. It checks the computer and makes it ready to work. 2. One set of operating-system services provides functions that are helpful to the user Communications -- Processes may exchange information, on the same computer or between computers over a network Communications may be via shared memory or through message passing (packets moved by the OS) 3. Error detection -- OS needs to be constantly aware of possible errors that may occur in the CPU and memory hardware, in I/O devices, in user program. 4. Memory Management: Memory management refers to management of Primary Memory or Main Memory. Main memory is a large array of words or bytes where each word or byte has its own address. - Keeps tracks of primary memory, i.e., what part of it are in use by whom, what part are not in use. - In multiprogramming, the OS decides which process will get memory when and how much. - Allocates the memory when a process requests it to do so. - De-allocates the memory when a process no longer needs it or has been terminated. 5. Processor Management: In multiprogramming environment, the OS decides which process gets the processor when and for how much time. This function is called process scheduling. - Keeps tracks of processor and status of process. The program responsible for this task is known as traffic controller. - Allocates the processor (CPU) to a process. - De-allocates processor when a process is no longer required. 6. Device Management: An Operating System manages device communication via their respective drivers. - Keeps tracks of all devices. Program responsible for this task is known as the I/O controller. - Decides which process gets the device when and for how much time. - Allocates the device in the efficient way. - De-allocates devices. 7. File Management: A file system is normally organized into directories for easy navigation and usage. - Keeps track of information, location, uses, status etc. The collective facilities are often known as file system. - Decides who gets the resources. - Allocates the resources. - De-allocates the resources. 8. Other Important Activities: Following are some of the important activities that an Operating System performs − iii. Job accounting − Keeping track of time and resources used by various jobs and users. iv. Coordination between other softwares and users − Coordination and assignment of compilers, interpreters, assemblers and other software to the various users of the computer systems. 9. Providing interface  Figure 2: OS handles all of the above tasks for the system and application software. Operating System Interfaces =========================== Users and application programmers can communicate with an operating system through its interfaces. There are three general levels of interfaces provided by an operating system: - Graphical user interface (GUI) - Command line interpreter (also called the shell) - System-call interface Figure 3 illustrates the basic structure of an operating system and shows the three levels of interfaces, which are found immediately above the kernel. The highest level is the graphical user interface (GUI), which allows I/O interaction with a user through intuitive icons, menus, and other graphical objects. With these objects, the user interacts with the operating system in a relatively easy and convenient manner for example, using the click of a mouse to select an option or command. The most common GUI examples are the Windows desktop and the X-Window in Unix. The user at this level is completely separated from any intrinsic detail about the underlying system. This level of operating system interface is not considered an essential part of the operating system; it is rather an add-on system software component. Figure 3: Basic structure of an operating system. The second level of interface, the command line interpreter, or shell, is a text oriented interface. Advanced users and application programmers will normally directly communicate with the operating system at this level. In general, the GUI and the shell are at the same level in the structure of an operating system. The third level, the system-call interface, is used by the application programs to request the various services provided by the operating system by invoking or calling system functions. Multi-Level Views of an Operating System ======================================== The overall structure of an operating system can be more easily studied by dividing it into the various software components and using a top-down (layered) approach. This division includes the separation of the different interface levels, as previously discussed, and the additional components of the operating system. The higher the level of the layer, the simpler the interaction with the system. The top layer provides the easiest interface to the human operators and to users interacting with the system. Any layer uses the services or functions provided by the next lower layer. As mentioned previously, the main goal of an operating system is to provide services to the various user and system programs. The operating system is structured into several components, each one providing its own group of services. For a more clear understanding of the complexities of how the various services are provided, two abstract views of the OS are presented: (1) the external view and (2) the internal view. External View of an Operating System ==================================== The external view of an operating system is the set of interfaces discussed previously. These are sometimes referred to as the abstract views. Users of a computer system directly or indirectly communicate with the operating system in order to request and receive some type of service provided by the operating system. Users and application programs view the computer system at the higher level(s) of the operating system interface. The low-level OS structures (internal view) and the hardware details are hidden behind the OS interface. Figure 4 illustrates the abstract views of a computer system. Only the upper level abstract views are important to users of the OS. The low-level OS view and the hardware view are relevant only to system specialists.  Figure 4: Abstract views of a computer system. One of the main principles applied in the design of the external view concept is simplicity. The system interfaces hide the details of how the underlying (lower-level) machinery operates. The operational model of the computer system presented to the user should be relatively easy to use and is an abstract model of the operations of the system. Kernel is the most central part of the operating systems. The abstraction provided by the OS interfaces gives users and application programs the appearance of a simpler machine. The various programs also convey the illusion that each one executes on its own machine; this abstraction is sometimes called the abstract machine view. Terms which are parts of the operating system ============================================= 1. Application: The application represents the software that a user is running on an operating system it can be either system or application software eg slack, sublime text editor, etc. 2. Shell: The shell represents software that provides an interface for the user where it serves to launch or start some program for which the user gives instructions. It can be of two types first is a command line and another is a graphical user interface for eg: MS-DOS Shell, PowerShell, csh, ksh, etc. 3. Kernel: Kernel represents the most central and crucial part of the operating system where it is used for resource management i.e. it provides necessary I/O, processor, and memory to the application processes through inter-process communication mechanisms and system calls. Internal View of an Operating System ==================================== The system services interface (or the system call interface) separates the kernel from the application layer. Located above the hardware, the kernel is the core and the most critical part of the operating system and needs to be always resident in memory. A detailed knowledge about the different components of the operating system, including these lower-level components, corresponds to an internal view of the system. In studying the internal view of the operating system, it becomes important to identify the various components of the OS that establish policies for the various services they support and the mechanisms used to implement these policies. It was previously noted that the various services provided by the operating systems include process management, memory management, device management, file management, network management, and other more advanced services related to protection and security. The most important functional components of the operating system are as follows: - Process manager - Memory manager - Resource manager - File manager - Device manager These components are actually modules of the operating system and are strongly related. In addition to these basic functions, most operating systems have some type of network management, security management, and other more advanced functions. Process Manager: The process manager can be considered the most important component of the operating system. It carries out several services such as creating, suspending (blocking), executing, terminating, and destroying processes. With multiprogramming, several active processes are stored and kept in memory at the same time. If there is only one CPU in the system, then only one process can be in execution at a given time; the other processes are waiting for CPU service. The decision regarding which process to execute next is taken by the **scheduler**. The **dispatcher** allocates the CPU to a process and deallocates the CPU from another process. This switching of the CPU from one process to another process is called **context switching** and is considered overhead time. Memory Manager: The memory manager controls the allocation and deallocation of memory. It imposes certain policies and mechanisms for memory management. This component also includes policies and mechanisms for memory protection. Relevant memory management schemes are paging, segmentation, and virtual memory. Resource Manager: The resource manager facilitates the allocation and deallocation of resources to the requesting processes. Functions of this component include the maintenance of resource tables with information such as the number of resources of each type that are available and the number of resources of each type that have been allocated to specific processes. The access mode for the various resources is another type of function. File Manager: The file manager allows users and processes to create and delete files and directories. In most modern operating systems, files are associated with mass storage devices such as magnetic tapes and disks. Data can be read and/or written to a file using functions such as open file, read data from file, write data to file, and close file. The Unix operating system also uses files to represent I/O devices (including the main input device and a main output device such as the console keyboard and video screen). Device Manager: For the various devices in the computer system, the device manager provides an appropriate level of abstraction to handle system devices. For every device type, a device driver program is included in the OS. The device manager operates in combination with the resource manager and file manager. Usually, user processes are not provided direct access to system resources. Instead, processes request services to the file manager and/or the resource manager. Types of Operating Systems ========================== Operating systems are there from the very first computer generation and they keep evolving with time. Some of the important types of operating systems which are most commonly used are: **Batch operating system:** The users of a batch operating system do not interact with the computer directly. Each user prepares his job on an off-line device like punch cards and submits it to the computer operator. To speed up processing, jobs with similar needs are batched together and run as a group. The programmers leave their programs with the operator and the operator then sorts the programs with similar requirements into batches. The problems with Batch Systems are as follows − - Lack of interaction between the user and the job. - CPU is often idle, because the speed of the mechanical I/O devices is slower than the CPU. - Difficult to provide the desired priority. **Time-sharing operating systems:** Time-sharing is a technique which enables many people, located at various terminals, to use a particular computer system at the same time. Time-sharing or multitasking is a logical extension of multiprogramming. Processor\'s time which is shared among multiple users simultaneously is termed as time-sharing. The main difference between Multiprogrammed Batch Systems and Time-Sharing Systems is that in case of Multiprogrammed batch systems, the objective is to maximize processor use, whereas in Time-Sharing Systems, the objective is to minimize response time. Multiple jobs are executed by the CPU by switching between them, but the switches occur so frequently. Thus, the user can receive an immediate response. For example, in a transaction processing, the processor executes each user program in a short burst or quantum of computation. That is, if n users are present, then each user can get a time quantum. When the user submits the command, the response time is in few seconds at most. The operating system uses CPU scheduling and multiprogramming to provide each user with a small portion of a time. Computer systems that were designed primarily as batch systems have been modified to time-sharing systems. Advantages of Timesharing operating systems are as follows − - Provides the advantage of quick response. - Avoids duplication of software. - Reduces CPU idle time. Disadvantages of Time-sharing operating systems are as follows -- - Problem of reliability. - Question of security and integrity of user programs and data. - Problem of data communication. **Distributed operating System:** Distributed systems use multiple central processors to serve multiple real-time applications and multiple users. Data processing jobs are distributed among the processors accordingly. The processors communicate with one another through various communication lines (such as high-speed buses or telephone lines). These are referred to as loosely coupled systems or distributed systems. Processors in a distributed system may vary in size and function. These processors are referred as to sites, nodes, computers, and so on. The advantages of distributed systems are as follows − - With resource sharing facility, a user at one site may be able to use the resources available at another. - Speedup the exchange of data with one another via electronic mail. - If one site fails in a distributed system, the remaining sites can potentially continue operating. - Better service to the customers. - Reduction of the load on the host computer. - Reduction of delays in data processing. **Network operating System:** A Network Operating System runs on a server and provides the server the capability to manage data, users, groups, security, applications, and other networking functions. The primary purpose of the network operating system is to allow shared file and printer access among multiple computers in a network, typically a local area network (LAN), a private network or to other networks. Examples of network operating systems include Microsoft Windows Server 2003, Microsoft Windows Server 2008, UNIX, Linux, Mac OS X, Novell NetWare, and BSD. The advantages of network operating systems are as follows − - Centralized servers are highly stable. - Security is server managed. - Upgrades to new technologies and hardware can be easily integrated into the system. - Remote access to servers is possible from different locations and types of systems. The disadvantages of network operating systems are as follows − - High cost of buying and running a server. - Dependency on a central location for most operations. - Regular maintenance and updates are required. **Real Time operating System:** A real-time system is defined as a data processing system in which the time interval required to process and respond to inputs is so small that it controls the environment. The time taken by the system to respond to an input and display of required updated information is termed as the response time. So in this method, the response time is very less as compared to online processing. Real-time systems are used when there are rigid time requirements on the operation of a processor or the flow of data and real-time systems can be used as a control device in a dedicated application. A real-time operating system must have well-defined, fixed time constraints, otherwise the system will fail. For example, scientific experiments, medical imaging systems, industrial control systems, weapon systems, robots, air traffic control systems, etc. There are two types of real-time operating systems. Hard real-time systems: Hard real-time systems guarantee that critical tasks complete on time. In hard real-time systems, secondary storage is limited or missing and the data is stored in ROM. In these systems, virtual memory is almost never found. Soft real-time systems: Soft real-time systems are less restrictive. A critical real-time task gets priority over other tasks and retains the priority until it completes. Soft real-time systems have limited utility than hard real-time systems. For example, multimedia, virtual reality, Advanced Scientific Projects like undersea exploration and planetary rovers, etc. **Small and Specialized Operating Systems:** A mobile operating system, also known as a mobile OS, a mobile platform, or a handheld operating system, is the operating system that controls a mobile device. Compared to the standard general-purpose operating systems, mobile operating systems are currently somewhat simpler, and focus on wireless versions of broadband and local connectivity, mobile multimedia formats, and different input methods. Mobile operating systems that can be found on smartphones include Nokia\'s Symbian OS, Apple\'s IOS, RIM\'s BlackBerry OS, Windows Phone, Linux, Palm WebOS, Google\'s Android, and Nokia\'s Maemo. Android, WebOS, and Maemo are in turn built on top of Linux, and the iPhone OS is derived from the BSD and NeXTSTEP operating systems, which are all related to Unix. **Embedded Operating Systems:** An embedded operating system is an operating system for embedded computer systems. These operating systems are designed to be very compact and efficient, with similar functions that nonembedded computer operating systems provide, but which are more specialized depending on the applications they run. Most embedded operating systems are real-time operating systems. Examples of systems that use embedded operating systems include: Automated Teller Machines, cash registers, CCTV systems, a TV box set, a GPS, jukeboxes, and missiles. Architecture of an Operating System =================================== Booting is the start process of an OS through which it sets up its environment and starts working. After booting, the OS begins its initial process and hands over the control to the user process. Since a user is not allowed to perform any I/O operation, all these are performed by the OS. However, a user needs to request the OS for all I/O operations. System call is the medium through which a user sends the request. The OS works on the hardware on behalf of the user and provides the results back to the user. Thus, system call execution and its types are fundamental for understanding the working of the OS. After a discussion of the details of the working, various architectures developed have been discussed in this chapter. The architectures have been evolved over time, catering to the needs of various requirements and keeping pace with technological advancement in computer hardware. GENERAL WORKING OF AN OPERATING SYSTEM ====================================== The role of an OS starts as soon as the computer system is switched on and lasts till it is shut down. But where is the OS in the computer system? How does the OS get loaded in the system? How does it start? These are some questions addressed here in this section. Before delving into the working of an OS, there are some basic definitions/concepts that need to be understood. **BIOS** Basic Input-output System (BIOS) is a software that basically consists of input-output functions. These functions are low-level routines that the OS uses to interface with different I/O devices, such as keyboard, mouse, monitor, ports, and so on. This is the reason that this software is named as such (BIOS). However, the meaning of BIOS was extended beyond this functioning. Since the OS is on the hard disk, it needs to be loaded onto the main memory to start the functioning of the system. So the problem is to find a way to tell the microprocessor to load the OS. It needs some instructions that, when executed, load the OS. These instructions are provided by the BIOS. In this way, along with providing the basic input-output low-level routines, it also provides the initialization function. This is the reason that the BIOS is embedded in the ROM or flash RAM so that whenever the system is switched on, the initial instructions get executed automatically and the process of loading the OS initiates. However, it was found that BIOS was inefficient for Oss such as Linux and Windows written for 32 bit CPUs. Therefore, with the advent of new CPU architecture and development in OSs, BIOS is getting replaced. For example, since 2008 in x86 Windows systems, Extensible Firmware Interface (EFI) booting is being supported. The EFI is more flexible in accessing devices. In this way, today, BIOS is primarily used for loading the OS and initialization purposes and otherwise not used, as during the general operation of the system. Instead of calling BIOS, OSs use device drivers for accessing the hardware. Booting/Bootstrapping ===================== When a system is switched on the first time, it does not have an OS. We need to get the OS ready from the hard disk or other secondary storage onto the memory. A set of sequence of operations is needed to load the OS. This process of placing the OS in memory is known as booting or bootstrapping. Boot Software/Boot Loader/Bootstrap Loader ========================================== The set of instructions needed for booting, that is, to load the OS in RAM is known as boot software/boot loader/bootstrap loader. Boot Device =========== The OS is originally stored in a non volatile secondary storage such as hard disk, CD, and the like. In the process of booting, there is a need to search this storage device, where an OS is stored, to load it onto the RAM. The device that stores the OS is called boot device. Privileged Instructions ======================= There are some operations, provided in the form of instructions, that need to interact with hardware devices. But a user is not allowed to access the devices directly. The instructions are first passed on to the OS, and the OS then interacts with devices on behalf of the user. Thus, the instructions, which are not directly executed by the user but need to be passed to the OS, are known as privileged instructions. System Call =========== All privileged instructions, that is, instructions, which need to interact with hardware and other resources, and are therefore passed on to the OS for execution, are known as system calls. For example, when the user needs to write something on the screen, he/she writes the output instruction in the appropriate format. This instruction in the program is system call. The general working of an OS is discussed in the following steps: Initialization ============== It was discussed that the OS acts as a resource manager, so it must have the initialized set of devices in the system. Therefore, whenever the computer is switched on, the control is transferred to the BIOS in the ROM by the hardware. The first job for the BIOS is to initialize and identify system devices such as the video display card, keyboard and mouse, hard disk, CD/DVD drive, and other hardware. This initialization job is known as power on self test (POST). It is a built-in diagnostic program that initializes and configures a processor and then checks the hardware to ensure that every connected device is present and functioning properly. In other words, it tests the computer to make sure it meets the necessary system requirements and that all the hardware is working properly before starting of the system. There may be some errors while the execution of POST. These errors are stored or reported through auditory or visual means, for example, through a series of beeps, flashing LEDs, or text on a display. Booting ======= a. After the execution of POST, the BIOS determines the boot device, for example, floppy, CD, or hard disk. b. BIOS contains a program that loads the first sector of the boot device called boot sector. c. The boot sector contains a program. The program in boot sector, when loaded onto the memory and executed, first examines the partition table at the end of the boot sector to determine which partition is active. d. In the partition, there is a boot loader/bootstrap loader, which is now loaded onto the memory by the boot sector program (see Figure 5). The area where the boot program/loader is stored is called boot block of the boot device. e. Boot loader contains the instructions that, when executed, load the OS onto the main memory (bootstrapping) and the control is passed on to the OS by setting bits, corresponding to the privileged mode. Start the Operation =================== a. After being loaded and executed, the OS first queries the BIOS to get the configuration information. b. For each device, it checks the corresponding device driver. After confirming all the device drivers, it loads them into the kernel. c. The OS initializes its tables, creates needed background processes, and kicks off the startup of the first process, such as the login program. d. The user programs are loaded onto the memory as the users log in. The control is transferred to the scheduler that selects a user program from the memory and transfers control to the selected program by setting bits corresponding to the user mode, that is, the CPU is now in user mode. Figure 5: Booting sequence 1. Load the boot sector 2. Boot sector program examines the active partition at the end of the boot sector 3. Boot sector program loads the boot loader 4. Boot loader loads the OS e. Given the interrupt-driven nature of the OS, it waits for an event. When there is an event signalled by the interrupt from the hardware or software, it starts responding. The hardware interrupts are triggered by sending a signal to the CPU on the system bus. Software interrupts are triggered by executing a special operation or control instruction called a system call. For instance, when a user wants to access an I/O device, he/she will send a request to the OS in the form of a system call, which, in turn, executes a software interrupt and transfers the control to the OS. f. These system calls are handled by the system call handler that identifies the cause of interrupt by analyzing the interrupt code and transfers control to the corresponding interrupt-handling routine/event handler in the OS. For example, if there is an I/O interrupt, then control is passed on to the I/O interrupt handler. Thus, the OS has many event handlers that are invoked through the system calls. GENERAL STRUCTURE OF OS ======================= It is clear now that the OS resides in the main memory. However, as the size of the OS increased, there was the problem of keeping it in the limited memory. Therefore, the OS was structured into two parts: Resident part or kernel and Transient part (see Figure 9). The resident part contains programs that are crucial and needed always. Therefore, they must reside in the memory forever. Thus, this makes up the resident part. The transient part is based on programs that are not always needed and, therefore, need not be in the memory forever. Therefore, this part is loaded only when needed, thereby reducing the memory requirement. In this way, the resident- and transient part programs structure the OS. The decision to put programs or data structures in resident or transient part depends on its frequency of use in the OS. If the function is inherent and used every time in the operation of the OS, it must be included in the resident part. Otherwise, it should be in the transient part. The resident part may contain the following programs or data structures: **Resource Allocation Data Structures:** The data structures related to the allocation of various resources must be in the resident part. A device, if allocated to some process, needs to be checked before being allocated to some other process. Therefore, this data structure is important for smooth allocation of resources. **Information Regarding Processes and their States:** Every process contains some information such as its ID, priority, state, and so on. This information is useful while switching from one process to another. The switching operation is quite frequent in multi-programming OSs. Thus, this data structure should also be in the resident part. **System Call Handler:** Since the user uses system calls frequently in his/her programs, there is a need to handle these system calls by the OS. Therefore, system call handler must be in the resident part. **Event Handlers:** Some event handlers are also necessary for the working of the OS, that is, they are in frequent use. For example, the memory handler or disk I/O handler is required for almost every operation.  Figure 9: Resident and transient parts of an OS in the memory **Scheduler:** This is a frequently used program in the OS whose job is to select the jobs in the queue and send it for dispatching. As we know, in a multi-programming system, there always are jobs to be executed in the queue. Therefore, there is a need to schedule them as well. So, this program should also be in the resident part. OPERATING SYSTEM ARCHITECTURE ============================= Operating systems can be categorized based on their architecture into a few main types. Each architecture has its own strengths and weaknesses, leading to different performance, security, and flexibility characteristics. **Monolithic Kernel:** A monolithic kernel operating system is one where the entire operating system, including device drivers, file system management, memory management, and system call interface, all run in the kernel space. This means that all kernel-level services are present within a single address space and share the same memory space. In a monolithic kernel architecture, system services are tightly integrated, which can lead to better performance due to reduced overhead in communication between kernel modules. However, it also means that if one part of the kernel fails, it can potentially crash the entire system. Examples of operating systems with monolithic kernels include traditional Unix systems like Linux, earlier versions of Windows (such as Windows 95, 98, and ME), and some variants of BSD (Berkeley Software Distribution). **Microkernel:** A microkernel operating system is a type of operating system architecture where the kernel provides minimal services, and additional functionality, including device drivers, file systems, and networking protocols, is implemented as user-space processes known as servers. The microkernel itself typically only provides essential services such as inter-process communication and memory management. Some notable examples of microkernel operating systems include: QNX: QNX is a real-time microkernel operating system known for its reliability, scalability, and performance. It is widely used in embedded systems, automotive systems, and industrial automation. MINIX: MINIX is a Unix-like microkernel-based operating system designed for teaching purposes. It became widely known after being the subject of Andrew S. Tanenbaum\'s textbook, \"Operating Systems: Design and Implementation.\" L4: L4 is a family of microkernel operating systems that includes various implementations optimized for different use cases, including embedded systems, real-time systems, and virtualization. Microkernel architectures offer several potential advantages, including modularity, scalability, and fault isolation. However, they can also introduce performance overhead due to increased message passing between user-space servers and the kernel and require careful design to ensure efficiency. **Hybrid Kernel:** A hybrid kernel operating system is a type of operating system architecture that combines elements of both monolithic and microkernel designs. In a hybrid kernel, some essential operating system services are implemented in kernel space, while others are implemented as user-space processes or drivers. Some notable examples of hybrid kernel operating systems include: Windows NT/2000/XP/7/8/10: Microsoft Windows operating systems are based on a hybrid kernel architecture. The kernel provides core operating system services such as memory management, process scheduling, and hardware abstraction, while device drivers and some subsystems run in user mode. Mac OS X/macOS: macOS, the operating system used by Apple\'s Mac computers, is based on a hybrid kernel known as XNU (X is Not Unix). XNU combines the Mach microkernel with components from FreeBSD and other Unix-like systems. Hybrid kernel architectures aim to strike a balance between the performance and flexibility of monolithic kernels and the modularity and fault isolation of microkernels. They can offer advantages such as improved performance and easier device driver development while still providing some degree of protection and isolation between components. **Exokernel:** An exokernel is an operating system architecture where the kernel provides minimal abstractions on top of hardware resources, allowing applications to directly manage hardware resources. In an exokernel system, applications have fine-grained control over resources such as CPU, memory, and I/O devices. Unlike traditional operating systems that provide high-level abstractions through system calls, exokernels expose low-level hardware resources to applications, enabling them to implement their own abstractions and policies. This approach can lead to increased performance and flexibility since applications can tailor resource management to their specific needs. Exokernels typically consist of a small, privileged kernel that manages hardware protection and resource allocation, along with a library or runtime system that provides higher-level abstractions to applications. Examples of exokernels include ExOS and Nemesis. The exokernel architecture emphasizes the importance of application-level resource management and enables efficient customization and specialization for different types of applications. However, developing and using exokernel-based systems often require more expertise and effort compared to traditional operating systems. Exokernels are a less common operating system architecture compared to monolithic or microkernel designs. However, there have been a few instances of exokernel operating systems developed for research purposes. Some notable examples include: While these exokernel projects demonstrated the potential benefits of the architecture, they were primarily research prototypes and not widely adopted for practical use. However, the concepts and ideas explored in these projects have influenced the development of other operating systems and research in areas such as virtualization, cloud computing, and specialized operating systems for specific domains. **Nano/Picokernel:** A nano or picokernel operating system is a type of operating system architecture characterized by an extremely minimalistic kernel that provides only essential functionality, such as basic process scheduling, memory management, and inter-process communication. In nano/picokernel systems, most operating system services and device drivers are implemented as user-space processes or libraries rather than being tightly integrated into the kernel. One of the key motivations behind nano/picokernel architectures is to minimize the trusted computing base (TCB), which is the portion of the operating system that must be trusted to enforce security policies and protect against system-level attacks. By keeping the kernel small and focused, nano/picokernel designs aim to reduce the potential attack surface and improve security. Examples of nano/picokernel operating systems include: Google\'s Fuchsia OS: Fuchsia is an open-source operating system developed by Google. It features a microkernel called \"Zircon,\" which can be considered a nano/picokernel. Zircon provides basic kernel services such as process management, inter-process communication, and hardware abstraction, while higher-level functionality is implemented as user-space components. Redox OS: Redox is a Unix-like operating system written in Rust. It utilizes a microkernel architecture with a nano/picokernel called \"Kernel.\" Kernel provides minimal functionality, and most system services, including device drivers and file systems, are implemented as user-space processes. Nano/picokernel architectures offer benefits such as improved security, scalability, and flexibility. However, they may also introduce overhead due to increased communication between user-space components and the kernel. Additionally, designing and implementing a nano/picokernel operating system requires careful consideration of performance, compatibility, and system complexity. Brief History of Operating Systems ================================== The development of operating systems can be summarized as follows: 1. Early computer systems had no operating systems and the programs had to directly control all necessary hardware components. 2. The first types of operating systems were the simple batch operating systems in which users had to submit their jobs on punched cards or tape. The computer operator grouped all the jobs in batches and stacked these on the main input device, which was a fast card reader or tape reader. One of the most important concepts for these systems was automatic job sequencing. An important performance metric for these systems was the CPU idle time, which affected the CPU utilization. The most important performance metric from the user point of view was the turnaround time, which is the interval from the submission of a job until the output was generated. 3. The next types of operating systems developed were batch systems with multiprogramming. These systems were capable of handling several programs active in memory at any time and required more advanced memory management. When a program stopped to wait for I/O in these systems, the OS was able to switch very rapidly from the currently executing program to the next. The short interval was called context switch time. Multiprogramming normally improves the processor and device utilization. 4. Time-sharing operating systems were the next important generation of systems developed. The most significant advantage of these systems was the capability to provide interactive computing to the users connected to the system. The basic technique employed on these systems was that the processor\'s time was uniformly shared by the user programs. The operating system provided CPU service during a small and fixed interval to a program and then switched to the next program. 5. Variations of multiprogramming operating systems were developed with more advanced techniques. These included improved hardware support for interrupt mechanisms and allowed implementation of better scheduling techniques based on priorities. Real-time operating systems were developed. 6. Advances in hardware and memory management techniques allowed development of operating systems with newer and more powerful features, such as paging and virtual memory, multi-level cache, and others. Most of the development of modern operating systems has focused on networking, distribution, reliability, protection, and security. Several widely used operating systems are available today: - Microsoft Windows, a family of systems that includes 98, Me, CE, 2000, XP, Vista, Windows 7, and others - Linux (Linus Torvalds, FSF GNU) - OSF-1 (OSF, DEC) - Solaris (Sun Microsystems) - IRIX (Silicon Graphics) - OS2 (IBM) - OS/390 (IBM) - VMS (Dec/Compaq/HP) - MacOS X (Apple) **Summary:** The two basic components of a computer system are the hardware and the software components. An operating system is a large and complex software component of a computer system that controls the major operations of user programs and manages all the hardware resources. The main type of system studied in this book is the general purpose operating system. This chapter has presented the fundamental concepts of operating systems. Discussions on the general structure, user interfaces, and functions of an operating system have also been presented. Two examples of well-known operating systems are Linux and Microsoft Windows. This chapter also described various views of the operating system, the high-level external view, also called the abstract machine view, and the low-level or internal view. The abstract machine view is seen by the programs that request some type of service from the operating system. The internal details of the OS are hidden below the interfaces. The internal view includes the components that represent the modules of the OS for carrying out various functions: the process manager, memory manager, resource manager, file manager, and device manager. The process manager is considered the most important component of the OS. 2. Processes Management and Threads =================================== Processes and threads are two important types of dynamic entities in a computer system. A process is basically a program in memory either in execution or waiting for CPU, I/O, or other service. Thus, a process is the fundamental computational unit that requests various types of services in the computer system. A process can contain one or more threads of execution. These two types of entities are handled by the process management module of the operating system. System resources are required by the processes and threads in order to execute. This chapter discusses how operating systems represent processes and threads, the various operating system interfaces, and the general principles involved in multiprogramming, which is the technique of supporting several processes in memory at the same time. Processes ========= A process is a program in execution, ready to execute, or one that has executed partially and is waiting for other services in the computer system. In simpler terms, a process is an instantiation of a program, or an execution instance of a program. A process is a dynamic entity in the system because it exhibits behavior (state changes), and is capable of carrying out some (computational) activity, whereas a program is a static entity. This is similar to the difference that exists between a class (a static entity) and an object (a dynamic entity) in object-oriented programming. Two basic types of processes are system processes and user processes. System processes execute operating system services, user processes execute application programs. The operating system (OS) manages the system hardware and provides various computing services for the processes. The OS hides from the user processes all details of the operation of the underlying hardware and how the various services are implemented. To accomplish this, several abstract models and views of the system are provided. A typical and simplified scenario of how the OS manages the various processes can be described as follows: processes request CPU and I/O services at various times and usually wait for these services. The OS maintains a waiting line or queue of processes for every one of these services. At some time instance, the process will be in a queue waiting for CPU service. At some other instance, the process will be in a different queue waiting for I/O service. When the process completes all service requests, it terminates and exits the system. Process management is one of the major functions of the operating system; it involves creating processes and controlling their execution. In most operating systems, several processes are stored in memory at the same time and the OS manages the sharing of one or more processors (CPUs) and other resources among the various processes. This technique implemented in the operating system is called multiprogramming. One of the requirements of multiprogramming is that the OS must allocate the CPUs and other system devices to the various processes in such a way that the CPUs and other devices are maintained busy for the longest total time interval possible, thus minimizing the idle time of these devices. If there is only one CPU in the computer system, then only one process can be in execution at any given time. Some other processes are ready and waiting for CPU service while other processes are waiting or receiving I/0 service. The CPU and the I/0 devices are considered active resources of the system because these resources provide some service to the various processes during some finite interval of time. Processes also request access to passive resources, such as memory. The operating system can be represented by an abstract machine view, in which the processes have the illusion that each one executes on its own machine. Using this abstraction, a process is defined as a computational unit with its own environment, and components that include a process identifier, address space, program code, data, and resources required. For every program that needs execution in the system, a process is created and is allocated resources (including some amount of memory). The address space of a process is the set of memory addresses that it can reference. Process States ============== The process manager controls execution of the various processes in the system. Processes change from one state to another during their lifetime in the system. From a high level of abstraction, processes exhibit their behavior by changing from one state to the next. The state changes are really controlled by the OS. For example, when the process manager blocks a process because it needs a resource that is not yet available, the process changes from the running state to the waiting for resource state. When a process is waiting for service from the CPU, it is placed in the ready queue and is in the ready state. In a similar manner, when a process is waiting for I/O service, it is placed in one of several I/O queues and it changes to a wait state. The OS interrupts a process when it requests a resource that is not available. If a process is interrupted while executing, the OS selects and starts the next process in the ready queue. During its lifetime, a process will be in one of the various states mentioned previously: - Created - Waiting for CPU (i.e., the process is ready) - Executing (i.e., receiving service from the CPU) - Waiting for I/O service (the process is blocked) - Receiving I/O service - Waiting for one or more passive resources - Interrupted by the OS - Terminated When a process executed, it changes the state, generally the state of process is determined by the current activity of the process. Each process may be in one of the following states: 1. New: The process is being created. 2. Running: The process is being executed. 3. Waiting: The process is waiting for some event to occur. 4. Ready: The process is waiting to be assigned to a processor. 5. Terminated: The Process has finished execution. Only one process can be running in any processor at any time, But many process may be in ready and waiting states. The ready processes are loaded into a ―ready queue‖. a. New -\>Ready: OS creates process and prepares the process to be executed, then OS moved the process into ready queue. b. Ready-\>Running: OS selects one of the Jobs from ready Queue and move them from ready to Running. c. Running-\>Terminated: When the Execution of a process has Completed, OS terminates that process from running state. Sometimes OS terminates the process for some other reasons including Time exceeded, memory unavailable, access violation, protection Error, I/O failure and soon. d. Running-\>Ready: When the time slot of the processor expired (or) If the processor received any interrupt signal, the OS shifted Running -\> Ready State. e. Running -\> Waiting: A process is put into the waiting state, if the process need an event occur (or) an I/O Device require. f. Waiting-\>Ready: A process in the waiting state is moved to ready state when the event for which it has been Completed. A state diagram represents the various states of a process and the possible transitions in the behavior of a process. Figure 2.1 shows the state diagram of a typical process. Each state is indicated by a rounded rectangle and the arrows connecting the states represent transitions from one state to the next. The small blue circle denotes that the state it points to is the initial state. In a similar manner, the state before the small gray circle is the last state in the behavior of a process. Normally, a process spends a finite time in any of its states. Figure 2.1 State diagram of a typical process. When a job arrives, and if there are sufficient resources (such as memory) available, a corresponding process is created. In a time-sharing system, when a user logs in, a new process is created. After being created, the process becomes ready and waits for CPU service. It eventually receives this service, then waits for I/O service, and at some later time receives I/O service. The process then goes back to the ready state to wait for more CPU service. The state in which a process is waiting for I/O service is normally called the blocked state. After satisfying all service requests, the process terminates. Another possible wait state is defined when the process is swapped out to disk if there is not sufficient memory. This means that the operating system can move a process from memory to disk and have the process wait in a suspended state; at some other time the process is moved back to memory. Process Descriptor ================== For every new process in the system, a data structure called the process descriptor, also known as a process control block (PCB), is created. It is on this data structure that the OS stores all data about a process. The various queues that the OS manipulates thus contain process descriptors or pointers to the process descriptors, not actual processes. A process descriptor represents a process in the system and when the process terminates, its descriptor is normally destroyed. For a user process, its owner is the user, for a system process, the owner is the system administrator or the system service that created the process. If a process creates another process, this second process is referred to as a child process. A process descriptor includes several data items or fields that will be defined in the next subsection. The most important of these data fields are as follows: 1. Process State: The State may be new, ready, running, and waiting, Terminated. 2. Program Counter: indicates the Address of the next Instruction to be executed. 3. CPU registers: registers include accumulators, stack pointers, General purpose Registers.... 4. CPU-Scheduling information: includes a process pointer, pointers to scheduling Queues, other scheduling parameters etc. 5. Memory management information: includes page tables, segmentation tables, value of base and limit registers. 6. Accounting Information: includes amount of CPU used, time limits, Jobs(or)Process numbers. 7. I/O Status Information: Includes the list of I/O Devices Allocated to the processes, list of open files. Concurrent process ================== Concurrent processing is a computing model in which multiple processors executes instructions simultaneously for better performance. Tasks are broken down into subtasks that are then assigned to separate processors to perform simultaneously, instead of sequentially as they would have to be carried out by a single processor. Concurrent processing is sometimes said to be synonymous with parallel processing. executed in parallel. Each of the concurrently executing sequential programs is called a process. Process execution, although concurrent, is usually not independent. Processes may affect each other\'s behavior through shared data, shared resources, communication, and synchronization. Fig 2.3: Concurrent process In figure (a) process1 starts its execution at time t0, process2 starts its execution only after process1 finished its execution, and process3 starts its execution only when process2 finished its execution. These process are said to be serial processes. In figure (b), the execution time of process1, process2, process3 are overlapped, so these are said to be concurrent processing. Thread ====== A process is divide into number of light weight process, each light weight process is said to be a Thread. A thread is a basic unit of execution within a process. That is are individual sequence of instructions that can be executed independently within a process. Threads share the process resources, such as memory and files and can communicate with each other more efficiently than separate processes. They allow for concurrent execution within a single process, enabling tasks to be performed simultaneously or in parallel. Eg: Word processor. Typing, Formatting, Spell check, saving are threads. Differences between Process and Thread ====================================== **Thread** -- ------------ Multithreading ============== A process is divided into number of smaller tasks each task is called a Thread. Number of threads within a Process execute at a time is called Multithreading. If a program, is multithreaded, even when some portion of it is blocked, the whole program is not blocked. The rest of the program continues working if multiple CPU's are available. Based on the functionality threads are divided into four categories: 1. One to one 2. One to Many 3. Many to one 4. Many to many  One to one: (One process one thread) In this approach, the process maintains only one thread, so it is called as single threaded approach. MS-DOS operating system supports this type of approach. One to Many :( One process, multiple threads) In this approach a process is divided into number of threads. The best example of this is JAVA run time environment. Many to one: (Multiple processes, one thread per process) An operating system support multiple user processes but only support one thread per process. Best example is UNIX. Many to many: ( Multiple processes, multiple threads per process) In this approach each process is divided into number of threads. Examples are Windows 2000, Solaris LINUX. There are two main ways to implement threads:  1. User Threads: Thread creation, scheduling, management happen in user space by Thread Library. User threads are faster to create and manage. This type of threads loaded entirely in user space, the kernel knows nothing about them. When threads are managed in user space, each process has its own private thread table. The thread table contains information like program counter, registers, state etc. When the thread is moved to ready state or blocked state, the information needed to restart it is stored in the thread table. User level threads allow each process to have its own scheduling algorithm. The entire process loaded in user space, so the process does not switch to the kernel mode to do thread management. User level threads can run on any operating system. When user level thread executes a system call, all the threads with in the process are blocked. Only a single thread with in a process can execute at a time, so multiprocessing is not implemented. 2. **Kernel Threads:** kernel creates, schedules, manages these threads. These threads are slower, manage. If one thread in a process blocked, all process needs not be blocked. In kernel level threads the kernel does total work of head movement. There is no thread table in each process. The kernel has a thread table that keeps track of all the threads in the system. When a thread wants to create a new thread or destroy any existing thread it makes call to the kernel, kernel then takes the action. The kernel thread table holds each thread register, state and other information. The information is the same as with user level threads, but it is now in the kernel instead of the user space. The kernel can simultaneously schedule a multiple threads from the same process on multiple processors. If a thread in a process is blocked, then the kernel can schedule another thread of the same process. It requires more cost for creating and destroying threads in kernel. The transfer of control from one thread to another within the same process requires a mode switch to the kernel. Figure 2.4: (a) Three processes each with one thread (b) One process with three threads  Figure 2.5: Threads and Processes Benefits of Threads =================== - It takes less time to create a new thread than a process - It takes less time to terminate a thread than a process - It takes less time to switch between two threads within the same process - Since threads within the same process share memory and files, they can communicate with each other without invoking the kernel. - Suspending a process involves suspending all threads of the process since all threads share the same address space. - Termination of a process, terminates all threads within the process All threads that belong to a process share the code and resources of the process, as illustrated in Figure 2.6. Multithreading - Operating system supports multiple threads of execution within a single process - MS-DOS supports a single thread - UNIX supports multiple user processes but only supports one thread per process - Windows 2000, Solaris, Linux, Mach, and OS/2 support multiple threads **Summary:** Processes and threads are the main concepts explained in this chapter. The process is the fundamental unit of computation. It is a dynamic entity, unlike a program, which is a static entity. The process descriptor is the main data structure that the OS uses to manipulate processes. This descriptor contains essential data about a process. A thread is a sequential flow of execution; it is also called a lightweight process and is a dynamic component of a process. The threads within a process share part of the code and resources of the process. A process goes through several possible states during its lifetime in the system. The operating system handles a process in such a way that it changes state until the process terminates. The state changes are shown in the process state diagram. Appendix B contains more detailed information on Java and POSIX threads. There are several queues created and managed by the operating system. Processes wait for service or for resources in queues. The various examples of queues include the ready queue, I/O queue, and input queue. Multiprogramming is a facility of the OS for supporting several processes in memory; this increases the CPU and device utilizations. Context switching is needed to change the CPU allocation from one process to another. 3. Synchronization Principles ============================= The focus of synchronization is the coordination of the activities of the active processes in the computer system. Processes need to be synchronized when they compete for shared resources or when they need to cooperate in carrying out their activities. The operating system incorporates a collection of mechanisms and tools for the coordination of the activities of multiple processes. The study of synchronization mainly includes the principles, techniques, and tools provided by the operating system. Basic Synchronization Principles ================================ Synchronization is the coordination of the activities of two or more processes that usually need to carry out the following activities: - Compete for resources in a mutually exclusive manner. - Cooperate in sequencing or ordering specific events in their individual activities. No Synchronization ================== When two or more processes execute and independently attempt to simultaneously share the same resources, their executions generally will not produce correct results. Since synchronization is absent, the results of these process executions depend on their relative speeds and on the order of use of the resources. A simple example is a global variable shared by several processes. One process increases the value of the global variable, while another is taking its value to add to a local variable. This leads to unpredictable results and is sometimes called a race condition. To avoid this problem, synchronization is used so that processes will be made to compete in some appropriate manner and ensure correct results. Mutual Exclusion ================ To solve the race condition problem when a group of processes are competing to use a resource, only one process must be allowed to access the shared resource at a time. In other words, two or more processes are prohibited from simultaneously or concurrently accessing a shared resource. When one process is using a shared resource, any other process that needs access to that resource is excluded from using it at the same time. This condition is called mutual exclusion. At any given time, only one process is allowed to access a shared resource; all other processes must wait. Critical Sections ================= A simple analogy to help understand the concept of a critical section is the example of a road intersection shown in Figure 3.1. Two vehicles, one moving on Road A and the other moving on Road B, are approaching the intersection. If the two vehicles reach the intersection at the same time, there will be a collision, which is an undesirable event. Figure 3.1 A simple analogy for a critical section: A road intersection. The road intersection is critical for both roads because it is part of Road A and also part of Road B, but only one vehicle should enter the intersection at any given time. Therefore, mutual exclusion should be applied on the road intersection. The part or segment of code in a process that accesses and uses a shared resource is called the critical section. Every process that needs to access a shared resource has its own critical section. Figure 3.2 shows two processes, Pl and P2, each with a critical section in which access to a global variable x is carried out.  Figure 3.2 Critical sections in processes. The critical section problem is to design a protocol that the processes can use to cooperate. Each process must request permission to enter its critical section. The section of code implementing this request is the entry section. The critical section may be followed by an exit section. The remaining code is the remainder section. To achieve mutual exclusion, the approach used is to coordinate the group of processes that access shared resources such that only one process can execute its critical section at any instant, and the other processes are excluded. The following conditions must be met for mutual exclusion on the critical sections: - Mutual exclusion: Only one process may be executing its critical section at any time. - Absence of starvation: Processes wait a finite time interval to enter their critical sections. - Absence of deadlock: Processes should not block each other indefinitely. - Progress: A process will take a finite time interval to execute its critical section. Approaches for Implementing Synchronization =========================================== There are several approaches for implementing solutions to the critical section problem. The most notable of the many algorithms that have been proposed for the solution to the critical section problem are Dekker\'s algorithm and Peterson\'s algorithm. **Peterson's solution:** Peterson solution is one of the solutions to critical section problem involving two processes. This solution states that when one process is executing its critical section then the other process executes the rest of the code and vice versa. Peterson solution requires two shared data items: 1. turn: indicates whose turn it is to enter into the critical section. If turn == i ,then process i is allowed into their critical section. 2. flag: indicates when a process wants to enter into critical section. When process i wants to enter their critical section, it sets flag\[i\] to true. **do {flag\[i\] = TRUE; turn = j;** while (flag\[j\] && turn == j); critical section flag\[i\] = FALSE; remainder section } while (TRUE); Synchronization hardware ============================================================================================================================== In a uniprocessor multiprogrammed system, mutual exclusion can be obtained by disabling the interrupts before the process enters its critical section and enabling them after it has exited the critical section. Disable interrupts Critical section Enable interrupts ===================================================== Once a process is in critical section it cannot be interrupted. This solution cannot be used in multiprocessor environment. since processes run independently on different processors. In multiprocessor systems, Testandset instruction is provided, it completes execution without interruption. Each process when entering their critical section must set lock, to prevent other processes from entering their critical sections simultaneously and must release the lock when exiting their critical sections. **do { acquire lock critical section release lock remainder section** } while (TRUE); =============== A process wants to enter critical section and value of lock is false then testandset returns false and the value of lock becomes true. Thus for other processes wanting to enter their critical sections testandset returns true and the processes do busy waiting until the process exits critical section and sets the value of lock to false. ** Definition:** **boolean TestAndSet(boolean&lock){ boolean temp=lock;** **Lock=true; return temp;** **}** Algorithm for TestAndSet do{ while testandset(&lock) //do nothing //critical section lock=false remainder section }while(TRUE); =============================================================================================================================== 4. Deadlocks ============ Processes that are executing concurrently in a multiprogramming environment may often reach a state of starvation or deadlock. Deadlock may occur when the operating system is attempting to allocate resources to a set of processes requesting these resources. The basic principles of deadlock and the most common approaches used to deal with it-deadlock prevention, deadlock avoidance, and deadlock detection and recovery-are discussed in this chapter. The five dining philosophers-a classical problem used to explain synchronization and deadlock principles-illustrates why and how deadlock occurs as well as deadlock solutions. Several different simulation models of the dining philosophers problem are presented to demonstrate deadlock and solutions for preventing it. Basic Principles of Deadlock ============================ Deadlock is the state of indefinite waiting that processes may reach when competing for system resources or when attempting to communicate. When a process requests a resource to the operating system, it normally waits for the resource to become available. A process acquires a resource when the operating system allocates the resource to the process. After acquiring a resource, the process holds the resource. The resources of concern are those that will normally not be shared, such as a printer unit, a magnetic tape unit, and a CD unit. These kinds of resources can only be acquired in a mutually exclusive manner. During its normal execution, a process usually needs access to one or more resources or instances of a resource type. The following sequence of steps describes how a process acquires and uses resources: 1. Request one or more resource instances. 2. Acquire the resource instances if they are available. The operating system allocates an available resource when it is requested by a process. If the resource instances are not available, the process has to wait until the resource instances become available. 3. Use the resource instance for a finite time interval. 4. Release the resource instances. The operating system deallocates the resource instances and makes them available for other requesting processes. Suppose there are two processes, Pl and P2, and two resource types, RI and R2. The processes are attempting to complete the following sequence of steps in their executions: 1. Process Pl requests resource RI. 2. Process P2 requests resource R2. 3. Process Pl acquires resource Rl. 4. Process P2 acquires resource R2. 5. Process Pl requests resource R2. 6. Process Pl is suspended because resource R2 is not available. 7. Process P2 requests resource RI. 8. Process P2 is suspended because resource RI is not available. 9. The executions of both processes have been suspended. The previous discussion is a simple example of deadlock because there are two processes each holding a resource but requesting a second resource that the other process holds. In this state, both processes are blocked indefinitely, waiting for each other to release a resource. If the operating system does not avoid, prevent, or detect deadlock and recover, the deadlocked processes will be blocked forever and the resources that they hold will not be available for other processes. Resource Allocation Graph ========================= The resource allocation graph is a directed graph that is very useful in showing the state of a system. The two types of nodes that are included in the graph represent a set of processes, P = {Pl, P2, P3, , Pn}, and a set of resource types, R = {Rl, R2, R3, , Rm}. In the graph, a process is drawn as an oval or ellipse, and the resources are shown as rectangular boxes. The graph is an abstract description of the state of the system with respect to processes and resources. There are two types of edges drawn as arrows. An edge from a process to a resource type indicates that the process is requesting one instance of the resource type. An edge from a resource type to a process indicates that one instance of the resource type has been allocated to the process. With these elements, the graph shows the processes that are either requesting resources and/or have acquired resources. The graph also shows the resources available and the ones that have been allocated. Figure 7.1 shows a resource allocation graph with the two processes Pl and P2 in a deadlock state. The two resource types involved, Rl and R2, are shown with one instance each. The resource allocation graph is a standard type of diagram used to represent deadlock or the potential for deadlock. The graph shows that process Pl has acquired (holds) an instance of resource Rl and is requesting an instance of resource R2. Process P2 has acquired (holds) an instance of resource R2 and is requesting an instance of resource Rl. Each process is waiting for the other to release the resource it needs, events that will never occur. A more complex example would include a larger number of processes, resource types, and instances of each resource type. Figure 4.1 shows only one instance of each resource type. Figure 4.1: A resource allocation graph showing the deadlock of two processes. Conditions for the Existence of Deadlock ======================================== Deadlock is possible if the following four conditions are present simultaneously: 1. Mutual exclusion: Only one process can access a resource at a time and the process has exclusive use of the resource. 2. Hold and wait: A process has acquired one or more resources (already holds these resources) and is requesting other resources. 3. Circular wait: A condition that is represented by a closed path (cycle) of resource allocations and requests. For example, process Pl holds resource Rl and is requesting resource R2; process P2 holds resource R2 and is requesting resource R3; process.PJ holds resource R3 and is requesting resource Rl (held by Pl). This situation can include more than three processes and resource types. 4. No preemption: A process cannot be interrupted and forced to release resources. These conditions are necessary but not sufficient for deadlock to occur. This means that even if the four conditions are present, deadlock may not actually occur. The presence of the four conditions implies that there is potential for deadlock. The examples that follow illustrate several system states represented by resource allocation graphs. These are used to analyze the existence of the conditions for deadlock. There are three processes (Pl, P2, and.PJ) and three resource types (Rl, R2, and R3). As shown in Figure 4.2, process Pl has acquired an instance of resource type Rl; so Pl holds a unit of resource Rl. Process P2 has acquired an instance of resource type R2. Process P3 has acquired an instance of resource type R3. Process Pl is requesting (and waiting for) an instance of resource type R2. Process P2 is requesting an instance of resource type R3. In the state shown, the system is not in deadlock. Process P3 is not in a hold and wait condition, although Pl and P2 are. The processes are not in a circular wait condition.  Figure 4.2 Resource allocation graph with three processes. Because there are not sufficient resources for the three processes to proceed concurrently in the system state described, we must find the order of how processes can execute. Process P3 is not requesting any resources; consequently, P3 can proceed immediately. The following sequence of events describes how processes Pl, P2, and P3 can execute: 1. Process P3 starts executing using resource R3. 2. After a finite interval, process P3 releases resource R3. 3. Process P2 acquires resource R3. 4. Process P2 starts executing using resources R2 and R3. 5. After a finite interval, process P2 releases resources R2 and R3. 6. Process Pl acquires resource R2. 7. Process Pl starts executing using resources Rl and R2. 8. After a finite interval, process Pl releases resources Rl and R2. Figure 4. 3 shows an example of a system state that is slightly different than the one shown in the previous figure. The main differences are that process P3 is requesting resource Rl and there are two instances of resource Rl. In this example, process P3 can start without waiting because there is an instance of resource Rl available that it can immediately acquire. There is no deadlock in the system and the sequence of events is very similar to the one discussed previously. Figure 4.4 illustrates the presence of a cycle in a resource allocation graph with three processes. As in the previous example, process P3 requests an instance of resource type Rl and assumes one instance is immediately allocated to P3, since the system has two instances of resource Rl. Process P2 is also requesting an instance of resource Rl, and Figure 4.3 Another system state with three processes.  Figure 4.4 A cycle in a graph with three processes. P2 must wait for the availability of resource Rl. The following cycle can be identified in the graph: Pl\-\--+R2\-\--+ P2\-\--+Rl\-\--+Pl. There is no deadlock in this example because process P3 can proceed and eventually release resources Rl and R3. Process P2 can then acquire resource R3, for which it was waiting. In the system state shown in Figure 4.5, there is deadlock because the three processes are blocked indefinitely, waiting for each other to release a resource. The four conditions for deadlock are true. Processes Pl, P2, and P3 are in hold and wait because each is holding a resource and waiting for another resource. The main difference with the previous example is that there is only one instance of resource type Rl, which means that process P3 must wait for resource Rl. Figure 4.5 Resource allocation graph with a cycle. In Figure 4.5, the circular wait condition is true for the three processes because there is a cycle in the graph following the arrows that represent resource allocations and resource requests, and there is a single instance of each resource type. Deadlock can be considered worse than starvation: There is a collection of processes in indefinite waiting, and these processes are holding system resources. Conditions for Deadlock ======================= Deadlock can be defined as the permanent blocking of a set of processes that either compete for system resources or communicate with each other. A set of processes is deadlock when each process in the set is blocked awaiting an event (typically the freeing up of some requested resources) that can only be triggered by another blocked process in the set. Deadlock is permanent when none of the events is ever triggered. Unlike other problems in concurrent process management, there is no efficient solution in the general case. A common example is the traffic deadlock. Three conditions for Deadlock ============================= Three conditions of policy must be present for a deadlock to be possible: 1. Mutual exclusion. Only one process may use a resource at a time. No process may access a resource unit that has been allocated to another process.62 2. Hold and Wait. A process may hold allocated resources while awaiting assignment of other resources. 3. No preemption. No resource can be forcibly removed from a process holding it. In many ways these conditions are quite desirable. For example, mutual exclusion is needed to ensure consistency of results and the integrity of a database. Similarly, preemption should not be done arbitrarily. For example, when data resources are involved, preemption must be supported by a rollback recovery mechanism, which restores a process and its resources to a suitable previous state from which the process can eventually repeat its actions. Deadlock can occur with these three conditions but might not exist with just these three conditions. For deadlock to actually take place, a fourth condition is required. 4. Circular wait. A closed chain of processes exists, such that each process holds at least one resource needed by the next process in the chain. The first three conditions are necessary but not sufficient for a deadlock to exist. The fourth condition is, actually, a potential consequence of the first three. That is, given that the first three conditions exist, a sequence of events may occur that lead to an unresolved circular wait. The unresolved circular wait is in fact the definition of deadlock. The circular wait listed as condition 4 is unresolvable because the first three conditions hold. Thus, the four conditions, taken together, constitute necessary and sufficient conditions for deadlock. Deadlock Prevention =================== The strategy of deadlock prevention is, simply to design a system in such a way that the possibility of deadlock is excluded. We can view deadlock prevention methods as falling into two classes. An indirect method of deadlock prevention is to prevent the occurrence of one of the three necessary conditions listed previously (items 1 through 3). A direct method of deadlock prevention is to prevent the occurrence of a circular wait (item 4). We now examine techniques related to each of the four conditions. **Mutual Exclusion:** In general, the first of the four listed conditions cannot be disallowed. If access to a resource requires mutual exclusion, then mutual exclusion must be supported by the operating system. Some resources, such as files, may allow multiple accesses for reads but only exclusive access for writes. Even in this case, deadlock can occur if more than one process requires write permission. **Hold and Wait:** The hold-and-wait condition can be prevented by requiring that a process request all of its required resources at one time and blocking the process until all requests can be granted simultaneously. This approach is inefficient in two ways. First, a process may be held up for a long time waiting for all of its resource requests to be fulfilled, when in fact it could have proceeded with only some of the resources. Second, resources allocated to a process may remain63 unused for a considerable period during which time they are denied to other processes. Another problem is that a process may not know in advance all of the resources that it will require. There is also the practical problem created by the use of modular programming or a multithreaded structure for an application. An application would need to be aware of all resources that will be required at all levels or in all modules to make the simultaneous request. **No preemption:** This condition can be prevented in several ways. First, if a process holding certain resources is denied a further request, that process must release its original resources and, if necessary, request them again together with the additional resource. Alternatively, if a process requests a resource that is currently held by another process, the operating system may preempt the second process and require it to release its resources. This latter scheme would prevent deadlock only if no two processes possessed the same priority. This approach is practical only when applied to resources whose state can be easily saved and restored later, as is the case with a processor. **Circular wait:** The circular wait condition can be prevented by defining a linear ordering of resource types. If a process has been allocated resources of type R, then it may subsequently request only resources of types following R in the ordering. **Deadlock Avoidance:** An approach to solving the deadlock problem that differs subtly from deadlock prevention is deadlock avoidance. In deadlock prevention, we constrain resource requests to prevent at least one of the four conditions of deadlock. This is either done indirectly, by preventing one of the three necessary policy conditions (mutual exclusion, hold and wait, no preemption), or directly, by preventing circular wait. This leads to inefficient use of resources and inefficient execution of processes. Deadlock avoidance, on the other hand, allows the three necessary conditions but makes judicious choices to assure that the deadlock point is never reached. As such, avoidance allows a more concurrency than prevention. With deadlock avoidance, a decision is made dynamically whether the current resource allocation request will, if granted, potentially lead to a deadlock. Deadlock avoidance thus requires knowledge of future process resource requests. **Deadlock Detection:** Deadlock prevention strategies are very conservative. They solve the problem of deadlock by limiting access to resources and by imposing restrictions on processes. At the opposite extreme, deadlock detection strategies do not limit resource access or restrict process actions. With deadlock detection, requested resources are granted to processes whenever possible. Periodically, the operating system performs an algorithm that allows it to detect the circular wait condition described earlier in condition (4). 5. File Management ================== 5.1 File system --------------- The file system is the most visible aspect of an operating system. It provides the mechanism for on-line storage of and access to both data and programs of the operating system and all the users of the computer system. The file system consists of two distinct parts: a collection of files, each storing related data, and a directory structure, which organizes and provides information about all the files in the system. **File Concept:** File management is one of the most visible services of an operating system. Computer can store information in several different physical forms; magnetic tape, disk, optical disk are the most common forms. Each of these devices has its own characteristics and physical organization. The operating system abstracts from the physical properties of its storage devices to define a logical storage unit, the file. Files are mapped by the operating system onto physical devices. These storage devices are usually nonvolatile, so the contents are persistent through power failures and system reboots. A file is a named collection of related information that is recorded on secondary storage. data cannot be written to secondary storage unless they are within a file. Commonly, files represent programs (both source and object forms) and data. Data files may be numeric, alphabetic, alphanumeric, or binary. Files may be free form, such as text files, or may be formatted rigidly. In general, a file is a sequence of bits, bytes, lines, or records, the meaning of which is defined by the file\'s creator and user. The information in a file is defined by its creator. Many different types of information may be stored in a file---source programs, object programs, executable programs, numeric data, text, payroll records, graphic images, sound recordings, and so on. A file has a certain defined structure, which depends on its type. A text file is a sequence of characters organized into lines (and possibly pages). A source file is a sequence of subroutines and functions, each of which is further organized as declarations followed by executable statements. An object file is a sequence of bytes organized into blocks understandable by the system\'s linker. An executable file is a series of code sections that the loader can bring into memory and execute. 5.2 File Attributes ------------------- A file is named, for the convenience of its human users, and is referred to by its name. A name is usually a string of characters, such as ‗exm.c'. Some systems differentiate between uppercase and lowercase characters in names, whereas other systems do not. When a file is named, it becomes independent of the process, the user, and even the system that created it. The information about all files is kept in the directory structure, which also resides on secondary storage. A file has certain other attributes, which vary from one operating system to another but typically consist of these: - Name: The symbolic file name is the only information kept in human readable form. - Identifier: This unique tag, usually a number, identifies the file within the file system; it is the non human-readable name for the file. - Type: This information is needed for those systems that support different types of files. - Location: This information is a pointer to a device and to the location of the file on that device. - Size: The current size of the file (in bytes, words, or blocks) and possibly the maximum allowed size are included in this attribute. - Protection: Access-control information determines who can do reading, writing, executing, and so on. - Time, date, and user identification: This information may be kept for creation, last modification, and last use. These data can be useful for protection, security, and usage monitoring. 5.3 Operations on Files ----------------------- A file is an abstract data type. The basic operation performed on files are create file, write to a file, read a file, reposition a file, delete a file. The operating system can provide system calls to perform all these operations. 1. Creating a file: Two steps are necessary to create a file. First, space in the file system must be found for the file. Second, an entry for the new file must be made in the directory. The directory entry records the name of the file, its location in the file system, and possibly other information. 2. Writing a file: To write a file, we make a system call specifying both the name of the file and the information to be written to the file. Given the name of the file, the system searches the directory to find the file\'s location. The directory entry will need to store a pointer to the current end of the file. Using this pointer the address of the next block can be computed and the information can be written. The write pointer must be updated. 3. Reading a file: To read from a file, we use a system call that specifies the name of the file and memory location where the next block of the file should be put. Again the directory is searched for the associated directory entry. And again the directory will need a pointer to the next block to be read. Once that block is read , the pointer is updated. A given process is usually only reading or writing a given file, and the current operation location is kept as a per-process current-file-position pointer. Both the read and write operations use this same pointer, saving space and reducing the system complexity. 4. Repositioning within a file: The directory is searched for the appropriate entry, and the current file-position pointer is set to a given value (given position). Repositioning within a file need not involve any actual I/O. This file operation is also known as files seek. 5. Deleting a file: To delete a file, we search the directory for the named file. Having found the associated directory entry, we release all file space, so that it can be reused by other files, and erase the directory entry. Folders ======= An important attribute of the folder is the name given to it. Typically, a folder may contain files and other folders (commonly called subfolders or subdirectories). This results in a tree structure of folders and files. In Figure 6.2, folder abc contains folder def and file Al. Folder def contains files Bl and B2. Pathnames ========= The pathname of a file specifies the sequence of folders users must traverse to travel down the tree to the file. Thus, the pathname for file B2 is abc/def/B2. This pathname actually describes the absolute path of the file, which is the sequence of folders users must travel from the root of the tree to the desired file. A relative path describes the sequence of folders users must traverse starting at some intermediate place on the absolute path.  Figure 6.2: Tree structure of folders and files. Figure 6.3: Legal and illegal tree structures. The absolute path provides a unique identification for a file. Two different files can have the same filename as long as the resulting pathnames are unique. Thus two different folders can have a file named Bl, but there cannot be two files named Bl in the same folder, as shown in Figure 6.3. This pure tree structure is highly restrictive. Modern systems also support a mechanism that allows a file to appear to be in a different part of the tree structure than where it actually resides. This is called a Shortcut on Windows and a Symbolic Link on Unix/Linux. In Figure 6.4, file B2 appears to reside in folder abc (as well as folder def, where it truly resides).  Figure 6.4 Example of a symbolic link. Access Methods ============== An access method describes the manner and mechanisms by which a process accesses the data in a file. There are two common access methods: Sequential Random (or direct) In the sequential access method, the file is read or written sequentially, starting at the beginning of the file and moving to the end. In the random access method, the application may choose to access any part of the file at any time. It is important to understand that the access method describes how the data is accessed and used. It has nothing to do with how the data has been stored in the file. A good analogy is a music CD. Users can choose to play the music tracks in order (sequentially) or they can choose shuffle play and the tracks will be played in a random order. The choice of how to access the tracks has no effect on how the tracks were recorded on the CD. Streams, Pipes, and I/0 Redirection =================================== A stream is the flow of data bytes, one byte after another, into the process (for reading) and out of the process (for writing). This concept applies to sequential access and was originally invented for network I/0, but several modern programming environments (e.g., Java and the Windows.Net framework) have also incorporated it. A pipe is a connection that is dynamically established between two processes. When a process reads data, the data will come from another process rather than from a file. Thus, a pipe has a process at one end that is writing to the pipe and another process reading data at the other end of the pipe. It is often the situati