Operating System Concepts and Mechanisms

Posted on Dec 17, 2024 in Computers

Operating System

An operating system (OS) is the program that, after being initially loaded into the computer by a boot program, manages all of the other application programs in a computer. The application programs make use of the operating system by making requests for services through a defined application program interface (API). In addition, users can interact directly with the operating system through a user interface, such as a command-line interface (CLI) or a graphical UI (GUI). The operating system manages a computer’s software and hardware resources, including:

• Input devices such as a keyboard and mouse.
• Output devices such as display monitors and printers.
• Network devices such as modems, routers, and network connections.
• Storage devices such as internal and external drives.

System Calls

System calls provide an interface to the services made available by an operating system. These calls are generally available as routines written in C and C++, although certain low-level tasks. Once the two file names are obtained, the program must open the input file and create the output file. Each of these operations requires a system call. There are also possible error conditions for each operation. When the program tries to open the input file, it may find that there is no file of that name or that the file is protected against access. After the entire file is copied, the program may close both files (another system call), write a message to the console or window (more system calls), and finally terminate normally (the final system call). Frequently, systems execute thousands of system calls per second.

Types of System Calls

System calls can be grouped roughly into six major categories:

• Process control
• File manipulation
• Device manipulation
• Information maintenance
• Communication
• Protection

Operating System Structure

A system as large and complex as a modern operating system must be engineered carefully if it is to function properly and be modified easily. A common approach is to partition the task into small components rather than have one monolithic system. Each of these modules should be a well-defined portion of the system, with carefully defined inputs, outputs, and functions. These components are interconnected and melded into a kernel.

Layered Approach

With proper hardware support, the OS can be broken into pieces that are smaller and more appropriate than those allowed by the original MS-DOS and UNIX systems. The OS can then retain much greater control over the computer and over the applications that make use of that computer. Implementers have more freedom in changing the inner workings of the system and in creating modular operating systems. Under a top-down approach, the overall functionality and features are determined and are separated into components. Information hiding is also important because it leaves programmers free to implement the low-level routines as they see fit, provided that the external interface of the routine stays unchanged.

Components of OS

A computer system can be divided roughly into four components: the hardware, the operating system, the application programs, and the users. The hardware – the Central Processing Unit (CPU), the memory, and the Input/Output devices – provides the basic computing resources for the system. The application programs – such as word processors, spreadsheets, compilers, and Web browsers – define the ways in which these resources are used to solve users’ computing problems. The operating system controls the hardware and coordinates its use among the various application programs for the various users. We can also view a computer system as consisting of hardware, software, and data. The operating system provides the means for proper use of these resources in the operation of the computer system. Operating systems have two viewpoints: that of the user and that of the system.

Functions of OS

An Operating System acts as a communication bridge (interface) between the user and computer hardware. The purpose of an operating system is to provide a platform on which a user can execute programs in a convenient and efficient manner. Functions are specified below:

1. Processor Management

   A program does nothing unless its instructions are executed by a CPU. A program in execution is a process. A process needs certain resources – including CPU time, memory, files, and I/O devices to accomplish its task. These resources are either given to the process when it is created or allocated to it while it is running. The operating system is responsible for the following activities in connection with process management:

   • Scheduling processes and threads on the CPUs
   • Creating and deleting both user and system processes
   • Suspending and resuming processes
   • Providing mechanisms for process synchronization
   • Providing mechanisms for process communication

2. Memory Management

   For a program to be executed, it must be mapped to absolute addresses and loaded into memory. As the program executes, it accesses program instructions and data from memory by generating these absolute addresses.

   The operating system is responsible for the following activities in connection with memory management:

   • Keeping track of which parts of memory are currently being used and by whom
   • Deciding which processes (or parts thereof) and data to move into and out of memory
   • Allocating and de-allocating memory space as needed

3. Storage Management

   The operating system provides a uniform, logical view of information storage. The operating system abstracts from the physical properties of its storage devices to define a logical storage unit that is the file. The operating system maps files onto physical media and accesses these files via the storage devices.

   3.1 File-System Management

   It is one of the most visible components of an operating system. Computers can store information on several different types of physical media, making them easier to use.

   3.2 Mass-Storage Management

   The main memory is too small to accommodate all data and programs, and because the data that it holds are lost when power is lost, the computer system must provide secondary storage to back up main memory.

   3.3 Caching

   Cache is a high-speed memory with a limited size which locates in between the position of RAM and CPU registers. Internal programmable registers, such as index registers, provide a high-speed cache for main memory.

4. Protection and Security

   Protection, then, is any mechanism for controlling the access of processes or users to the resources defined by a computer system. This mechanism must provide means to specify the controls to be imposed and means to enforce the controls.

   Protection can improve reliability by detecting latent errors at the interfaces between component subsystems. Early detection of interface errors can often prevent contamination of a healthy subsystem by another subsystem that is malfunctioning.

5. Device Management

   An Operating System manages device communication via their respective drivers. It performs the following activities for device management.

   • Keeps tracks of all devices connected to the system.
   • Designates a program responsible for every device known as the Input/output controller.
   • Decides which process gets an efficient way.
   • De-allocates devices when they are no longer required.

6. Control over system performance

   Monitors overall system health to help improve performance. Records the response time between service requests and system response. Improves the performance by providing important information needed to troubleshoot problems.

   (7) Coordination between other software and users

   Operating systems also coordinate and assign interpreters, compilers, assemblers, and other software to the various users of the computer systems.

Operating System Operations

Modern operating systems are interrupt-driven. If there are no processes to execute, no I/0 devices to service, an operating system will sit quietly, waiting for something to happen. Events are almost always signaled by the occurrence of an interrupt or a trap. (is a software-generated interrupt caused either by an error or by a specific request from a user program that an operating system service be performed. For each type of interrupt, separate segments of code in the operating system determine what action should be taken.

Dual-Mode Operation

The proper execution of the operating system must be able to distinguish between the execution of operating-system code and user-defined code. The approach taken by most computer systems is to provide hardware support that allows us to differentiate among various modes of execution. we need two separate modes of operation: user mode and kernel mode (supervisor mode, system mode). A bit, called the mode bit, is added to the hardware of the computer to indicate the current mode: kernel(0) or user(1). With the mode bit we are to distinguish between a task that is executed on behalf of the operating system and one that is executed on behalf of user systems.

Evolution of OS

The evolution of OS is directly dependent on the development of computer systems and how users use them. The following specifications are the computing systems through the past 75 years in the timeline.

Early Evolution

• 1945: ENIAC, Moore School of Engineering, University of Pennsylvania.
• 1949: EDSAC and EDVAC
• 1949: BINAC – a successor to the ENIAC
• 1951: UNIVAC by Remington
• 1952: IBM 701
• 1956: The interrupt
• 1954-1957: FORTRAN was developed

OSs – Late 1950s

By the late 1950s OSs were well improved and started supporting following usages:

• It was able to perform Single stream batch processing.
• It could use Common, standardized, input/output routines for device access.
• Program transition capabilities to reduce the overhead of starting a new job were added.
• Error recovery to clean up after a job terminated abnormally was added.
• Job control languages that allowed users to specify the job definition and resource requirements were made possible.

OSs – In 1960s

• 1961: The dawn of minicomputers
• 1962: Compatible Time-Sharing System (CTSS) from MIT
• 1963: Burroughs Master Control Program (MCP) for the B5000 system
• 1964: IBM System/360
• 1960s: Disks became mainstream
• 1966: Minicomputers got cheaper, more powerful, and really useful.
• 1967-1968: Mouse was invented.
• 1964 and onward: Multics
• 1969: The UNIX Time-Sharing System from Bell Telephone Laboratories.

OS Features by 1970s

• Multi-User & Multi-tasking was introduced.
• Dynamic address translation hardware and Virtual machines came into the picture.
• Modular architectures came into existence.
• Personal, interactive systems came into existence.

after 1970

• 1971: Intel announces the microprocessor
• 1972: IBM comes out with VM: the Virtual Machine OS
• 1973: UNIX 4th Edition is published
• 1973: Ethernet
• 1974 The Personal Computer Age begins
• 1974: Gates and Allen wrote BASIC for the Altair
• 1976: Apple II
• August 12, 1981: IBM introduces the IBM PC
• 1983 Microsoft begins work on MS-Windows
• 1984 Apple Macintosh comes out
• 1990 Microsoft Windows 3.0 comes out
• 1991 GNU/Linux
• 1992 The first Windows virus comes out
• 1993 Windows NT
• 2007: iOS
• 2008: Android

Unit 2

Process State

As a process executes, it changes state. The state of a process is defined in part by the current activity of that process. Each process may be in one of the following states:

• New: The process is being created.
• Running: Instructions are being executed.
• Waiting: The process is waiting for some event to occur (such as an I/0 completion or reception of a signal).
• Ready: The process is waiting to be assigned to a processor.
• Terminated: The process has finished execution.

It is important to realize that only one process can be running on any processor at any instant.

Process Control Block

Each process is represented in the operating system by a Process Control Block (PCB) – also called a task control block. It contains many pieces of information associated with a specific process, including these:

• Process state: The state may be new, ready running, waiting, halted, and so on.
• Program counter: The counter indicates the address of the next instruction to be executed for this process.
• CPU registers: The registers vary in number and type, depending on the computer architecture. They include accumulators, index registers, stack pointers, and general-purpose registers, plus any condition-code information.
• Along with the program counter, this state information must be saved when an interrupt occurs, to allow the process to be continued correctly afterward. (diagram below)
• CPU-scheduling information: This information includes a process priority, pointers to scheduling queues, and any other scheduling parameters.
• Memory-management information: This information may include such information as the value of the base and limit registers, the page tables, or the segment tables, depending on the memory system used by the operating system.
• Accounting information: This information includes the amount of CPU and real time used, time limits, account numbers, job or process numbers, and so on.
• I/O status information: This information includes the list of I/O devices allocated to the process, a list of open files, and so on.

Synchronization

Communication between processes takes place through calls to send() and receive() primitives. There are different design options for implementing each primitive.

Message passing may be either blocking or non-blocking also known as synchronous and asynchronous.

• Blocking send: The sending process is blocked until the message is received by the receiving process or by the mailbox.
• Non-blocking send: The sending process sends the message and resumes operation.
• Blocking receive: The receiver blocks until a message is available.
• Non-blocking receive: The receiver retrieves either a valid message or a null.

Context Switch

Switching the CPU to another process requires performing a state save of the current process and a state restore of a different process. This task is known as a context switch. When a context switch occurs, the kernel saves the context of the old process in its PCB and loads the saved context of the new process scheduled to run. Context-switch time is pure overhead, because the system does no useful work while switching. Its speed varies from machine to machine, depending on the memory speed, the number of registers that must be copied, and the existence of special instructions (such as a single instruction to load or store all registers). Typical speeds are a few milliseconds. Context-switch times are highly dependent on hardware support.

Process Scheduling

The objective of multiprogramming is to have some process running at all times, to maximize CPU utilization. The objective of time-sharing is to switch the CPU among processes so frequently that users can interact with each program while it is running. To meet these objectives, the process scheduler selects an available process (possibly from a set of several available processes) for program execution on the CPU. For a single-processor system, there will never be more than one running process. If there are more processes, the rest will have to wait until the CPU is free and can be rescheduled.

Scheduling Queues

As processes enter the system, they are put into a job queue, which consists of all processes in the system. The processes that are residing in main memory and are ready and waiting to execute are kept on a list called the ready queue. This queue is generally stored as a linked list. A ready-queue header contains pointers to the first & final PCBs in the list. Each PCB includes a pointer field that points to the next PCB in the ready queue.

Schedulers

The long-term scheduler, or job scheduler, selects processes from this pool and loads them into memory for execution. The short-term scheduler, or CPU scheduler, selects from among the processes that are ready to execute and allocates the CPU to one of them.

The primary distinction between these two schedulers lies in the frequency of execution. The short-term scheduler must select a new process for the CPU frequently. A process may execute for only a few milliseconds before waiting for an I/0 request. Often, the short-term scheduler executes at least once every 100 milliseconds. Because of the short time between executions, the short-term scheduler must be fast.

Operations on Processes

The processes in most systems can execute concurrently, and they may be created and deleted dynamically. Thus, these systems must provide a mechanism for process creation and termination.

• Process Creation

  A process may create several new processes, via a create-process system call, during the course of execution. The creating process is called a parent process, and the new processes are called the children of that process. Each of these new processes may in turn create other processes, forming a tree of processes.

• Process Termination

  A process terminates when it finishes executing its final statement and asks the operating system to delete it by using the exit() system call. Termination can occur in other circumstances as well. A process can cause the termination of another process via an appropriate system call (for example, TerminateProcess () in Win32). Usually, such a system call can be invoked only by the parent of the process that is to be terminated

Buffering

Whether communication is direct or indirect, messages exchanged by communicating processes reside in a temporary queue. Basically, such queues can be implemented in three ways:

• Zero capacity: The queue has a maximum length of zero; thus, the link cannot have any messages waiting in it. the sender must block until the recipient receives the message.
• Bounded capacity: The queue has finite length n; thus, at most n messages can reside in it. If the queue is not full when a new message is sent, the message is placed in the queue and the sender can continue execution without waiting. The link’s capacity is finite, however. If the link is full, the sender must block until space is available in the queue.
• Unbounded capacity: The queue’s length is potentially infinite; thus, any number of messages can wait in it. The sender never blocks. The zero-capacity case is sometimes referred to as a message system with no buffering; the other cases are referred to as systems with automatic buffering.

Inter-process Communication

Processes executing concurrently in the operating system may be either independent processes or cooperating processes. A process is independent if it cannot affect or be affected by the other processes executing in the system. Any process that does not share data with any other process is independent. A process is cooperating if it can affect or be affected by the other processes executing in the system. Clearly, any process that shares data with other processes is a cooperating process

• Information sharing: Since several users may be interested in the same piece of information we must provide an environment to allow concurrent access to such information.
• Computation speedup: If we want a particular task to run faster, we must break it into subtasks, each of which will be executing in parallel with the others. Notice that such a speedup can be achieved only if the computer has multiple processing elements (such as CPUs or I/O channels)
• Modularity: It has to construct the system in a modular fashion, dividing the system functions into separate processes or threads.
• Convenience: Even an individual user may work on many tasks at the same time. For instance, a user may be editing, printing, and compiling in parallel.

Cooperating processes require an Inter Process Communication (IPC) mechanism that will

→allow them to exchange data and information. There are two fundamental models of inter-process communication: (1) shared memory and (2) message passing. In the shared-memory model, a region of memory that is shared by cooperating processes is established. Processes can then exchange information by reading and writing data to the shared region. In the message passing model, communication takes place by means of messages exchanged between the cooperating processes.

Process: Scheduling Criteria

Different CPU-scheduling algorithms have different properties, and the choice of a particular algorithm may favor one class of processes over another. Many criteria have been suggested for comparing CPU-scheduling algorithms. Which characteristics are used for comparison can make a substantial difference in which algorithm is judged to be best. The criteria include the following:

• CPU utilization: We want to keep the CPU as busy as possible. Conceptually, CPU utilization can range from 0 to 100 percent. In a real system, it should range from 40 percent (for a lightly loaded system) to 90 percent (for a heavily used system).

• Throughput: If the CPU is busy executing processes, then work is being done. One measure of work is the number of processes that are completed per time unit, called throughput. For long processes, this rate may be one process per hour; for short it may ten processes per second.

• Turnaround time: From the point of view of a particular process, the important criterion is how long it takes to execute that process. The interval from the time of submission of a process to the time of completion is the turnaround time. Turnaround time is the sum of the periods spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/0.

• Waiting time: The CPU-scheduling algorithm does not affect the amount of time during which a process executes or does I/0; it affects only the amount of time that a process spends waiting in the ready queue. Waiting time is the sum of the periods spent waiting in the ready queue.

• Response time: In an interactive system, turnaround time may not be the best criterion. another measure is the time from the submission of a request until the first response is produced. This measure, called response time, is the time it takes to start responding, not the time it takes to output the response. The turnaround time is generally limited by the speed of the output device.

Process: Scheduling Algorithms

CPU scheduling deals with the problem of deciding which of the processes in the ready queue is to be allocated the CPU. There are many different CPU-scheduling algorithms

First-Come, First-Served Scheduling

By far the simplest CPU-scheduling algorithm is the first-come, first-served (FCFS) scheduling algorithm. With this scheme, the process that requests the CPU first is allocated the CPU first. The implementation of the FCFS policy is easily managed with a FIFO queue. When a process enters them ready queue, its PCB is linked onto the tail of the queue. When the CPU is free, it is allocated to the process at the head of the queue. The running process is then removed from the queue.

Shortest-Job-First Scheduling

The shortest-job-first (SJF) scheduling algorithm associates with each process the length of the process’s next CPU burst. When the CPU is available, it is assigned to the process that has the smallest next CPU burst. If the next CPU bursts of two processes are the same, FCFS scheduling is used to break the tie. Note that a more appropriate term for this scheduling method would be the shortest-next-CPU-burst algorithm, because scheduling depends on the length of the next CPU burst of a process, rather than its total length

Priority Scheduling

A priority is associated with each process, and the CPU is allocated to the process with the highest priority. Equal-priority processes are scheduled in FCFS order. An SJF algorithm is simply a priority algorithm where the priority (p) is the inverse of the (predicted) next CPU burst. The larger the CPU burst, the lower the priority, and vice versa. Priorities are generally indicated by some fixed range of numbers; here assume that low numbers represent high priority.

Round-Robin Scheduling

The Round-Robin (RR)  scheduling  algorithm  is  designed  especially for timesharing systems. It is similar to FCFS scheduling, but preemption is added to enable the system to switch between processes. A small unit of time, called a time quantum or time slice, is defined. A time quantum is generally from 10 to 100 milliseconds in length. The ready queue is treated as a circular queue. The CPU scheduler goes around the ready queue, allocating the CPU to each process for a time interval of up to 1 time quantum.

Multilevel Queue Scheduling

A multilevel queue scheduling algorithm partitions the ready queue into several separate queues The processes are permanently assigned to one queue, generally based on some property of the process, such as memory size, process priority, or process type. Each queue has its own scheduling algorithm. For example, separate queues might be used for foreground or interactive and background or batch processes. The foreground queue might be scheduled by an RR algorithm, while the background queue is scheduled by an FCFS algorithm.

Multilevel Feedback Queue Scheduling

This Algorithm allows a process to move between queues. The idea is to separate processes according to the characteristics of their CPU bursts. If a process uses too much CPU time, it will be moved to a lower-priority queue. This scheme leaves I/O-bound and interactive processes in the higher-priority queues. In addition, a process that waits too long in a lower-priority queue may be moved to a higher-priority queue. This form of aging prevents starvation.

Unit 3

Deadlock

A deadlock is a situation where a set of processes are permanently blocked because each process is holding some resources and waiting for another resource which are held by others-thus any of the processes are impossible to proceed. Eg :- Processes P1 holding resource R1 and waiting for R2 which is acquired by P2, and P2 is waiting for R1, which is shown in the following model.

Deadlock characterization

Necessary Conditions: A deadlock situation may occur if the following four conditions hold simultaneously in a system.

a) Mutual Exclusion

b) Hold and Wait

c) No Preemption

d) Circular Wait

Mutual Exclusion: At least one resource must be held in non-sharable mode that is only one process can use the resources. If another process requests that resource, requesting process must wait until the resource has been released.

Hold and wait: A process must be holding at least one resource and waiting to acquire additional resource that is currently held by other processes.

No Preemption: Resources allocated to a process can’t be forcibly taken out from it unless it releases that resource after completing the task.

Circular Wait: A set {P0 , P1 , …….Pn} of waiting processes must exists such that P0 is waiting for a resource that is held by P1 , P1 is waiting for the resource that is held by P2 ….. P (n – 1) is waiting for the resource that is held by Pn and Pn is waiting for the resources that is held by P0

Synchronization

A cooperating process is one that can affect or be affected by other processes executing in the system. Cooperating processes can either directly share a logical address space (that is, both code and data) or be allowed to share data only through files or messages.

The Critical Section Problem

Consider a system consisting of n processes {Po, P 1 , … , P 11 _ I}. Each process has a segment of code, called a critical section, in which the process may be changing common variables, updating a table, writing a file, and so on. The important feature of the system is that, when one process is executing in its critical section, no other process is to be allowed to execute in its critical section. There is no two processes are executing in their critical sections at the same time. 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

Semaphores

It  can use as a synchronization tool for application programmers. A semaphore is a variable or abstract data type used to control access to a common resource by multiple processes in a current system such as multitasking OS. A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait () and signal (). The wait () operation was originally termed P “to tes”); signal () was originally called V “to incremen”). The definition of wait () is as follows:

wait(S) { } while S <= 0 ; // no-op s–; The definition of signal () is as follows: Signal (S) { S++; } All modifications to the integer value of the semaphore in the wait () and signal () operations must be executed indivisibly. That is, when one process modifies the semaphore value, no other process can simultaneously modify that same semaphore value.

Deadlock Prevention

Deadlock prevention is a set of methods for ensuring that at least one of these necessary conditions cannot hold.

Mutual Exclusion: The mutual exclusion condition must hold for non-sharable resources. For example a printer cannot be simultaneously shared by several processes. Sharable resources do not require mutual exclusive access and thus cannot be involved in a dead lock. Read only files are good example of a shared resource. If several processes attempt to open the read only file at the same time they can be granted simultaneous access to the file. A process never needs to wait for a shareable resource. In general deadlock cannot prevent by denying the mutual exclusion condition. Some resources are intrinsically non-sharable.

Hold and wait: The hold and wait condition can be eliminated by requiring or forcing a process to release all resources hold by it whenever it request a resource that is not available. In other words deadlocks are prevented because waiting processes are not holding any resources. One protocol can be used requires each process to request and be allocated all its resources before it begins execution. Another protocol allows a process to request resources only when the process has none. A process may request some resources and use them. Before it request any additional resources, however, it must release all the resources that it is currently allocated.

These protocols have two main disadvantages. First, resource utilization may be low, since many of the resources may be allocated but unused for a long period. Second, starvation is possible. A process that needs several popular resources may have to wait indefinitely, because at least one of the resources that it needs is always allocated to some other process.

No Preemption: The third necessary condition is that there be no pre-emption of resources that have already been allocated. To ensure that this condition does not hold, we can use the following protocol. If a process is holding some resources and request another resource that cannot be immediately allocated to it (that is the process must wait), then all resources currently being held are pre-empted. In other words these resources are implicitly released. The

pre-empted resources are added to the list of resources for which the process is waiting. The process will restart only when it can regain its old resources, as well as the new ones that it is requesting.

Circular Wait: One way to ensure that circular wait never holds: ● impose a total ordering of all resource types and● require that each process requests resources in an increasing order of enumeration. A process can initially request any number of instances of a resource type -say, Ri. After that, the process can request instances of resource type Rj if and only if F(Rj) > F(Ri).Where F(Rj) is the numeric order of resources Rj.

Deadlock Avoidance

Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need ● The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition ● Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.

Safe State: ● When a process requests an available resource, system must decide if

immediate allocation leaves the system in a safe state ● System is in safe state if there exists a sequence <P1, P2, …, Pn> of ALL the processes in the systems such that for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j < I

Resource-Allocation Graph Scheme: ● Claim edge Pi→ Rj indicated that process Pj may request resource Rj; represented by a dashed line ● Claim edge converts to request edge when a process requests a resource● Request edge converted to an assignment edge when the resource is allocated to the process ● When a resource is released by a process,assignment edge reconverts to a claim edge ● Resources must be claimed a priori in the system

Banker’s Algorithm: ● When a new process enters the system, it must declare the maximum number of instances of each resource type that it may need. ● The requirement may not exceed the total number of resources in the system. ● When a user requests a set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state. ● If it will, the resources are allocated; otherwise, the process must wait until some

other process releases enough resources.

Data structures need to implement the banker’s algorithm:

1. Available: A vector of length m indicates the number of available resources of each type.

• If Available[j] = k, then k instances of resource type Rj are available.

2. Max: An n x m matrix defines the maximum demand of each process. • If Max[i] [j] = k, then process Pi may request at most k instances of resource type Rj.
3. Allocation: An n x m matrix defines the number of resources of each type currently allocated to each process. • If Allocation[i][j] = k, then process Pi is currently allocated k instances of resource type Rj.
4. Need: An n x m matrix indicates the remaining resource need of each process.• If Need[i][j] = k, then process Pi may need k more instances of resource type Ri to complete its task.

• Need[i][j]=Max[i][j]-Allocation [i][j].

Safety Algorithms: 1. Let Work and Finish be vectors of length m and n, respectively. Initialize: Work = Available Finish [i] = false for i = 0, 1, …, n- 1

2. Find an i such that both: (a) Finish [i] = false (b) Needi
3. Work = Work + Allocation i Finish[i] = true go to step 2
4. If Finish [i] == true for all i, then the system is in a safe state.

Monitors:Various types of errors can be generated easily when programmers use semaphores incorrectly to solve the critical-section problem. Similar problems may arise in the other synchronization models. To deal with such errors, researchers have developed high-level language constructs. One of the fundamental high-level synchronization construct is the monitor type

Deadlock Detection: ● System does not use either a deadlock-prevention or a deadlock avoidance algorithm, and may enter in to a deadlock state ● system may provide: • An algorithm that examines the state of the system to determine whether a deadlock has occurred• An algorithm to recover from the deadlock.

Single instance of each Resource Type: ● Deadlock detection algorithm use a variant of resource allocation graph called wait for graph. ● Edge Pi→Pj implies Pi is waiting for Pj to release a resource ● An edge Pi→Pj in a wait-for graph is obtained by merging two edges Pi→Rq and Rq→Pj in the corresponding resource allocation graph\

Single Instance of Each Resource Type:● a deadlock exists in the system if and only if the wait-for graph contains a cycle. ● Periodically invoke an algorithm that searches for a cycle in the graph. ● An algorithm to detect a cycle in a graph requires an order of n2 operations, where n is the number of vertices in the graph.

Detection Algorithm:

1. Let Work and Finish be vectors of length m and n, respectively Initialize:

(a) Work = Available (b) For i = 1,2, …, n, if Allocation i =! 0, then Finish[i]=false;otherwise, Finish[i] = true.

2. Find an index i such that both: (a) Finish[i] == false (b) Request i
3. Work = Work + Allocation i Finish[i] = true go to step 2
4. IfFinish[i]==false,forsomei,1

Recovery from Deadlock : Process Termination ● Abort all deadlocked processes.

• Abort one process at a time until the deadlock cycle is eliminated. ● In which order should we choose to abort?• Priority of the process.• How long process has computed, and how much longer to completion. • Resources the process has used. • Resources process needs to complete. • How many processes will need to be terminated. • Is process interactive or batch? Recovery from Deadlock : Resource Preemption ● Selecting a victim – determine the order of preemption to minimize cost. Cost factors may include such parameters as the number of resources a deadlocked process is holding and the amount of time the process has thus far consumed during its execution. ● Rollback – We must roll back the process to some safe state and restart it from that state. • Since, in general, it is difficult to determine what a safe state is, the simplest solution is a total rollback: abort the process and then restart it. • Although it is more effective to roll back the process only as far as necessary to break the deadlock, this method requires the system to keep more information about the state of all running processes return to some safe state,restart process for that state.

Unit 4

swapping:In multiprogramming, a memory management scheme called swapping can be used to increase the CPU utilisation. The process of bringing a process to memory and after running a while, temporarily copying it to disk is known as swapping, for example assuming a multiprogramming environment with a round-robin CPU scheduling algorithm. When time slice expires, the memory manager will start to swap out the process that just finished, and to swap another process to the memory space that has been freed.Normally a process that is swapped out will be the swapped back to the same memory space that it occupied previously. If binding is done at load time, then the process cannot be moved to different memory locations. If execution time binding is being used, then a process can be swapped into a different memory space, because the physical address are computed during execution time.

Contiguous Memory Allocation:The memory is usually divided into two partitions: one for the resident operating system and one for the user processes. We can place the operating system in either low memory or high memory. The major factor affecting this decision is the location of the interrupt vector. Since the interrupt vectoris often in low memory, programmers usually place the operating system in low memory as well. In. contiguous memory allocation, each process is contained in a single contiguous section of memory

operating system during program execution.

Memory Allocation:One of the simplest methods for allocating memory is to divide memory into several fixed-sized partitions. Each partition may contain exactly one process. Thus, the degree of multiprogramming is bound by the number of partitions. In this, when a partition is free a process is selected from the input queue and is loaded into the free partition. When the process terminates, the partition becomes available for another process. The operating system can order the input queue according to a scheduling algorithm. This procedure is a particular instance of the general dynamic storage allocation problem, which concerns how to satisfy a request of size n from a list of free size. There are many solutions to this problem. The first-fit, best-fit and worst-fit strategies are the ones most commonly used to select a free hole from the set of available holes.

First fit . Allocate the first hole that is big enough. Searching can start either at the beginning of the set of holes or at the location where the previous first-fit search ended. It can stop searching as soon as it finds a free hole that is large enough.

Best fit . Allocate the smallest hole that is big enough. It must search the entire list, unless the list is ordered by size. This strategy produces the smallest leftover hole.

Worst fit . Allocate the largest hole. Again, it must search the entire list, unless it is sorted by size. This strategy produces the largest leftover hole, which may be more useful than the smaller leftover hole from a best-fit approach.

Fragmentation:Both the first-fit and best-fit strategies for memory allocation suffer from external fragmentation.As processes are loaded and removed from memory, the free memory space is broken into littlepieces. External fragmentation exists when there is enough total memory space to satisfy a request but the available spaces are not contiguous; storage is fragmented into a large number of small holes. This fragmentation problem can be severe. In the worst case, It could have a block of free (or wasted) memory between every two processes. If all these small pieces of memory were in one big free block instead, we might be able to run several more processes.Memory fragmentation can be internal as well as external. Consider a

multiple-partition allocation scheme with a hole of 18,464 bytes. Suppose that the next process requests 18,462 bytes. If we allocate exactly the requested block, we are left with a hole of 2 bytes. The overhead to keep trackof this hole will be substantially larger than the hole itself. The general approach to avoiding this problem is to break the physical memory into fixed-sized blocks and allocate memory in units based on block size. With this approach, the memory allocated to a process may be slightly larger than the requested memory. The difference between these two numbers is internal memory that is internal fragmentation – used internal to a partition.

Paging is a memory-management scheme that permits the physical address space a process to be non-contiguous. Paging avoids external fragmentation and the need for compaction. It also solves the considerable problem of fitting memory chunks of varying sizes onto the backing store; most memory management schemes used before the introduction of paging suffered from this problem. The problem arises because, when some code fragments or data residing in main memory need to be swapped out, space must be found on the backing store. The backing store has the same fragmentation problems, but access is much slower, so compaction is impossible. Because of its advantages over earlier methods, paging in its various forms is used in most operating systems. Traditionally, support for paging has been handled by hardware. However, recent designs have implemented paging by closely integrating the hardware and operating system, especially on 64-bit microprocessors.

Segmentation:Segmentation is a memory-management scheme that supports this user view of memory. A logical address space is a collection of segments. Each segment has a name and a length. The addresses specify both the segment name and the offset within the segment. The user therefore specifies each address by two quantities: a segment name and an offset. (Contrast this scheme with the paging scheme, in which the user specifies only a single address, which is partitioned by the hardware into a page number and an offset, all invisible to the programmer.)An. important aspect of memory management that became unavoidable with paging is the separation of the user’s view of memory from the actual physical memory. The user’s view of memory is not the same as the actual physical memory. The user’s view is mapped onto physical memory. This mapping allows differentiation between logical memory and physical memory. Usersprefer to view memory as a collection of variable-sized segments, with no necessary ordering among segments.

Virtual Memory Management:Virtual memory is a technique that allows the execution of processes that are not completely in memory. One major advantage of this scheme is that programs can be larger than physical memory. Further, virtual memory abstracts main memory into an extremely large, uniform array of storage, separating logical memory as viewed by the user from physical memory. This technique frees programmers from the concerns of

memory-storage limitations. Virtual memory also allows processes to share files easily and to implement shared memory. In addition, it provides an efficient mechanism for process creation. Virtual memory involves the separation of logical memory as perceived by users from physical memory. This separation allows an extremely large virtual memory to be provided for programmers when only a smaller physical memory is available (figure below). Virtual memory makes the task of programming much easier, because the programmer no longer needs to worry about the amount of physical memory available; the programmer can concentrate instead on the problem to be programmed.

Demand Paging:Consider how an executable program might be loaded from disk into memory. One option is to load the entire program in physical memory at program execution time.

However, a problem with this approach is that it may not initially need the entire program in memory. demand-paging :system is similar to a paging system with swapping (Figure below) where processes reside in secondary memory (usually a disk). When we want to execute a process, we swap it into memory. A swapper manipulates entire processes, whereas a page is concerned with the individual pages of a process.

Page Replacement:Consider the system memory is not used only for holding program pages. Buffers for I/ 0 also consume a considerable amount of memory. This use can increase the strain on memory-placement algorithms. Deciding how much memory to allocate to I/0 and how much to program pages is a significant challenge. Some systems allocate a fixed percentage of memory for I/0 buffers, whereas others allow both user processes and the I/0 subsystem to compete for all system memory. Over-allocation of memory manifests itself as follows. While a user process is executing, a page fault occurs. The operating system determines where the desired page is residing on the disk but then finds that there are no free frames on the

free-frame list; all memory is in use.The operating system could instead swap out a process, freeing all its frames and reducing the level of multiprogramming. types:

*Basic Page Replacement *FIFO Page Replacement *Optimal Page Replacement

*LRU Page Replacement *LRU-Approximation Page Replacement *Counting-Based Page Replacement

Unit5

Access Methods:Files store information. When it is used, this information must be accessed and read into computer memory. The information in the file can be accessed in several ways. Some systems provide only one access method for files. Other systems, such as those of IBM, support many access methods, and choosing the right one for a particular application is a major design problem.

Sequential Access:The simplest access method is sequential access. Information in the file is processed in order, one record after the other. This mode of access is by far the most common; for example, editors and compilers usually access files in this fashion.

Direct Access:A file is made up of fixed-length that allow programs to read and write records rapidly in no particular order. The direct-access method is based on a disk model of a file, since disks allow random access to any file block. For direct access, the file is viewed as a numbered sequence of blocks or records.

Other Access Methods:These methods generally involve the construction of an index for the file. The index like an index in the back of a book contains pointers to the various blocks. To find a record in the file, we first search the index and then use the pointer to access the file directly and to find the desired record.

File System Structure:Disks provide the bulk of secondary storage on which a file system is maintained. They have two characteristics that make them a convenient medium for storing multiple files: *A disk can be rewritten in place; it is possible to read a block from the disk, modify the block, and write it back into the same place. *A disk can access directly any block of information it contains. Thus, it is simple to access any file either sequentially or randomly, and switching from one file to another requires only moving the read-write heads and waiting for the disk to rotate.

File Systems provide efficient and convenient access to the disk by allowing data to be stored, located, and retrieved easily. A file system poses two quite different design problems. The first problem is defining how the file system should look to the user. This task involves defining a file and its attributes, the operations allowed on a file, and the directory structure for organizing files. The second problem is creating algorithms and data structures to map the logical file system onto the physical secondary-storage devices. The file system itself is generally composed of many different levelsThe basic file system needs only to issue generic commands to the appropriate device driver to read and write physical blocks on the disk. Each physical block is identified by its numeric disk addressbefore the transfer of a disk block can occur. When the buffer is full, the buffer manager must find more buffer memory or free up buffer space to allow a requested I/O to complete.*The file organization module knows about files and their logical blocks, as well as physical blocks. By knowing the type of file allocation used and the location of the file, the file-organization module can translate logical block addresses to physical block addresses for the basic file system to transfer.The file-organization module also includes the free-space manager, which tracks unallocated blocks and provides these blocks to the

file-organization module when requested.*The logical file system manages metadata information. Metadata includes all of the file-system structure except the actual data (or contents of the files). The logical file system manages the directory structure to provide the file organization module with the information the latter needs, given a symbolic file name. It maintains file structure via file-control blocks.

Disk Scheduling:One of the responsibilities of the operating system is to use the hardware efficiently. For the disk drives, meeting this responsibility entails having fast access time and large disk bandwidth. The access time has two major components. The seek time is the time for the disk arm to move the heads to the cylinder containing the desired sector. The rotational latency is the additional time for the disk to rotate the desired sector to the disk head. The disk bandwidth is the total number of bytes transferred, divided by the total time between the first request for service and the completion of the last transfer. Whenever a process needs I/O to or from the disk, it issues a system call to the operating system. The request specifies several pieces of information:*Whether this operation is input or output *What the disk address for the transfer is *What the memory address for the transfer is*What the number of sectors to be transferred is

File OperationsA file is an abstract data type. To define a file properly, it has to consider the operations that can be performed on files. The operating system can provide system calls to create the following six basic file operations.

Creating a file. Two steps are necessary to create a file. First, space in the file system must be found for the file, and an entry for the new file must be made in the directory.

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.

Reading a file. To read from a file, we use a system call that specifies the name of the file and where (in memory) the next block of the file should be put.

Repositioning within a file. The directory is searched for the appropriate entry, and the

current-file- position pointer is repositioned to a given value. Repositioning within a file need not involve any actual I/0. This file operation is also known as a file seek.

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.

Truncating a file. The user may want to erase the contents of a file but keep its attributes. Counting:Another approach takes advantage of the fact that, generally, several contiguous blocks may be allocated or freed simultaneously, particularly when space is allocated with the contiguous- allocation algorithm or through clustering. Thus, rather than keeping a list of n free disk addresses, we can keep the address of the first free block and the number (n) of free contiguous blocks that follow the first block. Each entry in the free-space list then consists of a disk address and a count. Although each entry requires more space than would a simple disk address, the overall list is shorter, as long as the count is generally greater than 1. Note that this method of tracking free space is similar to the extent method of allocating blocks. These entries can be stored in a B-tree, rather than a linked list for efficient lookup, insertion, and deletion.

Space Maps:Sun’s ZFS ( Zettabyte File System ) was designed to encompass huge numbers of files, directories, and even file systems .the resulting data structures could have been large and inefficient if they had not been designed and implemented properly. On these scales, metadata I/0 can have a large performance impact.

File Attribute

Name,Identifier,Type.,Location,Size,Protection.Time, date, and user identification.