Suppose a stack is to be used by the processor to manage procedure calls and returns. Can the program counter be eliminated by using the top of the stack as a program counter?
> Explain the distinction between a real address and a virtual address.
> Suppose the following two processes, foo and bar, are executed concurrently and share the semaphore variables S and R (each initialized to 1) and the integer variable x (initialized to 0). a. Can the concurrent execution of these two processes result in
> A pipeline algorithm is implemented so a stream of data elements of type T produced by a process P0 passes through a sequence of processes P1, P2, …, Pn−1, which operates on the elements in that order. a. Define a generalized message buffer that contains
> Evaluate the banker’s algorithm for its usefulness in an OS.
> Consider a system with a total of 150 units of memory, allocated to three processes as shown: Apply the banker’s algorithm to determine whether it would be safe to grant each of the following requests. If yes, indicate a sequence of te
> In the THE multiprogramming system, a page can make the following state transitions: a. Define the effect of these transitions in terms of the quantities i, o, and p. b. Can any of them lead to a deadlock if the assumptions made in Problem 6.6 about inp
> Show that the four conditions of deadlock apply to Figure 6.1a. Figure 6.1a: (a) Deadlock possible
> Consider the following program: This software solution to the mutual exclusion problem for two processes is proposed in [HYMA66]. Find a counterexample that demonstrates that this solution is incorrect. It is interesting to note that even the Communicat
> Is busy waiting always less efficient (in terms of using processor time) than a blocking wait? Explain.
> Consider the following program: a. Determine the proper lower bound and upper bound on the final value of the shared variable tally output by this concurrent program. Assume processes can execute at any relative speed, and a value can only be incremente
> Consider the following program: Note the scheduler in a uniprocessor system would implement pseudo-parallel execution of these two concurrent processes by interleaving their instructions, without restriction on the order of the interleaving. a. Show a s
> List and briefly explain five storage management responsibilities of a typical OS.
> Processes and threads provide a powerful structuring tool for implementing programs that would be much more complex as simple sequential programs. An earlier construct that is instructive to examine is the coroutine. The purpose of this problem is to int
> At the beginning of Section 5.2, it is stated that multiprogramming and multiprocessing present the same problems, with respect to concurrency. This is true as far as it goes. However, cite two differences in terms of concurrency between multiprogramming
> Demonstrate that the following software approaches to mutual exclusion do not depend on elementary mutual exclusion at the memory access level: a. The bakery algorithm. b. Peterson’s algorithm.
> Consider Dekker’s algorithm written for an arbitrary number of processes by changing the statement executed when leaving the critical section from Evaluate the algorithm when the number of concurrently executing processes is greater tha
> Consider a sharable resource with the following characteristics: (1) As long as there are fewer than three processes using the resource, new processes can start using it right away. (2) Once there are three process using the resource, all three must le
> Consider the following definition of semaphores: Compare this set of definitions with that of Figure 5.6. Note one difference: With the preceding definition, a semaphore can never take on a negative value. Is there any difference in the effect of the tw
> When a special machine instruction is used to provide mutual exclusion in the fashion of Figure 5.5, there is no control over how long a process must wait before being granted access to its critical section. Devise an algorithm that uses the compare &
> Consider the first instance of the statement / in Figure 5.5b. Figure 5.5b: a. Achieve the same result using the exchange instruction. b. Which method is preferable?
> Consider the following program which provides a software approach to mutual exclusion: Where 1≤k≤N, and each element of “control” is either 0, 1, or 2. All elements of â&#
> Now consider a version of the bakery algorithm without the variable choosing. Then we have Does this version violate mutual exclusion? Explain why or why not. 1 int number [n]; 2 while (true) { number [i] = 1 + getmax (number [], n); 4 for (intj =
> How is the execution context of a process used by the OS?
> A software approach to mutual exclusion is Lamport’s bakery algorithm [LAMP74], so called because it is based on the practice in bakeries and other shops in which every customer receives a numbered ticket on arrival, allowing each to be
> Demonstrate the correctness of Dekker’s algorithm. a. Show that mutual exclusion is enforced. Hint: Show that when Pi enters its critical section, the following expression is true: b. Show that a process requiring access to its critical
> Consider the following code using the POSIX Pthreads API: In / we first declare a variable called mythread, which has a type of /. This is essentially an ID for a thread. Next, the / statement creates a thread associated with /. The call returns zero on
> But some existing optimizing compilers (including gcc, which tends to be relatively conservative) will “optimize” / to something similar to What problem or potential problem occurs with this compiled version of the pr
> Many current language specifications, such as for C and are inadequate for multithreaded programs. This can have an impact on compilers and the correctness of code, as this problem illustrates. Consider the following declarations and function definition:
> The OS/390 mainframe operating system is structured around the concepts of address space and task. Roughly speaking, a single address space corresponds to a single application and corresponds more or less to a process in other operating systems. Within a
> If a process exits and there are still threads of that process running, will they continue to run?
> Consider an environment in which there is a one-to-one mapping between user-level threads and kernel-level threads that allows one or more threads within a process to issue blocking system calls while other threads continue to run. Explain why this model
> OS/2 from IBM is an obsolete OS for PCs. In OS/2, what is commonly embodied in the concept of process in other operating systems is split into three separate types of entities: session, processes, and threads. A session is a collection of one or more pro
> In virtually all systems that include DMA modules, DMA access to main memory is given higher priority than processor access to main memory. Why?
> What is a process?
> Consider a computer system that contains an I/O module controlling a simple keyboard/printer Teletype. The following registers are contained in the CPU and connected directly to the system bus: INPR: Input Register, 8 bits OUTR: Output Register, 8 bits F
> In IBM’s mainframe OS, OS/390, one of the major modules in the kernel is the System Resource Manager. This module is responsible for the allocation of resources among address spaces (processes). The SRM gives OS/390 a degree of sophistication unique amon
> What is the purpose of system calls, and how do system calls relate to the OS and to the concept of dual-mode (kernel-mode and user-mode) operation?
> Contrast the scheduling policies you might use when trying to optimize a time-sharing system with those you would use to optimize a multiprogrammed batch system.
> An I/O-bound program is one that, if run alone, would spend more time waiting for I/O than using the processor. A processor-bound program is the opposite. Suppose a short-term scheduling algorithm favors those programs that have used little processor tim
> Consider a memory system with the following parameters: Tc=100 ns Cc=0.01 cents/bitTm=1,200 ns Cm=0.001 cents/bit a. What is the cost of 1 MByte of main memory? b. What is the cost of 1 MByte of main memory using cache memory technology? c. If the effect
> Suppose the hypothetical processor of Figure 1.3 also has two I/O instructions: 0011=Load AC from I/O0111 =Store AC to I/O. In these cases, the 12-bit address identifies a particular external device. Show the program execution (using the format of Figure
> Consider the following code: a. Give one example of the spatial locality in the code. b. Give one example of the temporal locality in the code. for (i = 0; i < 20; i++) for (j = 0; j < 10; j++) %3D a[i] = a[i] * j
> In the discussion of ULTs versus KLTs, it was pointed out that a disadvantage of ULTs is that when a ULT executes a system call, not only is that thread blocked, but also all of the threads within the process are blocked. Why is that so?
> Suppose we have a multiprogrammed computer in which each job has identical characteristics. In one computation period, T, for a job, half the time is spent in I/O, and the other half in processor activity. Each job runs for a total of N periods. Assume a
> What is multiprogramming?
> Consider a 32-bit microprocessor, with a 16-bit external data bus, driven by an 8-MHz input clock. Assume this microprocessor has a bus cycle whose minimum duration equals four input clock cycles. What is the maximum data transfer rate across the bus tha
> Consider a hypothetical microprocessor generating a 16-bit address (e.g., assume the program counter and the address registers are 16 bits wide) and having a 16-bit data bus. a. What is the maximum memory address space that the processor can access di
> Consider a hypothetical 32-bit microprocessor having 32-bit instructions composed of two fields. The first byte contains the opcode, and the remainder an immediate operand or an operand address. a. What is the maximum directly addressable memory capacity
> The program execution of Figure 1.4 is described in the text using six steps. Expand this description to show the use of the MAR and MBR. Figure 1.4: Fetch stage Execute stage Memory 300 I9 4 0 301 5 9 4 I 302 29 4 1 CPU registers 300 PC Meтory 300I
> A computer has a cache, main memory, and a disk used for virtual memory. If a referenced word is in the cache, 20 ns are required to access it. If it is in main memory but not in the cache, 60 ns are needed to load it into the cache (this includes the ti
> Explain the rationale for the Uninterruptible state in Linux.
> In Solaris 9 and Solaris 10, there is a one-to-one mapping between ULTs and LWPs. In Solaris 8, a single LWP supports one or more ULTs. a. What is the possible benefit of allowing a many-to-one mapping of ULTs to LWPs? b. In Solaris 8, the thread execu
> The Solaris documentation states that a ULT may yield to another thread of the same priority. Isn’t it possible that there will be a runnable thread of higher priority, and that therefore the yield function should result in yielding to a thread of the sa
> It was pointed out that two advantages of using multiple threads within a process are that (1) less work is involved in creating a new thread within an existing process than in creating a new process, and (2) communication among threads within the same
> What is the kernel of an OS?
> What are the motivations for preemptive and nonpreemptive process migration?
> Figure 3.8b suggests that a process can only be in one event queue at a time. a. Is it possible that you would want to allow a process to wait on more than one event at the same time? Provide an example. b. In that case, how would you modify the queueing
> The VMS scheme discussed in the preceding problem is often referred to as a ring protection structure, as illustrated in Figure 3.18 . Indeed, the simple kernel/user scheme, as described in Section 3.3 , is a two-ring structure. A potential disadvantage
> The VAX/VMS operating system makes use of four processor access modes to facilitate the protection and sharing of system resources among processes. The access mode determines: Instruction execution privileges: What instructions the processor may execute
> Table 3.13 shows the process states for the VAX/VMS operating system. Table 3.13: a. Can you provide a justification for the existence of so many distinct wait states? b. Why do the following states not have resident and swapped-out versions: Page Faul
> Consider the state transition diagram of Figure 3.9b. Suppose it is time for the OS to dispatch a process and there are processes in both the Ready state and the Ready/Suspend state, and at least one process in the Ready/Suspend state has higher scheduli
> For the seven-state process model of Figure 3.9b, draw a queuing diagram similar to that of Figure 3.8b. Figure 3.9b: Figure 3.8b: New Suspend Activate Dispatch Release Ready/ Suspend Ready Running Exit Suspend Time-out Activate Blocked/ Suspend Bl
> Figure 3.9b contains seven states. In principle, one could draw a transition between any two states, for a total of 42 different transitions. a. List all of the possible transitions and give an example of what could cause each transition. b. List all of
> Assume at time 5, no system resources are being used except for the processor and memory. Now consider the following events: At time 5: P1 executes a command to read from disk unit 3. At time 15: P5’s time slice expires. At time 18: P7 executes a command
> You have executed the following C program: What are the possible outputs, assuming the fork succeeded? main () { int pid; pid fork () ; printf (“%d \n", pid);
> In Section 3.4 , it was stated that UNIX is unsuitable for real-time applications because a process executing in kernel mode may not be preempted. Elaborate.
> What are three objectives of an OS design?
> In a number of early computers, an interrupt caused the register values to be stored in fixed locations associated with the given interrupt signal. Under what circumstances is this a practical technique? Explain why it is inconvenient in general.
> The following state transition table is a simplified model of process management, with the labels representing transitions between states of READY, RUN, BLOCKED, and NONRESIDENT Give an example of an event that can cause each of the above transitions. D
> A computer consists of a CPU and an I/O device D connected to main memory M via a shared bus with a data bus width of one word. The CPU can execute a maximum of 106 instructions per second. An average instruction requires five processor cycles, three of
> A DMA module is transferring characters to main memory from an external device transmitting at 9600 bits per second (bps). The processor can fetch instructions at the rate of 1 million instructions per second. By how much will the processor be slowed dow
> Explain what is the problem with this implementation of the one-writer many-readers problem? int readcount; // shared and initialized to 0 Semaphore mutex, wrt; // shared and initialized to 1; // Writer : // Readers : semwait (mutex) ; readcount := r
> Show that message passing and semaphores have equivalent functionality by a. Implementing message passing using semaphores. Hint: Make use of a shared buffer area to hold mailboxes, each one consisting of an array of message slots. b. Implementing a sem
> This problem demonstrates the use of semaphores to coordinate three types of processes. Santa Claus sleeps in his shop at the North Pole and can only be awakened by either (1) all nine reindeer being back from their vacation in the South Pacific, or (2)
> The following pseudo code is a correct implementation of the producer/consumer problem with a bounded buffer: Labels p1, p2, p3 and c1, c2, c3 refer to the lines of code shown above (p2 and c2 each cover three lines of code). Semaphores empty and full a
> Consider Figure 5.16. Would the meaning of the program change if the following were interchanged? a. / b. / c. / d. / Figure 5.16: semwait (e) ;semwait (s) semsignal (s);semSignali (n)
> Consider the solution to the infinite-buffer producer/consumer problem defined in Figure 5.13. Suppose we have the (common) case in which the producer and consumer are running at roughly the same speed. The scenario could be: Producer: append;/; produce;
> Comment on the following solution to the dining philosophers problem. A hungry philosopher first picks up his left fork; if his right fork is also available, he picks up his right fork and starts eating; otherwise, he puts down his left fork and repeats
> In the commentary on Figure 5.12 and Table 5.4, it was stated that “it would not do simply to move the conditional statement inside the critical section (controlled by s) of the consumer because this could lead to deadlock.â€
> The following problem was once used on an exam: Jurassic Park consists of a dinosaur museum and a park for safari riding. There are m passengers and n single-passenger cars. Passengers wander around the museum for a while, then line up to take a ride in
> In 1978, Dijkstra put forward the conjecture that there was no solution to the mutual exclusion problem avoiding starvation, applicable to an unknown but finite number of processes, using a finite number of weak semaphores. In 1979, J. M. Morris refuted
> The UNIX kernel will dynamically grow a process’s stack in virtual memory as needed, but it will never try to shrink it. Consider the case in which a program calls a C subroutine that allocates a local array on the stack that consumes 10 K. The kernel wi
> Consider a paged logical address space (composed of 32 pages of 2 kB each) mapped into a 1-MB physical memory space. a. What is the format of the processor’s logical address? b. What is the length and width of the page table (disregarding the “access rig
> Assume a task is divided into four equal-sized segments, and the system builds an eight-entry page descriptor table for each segment. Thus, the system has a combination of segmentation and paging. Assume also the page size is 2 kB. a. What is the maximu
> Five batch jobs, A through E, arrive at a computer center at essentially the same time. They have an estimated running time of 15, 9, 3, 6, and 12 minutes, respectively. Their (externally defined) priorities are 6, 3, 7, 9, and 4, respectively, with a lo
> The Multilink Protocol (MLP) is part of X.25; a similar facility is used in IBM’s System Network Architecture (SNA). With MLP, a set of data links exists between two nodes and is used as a pooled resource for transmitting packets, regardless of virtual c
> Consider a frame relay node that is handling a Poisson stream of incoming frames to be transmitted on a particular 1- Mbps outgoing link. The stream consists of two types of frames. Both types of frames have the same exponential distribution of frame len
> Consider a single queue with a constant service time of four seconds and a Poisson input with mean rate of 0.20 items per second. a. Find the mean and standard deviation of queue size. b. Find the mean and standard deviation of residence time
> In general, what are the strategies for exploiting spatial locality and temporal locality?
> Often inputs to a queueing system are not independent and random, but occur in clusters. Mean waiting delays are greater for this type of arrival pattern than for Poisson arrivals. This problem demonstrates the effect with a simple example. Assume items
> Messages arrive at a switching center for a particular outgoing communications line in a Poisson manner with a mean ρ = λTs/N. arrival rate of 180 messages per hour. Message length is distributed exponentially with a mean length of 14,400 characters. Lin
> Messages of three different sizes flow through a message switch. Seventy percent of the messages take 1 millisecond to serve, 20% take 3 milliseconds, and 10% take 10 milliseconds. Calculate the average time spent in the switch, and the average number of
> Messages arrive at random to be sent across a communications link with a data rate of 9,600 bps. The link is 70% utilized, and the average message length is 1,000 octets. Determine the average waiting time for constant-length messages and for exponential
> At an ATM machine in a supermarket, the average length of a transaction is two minutes, and on average, customers arrive to use the machine once every five minutes. How long is the average time that a person must spend waiting and using the machine? What
> What is the utilization of an M/M/1 queue that has four people waiting on average?
> If an M/M/1 queue has arrivals at a rate of two per minute and serves at a rate of four per minute, how many customers are found in the system on average? How many customers are found in service on average?
> Section 21.3 provided an intuitive argument to justify the single-server relationship ρ = λTs. Develop a similar argument to justify the multiserver relationship ρ = λTs/N.
> A simulation program of a multiprocessor system starts running with no jobs in the queue and ends with no jobs in the queue. The simulation program reports the average number of jobs in the system over the simulation run as 12.356, the average arrival ra
> The owner of a shop observes that on average 18 customers per hour arrive and there are typically 8 customers in the shop. What is the average length of time each customer spends in the shop?
> Consider the following fragment of code on a Linux system. Where / is a reader–writer lock . What is the effect of this code? read_lock (&mr_rwlock) ; write_lock (&mr_rwlock) ;
