|
(a) Describe, using suitable examples,
how the following scheduling algorithms
work: [6]
(i) Shortest job first
When CPU is available, it is assigned to the process with the smallest
CPU burst time (1 mark). A further mark should be awarded for a suitable
example.
(ii) Priority scheduling
Each process is assigned a priority, and
the process with the highest priority is assigned the CPU first (1
mark). A further mark should be awarded for a suitable example.
(iii) Round robin
A small unit of time, called a time quantum,
is defined, and the
scheduler goes around the ready queue, allocating CPU to each
process for a time interval of up to a quantum in length (1 mark).
A further mark should be awarded for a suitable example.
[6 marks]
(b) (i) Explain the terms external fragmentation
and internal fragmentation. [2]
External fragmentation exists when enough
total space exists to
satisfy a request, but it is not contiguous (1 mark). Internal
fragmentation exists when there is enough contiguous space, but
a request does not use the entire space (1 mark). [2 marks]
(ii) Give one drawback of coalescing and one drawback of compaction.
[2]
A drawback of coalescing is that summation
of the freed adjacent partition may not be big enough to run a process
(1 mark). A drawback of compaction is that in involves the relocation
of jobs (1 mark). [2 marks]
(c) Describe, using suitable examples, the following methods of indirect
addressing: [6]
(i) Prime number division
The key is divided by the largest prime number
within the available
number of blocks, and the remainder from the division is the relative
block number (1 mark). A further mark should be awarded
for a suitable example.
(ii) Mid-square
The key is squared and the address is obtained
by truncating digits at both ends until the desired length is obtained
(1 mark). A further mark should be awarded for a suitable example.
(iii) Folding
The key is split into two or more parts and
they are then added together (1 mark). A further mark should be awarded
for a suitable example. [6 marks]
(d) Describe two approaches to overflow handling. [4]
One mark should be awarded for each approach
named and a further mark should be awarded for each satisfactory elaboration.
The approaches are:
- Chaining (1 mark). The overflow pointer from a track points to the
track where the overflow record is contained; each record in the overflow
is chained through a link field which gives the track and record number
(1 mark).
- Tagging (1 mark). For every record displaced to an overflow area,
a tag is written; the tag contains the record key and address to which
it has been written, and is retained in the home area (1 mark).
[4 marks]
(e) (i) List two disadvantages of a single-level directory structure.
[2]
One mark should be awarded for each disadvantage named (up to
a maximum of two marks). Examples include the following:
- Limited naming capabilities.
- Long search time.
- Maintaining a sorted directory may result in a high overhead
cost. Other correct answers should also receive credit. [2
marks] (ii) List one
advantage and one disadvantage of a two-level directory
structure. [2]
An advantage is that name conflicts are eliminated,
while duplicate file names are allowed (1 mark). A disadvantage is
that it does not allow files to be organised logically within the
directory (1 mark).
Other correct answers should also receive credit. [2 marks]
(iii) List two advantages of a tree directory structure. [2]
It enables users to organise their files
logically (1 mark) and it also
enables users to share files (1 mark). [2 marks]
(f) The Tower of Hanoi problem is an example of an artificial intelligence
problem.
(i) Describe the Tower of Hanoi problem. [2]
The problem has three pegs, labelled A, B
and C (1 mark). Three disks (of different sizes) are arranged from
largest to smallest (with the smallest on top) on peg A (1 mark).
[2 marks]
(ii) What is the goal state for the Tower of Hanoi problem? [2]
The goal is to transfer the disks to peg
C (1 mark), while arranging them in the same descending order of size
that existed in the initial state (1 mark). [2 marks]
|