Question: Consider the following fragment of code on

> 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?

> Figure 21.3 shows the number of items in a system as a function of time. This can be viewed as the difference between an arrival process and a departure process, of the form a. On one graph, show the functions a(t) and d(t) that produce the n(t) shown

> Section 21.3 provided an intuitive argument to justify Little’s formula. Develop a similar argument to justify the relationship r=λTr.

> The continuous random variable R has a uniform density between 900 and 1,100, and 0 elsewhere. Find the probability that R is between 950 and 1,050.

> The mean and variance of X are 50 and 4, respectively. Evaluate the following: a. The mean of X2 b. The variance and standard deviation of 2X+3 c. The variance and standard deviation of - X

> In the carnival game known as chuck-a-luck, a player pays an amount E as an entrance fee, selects a number between one and six, and then rolls three dice. If all three dice show the number selected, the player is paid four times the entrance fee; if two

> A player tosses a fair die. If a prime number greater than 1 appears, he wins that number of dollars, but if a nonprime number appears, he loses that number of dollars. a. Denote the player’s gain or loss on one toss by the random variable X. Enumerate t

> A pair of fair dice (the probability of each outcome is 1/6) is thrown. Let X be the maximum of the two numbers that comes up. a. Find the distribution of X. b. Find the expectation E[X], the variance Var[X], and the standard deviation σX.

> The birthday paradox is a famous problem in probability that can be stated as follows: What is the minimum value of K such that the probability is greater than 0.5 that at least two people in a group of K people have the same birthday? Ignore February 29

> A taxicab was involved in a fatal hit-and-run accident at night. Two cab companies, the Green and the Blue, operate in the city. You are told that: 85% of the cabs in the city are Green and 15% are Blue A witness identified the cab as Blue The court test

> A patient has a test for some disease that comes back positive (indicating he has the disease). You are told that the accuracy of the test is 87% (i.e., if a patient has the disease, 87% of the time, the test yields the correct result, and if the patient

> What is the distinction between spatial locality and temporal locality?

> Let {Zn} be a set of uncorrelated real-valued random variables, each with a mean of 0 and a variance of 1. Define the moving average Yn=∑i=0KαiZn−i for constants α0, α1, …, αK. Show that Y is stationary and find its autocovariance function

> Suppose x(t) is a stochastic process with μ(t)=3 R(t1, t2)=9+4e −0.2| t1−t2 |.Determine the mean, variance, and covariance of the following random variables: Z=x(5) and W=x(8).

> An artificial example of a stochastic process is a deterministic signal x(t)=g(t). Determine the mean, variance, and autocorrelation of x(t).

> Consider a random variable X with the following distribution: Pr[X= −1]=0.25;Pr[X=0]=0.5; Pr[X=1]=0.25. Let Y=X2. a. Are X and Y independent random variables? Justify your answer. b. Calculate the covariance Cov(X, Y). c. Are X and Y uncorrelated? Justif

> Suppose X and Y each have only two possible values, 0 and 1. Prove if X and Y are uncorrelated, then they are also independent.

> Show that, all other things being equal, the greater the correlation coefficient of two random variables is, the greater the variance of their sum and the less the variance of their difference will be.

> You are asked to play a game in which I hide a prize in one of three boxes (with equal probability for all three boxes) while you are out of the room. When you return, you have to guess which box hides the prize. There are two stages to the game. First,

> In to retransmit lost packets, TFTP must keep a copy of the data it sends. How many packets of data must TFTP keep at a time to implement this retransmission mechanism?

> The TFTP specification (RFC 1350) states that the transfer identifiers (TIDs) chosen for a connection should be randomly chosen, so the probability that the same number is chosen twice in immediate succession is very low. What would be the problem of usi

> In Figure 19.11b, explain why the second line cannot simply read "request (j)=t." Figure 19.11b: (b) Second Part Notation send (j, access, end message of type access, with token, by process j token) broadcast (request, send message from process i of

> In Table 6.2, some of the Linux atomic operations do not involve two accesses to a variable, such as /. A simple read operation is obviously atomic in any architecture. Therefore, why is this operation added to the repertoire of atomic operations? Table

> For the token-passing mutual exclusion algorithm, prove that it: a. guarantees mutual exclusion. b. avoids deadlock. c. is fair

> In the token-passing mutual exclusion algorithm, is the timestamping used to reset clocks and correct drifts, as in the distributed queue algorithms? If not, what is the function of the timestamping?

> For the mutual exclusion algorithm of [RICA81], a. Prove that mutual exclusion is enforced. b. If messages do not arrive in the order that they are sent, the algorithm does not guarantee that critical sections are executed in the order of their requests.

> For Lamport’s algorithm, are there any circumstances under which Pi can save itself the transmission of a Reply message?

> For Figure 19.9, it is claimed that all four processes assign an ordering of to the two messages, even though q arrives before a at Work through the algorithm to demonstrate the truth of the claim Figure 19.9: PI P4 (a,1,1) I (q.1,4) Time (local clo

> In priority-based process scheduling, the scheduler only gives control to a particular process if no other process of higher priority is currently in the Ready state. Assume no other information is used in making the process scheduling decision. Also ass

> Some have argued that Unix/Linux systems reuse a small number of security features in many contexts across the system; while Windows systems provide a much larger number of more specifically targeted security features used in the appropriate contexts. Th

> What are the advantages and disadvantages of using a file integrity checking tool (e.g., tripwire). This is a program which notifies the administrator of any changes to files on a regular basis? Consider issues such as which files you really only want to

> TFTP’s time-out-and-retransmission scheme implies that all data packets will eventually be received by the destination host. Will these data also be received uncorrupted? Why or why not?

> We have seen that in order to deal with lost packets, TFTP implements a time-out-and-retransmit scheme, by setting a retransmission timer when it transmits a packet to the remote host. Most TFTP implementations set this timer to a fixed value of about fi

> What is the difference between a multiprocessor and a multicore system?

> TFTP, like most protocols, will never send an error packet in response to an error packet it receives. Why?

> The flushing policy is described in the subsection on process migration strategies in Section 19.1. a. From the perspective of the source, which other strategy does flushing resemble? b. From the perspective of the target, which other strategy does flush

> A user on a UNIX host wants to transfer a 4,000-byte text file to a Microsoft Windows host. In order to do this, he transfers the file by means of TFTP, using the netascii transfer mode. Even though the transfer was reported as being performed successful

> What is the limiting factor in the time required to transfer a file using TFTP?

> The previous version of the TFTP specification, RFC 783, included the following statement: All packets other than those used for termination are acknowledged individually unless a timeout occurs. The new specification revises this to say All packets othe

> Why does the TCP header have a header length field while the UDP header does not?

> The following FORTRAN program is to be executed on a computer, and a parallel version is to be executed on a 32- b computer cluster: L1: DO 10 I=1,1024 L2: SUM(I)=0 L3: DO 20 J=1, I L4: 20 SUM(I)=SUM(I)+I L5: 10 CONTINUE Suppose lines 2 and 4 each take t

> An application program is executed on a nine-computer cluster. A benchmark program takes time T on this cluster. Further, 25% of T is time in which the application is running simultaneously on all nine computers. The remaining time, the application has t

> Let be the percentage of program code that can be executed simultaneously by n computers in a cluster, each computer using a different set of parameters or initial conditions. α Assume the remaining code must be executed sequentially by a single processo

> A TCP segment consisting of 1,500 bits of data and 160 bits of header is sent to the IP layer, which appends another 160 bits of header. This is then transmitted through two networks, each of which uses a 24-bit packet header. The destination network has

> Figure 6.18 shows another solution to the dining philosophers problem using monitors. Compare to Figure 6.14 and report your conclusions. Figure 6.18: Figure 6.14: monitor dining_controller; enum states (thinking, hungry, eating) state [5]; cond ne

> List the major disadvantages of the layered approach to protocols.

> For this problem, first consider the case where you wish to order pizza for a party of guests. The layer models in Figure 17.8 can be used to describe the ordering and delivery of a pizza. The guest effectively places the order with the cook. The host co

> Consider user accounts on a system with a Web server configured to provide access to user Web areas. In general, this scheme uses a standard directory name, such as , in a user’s home directory. This acts as the user’s Web area if it exists. However, to

> In the traditional UNIX file access model, UNIX systems provide a default setting for newly created files and directories, which the owner may later change. The default is typically full access for the owner combined with one of the following: no access

> UNIX treats file directories in the same fashion as files; that is, both are defined by the same type of data structure, called an inode. As with files, directories include a 9-bit protection string. If care is not taken, this can create access control p

> User “ahmed” owns a directory, “stuff,” containing a text file called “ourstuff.txt” that he shares with users belonging to the group “staff.” Those users may read and change this file, but not delete it. They may not add other files to the directory. Ot

> Set user (SetUID) and set group (SetGID) programs and scripts are a powerful mechanism provided by Unix to support “controlled invocation” to manage access to sensitive resources. However, precisely because of this, it is a potential security hole, and b