Fachhochschule München FB 07 - Informatik Prof. Dr. Christian Vogt
Written Examination on "Operating Systems" WS 2003/04
Page 1/9
Date: 26. Januar 2004 Name: ______First Name: ______
Duration: 90 Minutes Matr.-Nr.: ______Group: ______
Utilities: None Signature: ______ (except calculator)
Please give your solutions on these sheets. If necessary, use back sides as well. Give a reasoning for all your answers!
Exercise 1: (approx. 6/100 Points)
An application, consisting of several threads, uses two exclusive resources A and B, mutual exclusion being achieved by using two mutexes. When a thread needs access to both resources, it always requests the mutex for B first, and then the one for A.
Is it possible that this application runs into a deadlock? If so: how, and what can be done in order to avoid deadlocks? If not so: why not?
Page 2/9
Exercise 2: (approx. 12/100 Points)
a) Explain the concepts „process“ and „thread“ in an operating system.
b) Which advantages may it have to use several threads in an application?
Page 3/9
Exercise 3: (approx. 14/100 Points)
a) Both in Windows and in Solaris there are two „kinds“ or „classes“ of priorities, one of which is called „real time priorities“. Explain the basic differences between these two kinds of priorities for one of these operating systems.
I will give the explanation for the ______operating system.
b) Describe the dynamic adjustment of priorities by the operating system for either the Windows or the Solaris operating system. (It is not important to give all the details, which for Solaris are quite numerous.)
I will give the explanation for the ______operating system.
Page 4/9
Exercise 4: (approx. 10/100 Points)
On a system with two CPUs P1 und P2 , 4 Threads are awaiting execution, which are placed in the queue of ready threads in the order A - B - C - D. The threads have the following properties:
A: execution time 6 time units, blocks every 3 time units
B: execution time 6 time units, blocks every 2 time units
C: execution time 6 time units, blocks every 3 time units
D: execution time 2 time units, blocks after each time unit
The blocking time always is less than one time unit. When a thread becomes ready again, it is inserted at the tail of the queue. No preemption of a running thread takes place.
a) How are the threads executed?
P1 time
P2 time
b) How are the threads executed, when the scheduler always chooses the first thread in the queue of ready threads which has „soft affinity“ to the available processor (resp. the first thread in the queue if none of the threads has “soft affinity”)?
P1 time
P2 time
c) What is the effect on the elapsed times of the threads of taking “soft affinity” into account in this example? Which (unrealistic) assumption in the exercise hides the advantage of taking soft affinity into account?
Page 5/9
Exercise 5: (approx. 10/100 Points)
a) Explain how a race condition can occur when two threads both increment a shared variable.
b) What are the possible values of this variable after both operations complete, and which of the values is the correct one?
Page 6/9
Exercise 6: (approx. 14/100 Points)
An application consists of several threads, and needs to ensure mutual exclusion for some critical sections in the code. Describe – either for Windows or for Unix – one of the mechanisms offered by the operating system in order to achieve this. If possible, give all the details of the functionality of the mechanism you choose.
I will describe ______in the ______operating system.
Page 7/9
Exercise 7: (approx. 12/100 Points)
Describe the meaning of the following bits in a page table entry. Also specify in each case, who (hardware, operating system component, application) sets, clears, and reads (evaluates) the bit.
a) Valid Bit
b) Modify Bit
c) Reference Bit
(no details about the use of this bit!)
d) Copy-on-write Bit
(no details about the use of this bit!)
Page 8/9
Exercise 8: (approx. 12/100 Points)
a) Describe (e.g. by sketching a figure) the format of a virtual address and the course of actions of an address translation for a system working with 2-level paging.
b) What determines the size of the virtual and of the physical address space?
c) Why can it be meaningful to provide a physical address space which is bigger than the virtual one?
(One of the two possible answers suffices. Additional points for two correct answers.)
Page 9/9
Exercise 9: (approx. 10/100 Points)
Describe the page replacement using the two-handed-clock-algorithm.
(If you are not able to answer this question, you may as well describe the second-chance-algorithm. However, this will yield fewer points.)