Although semaphores provide a convenient and effective mechanism for process synchronization, using them incorrectly can result in timing errors that are difficult to detect, since these errors happen only if some particular execution sequences take place and these sequences do not always occur. We have seen an example of such errors in the use of counters in our solution to the producer-consumer problem (Section 6.1). In that example, the timing problem happened only rarely, and even then the counter value appeared to be reasonable—off by only 1- Nevertheless, the solution is obviously not an acceptable one. It is for this reason that semaphores were introduced in the first place.

Unfortunately, such timing errors can still occur when semaphores are used. To illustrate how, we review the semaphore solution to the criticalsection problem. All processes share a semaphore variable mutex, which is. initialized to 1. Each process must execute wait (mutex) before entering the critical section and signal (mutex) afterward. If this sequence is not observed, two processes may be in their critical sections simultaneously. Let us examine the various difficulties that may result. Note that these difficulties will arise even if a single process is not well behaved. This situation may be caused by an honest programming error or an uncooperative programmer.

• Suppose that a process interchanges the order in which the wait(j and signal () operations on the semaphore mutex are executed, resulting in the following execution:

Topics You May Be Interested In
Real Time Operating System Linux-input & Output
Thrashing Example: The Intel Pentium
File Sharing Firewalling To Protect Systems And Networks
File Access Methods What Is Atomicity?
Computing Environments- Traditional Computing, Client-server Computing, Peer-to-peer Computing, Web-based Computing Summary Of Os Structures


critical section


In this situation, several processes may be executing in their critical sections simultaneously, violating the mutual-exclusion requirement. This error may be discovered only if several processes are simultaneously active in their critical sections. Note that this situation may not always be reproducible.

Topics You May Be Interested In
Process Scheduling Deadlock Avoidance
System Programs Thread Scheduling
Critical Section Problems How Is Cpu Scheduling Done In Multimedia Systems?
Segmentation Windows Xp- History
Allocating Kernel Memory Atomic Transactions

• Suppose that a process replaces signal (mutex) with wait (mutex). That is, it executes


critical section


Topics You May Be Interested In
Microkernel Architecture Of Operating System Thread Scheduling
Contiguous Memory Allocation System And Network Threats
Allocation Of Frames What Is The Wafl File System?
File Protection Features Of Real-time Kernels
User Os Interface, Command Interpreter, And Graphical User Interfaces Threads-summary

In this case, a deadlock will occur.

• Suppose that a process omits the wait (mutex), or the signal (mutex), or both. In this case, either mutual exclusion is violated or a deadlock will occur. These examples illustrate that various types of errors can be generated easily when programmers use semaphores incorrectly to solve the critical-section problem.. To deal with such errors, researchers have developed high-level language constructs. In this section, we describe one fundamental high-level synchronization construct—the monitor type.


 A type, or abstract data type, encapsulates private data with public methods to operate on that data. A monitor type presents a set of programmer-defined operations that are provided mutual exclusion within the monitor. The monitor type also contains the declaration of variables whose values define the state of an instance of that type, along with the bodies of procedures or functions that operate on those variables. The syntax of a monitor is shown in Figure 6.16. The representation of a monitor type cannot be used directly by the various processes. Thus, a procedure defined within a monitor can access only those variables declared locally within the monitor and its formal parameters. Similarly, the local variables of a monitor can be accessed by only the local procedures.

Topics You May Be Interested In
Batch Operating Systems Disk Scheduling In Multimedia Systems
Contiguous Memory Allocation Multimedia- Network Management
Design Principles What Is Multics?
I/o Performance What Is Concurrency Control?
How Is Cpu Scheduling Done In Multimedia Systems? Atomic Transactions

 The monitor construct ensures that only one process at a time can be active within the monitor. Consequently, the programmer does not need to code this synchronization constraint explicitly (Figure 6.17). However, the monitor construct, as defined so far, is not sufficiently powerful for modeling some synchronization schemes. For this purpose, we need to define additional synchronization mechanisms. These mechanisms are provided by the condition construct. A programmer who needs to write a tailor-made synchronization scheme can define one or more variables of type condition:

 condition x, y;

The only operations that can be invoked on a condition variable are wait () and signal(). The operation x.waitO ; means that the process invoking this operation is suspended until another process invokes x.signal(); The x. signal () operation resumes exactly one suspended process. If no process is suspended, then the signal () operation has no effect; that is, the state of x is the same as if the operation had never been executed (Figure 6.18). Contrast this operation with the signal () operation associated with semaphores, which always affects the state of the semaphore.

Now suppose that, when the x. s ignal () operation is invoked by a process P, there is a suspended process Q associated with condition x. Clearly, if the suspended process Q is allowed to resume its execution, the signaling process P must wait. Otherwise, both P and Q would be active simultaneously within the monitor. Note, however, that both processes can conceptually continue with their execution. Two possibilities exist:

Topics You May Be Interested In
Multiprocessor Systems Deadlock Prevention
Critical Section Problems Swap Space Management
File Concept Stateful Versus Stateless Service
Operating System Services Rc 4000
Virtual Machines Overview Of Mass Storage Structure

1. Signal and wait. P either waits until Q leaves the monitor or waits for another condition.

2. Signal and continue. Q either waits until P leaves the monitor or waits for another condition. There are reasonable arguments in favor of adopting either option. On the one hand, since P was already executing in the monitor, the signal-and-continue method seems more reasonable. On the other hand, if we allow thread P to continue, then by the time Q is resumed, the logical condition for which Q was waiting may no longer hold. A compromise between these two choices was adopted in the language Concurrent Pascal. When thread P executes the signal operation, it immediately leaves the monitor. Hence, Q is immediately resumed

Dining-Philosophers Solution Using Monitors

We now illustrate monitor concepts by presenting a deadlock-free solution to the dining-philosophers problem. This solution imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available. To code this solution, we need to distinguish among three states in which we may find a philosopher. For this purpose, we introduce the following data structure: enum {thinking, hungry, eating} stat e [5] ; Philosopher i can set the variable stat e [i] = eating only if her two neighbors are not eating: (state [(i+4) °/» 5] != eating) and (state [(i+1) % 5] != eating). We also need to declare condition self [5]; where philosopher ;' can delay herself when she is hungry but is unable to obtain the chopsticks she needs. We are now in a position to describe our solution to the diiiing-philosophers problem. The distribution of the chopsticks is controlled by the monitor dp, whose definition is shown in Figure 6.19. Each philosopher, before starting to eat, must invoke the operation pi ckup (). This may result in the suspension of the philosopher process.

Topics You May Be Interested In
Network Operating System Thread Libraries
Hybrid Architecture Of Operating System Memory Mapped Files
Allocation Of Frames File System Example
File Concept Atomic Transactions
Scheduling Criteria Distributed System


After the successful completion of the operation, the philosopher may eat. Following this, the philosopher invokes the putdownO operation. Thus, philosopher i must invoke the operations pi ckup () and putdownO in the following sequence:


eat dp.putdown(i);

Topics You May Be Interested In
Batch Operating Systems Thread Scheduling
Distributed Operating Systems Thread Libraries
Os Examples Atomicity
Deadlock Avoidance Linux-input & Output
File Replication What Is The Wafl File System?


It is easy to show that this solution ensures that no two neighbors are eating simultaneously and that no deadlocks will occur. We note, however, that it is possible for a philosopher to starve to death. We do not present a solution to this problem but rather leave it as an exercise for you.

Implementing a Monitor Using Semaphores

We now consider a possible implementation of the monitor mechanism using semaphores. For each monitor, a semaphore mut ex (initialized to 1) is provided. A process must execute wait (mutex) before entering the monitor and must execute signal (mutex) after leaving the monitor. Since a signaling process must wait until the resumed process either leaves or waits, an additional semaphore, next, is introduced, initialized to 0, on which the signaling processes may suspend themselves. An integer variable next-count is also provided to count the number of processes suspended on next. Thus, each external procedure F is replaced by

Topics You May Be Interested In
Distributed Operating Systems What Is The Security Problem?
Hybrid Architecture Of Operating System What Is Multimedia?
Mass Storage Structure Overview Explain Reaching Agreement.
Operating System Services Introduction To Memory Management
Atlas Introduction To Storage Management


body of F if (next_count > 0)



Topics You May Be Interested In
Operating System Operations- Dual-mode Operation, Timer Petersons's Solution
Allocating Kernel Memory An Example-windows Xp
Free Space Management User Authentication
Deadlock Prevention How Is Cpu Scheduling Done In Multimedia Systems?
Directory Implementation Atomic Transactions


 Mutual exclusion within a monitor is ensured. We can now describe how condition variables are implemented. For each condition x, we introduce a semaphore x_sem and an integer variable x_count, both initialized to 0. The operation x. wait () can now be implemented as


 if (next_count > 0)

Topics You May Be Interested In
Various Operating System Services Memory Mapped Files
Monitors Revocation Of Access Rights
Allocation Methods An Example: Networking
Directory Implementation Algorithm Evaluation
System Model Access Matrix





Topics You May Be Interested In
Different Types Of Operating Systems An Example: Cineblitz
Microkernel Architecture Of Operating System What Is Ctss?
Instruction Execution Explain Reaching Agreement.
Segmentation Implementing Real-time Operating Systems
Atomicity Mutual Exclusion


The operation x. signal () can be implemented as if (x_count > 0) { next_count++; signal(x_sem); wait(next) ; next_count—; This implementation is applicable to the definitions of monitors given by both Hoare and Brinch-Hansen. In some cases, however, the generality of the implementation is unnecessary, and a significant improvement in efficiency is possible.

Resuming Processes Within a Monitor We turn now to the subject of process-resumption order within a monitor. If several processes are suspended on condition x, and an x. signal () operation is executed by some process, then how do we determine which of the suspended processes should be resumed next? One simple solution is to use an FCFS ordering, so that the process waiting the longest is resumed first. In many circumstances, however, such a simple scheduling scheme is not adequate. For this purpose, the conditional-wait construct can be used; it has the form


Topics You May Be Interested In
Operating System Concepts ( Multi Tasking, Multi Programming, Multi-user, Multi-threading ) File Sharing
Direct Memory Access Deadlock Characteristics
Monitors Multiprocessor Scheduling
Os Examples What Is The Security Problem?
Mass Storage Structure Overview What Is Election Algorithms ?

where c is an integer expression that is evaluated when the wait () operation is executed. The value of c, which is called a priority number, is then stored with the name of the process that is suspended. When x. signal () is executed, the process with the smallest associated priority number is resumed next. To illustrate this new mechanism, we consider the ResourceAllocator monitor shown in Figure 6.20, which controls the allocation of a single resource among competing processes.


 Each process, when requesting an allocation of this resource, specifies the maximum time it plans to use the resource. The monitor allocates the resource to the process that has the shortest timeallocation request. A process that needs to access the resource in question must observe the following sequence:


 access the resource;

 R. releaseO ;

where R is an instance of type ResourceAllocator. Unfortunately, the monitor concept cannot guarantee that the preceding access sequence will be observed. In particular, the following problems can occur:

• A process might access a resource without first gaining access permission to the resource.

 • A process might never release a resource once it has been granted access to the resource.

• A process might attempt to release a resource that it never requestecj.

• A process might request the same resource twice (without first releasing the resource). The same difficulties are encountered with the use of semaphores, and these difficulties are similar in nature to those that encouraged us to develop the monitor constructs in the first place.

 Previously, we had to worry about the correct use of semaphores. Now, we have to worry about the correct use of higher-level programmer-defined operations, with which the compiler can no longer assist us. One possible solution to the current problem is to include the resourceaccess operations within the ResourceAllocator monitor. However, using this solution will mean that scheduling is done according to the built-in monitor-scheduling algorithm rather than the one we have coded. To ensure that the processes observe the appropriate sequences, we must inspect all the programs that make use of the ResourceAllocator monitor and its managed resource. We must check two conditions to establish the correctness of this system.

First, user processes must always make their calls on the monitor in a correct sequence. Second, we must be sure that an uncooperative process does not simply ignore the mutual-exclusion gateway provided by the monitor and try to access the shared resource directly, without using the access protocols. Only if these two conditions can be ensured can we guarantee that no time-dependent errors will occur and that the scheduling algorithm will not be defeated. Although this inspection may be possible for a small, static system, it is not reasonable for a large system or a dynamic system. This access-control problem can be solved only by additional mechanisms that will be described in Chapter 14. Many programming languages have incorporated the idea of the monitor as described in this section, including Concurrent Pascal, Mesa, C# (pronounced C-sharp), and Java. Other languages—such as Erlang—provide some type of concurrency support using a similar mechanism.


Frequently Asked Questions

Ans: The main memory must accommodate both the operating system and the various user processes. We therefore need to allocate the parts of the main memory in the most efficient way possible. This section explains one common method, contiguous memory allocation. view more..
Ans: The various hardware-based solutions to the critical-section problem (using the TestAndSetC) and SwapO instructions) are complicated for application programmers to use. To overcome this difficulty, we can use a synchronization tool called a semaphore. A semaphore S is an integer variable that, apart from initialization, is accessed only through two standard atomic operations: wait () and signal (). view more..
Ans: 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. The general structure of a typical process P. The entry section and exit section are enclosed in boxes to highlight these important segments of code. view more..
Ans: Although semaphores provide a convenient and effective mechanism for process synchronization, using them incorrectly can result in timing errors that are difficult to detect, since these errors happen only if some particular execution sequences take place and these sequences do not always occur. We have seen an example of such errors in the use of counters in our solution to the producer-consumer problem view more..
Ans: An important aspect of memory management that became unavoidable with paging is the separation of the user's view of memory and the actual physical memory. As we have already seen, 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. view more..
Ans: Paging is a memory-management scheme that permits the physical address space of a process to be noncontiguous. Paging avoids 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. view more..
Ans: 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 we may not initially need the entire program in memory. Consider a program that starts with a list of available options from which the user is to select. Loading the entire program into memory results in loading the executable code for all options, regardless of whether an option is ultimately selected by the user or not. An alternative strategy is to initially load pages only as they are needed. This technique is known as demand paging and is commonly used in virtual memory systems. view more..
Ans: Thrashing If the number of frames allocated to a low-priority process falls below the minimum number required by the computer architecture, we must suspend, that process's execution. We should then page out its remaining pages, freeing all its allocated frames. This provision introduces a swap-in, swap-out level of intermediate CPU scheduling. In fact, look at any process that does not have ''enough" frames. If the process does not have the number of frames it needs to support pages in active use, it will quickly page-fault. At this point, it must replace some page. However, since all its pages are in active use, it must replace a page that will be needed again right away. Consequently, it quickly faults again, and again, and again, replacing pages that it must bring back in immediately. This high paging activity is called thrashing. A process is thrashing if it is spending more time paging than executing. view more..
Ans: When a process running in user mode requests additional memory, pages are allocated from the list of free page frames maintained by the kernel. This list is typically populated using a page-replacement algorithm such as those discussed in Section 9.4 and most likely contains free pages scattered throughout physical memory, as explained earlier. Remember, too, that if a user process requests a single byte of memory, internal fragmentation will result, as the process will be granted, an entire page frame. Kernel memory, however, is often allocated from a free-memory pool different from the list used to satisfy ordinary user-mode processes. view more..
Ans: We turn next to a description of the scheduling policies of the Solaris, Windows XP, and Linux operating systems. It is important to remember that we are describing the scheduling of kernel threads with Solaris and Linux. Recall that Linux does not distinguish between processes and threads; thus, we use the term task when discussing the Linux scheduler. view more..
Ans: Overview of Mass-Storage Structure In this section we present a general overview of the physical structure of secondary and tertiary storage devices view more..
Ans: Allocation of Frames We turn next to the issue of allocation. How do we allocate the fixed amount of free memory among the various processes? If we have 93 free frames and two processes, how many frames does each process get? The simplest case is the single-user system. Consider a single-user system with 128 KB of memory composed of pages 1 KB in size. This system has 128 frames. The operating system may take 35 KB, leaving 93 frames for the user process. Under pure demand paging, all 93 frames would initially be put on the free-frame list. When a user process started execution, it would generate a sequence of page faults. The first 93 page faults would all get free frames from the free-frame list. view more..
Ans: The direct-access nature of disks allows us flexibility in the implementation of files, in almost every case, many files are stored on the same disk. The main problem is how to allocate space to these files so that disk space is utilized effectively and files can be accessed quickly. Three major methods of allocating disk space are in wide use: contiguous, linked, and indexed. Each method has advantages and disadvantages. Some systems (such as Data General's RDOS for its Nova line of computers) support all three. view more..
Ans: Free-Space Management Since disk space is limited, we need to reuse the space from deleted files for new files, if possible. (Write-once optical disks only allow one write to any given sector, and thus such reuse is not physically possible.) To keep track of free disk space, the system maintains a free-space list. The free-space list records all free disk blocks—those not allocated to some file or directory. To create a file, we search the free-space list for the required amount of space and allocate that space to the new file. This space is then removed from the free-space list. view more..
Ans: File Concept Computers can store information on various storage media, such as magnetic disks, magnetic tapes, and optical disks. So that the computer system will be convenient to use, 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, 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. view more..
Ans: Modern disk drives are addressed as large one-dimensional arrays of logical blocks, where the logical block is the smallest unit of transfer. The size of a logical block is usually 512 bytes, although some disks can be low-level formatted to have a different logical block size, such as 1,024 bytes. view more..
Ans: In the previous sections, we explored the motivation for file sharing and some of the difficulties involved in allowing users to share files. Such file sharing is very desirable for users who want to collaborate and to reduce the effort required to achieve a computing goal. Therefore, user-oriented operating systems must accommodate the need to share files in spite of the inherent difficulties. In this section, we examine more aspects of file sharing view more..
Ans: When information is stored in a computer system, we want to keep it safe from physical damage (reliability) and improper access (protection). Reliability is generally provided by duplicate copies of files. Many computers have systems programs that automatically (or through computer-operator intervention) copy disk files to tape at regular intervals (once per day or week or month) to maintain a copy should a file system be accidentally destroyed. view more..

Rating - 3/5