Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a publicly-available Web site.
CMPUT 379 – Practice Questions
Time: xx minutes Questions: xx
• Please, no questions during exam time.
Copyright By PowCoder代写 加微信 powcoder
• If you are unsure, write down your assumptions. • Write legibly (else, you risk losing marks!)
• Answer each question on a separate page.
1. General Concepts
Closed Book Calculators Allowed
1.1 Briefly explain (in point-form) each of the following concepts/objects:
• time-sharing, multiprogramming, multiprocessing operating systems
• threads, processes, programs, jobs
• process states in 4.3BSD UNIX (as introduced in the classroom)
• the memory resident part, and the swappable part of a process’ PCB in 4.3BSD UNIX (as introduced in the classroom)
• perror(), and errno in UNIX (see, e.g., [SR 3/E] Section 1.7 on Error Handling)
• fork(), and execl() UNIX system calls
• posted, delivered, pending, and blocked signals in UNIX
• thesignal()systemcall(inolderUNIXenvironments),andthe(POSIX)sigaction() system call
• pipes, named-pipes, and sockets in UNIX
• I/O multiplexing using the poll() or select() functions in Unix, and their role in
designing server programs
• the use of socket(), accept(), bind(), listen(), and connect() calls for inter process communication.
• basic design requirements that arise in solving critical section problems
• binary semaphores, counting semaphores, POSIX semaphores
2. Processes and IPC
2.1 In the M68000 family of CPUs, a Status Register is a special register composed of two bytes:
• The user byte 0 0 0 X N Z V C stores the following 1-bits flags: the extend (X), negative (N), zero (Z), overflow (V), and carry (C) flags. Arithmetic and logical instructions affect these flags.
• The system byte T 0 S 0 0 I2 I1 I0 stores the interrupt mask (I2, I1, I0), the user/supervisor (S) bit, and the CPU trace (T) bit.
Which of the following low-level operations is potentially disastrous in a UNIX-like environ- ment? Which is not? Why?
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a publicly-available Web site.
(a) A process running in the user mode and reading the contents of the user byte (b) Repeat (a) for reading the system byte while in the user mode.
(c) Repeat (a) and (b) for writing, instead of just reading.
2.2 List at least three actions that a running process might do that would cause the scheduler not to move it to the ready state when it stops running.
2.3 In UNIX, what does a forked process inherit from its parent?
2.4 In UNIX, suppose that a parent process and its child wish to establish two-way communica-
tions. Explain how this can be accomplished using pipes.
2.5 In UNIX, suppose that a parent process wishes to create 3 child processes, and allow any child to send data to any other child using a pipe. How many pipes must be created? Which process(es) should create the pipes?
2.6 Practice exercise 3.1, page 149 in [SGG 9/E], on the program in Fig. 3.30
2.7 Practice exercise 3.2, page 149 in [SGG 9/E], on the program in Fig. 3.31
2.8 Exercise 3.11, page 152 in [SGG 9/E], on the role of the init process
2.9 Exercise 3.12, page 152 in [SGG 9/E], on the program in Fig. 3.32
2.10 Exercise 3.13, page 152 in [SGG 9/E], on the program in Fig. 3.33
2.11 Exercise 3.14, page 152 in [SGG 9/E], on the program in Fig. 3.34
2.12 Exercise 3.16, page 153 in [SGG 9/E], on the RPC mechanism. (The use of word enforcing in the exercise is like using the word supporting.)
Note: Refer to Section 3.6.2 in [SGG 9/E] for an introduction to Remote Proce- dure Calls (RPC). RPC is an IPC mechanism between processes on the same, or different, hosts. The mechanism allows a program (running in a process on one host) to invoke a function (possibly, provided by a linked library) for a service. The function acts as a client that sends a packet to a server on some TCP or UDP port. The server replies to the client, and the function returns a result to the calling program.
2.13 Exercise 3.17, page 153 in [SGG 9/E], on the program in Fig. 3.35
3. Threads
3.1 For pthreads, how can a single thread within a process exits so that
a) the entire process exists
b) only the thread’s flow of control stops
3.2 Exercise 4.8, page 192 in [SGG 9/E], on multithreaded processes
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a publicly-available Web site.
3.3 Exercise 4.16, page 193 in [SSG 9/E], on using Linux (3.2.0) clone() to create processes and threads. Instead of contrasting the two approaches (as mentioned in the exercise), give an example of a kernel function that becomes simpler to implement when clone() is used, and an example of a kernel function that becomes harder to implement when clone() is used.
3.4 Exercise 4.17, page 193 in [SGG 9/E], on the program in Figure 4.16
3.5 Exercise 4.19, page 194 in [SGG 9/E], on pthread setcancelstate()
Note: As mentioned in Section 11.5 (Thread Termination) in [SR 3/E], a thread
can request that another thread in the same process be cancelled by calling pthread cancel(tid). In default circumstances, the thread specified by tid will behave as if it had
called pthread exit(PTHREAD CANCELLED). Exiting, however, does not
happen immediately, and pthread cancel(tid) does not wait for the spec-
ified thread to terminate. As mention in Section 12.7 (Cancel Options) in [SR 3/E],
a thread can change its cancelability state from the default PTHREAD CANCEL ENABLE
to PTHREAD CANCEL DISABLE by calling pthread setcancelstate(newValue, &oldValue).
4. Performance Analysis
4.1 Two processes, a producer and a consumer, communicate through a pipe. The capacity of the pipe is P “chunks” of data. The two processes work as follows:
producer() { repeat N times
consumer() { repeat N times
{write one chunk of data into the pipe} }}
{read one chunk of data from the pipe}
The producer requires time tp for each loop iteration, while the consumer requires time tc for each of its iterations. Both programs are non-blocking except that:
• The producer blocks if it tries to write into a full pipe. It remains blocked until the pipe is no longer completely full.
• The consumer blocks if it tries to read from an empty pipe. It remains blocked until the pipe is no longer completely empty.
(a) Assume that P < N. Suppose that both processes and the pipe are created at t = 0. Suppose that the producer process has a higher scheduling priority than the consumer, so that the scheduler will always run it if its runnable. At what times will each of the two processes finish executing?
(b) Repeat (a) under the assumption that P ≥ N .
(c) Repeat (a) assuming the consumer, rather than the producer, has higher scheduling pri-
4.2 Exercise 4.18, page 193 in [SGG 9/E], on running multithreaded programs using the many- to-many threading model on a multicore system.
Copyright Notice: Copyright by CMPUT 379, U. of Alberta, course instructor (E. Elmallah). All rights reserved. Do not post any part on a publicly-available Web site.
5. Process Synchronization
5.1 (Related to Exercise 5.8, page 243 in [SGG 9/E], on Dekker’s algorithm) Show that Dekker’s algorithm (on course slides) satisfies the bounded waiting requirement.
5.2 This question refers to the Peterson’s Algorithm, as presented on the course slides (you don’t have to memorize the algorithm during the exam). If we were to change the statement turn= his turn (in mutexBegin(i)) to turn= my turn, what would this modi- fication cause:
(a) No real change at all. The purpose of turn is to resolve which process can proceed to the critical section, when both processes wish to enter the critical section at the same time.
(b) Deadlock. The mutual exclusion will be preserved, but the processes will eventually deadlock.
(c) Lack of mutual exclusion. The processes will not reach deadlock, but they will be able to be both present in the critical section at the same time.
(d) Both deadlock and lack of mutual exclusion. It is possible that the processes will dead- lock and it is also possible that they will both be present in the critical section at the same time.
Explain your answer.
5.3 Prove that, in the bakery algorithm (course slides) the following property holds: If Pi is in its critical section, and Pk (k ̸= i) has already chosen its number[k] ̸= 0, then (number[i], i) < (number[k], k).
5.4 Exercises 5.10 and 5.11, pages 243-244 in [SGG 9/E], on disabling interrupts
5.5 Exercise 5.12, page 244 in [SGG 9/E], on a Linux spinlock policy
5.6 Exercise 5.13, page 244 in [SGG 9/E], on race conditions on kernel data structures
5.7 Exercise 5.14, page 244 in [SGG 9/E], on using the compare and swap() instruction to provide mutual exclusion and bounded-waiting.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com