Kuwait University Kuwait-City, January 10, 2004; 11:00 - 13:00

Department of Mathematics & Computer Science

Prof Dr. habil. Peter Neubert

Clear writing using pen or ballpoint is required !!

Using a pencil will not be accepted !!
Give clear, precise and instantly recognizable answers !
Ambiguous answers, even if partly correct, will not be counted !
The use of all mobile communication equipments (mobiles, pagers,
etc.) is not allowed during the exam time !

Operating Systems
Final Examination

ID-No: _ _ _ - _ _ - _ _ _ _ Name: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Assignment: 1 2 3 4 5 6 7 8 9 10
Tasknumber in pool PE 376_69 376_85 376_24 376_35 376_65 376_67 376_72 370_78 376_80 376_74
376_70 376_68 376_77

Scores: Max.: 60 3 5 8 6 8 4 7 7 6 6

Your result: Total:

1. Is it possible to have a deadlock involving only one single process? Explain your answer.
Answer:
No. This follows directly from the hold-and-wait condition. 3

Consider a system consisting of four resources of the same type that are shared by three
processes, each of which needs at most two resources. Show that the system is deadlock free.

Answer:
Suppose the system is deadlocked. This implies that each process is holding one resource and
is waiting for one more. Since there are three processes and four resources, one process must
be able to obtain two resources. This process requires no more resources and, therefore it will
return its resources when done. 3

Fe_376.doc
Final Examination Operating System page: 2

2. The following shell script is given. Explain the actions done by this script ! Give examples
for a possible output if the script is executed !
#!/bin/sh
case $# in
0) echo „copy from: \c„
read from
echo „copy to: \c „
read to
;;
1) from=$1
echo „copy to: \c „
read to
;;
*) from=$1
to=$2
esac
cp $from $to
echo „ done !“

Answer:
The script can be used to copy files. The shell accepts maximal two file names as parameters.
There are different options available: 3
• No parameter: the shell explicitly asks for the source and destination file (and path)
name.
• One parameter: the shell interprets it as source file name and asks for the destination file
name.
• Two parameters: the shell does not ask for any parameter and performs the copy
immediately.
The following lines show an example for using the shell script without parameters. 2
castor: /.../os/tutorial 9 > sh ex376_46a
copy from: [Link]
copy to: [Link]
done !
Using the shell script with one parameter looks like follows.
castor: /.../os/tutorial 9 > sh ex376_46a [Link]
copy from: [Link]
copy to: [Link]
done !
Using the shell script with two parameters looks like follows.
castor: /.../os/tutorial 9 > sh ex376_46a [Link] [Link]
copy from: [Link]
copy to: [Link]
done !

3. Give the code of a C program (representing a parent process) that creates a child process
(called child 1) using the fork statement, and the newly created child creates again a
child process (called child 2). The child processes are complete images of the parent
process. While the parent process calculates the square of three (five), the child 1 process
calculates concurrently with the parent process the square of four (three), and the child 2
process calculates the square of five (four). All three processes output their results at the

Fe_376.doc
Final Examination Operating System page: 3

terminal immediately when they have finished their calculations. Make sure that the child and
parent processes will terminate properly.
To present the results use the following statements.
printf („Parent is printing 3*3 (5*5) = %d\n“, 3*3 (5*5))
printf („Child 1 is printing 4*4 (3*3) = %d\n“, 4*4 (3*3))
printf („Child 2 is printing 5*5 (4*4)= %d\n“, 5*5 (4*4))
where printf is in the header file stdio.h.

Answer:
The program is as follows.
#include <stdio.h>
void main ()
{
int pid;
pid = fork ();
if (pid == 0)
{
pid = fork ();
if (pid == 0)
{
printf („Child 2 is printing 5*5 (4*4)= %d\n“, 5*5 (4*4));
exit ();
}
printf („Child 1 is printing 4*4 (3*3)= %d\n“, 4*4 (3*3));
exit ();
}
printf („Parent is printing 3*3 (5*5)= %d\n“, 3*3 (5*5));
wait (NULL);
} 8
The output of the program is as follows.
Child 2 is printing 5*5 (4*4)= 25 (16)
Parent is printing 3*3 (5*5) = 9 (25)
Child 1 is printing 4*4 (3*3) = 16 (9)

4. Explain the differences between

a) symmetric message passing and
b) asymmetric message passing.

Answer:
Message passing is a form of information exchange between a sender process S and a receiver
process R. To exchange a message, the sender S executing a send statement and the receiver
R executing a receive statement have to meet. This is called S and R have a rendezvous.
a) Symmetric message passing: sender and receiver identify each other explicitly.
S: send (R,message)
R: receive (S, message) 3
b) Asymmetric message passing: sender names the receiver, whereas the receiver is only
ready to accept a message but does not know the sender.
S: send (R,message)
Fe_376.doc
Final Examination Operating System page: 4

R: receive (message) 3

5. Consider the following set of processes, with the length of the CPU-burst time given in
milliseconds.

Process Burst Time Priority

P1 10 3
P2 1 1
P3 2 3
P4 1 4
P5 5 2

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.
a) Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a
non-preemptive priority (a smaller priority number implies a higher priority), and RR
(quantum = 1) scheduling.
b) What is the turnaround time of each process for each of the scheduling algorithms in part
a) ?
c) What is the waiting time of each process for each of the scheduling algorithms in part a) ?
d) Which of the schedules in part a) results in the minimal average waiting time (over all
processes)?

Answer:
a) The four Gantt charts are
FCFS:

P1 P2 P3 P4 P5

5 10 15 20 25
1
SJF:

P2 P4 P3 P5 P1

5 10 15 20 25
1
Priority:

P2 P5 P1 P3 P4

5 10 15 20 25
1
RR:

P1 P2 P3 P4 P5 P1 P3 P5 P1 P5 P1 P5 P1 P5 P1

5 10 15 20 25
1
b) Turnaround time
Fe_376.doc
Final Examination Operating System page: 5

FCFS SJF Priority RR

P1 10 19 16 19
P2 11 1 1 2
P3 13 4 18 7
P4 14 2 19 4
P5 19 9 6 14
5
c) Waiting time (turnaround time minus burst time)

FCFS SJF Priority RR

P1 0 9 6 9
P2 10 0 0 1
P3 11 2 16 5
P4 13 1 18 3
P5 14 4 1 9
5
d) Calculation of average waiting time:
FCFS:
twav = (0+10+11+13+15)/5 = 49/5 = 9.8
SJF:
twav = (9+0+2+1+4)/5 = 16/5 = 3.2
Priority:
twav = (6+0+16+18+1)/5 = 41/5 = 8.2
RR:
twav = (9+1+5+3+9)/5 = 27/5 = 5.4
The minimal average waiting time is given with the Shortest Job First schedule. 1

6. What is the meaning of the term busy waiting? What other kinds of waiting are there in an
operating system? Can busy waiting be avoided altogether? Explain your answer.

Answer:
Busy waiting is a permanent execution of a NOP instruction to implement mutual exclusion
and a semaphore. This continual looping is clearly a disadvantage in multiprocessing systems,
where a single CPU is shared among many processes. Busy waiting wastes CPU cycles that
some other processes might be able to use productively.
Another kind of waiting is possible when we modify the definition of the wait and signal
semaphore operation. In case of having to wait a process could block itself. This process is
moved into the waiting queue. When some other process executes a signal operation, this
process could be restarted by a wakeup operation.
Nevertheless, even with the definition of the wait and signal operation busy waiting
cannot be completely eliminated. We have still limited busy waiting in the critical sections of
the wait and signal operation, which is typically very short and can be accepted. 4

Fe_376.doc
Final Examination Operating System page: 6

Explain why spinlocks are not appropriate for uniprocessor systems yet may be suitable for
multiprocessor systems.

Answer:
The advantage of a spinlock is that no context switch is required when a process must wait on
a lock, and a context switch may take considerable time. Thus, when locks are expected to be
held for short times, spinlocks are useful. In multiprocessor system, were we have multiple
CPUs, this short interval of wasting CPU cycles can rather be accepted. In single-processor
system, were we have just one CPU, the spinlock reduces the performance because of having
other processes which could use the CPU more efficiently. 4

7. Given memory partitions of 100K, 500K, 200K, 300K, and 600K (in order), how would
each of the first-fit, best-fit, and worst-fit algorithms place processes of 212K,
417K, 112K, and 426K (in order)? Which algorithm makes the most efficient use of memory?

Answer:
a) first-fit:
212K is put in 500K partition,
417K is put in 600K partition,
112K is put in 288K partition (new partition 288K = 500K - 212K !!),
426K must wait; 2
b) best-fit:
212K is put in 300K partition,
417K is put in 500K partition,
112K is put in 200K partition,
426K is put in 600K partition; 2
c) worst-fit:
212K is put in 600K partition
417K is put in 500K partition
112K is put in 388K partition
426K must wait 2
In this example, best-fit turns out to be the best. 1

8. Consider the following page reference string:

1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.
How many page faults would occur for the following replacement algorithms, assuming one,
two, three, four, five, six, or seven frames? Remember all frames are initially empty, so your
first unique pages will all cost one fault each.
• LRU replacement,
• FIFO replacement,

Answer:
A detailed presentation of all these cases is given below.
LRU replacement:
1 frames available:

Fe_376.doc
Final Examination Operating System page: 7

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Total number of page faults: 20
2 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 3 3 2 1 1 6 6 1 3 3 6 6 2 2 1 6
2 2 4 4 2 5 5 2 2 2 7 7 3 3 1 3 3
Total number of page faults: 18
3 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 4 4 5 5 5 1 1 7 7 2 2 2
2 2 2 2 2 6 6 6 3 3 3 3 3 3
3 3 1 1 1 2 2 2 2 6 6 1 6
Total number of page faults: 15
4 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 1 1 1 6 6
2 2 2 2 2 2 2 2 2
3 3 5 5 3 3 3 3
4 4 6 6 7 7 1
Total number of page faults: 10
5 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2
3 3 3 6 6 6
4 4 4 3 3
5 5 5 7
Total number of page faults: 8
6 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3
4 4 4 7
5 5 5
6 6
Total number of page faults: 7
7 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3
4 4 4 4
5 5 5
6 6
7
Total number of page faults: 7

Fe_376.doc
Final Examination Operating System page: 8

FIFO replacement:
1 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
Total number of page faults: 20
2 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 3 3 2 2 5 5 2 2 2 7 7 3 3 1 3 3
2 2 4 4 1 1 6 6 1 3 3 6 6 2 2 2 6
Total number of page faults: 18
3 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 4 4 4 6 6 6 3 3 3 2 2 2 2
2 2 2 1 1 1 2 2 2 7 7 7 1 1 1
3 3 3 5 5 1 1 1 1 6 6 6 3 6
Total number of page faults: 16
4 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 5 5 5 5 3 3 3 3 1 1
2 2 2 2 6 6 6 6 7 7 7 7 3
3 3 3 3 2 2 2 2 6 6 6 6
4 4 4 4 1 1 1 1 2 2 2
Total number of page faults: 14
5 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 6 6 6 6 6
2 2 2 2 2 1 1 1 1
3 3 3 3 3 2 2 2
4 4 4 4 4 3 3
5 5 5 5 5 7
Total number of page faults: 10
6 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 1 7 7 7 7
2 2 2 2 2 2 1 1 1
3 3 3 3 3 3 2 2
4 4 4 4 4 4 3
5 5 5 5 5 5
6 6 6 6 6
Total number of page faults: 10
7 frames available:

1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
1 1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3
4 4 4 4
5 5 5

Fe_376.doc
Final Examination Operating System page: 9

6 6
7
Total number of page faults: 7

Finally, one can present all the page faults in a table

Number of frames LRU FIFO

1 20 20
2 18 18
3 15 16
4 10 14
5 8 10
6 7 10
7 7 7
for each value: 1

9. Consider a file currently consisting of 100 blocks. Assume that the file control block is
already in memory. Calculate how many disk I/O operations are required for contiguous, and
linked allocation strategies, if, for one block, the following conditions hold. In the contiguous
allocation case, assume that there is no room to grow in the beginning, but there is room to
grow in the end. Assume that the block information to be added is stored in memory.
a) The block is added at the beginning.
b) The block is added in the middle.
c) The block is added at the end.
d) The block is removed from the beginning.
e) The block is removed from the middle.
f) The block is removed from the end.

Answer:
First a detailed investigation of the file operations is given.
Contiguous allocation strategy:

Fe_376.doc
Final Examination Operating System page: 10

The contiguous allocation method

allocates to each file a set of directory:
contiguous blocks on the disk. This file start length
brings automatically a minimum of test 1 2
test pict 14 4
head movements for accessing the 0 1 XXX 2 XXX 3 mail 19 5
file. The file is identified on the unit1
list
unit1
28
6
4
2
disk by the address of the first 4 5 6 XXX 7 XXX

block and the number of blocks.

8 9 10 11 0
This concept is suitable for
pict block with number:
sequential access as well as for 12 13 14 XXX 15 XXX
direct access. The following figure mail
shows the concept. 16 XXX 17 XXX 18 19 XXX

The difficulty with this method is

20 XXX 21 XXX 22 XXX 23 XXX
finding space for a new file. We
have to find a set of contiguous 24 25 26 27
blocks on the disk in order to save list
the file. First-fit and best-fit 28 XXX 29 XXX 30 XXX 31 XXX

algorithms are also here the most

common strategies used to select a
free hole from the set of available series of blocks.
In details the actions performed are as follows.
a) 100 read-in operations, 1 write-out operation, 100 write-out operations: 201
b) 50 read-in operations, 1 write-out operation, 50 write-out operations: 101
c) 1 write-out operation: 1
d) 99 read-in operations, 99 write-out operations, overwriting the first block: 198
e) 49 read-in operations, 49 write-out operations (the first overwrites the deleted block): 98
f) no operation at all (just changing the length field in the directory): 0
Linked allocation strategy:
With linked allocation, each file is
a linked list of disk blocks; see the car
0 -1 1 14XX 2 5XX 3 7XX
following figure. In order to create directory
yacht
a new file, a new entry is created 4 -1 5 3XX 6 23XX 7 -1
file start end
car 2 7
in the directory with an initial camel 22 4
pointer set to nil (end-of-list 8 9 10XX 10 4XX 11 27XX plane 19 14
ship 12 0
pointer value). A write operation ship
yacht 6 18
12 13XX 13 25XX 14 -1 15
causes a free block to be found by
plane
the free-space management 16 17 18XX 18 -1 19 20XX -1: end-of-file value
module, and this new block camel
receives the data to be stored and 20 21XX 21 1XX 22 11XX 23 24XX
is linked to the end of the file. To
24 30XX 25 31XX 26 27 9XX
read a file, one simply has to read
blocks by following the pointers 28 29 30 17XX 31 0XX
from block to block.
In details the actions performed
are as follows.
a) 1 write-out operation: 1
b) 50 read-in operations, 2 write-out operation (one with the new link and the new block): 52
c) 1 read-in operation, 1 write-out operation, 1 write-out operation: 3
d) 1 read-in operation to update the directory block: 1
e) 51 read-in operations, 1 write-out operations (with the new link): 52

Fe_376.doc
Final Examination Operating System page: 11

f) 99 read-in operations, 1 write-out operation (the last one with EOF mark): 100
The following table gives a summary of all disk operations.

Contiguous Linked
a) 201 1
b) 101 52
c) 1 3
d) 198 1
e) 98 52
f) 0 100
for each correct value: 1

10. Consider a logical address space of eight pages of 1024 words each, mapped onto a
physical memory of 32 frames.
a) How many bits are there in the logical address?
b) How many bits are there in the physical address?

Answer:
a) Logical address: (3+10) = 13 bits 3
b) Physical address: (5+10) = 15 bits 3

A certain computer provides its users with a virtual-memory space of 4 Gbyte. The computer
has 256 Kbyte of physical memory. The virtual memory is implemented by paging, and the
page size is 4096 bytes. A user process generates the virtual address 1112345A. Explain how
the system establishes the corresponding physical location.

Answer:
The virtual address in binary form is
0001 0001 0001 0010 0011 0100 0101 1010
Since the page size is 212, the page table size is 220 (length of virtual address: 32 bit, offset
length: 12 bit). Therefore the low-order 12 bits
0100 0101 1010 3
are used as the offset in the page, while the remaining 20 bits
0001 0001 0001 0010 0011 3
are used as the displacement in the page table.

Fe_376.doc