Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

Question 1
Question 2
Two processes, P0 and P1, are to be run and they update a shared variable. This update is a) With regards to I/O design principles describe the layers of the I/O system and justify
protected by Petersons solution to the mutual exclusion problem. this structure.

a) Show Petersons algorithm and show the truth table for the part of the algorithm which (15)
dictates if a process is allowed to enter its critical region.
b) Consider the following C-language I/O statement:
(10)
count = read(fd, buffer, nbytes);
b) P0, attempts to enter its critical region. Show the state of the variables that are
created/updated. Will P0 be allowed to enter its critical region? If not, why not? where fd is an integer (called the file descriptor)
buffer is a memory address pointing into the processes data memory
(5) nbytes is an integer indicating the number of bytes to be read.

c) P1, attempts to enter its critical region. Show the state of the variables that are Supposing that fd refers to a file on disk with a controller which uses DMA, describe
created/updated. Will P1 be allowed to enter its critical region? If not, why not? how this statement may be handled in the layers of the I/O system?

(5) 5 marks

d) P0 leaves its critical region. What effect does this have on the variables? c) How are devices represented in the UNIX operating system? How are the drivers
specified? Could the file descriptor in question (b) be referring to a terminal? What
(2) would be the difference if this were so?

e) Assume no processes are running and P0 and P1 try to enter their critical region at 5 marks
exactly the same time. What will happen?

(3)

Graham Kendall Graham Kendall

Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

Question 3
Question 4
a) Describe the following scheduling algorithms
(a) Given a disk with 200 tracks, where track requests are received in the following
• Non Pre-Emptive, First Come, First Serve order
• Round Robin
• Shortest Job First 55, 58, 39, 18, 90, 160, 150, 38, 184.

(9) The starting position for the arm is track 100. Calculate the number of tracks
crossed when the following algorithms are used
b) Given the following processes and burst times
• First Come First Serve
Process Burst Time • Shortest Seek First
P1 13 • The elevator algorithm starting in the direction UP.
P2 5
P3 23
P4 3 (15)
P5 31
P6 3 b) Briefly explain, in which of the following cases can the algorithms in (a) augment its
P7 14 performance?
• A process is reading 10,000 blocks with consecutive disk addresses.
• A process is reading 10,000 blocks with random disk addresses.
Calculate the average wait time when each of the above scheduling algorithms is used? • A process is creating child processes to read 10,000 blocks with random
addresses.
Assume that a quantum of 6 is being used. • Processes are communicating with each other by writing and reading blocks to
disk.
(12)
(8)
c) Which scheduling algorithm, as an operating systems designer, would you implement?

(4) c) In the last case of question (b), could the algorithm influence the synchronisation
between the processes?

(2)

Graham Kendall Graham Kendall

 Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

Question 5 Question 6
a) The buddy system is a memory management scheme that uses variable sized partitions. a) Every file in a filing system has a set of attributes (read only, date created etc.).
Assume a filing system allows an attribute of temporary, meaning the creating process
Explain the basic principle behind the buddy system. only uses the file during the time it is executing and has no need for the data thereafter.
Assume the process is written correctly, so that it deletes the file at the end of its
(5) execution. Do you see any reason for an operating system to have temporary file
attribute? Give your reasons.
b) Assume a computer with a memory size of 256K, initially empty. Requests are
received for blocks of memory of 17K, 6K, 63K and 9K. Show how the buddy system (5)
would deal with each request, showing the memory layout at each stage and the status of
the lists at each stage. b) An operating system supplies system calls to allow you to COPY, DELETE and
RENAME a file.
(8) Discuss the differences between using COPY/DELETE and RENAME to give a file new
name?
(c) The processes terminate in the following order; 6K, 9K, 17K and 63K. Discuss what (5)
happens as each process terminates.
c) There is some debate as to what will constitute a fifth generation computer. Assume
(4) such a computer is available. What do you think will differentiate it from the computers
of today?
What advances do you think need to be made in order to produce a fifth generation
d) Describe and evaluate an alternative to the buddy system computer?

(8) (15)

Graham Kendall Graham Kendall

Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

Question 1 – Model Answer 5 marks, pro-rata, for how much the student re-produces

This question formed the basis of an exercise sheet given out in the lectures. (d) P0 leaves its critical region. What effect does this have on the variables?
P0 will set interested[0] to FALSE. This will allow the WHILE loop that P1 is
(a) Petersons Solution – The algorithm executing to terminate as
turn == process == TRUE && interested[0] == FALSE, thus allowing line 3 to be
int No_Of_Processes; called and P1 can now enter its critical region
int turn;
int interested[No_Of_Processes]; 2 marks, pro-rata, for how much the student re-produces
void enter_region(int process) {
int other;
other = 1 – process; (e) P0 and P1 try to enter their critical region at exactly the same time.
interested[process] = TRUE; As other is a local variable then both calls can set this variable without any problems.
turn = process; Similarly, the relevant element of the interested array can be set without race
while(turn == process && interested[other] == TRUE); conditions occurring.
}
As turn is a shared variable, there is the potential of race conditions occurring.
void leave_region(int process) { Assume P0 sets turn to zero and it is immediately set to one by P1 (or vice versa). Due
interested[process] = FALSE; to the WHILE statement, it does not matter which process sets the variable first (or
} last), only one of the processes will be allowed to enter its critical region. The other
will be forced to wait. That is,
8 marks (pro-rata) for re-producing the algorithm.
turn == process interested[other] = TRUE Action
The truth table for the while loop P0 F T F (Continue)
P1 T T T (Wait)
turn == process Interested[other] = TRUE Action
1. F F F (Continue) 3 marks if the student mentions all the above. 2 marks for mentioning part of it. 1
2. F T F (Continue) consolation mark for stating that one process can enter its critical region and the
3. T F F (Continue) other one will be forced to wait.
4. T T T (Wait)

2 marks for showing the truth table

(b) P0 tries to enter its critical region

other = 1, turn = 0
interested[0] = TRUE, interested[1] = FALSE
turn == process == TRUE && interested[other] == FALSE, therefore line 3 will be
called (above truth table) and thus P0 will be allowed to enter its critical region

5 marks, pro-rata, for how much the student re-produces

(c) P1 tries to enter its critical region

other = 0, turn = 1
interested[0] = TRUE, interested[1] = TRUE
turn == process == TRUE && interested[other] == TRUE, therefore line 3 will be
called and thus P1 will NOT be allowed to enter its critical region

Graham Kendall Graham Kendall

 Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

Question 2 – Model Answer Device independent I/O software will perform the following tasks:
Provide uniform interfaces for the device drivers
a) With regards to I/O design principles describe the layers of the I/O system and Do the naming
justify this structure. Handle device protection
Produce device independent block sizes
Layer Functions Buffer
User processes Produce I/O request, formatting, spooling Memory management on block devices
Device independent software Naming, protection, blocking, buffering, allocating Manage dedicated devices
Device drivers Setting device registers, check status Handle errors
Interrupt handlers Wake up the driver when I/O is ready As an example of naming, one can refer to the minor and major device numbers in
Hardware Perform the I/O operation
UNIX, and the representation of devices in the /dev directory. (see later)
6 marks for producing this table (pro-rata) Protection depends on the system. Personal systems (MS-DOS) need less protection
than mainframes. UNIX takes a way between with the rwx scheme.
Note: Stallings distinguishes general devices, communication devices and file Disks may differ in sector size. The OS should offer one block size and the device
systems. Each has a hardware, a scheduling and controlling and a device I/O layer independent software must do the translation. This is related to the concept of
(driver). The top layer is always “user processes”. The one layer in between is buffering. Buffers are used with block and character devices to bridge processing
different in the three cases: “logical I/O”, “Communication architecture” and speed differences.
three “sub-layers“ for the file system. Since this was presented in class, it should be The assignment of blocks, and the management of free blocks does not depend on
considered as a correct answer. the device, and is done in this layer.
Dedicated devices must be lockable. This can be implemented through the OPEN
The layered structure is justified by the need for efficiency on the hardware side and system call which locks the device or produces an error when it is occupied.
for uniformity, simplicity and device independence on the user side. User processes CLOSE will free the devices.
need a uniform way to treat I/O devices (e.g. UNIX). The naming must be Although errors are mostly treated by the device drivers, some errors may be passed
independent of the devices. Errors should be handled at the lowest level possible. to the upper layers.
Processes may produce I/O requests asynchronously, while, for efficiency, devices In the user processes I/O is handled by library routines translating the I/O requests
may be better of handling them in parallel. Some devices are dedicated, while other into system calls. Spooling systems must be considered as a user level solution for
can be shared. The handling of dedicated devices should be transparent and dedicated devices.
uniform.
9 marks for this discussion (pro-rata)
Interrupt handlers should be deeply hidden in the operating system, since treating
interrupts in a correct way is tricky and can cause serious system errors when done b) Consider the following C-language I/O statement:
incorrectly. The interrupt handlers may communicate with the device handlers
through the use of classical synchronisation techniques such as semaphores, signals count = read(fd, buffer, nbytes);
or monitors.
Device drivers contain all device dependent code. A driver can handle one type of where fd is an integer (called the file descriptor)
device or a set of related devices. The driver knows how to steer the controller, buffer is a memory address pointing into the processes data memory
knows about interleaving, tracks, cylinders,… It should offer an abstraction to the nbytes is an integer indicating the number of bytes to be read.
software layer above. It must accept requests at any time, but may put them in a
queue. The driver may wait for the controller to finish, effectively blocking, or it Supposing that fd refers to a file on disk with a controller which uses DMA,
may continue immediately in case it does not expect the controller to respond. In describe how this statement may be handled in the layers of the I/O system?
any case it has to check for possible errors.
“read” is a library routine which is linked to the program. It will produce a system call
to read nbytes from the file into the buffer. This system call will be treated at the
device independent software level to produce one or more I/O requests for blocks to
be read. It will select a buffer and pass it to the device driver. The device driver will
initiate a hardware I/O. It will pass the buffer address to the DMA module in the

Graham Kendall Graham Kendall

Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

controller. The device driver will then block. The controller will perform the I/O
operation on the disk, reading the requested sectors and checking for errors. Once the Question 3 – Model Answer
operation is finished, it will produce an interrupt. The device driver will then pass the
results to the device independent software which will copy the requested number of a) Describe the following scheduling algorithms
bytes to the original buffer.
3 marks available for each algorithm, pro-rata
5 marks, pro-rata, depending on how much of this the student covers

c) How are devices represented in the UNIX operating system? How are the drivers • Non Pre-Emptive, First Come, First Serve
An obvious scheduling algorithm is to execute the processes in the order they arrive and to execute them to
specified? Could the file descriptor in question (b) be referring to a terminal? completion. In fact, this simply implements a non-preemptive scheduling algorithm.
What would be the difference if this were so? It is an easy algorithm to implement. When a process becomes ready it is added to the tail of ready queue.
This is achieved by adding the Process Control Block (PCB) to the queue.
In UNIX devices are mounted into the filesystem. When the CPU becomes free the process at the head of the queue is removed, moved to a running state and
allowed to use the CPU until it is completed.
The problem with FCFS is that the average waiting time can be long.
1 mark

The drivers are specified by their major and minor numbers. • Round Robin
The processes to be run are held in a queue and the scheduler takes the first job off the front of the queue
and assigns it to the CPU (so far the same as FCFS).
1 mark In addition, there is a unit of time defined (called a quantum). Once the process has used up a quantum the
process is preempted and a context switch occurs. The process which was using the processor is placed at
Since devices look like files, the fd could refer to a terminal. In this case the device the back of the ready queue and the process at the head of the queue is assigned to the CPU.
independent software would apply buffering strategies for terminals which may be Of course, instead of being preempted the process could complete before using its quantum. This would
mean a new process could start earlier and the completed process would not be placed at the end of the
“raw” (character wise) or “cooked” (line wise). Other device drivers would be queue (it would either finish completely or move to a blocked state whilst it waited for some interrupt, for
involved. example I/O).
3 marks, pro-rata
The average waiting time using RR can be quite long.

• Shortest Job First

Using the SJF algorithm, each process is tagged with the length of its next CPU burst. The processes are
then scheduled by selecting the shortest job first.

In fact, the SJF algorithm is provably optimal with regard to the average waiting time. And, intuitively, this
is the case as shorter jobs add less to the average time, thus giving a shorter average.

The problem is we do not know the burst time of a process before it starts.

For some systems (notably batch systems) we can make fairly accurate estimates but for interactive
processes it is not so easy.

b) Given the following processes and burst times etc.

4 marks available for each algorithm. Full marks will be awarded for showing all
workings.

FCFS
The processes would execute in the order they arrived. Therefore, the processes would
execute as follows, with the wait times shown.

Graham Kendall Graham Kendall

 Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

Process Burst Time Wait Time Process Burst Time Wait Time
P1 13 0 P6 3 0
P2 5 13 P4 3 3
P3 23 18 P2 5 6
P4 3 41 P1 13 11
P5 31 44 P7 14 24
P6 3 75 P3 23 38
P7 14 78 P5 31 61

The average wait time is calculated as ∑WaitTime / No Of Processes The average wait time is calculated as ∑WaitTime / No Of Processes
= (0 + 13 + 18 + 41 + 44 + 75 + 78) / 7 = (0 + 3 + 6 + 11 + 24 + 38 + 61) / 7
= 269 / 7 = 143 / 7
= 32.43 = 20.43

Round Robin
This scheme allocates the processes to the CPU in the order they arrived, but only allows
them to execute for a fixed period of time (quantum = 8). Then the process is pre-empted c) Which scheduling algorithm, as an operating systems designer, would you
and placed at the end of the queue. implement?

This leads to the following wait times for each process This is an opportunity for the student to give their views on scheduling algorithms. As we
discussed in the lectures there is no ideal scheduling algorithm, there are always trade
Process Wait Time offs and compromises.
P1 47
P2 6 No marks will be awarded for saying shortest job first (SJF) would be implemented (as
P3 56 this is not possible), but an algorithm that estimates the burst time, so that SJF can be
P4 17 partially emulated would get some marks.
P5 61
P6 26 I would also give marks for saying that multi-level feedback queue scheduling would be a
P7 60 good choice as, by varying the parameters to this algorithm, it is possible to emulate all
the other algorithms we considered. But the student should also say that even this is not
I would expect the students to give more detail than this (as we did in the lecture ideal as vast amounts of testing and guesswork would still be needed. All implementing
exercises), to show they have applied the algorithm correctly. This, in essence, shows the this algorithm does is give you the flexibility to try various algorithms.
wait time at each stage of the process. If the students do this, but give the correct answer,
they should be given credit for applying the algorithm (half marks). Many other answers are possible and the marks will be awarded on the basis of their
However, if they do not show the working, but get the correct answer, then they should argument and how they defend it.
get full marks as they must have applied the algorithm to get the correct answer.

Summing all the wait times and dividing by the number of processes, gives us the
average wait time. That is

(47 + 6 + 56 + 17 + 61 + 26 + 60) = 273 / 7

= 39.00

Shortest Job First

This scheme, simply executes the process using the burst time as the priority. That is

Graham Kendall Graham Kendall

Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

3. The child processes will launch parallel I/O operations. The algorithms
Question 4 – Model Answer will reorder the random set of addresses so that better performance is
obtained.
4. Again processes are working in parallel on related block addresses. The
a) Given a disk with 200 tracks, where track requests are received in the algorithms will reorder the requests.
following order etc.
2 marks for each for each case (=8)
FCFS #crossings SSF #crossings Elevator #crossings
100 100 100
55 45 90 10 150 50 c) In the last case of question (b), could the algorithm influence the synchronisation
58 3 58 32 160 10 between the processes?
39 19 55 3 184 24
18 21 39 16 90 94 Since, in the last case, the algorithms do a reordering, the I/O requests will not be
90 72 38 1 58 32 performed in the order that they are produced. This may influence the
160 70 18 20 55 3 synchronisation between the processes.
150 10 150 132 39 16
38 112 160 10 38 1 2 marks
184 146 184 24 18 20
498 248 250

5 marks for each for each case (=15)

b) Briefly explain, in which of the following cases can the algorithms in (a) augment
its performance?
1. A process is reading 10,000 blocks with consecutive disk addresses.
2. A process is reading 10,000 blocks with random disk addresses.
3. A process is creating child processes to read 10,000 blocks with random
addresses.
4. Processes are communicating with each other by writing and reading blocks
to disk.

The performance of the algorithms is influenced by the way in which the requests
are initiated.
1. Consecutive production of I/O requests will make the process block
during each request, waiting before launching the following request.
Although the arm will be well positioned before each request, since the
addresses are consecutive, the algorithms cannot function since they
obtain the requests one by one.
2. Since the addresses are random, this operation will cause more arm
movements. But since the I/O requests are produced one after the other,
the algorithms still cannot operate.

Graham Kendall Graham Kendall

 Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

Question 5 – Model Answer The memory allocation will look like this (students only need to show down to the
arrow).
a) The buddy system is a memory management scheme that uses variable sized
partitions etc….

If we keep a list of holes (in memory) sorted by their size, we can make allocation to
processes very fast as we only need to search down the list until we find a hole that is big
enough.
The problem is that when a process ends the maintenance of the list is complicated. In
particular, merging adjacent holes is difficult as the entire list has to be searched in order
to find its neighbours. Allocation ends here. The
de-allocation is shown for
completeness
The Buddy System is a memory allocation that works on the basis of using binary
numbers as these are fast for computers to manipulate.

Lists are maintained which stores lists of free memory blocks of sizes 1, 2, 4, 8,…, n,
where n is the size of the memory (in bytes). This means that for a 256K memory we
require 19 lists.
If we assume we have 256K of memory and it is all unused then there will be one entry in
the 256K list; and all other lists will be empty.

5 marks, pro-rata

b) Assume a computer with a memory size of 256K, initially empty. Requests are 1 mark for each process allocated correctly
received for blocks of memory of 17K, 6K, 63K and 9K. Show how the buddy
system would deal with each request, showing the memory layout at each stage and The lists, at each stage, will look like this
the status of the lists at each stage.
List No. Block Size Start 17K 6K 63K 9K
1 1
2 2
3 4
4 8
5 16
6 32
7 64
8 128
9 256
10 512
11 1024 (1K)
12 2048 (2K)
13 4096 (4K)
14 8192 (8K) 40K 40K 40K
15 16384 (16K) 48K 48K
16 32768 (32K) 32K
17 65536 (64K) 64K 64K
18 131072 (128K) 128K 128K 128K 128K
19 262144 (256K) 0

Graham Kendall Graham Kendall

Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

Note : The list entries are memory addresses where a block of that size starts (e.g. initially there is 17 65536 (64K) 0K
one 256K block starting at address zero). The student should specify the addresses not just the 18 131072 (128K) 128K 128K 128K 128K
number of blocks of memory of that size. 19 262144 (256K) 0K
Each list could, in theory, hold more than one element but, in this case, this never happens.

1 mark for each list specified correctly where memory is allocated (i.e. no marks for
showing the initial state). 1 mark for each correct answer
(c) The processes terminate in the following order; 6K, 9K, 17K and 63K. Discuss
what happens as each process terminates. d) Describe and evaluate an alternative to the buddy system
The effect of each of these is described below and the changing lists are also shown. The Two alternatives were presented in the lectures. These were managing memory with bit
student can show either – but a description would be better. maps and managing memory with linked lists.

• When the 6K process is returned (b in the above diagram), the 8K slot of memory I would only expect a brief discussion of one of these methods. The notes below give
is returned. This returns a block of memory from 32K to 40K. Checking the 8K sample answers; although I would not expect the student to go into as much detail
list, it is found that there is an adjacent block of memory, which can be merged (certainly for linked lists) – just explain the basic principle of one of the schemes.
into a 16K block. Therefore the result is that the two 8K blocks are merged into a
16K block and this is added to the list. I would expect a brief evaluation with another scheme (probably the buddy system),
• When the 9K block is returned (d in diagram) this releases a 16K block of giving an evaluation of the scheme they have chosen to describe.
memory from 48K to 64K. Checking the 16K list there is a block from 32K (to
48K). As the two 16K blocks are consecutive it allows these two blocks to be Memory Usage with Bit Maps
merged into a 32K block.
Under this scheme the memory is divided into allocation units and each allocation unit
• The 17K block (a in diagram) returns a 32K block of memory from 0K to 32K. has a corresponding bit in a bit map. If the bit is zero, the memory is free. If the bit in the
This can be merged with the block from 32K to 64K, giving a block in the 64K bit map is one, then the memory is currently being used.
list. This scheme can be shown as follows.
• The final release of memory (64K, c in diagram) allows two 64K blocks to be
merged into a 128K block and then two 128K blocks to be merged to return to a
position where the memory is empty and there is only one list entry in the 256K
Allocation Units
block starting at 0K.

List No. Block Size Initial 6K 9K 17K 63K

1 1 1 0 0 0 1 1 1 0 1 Bit Map
2 2
3 4
4 8
5 16
6 32 The main decision with this scheme is the size of the allocation unit. The smaller the
7 64 allocation unit, the larger the bit map has to be. But, if we choose a larger allocation unit,
8 128
9 256
we could waste memory as we may not use all the space allocated in each allocation unit.
10 512
11 1024 (1K) The other problem with a bit map memory scheme is when we need to allocate memory
12 2048 (2K) to a process. Assume the allocation size is 4 bytes. If a process requests 256 bytes of
13 4096 (4K) memory, we must search the bit map for 64 consecutive zeroes. This is a slow operation
14 8192 (8K) 40K and for this reason bit maps are not often used.
15 16384 (16K) 32K
16 32768 (32K) 32K
Memory Usage with Linked Lists

Graham Kendall Graham Kendall

 Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination
Free and allocated memory can be represented as a linked list. The memory shown above
as a bit map can be represented as linked list as follows. First Fit : This algorithm searches along the list looking for the first segment that is large
enough to accommodate the process. The segment is then split into a hole and a process. This
method is fast as the first available hole that is large enough to accommodate the process is
used.
P 0 1 H 1 3 P 4 3 H 7 1 P 8 1 Best Fit : Best fit searches the entire list and uses the smallest hole that is large enough to
accommodate the process. The idea is that it is better not to split up a larger hole that might be
needed later.
Best fit is slower than first fit as it must search the entire list every time. It has also be shown that
Each entry in the list holds the following data best fit performs worse than first fit as it tends to leave lots of small gaps.
• P or H : for Process or Hole Worst Fit : As best fit leaves many small, useless holes it might be a good idea to always use
the largest hole available. The idea is that splitting a large hole into two will leave a large
• Starting segment address enough hole to be useful.
• The length of the memory segment It has been shown that this algorithm is no very good either.
• The next pointer is not shown but assumed to be present
These three algorithms can all be speeded up if we maintain two lists; one for processes
In the list above, processes follow holes and vice versa (with the exception of the start and one for holes. This allows the allocation of memory to a process to be speeded up as
and the end of the list). But, it does not have to be this way. It is possible that two we only have to search the hole list. The downside is that list maintenance is complicated.
processes can be next to each other and we need to keep them as separate elements in the If we allocate a hole to a process we have to move the list entry from one list to another.
list so that if one process ends we only return the memory for that process.
Consecutive holes, on the other hand, can always be merged into a single list entry. However, maintaining two lists allow us to introduce another optimisation. If we hold the
hole list in size order (rather than segment address order) we can make the best fit
This leads to the following observations when we a process terminates and we return the algorithm stop as soon as it finds a hole that is large enough. In fact, first fit and best fit
memory. effectively become the same algorithm.

A terminating process can have four combinations of neighbours (we’ll ignore the start The Quick Fit algorithm takes a different approach to those we have considered so far.
and the end of the list to simplify the discussion). Separate lists are maintained for some of the common memory sizes that are requested.
If X is the terminating process the four combinations are For example, we could have a list for holes of 4K, a list for holes of size 8K etc. One list
can be kept for large holes or holes which do not fit into any of the other lists.
Before X terminates After X terminates Quick fit allows a hole of the right size to be found very quickly, but it suffers in that
there is even more list maintenance.

• In the first option we simply have to replace the P by an H, other than that the list
remains the same.
• In the second option we merge two list entries into one and make the list one entry
shorter.
• Option three is effectively the same as option 2.
• For the last option we merge three entries into one and the list becomes two entries
shorter.

In order to implement this scheme it is normally better to have a doubly linked list so that
we have access to the previous entry.

When we need to allocate memory, storing the list in segment address order allows us to
implement various strategies.

Graham Kendall Graham Kendall

Operating Systems (G53OPS) - Examination Operating Systems (G53OPS) - Examination

c) There is some debate as to what will constitute a fifth generation computer.

Question 6 – Model Answer Assume such a computer is available. What do you think will differentiate it from
the computers of today?
What advances do you think need to be made in order to produce a fifth generation
The first two parts of this question (a and b) were not explicitly covered in the lectures computer?
and, answering them, could show evidence of reading around the subject. However,
anybody with even limited experience of using an operating system should be able to This question is really up to the student to provide a convincing argument as to what they think. The
lectures notes are given below. For simply re-producing that I will award half the marks for the question. I
provide some form of an answer. The questions are not difficult. am really looking for the student to provide their own, original, thoughts.

Part (c) really is an opportunity for the student to give their own views. Whatever answer they give, I would expect them to make the point that each generation of computing has
been hardware driven. Is this going to be the case for the next generation?
a) Every file in a filing system has a set of attributes (read only, date created etc.).
If you look through the descriptions of the computer generations you will notice that each have been
Assume a filing system allows an attribute of temporary, meaning the creating influenced by new hardware that was developed (vacuum tubes, transistors, integrated circuits and LSI).
process only uses the file during the time it is executing and has no need for the data The fifth generation of computers may be the first that breaks with this tradition and the advances in
thereafter. software will be as important as advances in hardware.
Assume the process is written correctly, so that it deletes the file at the end of its One view of what will define a fifth generation computer is one that is able to interact with humans in a
execution. Do you see any reason for an operating system to have temporary file way that is natural to us. No longer will we use mice and keyboards but we will be able to talk to computers
in the same way that we communicate with each other. In addition, we will be able to talk in any language
attribute? Give your reasons. and the computer will have the ability to convert to any other language.
Computers will also be able to reason in a way that imitates humans.
The main reason for the attribute is when a process terminates abnormally, or if the
system crashes. Under these circumstances the temporary file would not be deleted. Just being able to accept (and understand!) the spoken word and carry out reasoning on that data requires
However, by checking the temporary attribute of all files the operating system is able to many things to come together before we have a fifth generation computer. For example, advances need to
be made in AI (Artificial Intelligence) so that the computer can mimic human reasoning. It is also likely
delete those files are marked as temporary, thus keeping the filing system “tidy.” that computers will need to be more powerful. Maybe parallel processing will be required. Maybe a
Under normal circumstances, the attribute, is not needed. computer based on a non-silicon substance may be needed to fulfill that requirement (as silicon has a
Other reasons could be that the OS could decide to place all temporary files in a certain theoretical limit as to how fast it can go).
location – allowing the programmer to simply create a temporary file without having to
concern him/herself with the location details. This is one view of what will make a fifth generation computer. At the moment, as we do not have any, it is
difficult to provide a reliable definition.

b) An operating system supplies system calls to allow you to COPY, DELETE and
15 marks available to award based on the students argument and justification
RENAME a file.
Discuss the differences between using COPY/DELETE and RENAME to give a file
new name?

I would expect most students to say that there is a performance impact in using
copy/delete as the entire file is copied. If you use rename then only the index entry has to
be changed.
Limited marks will be give for this, with the rest of the marks being given for the students
other arguments – for example…

Perhaps a not so obvious reason, is that if you copy a file you create a brand new file and
some of the attributes will change (for example, date created). If you rename a file the,
date created attribute, for example, would not be changed.

Graham Kendall Graham Kendall