General Definition of Operating Systems An OS is a program which acts as an interface between computer system users and the computer hardware. It provides a user-friendly environment in which a user may easily develop and execute programs. Otherwise, hardware knowledge would be mandatory for computer programming. So, it can be said that an OS […]

Operating System History It all started with computer hardware in about 1945s. Computers were using vacuum tube technology. Programs were loaded into memory manually using switches, punched cards, or paper tapes.As time went on, card readers, printers, and magnetic tape units were developed as additional hardware elements. Assemblers, loaders and simple utility libraries were developed as software tools. Later, […]

Overview: A process is an executing program, including the current values of the program counter, registers, and variables.The subtle difference between a process and a program is that the program is a group of instructions whereas the process is the activity. In multi-programming systems, processes are performed in a pseudo-parallelism as if each process has its […]

Process States Overview: we have already read the concept of process ,not let us see what it is process states, please check the below figure States of Process: Start : The process has just arrived. Ready : The process is waiting to grab the processor. Running : The process has been allocated by the processor. […]

What is Scheduler in Operating System ? If we consider batch systems, there will often be more processes submitted than the number of processes that can be executed immediately. So incoming processes are spooled (to a disk). The long-term scheduler selects processes from this process pool and loads selected processes into memory for execution. The short-term scheduler selects […]

In order to achieve an efficient processor management, OS tries to select the most appropriate process from the ready queue. For selection, the relative importance of the Followings may be considered as performance criteria. Processor Utilization: The ratio of busy time of the processor to the total time passes for processes to finish. We would like to […]

Now, let’s discuss some processor scheduling algorithms again stating that the goal is to select the most appropriate process in the ready queue. For the sake of simplicity, we will assume that we have a single I/O server and a single device queue, and we will assume our device queue always implemented with FIFO method. […]

In a multi-programming system, in order to share the processor, a number of processes must be kept in memory. Memory management is achieved through memory management algorithms. Each memory management algorithm requires its own hardware support. In this Topic, we shall see the partitioning, paging and segmentation methods. In order to be able to load programs at anywhere […]

Why Paging is Required ? Paging permits a program to allocate noncontiguous blocks of memory. The OS divide programs into pages which are blocks of small and fixed size. Then, it divides the physical memory into frames which are blocks of size equal to page size. The OS uses a page table to map program pages to memory […]

Every access to memory should go through the page table. Therefore, it must be implemented in an efficient way. a. Using fast dedicated registers Keep page table in fast dedicated registers. Only the OS is able to modify these registers. However, if the page table is large, this method becomes very expensive since requires too many registers. Given […]

Concept Of Segmentation in Operating System In segmentation, programs are divided into variable size segments, instead of fixed size pages. Every logical address is formed of a segment name and an offset within that segment. In practice, segments are numbered. Programs are segmented automatically by the compiler or assembler. For example, a C compiler will create separate segments […]

Lets Discuss Virtual Memory Over here ,All the memory management policies we have discussed so far, try to keep a number of processes in the memory simultaneously to allow multi-programming. But they require an entire process to be loaded in the memory before it can execute. With the virtual memory technique, we can execute a process which […]

If there is no page fault, effective access time is effective memory acces time is eatNO-PF = emat If there is a page fault, we have eatPF = pfst + emat ≅ pfst where pfst is page fault service time. Since emat is very small compared to pfst it can be ignored. Now, let p be […]

Why Dirty Bit? What is Dirty Bit? In order to reduce the page fault service time, a special bit called the dirty bit can be associated with each page. The dirty bit is set to “1” by the hardware whenever the page is modified. (written into). When we select a victim by using a page replacement […]

A page replacement algorithm determines how the victim page (the page to be replaced) is selected when a page fault occurs. The aim is to minimize the page fault rate. The efficiency of a page replacement algorithm is evaluated by running it on a particular string of memory references and computing the number of page faults. Reference […]

Deadlocks Definition: In a multiprogramming system, processes request resources. If those resources are being used by other processes then the process enters a waiting state. However, if other processes are also in a waiting state, we have deadlock. The formal definition of deadlock is as follows: Definition: A set of processes is in a deadlock state if […]

Resource allocation graphs are drawn in order to see the allocation relations of processes and resources easily. In these graphs, processes are represented by circles and resources are represented by boxes. Resource boxes have some number of dots inside indicating available number of that resource, that is number of instances. If the resource allocation graph […]

Deadlock Prevention:To prevent the system from deadlocks, one of the four discussed conditions that may create a deadlock should be discarded. The methods for those conditions are as follows: Mutual Exclusion: In general, we do not have systems with all resources being shareable. Some resources like printers, processing units are non-sharable. So it is not possible to […]

Given some additional information on how each process will request resources, it is possible to construct an algorithm that will avoid deadlock states. The algorithm will dynamically examine the resource allocation operations to ensure that there won’t be a circular wait on resources. When a process requests a resource that is already available, the system must decide whether that […]

Banker’s Algorithm (Dijkstra and Habermann):It is a deadlock avoidance algorithm. The following data structures are used in the algorithm: m = number of resources n = number of processes Available [m] : One dimensional array of size m. It indicates the number of available resources of each type. For example, if Available [i] is k, there […]

If a system has no deadlock prevention and no deadlock avoidance scheme, then it needs a deadlock detection scheme with recovery from deadlock capability. For this, information should be kept on the allocation of resources to processes, and on outstanding allocation requests. Then, an algorithm is needed which will determine whether the system has entered a deadlock state. This […]

If the system is in a deadlock state, some methods for recovering it from the deadlock state must be applied. There are various ways for recovery: Allocate one resource to several processes, by violating mutual exclusion. Preempt some resources from some of the deadlocked processes. Abort one or more processes in order to break the deadlock. […]

Processes frequently need to communicate with other processes. For example, in a shell pipeline, the output of the first process must be passed to the second process, and so on down the line. Thus, there is a need for communication between processes, preferably in a well-structured way not using interrupts. Because, interrupts decrease system performance. That communication between […]

The problem of avoiding race conditions can also be formulated in an abstract way. Part of the time, a process is busy doing internal computations and other things that do not lead to race conditions. However, sometimes a process may be accessing shared memory or files, or doing other critical things that can lead to […]

Disabling Interrupts The simplest solution is to have each process disable all interrupts just after entering its CS  and re-enable them just before leaving it. With interrupts disabled, the processor can not switch to another process. Thus, once a process has disabled interrupts, it can examine and update the shared memory without fear that any other process […]

By combining the idea of taking turns with the idea of lock variables and warning variables, in 1965, a Dutch mathematician, T. Dekker, was the first one to devise a software solution to the mutual exclusion problem that does not require strict alternation. In 1981, G.L. Peterson discovered a much simpler way to achieve mutual exclusion, […]

E. W. Dijkstra suggested using an integer variable for IPC problems. In his proposal, a new variable type, called a semaphore, was introduced. Dijkstra proposed having two atomic operations, DOWN and UP (P and V in Dijkstra’s original paper). The DOWN operation on a semaphore checks to see if the value is greater than 0. If so, it […]

Besides its usage for CS problem, semaphores can also be used for synchronization of the processes. For example consider two concurrent processes: p1, p2. We require that statement s2 of p2 will be executed after statement s1 of p1. Let p1 and p2 share a common semaphore ‘synch’, initialized to 0. Semaphores can be used for this synchronization […]

Assume there are n slots capable of holding one item. Process producer will produce items to fill slots and process consumer will consume the items in these slots. There is no information on the relative speeds of processes. Devise a protocol which will allow these processes to run concurrently. A common buffer whose elements (slots) will be filled/emptied by […]

Imagine a big database, such as an airline reservation system, with many competing processes wishing to read and write. It is acceptable to have multiple processes reading the database at the same time, if one process is writing to the database, no other processes may have access to the database, not even readers. Following is a solution for […]

There are N philosophers spending their lives thinking and eating in a room. In their round table there is a plate of infinite rice and N chopsticks. From time to time, a philosopher gets hungry. He tries to pick up the two chopsticks that are on his right and his left. A philosopher that picks both chopsticks successfully […]

The barber shop has one barber, one barber chair, and N chairs for waiting customers, if any, to sit in. If there is no customer at present, the barber sits down in the barber chair and falls asleep. When a customer arrives, he has to wake up the sleeping barber. If additional customers arrive while the barber is […]