Operating Systems Sample Exam AnswersNote: These answers
were provided by student posts to the forum in past years, or by the
lecturer. They are intended as a guide to the correct answers. Many
thanks to those who have contributed.
For the questions without answers, post your attempts to the forum and I will correct them.
Good luck in the exam.
Answers to Sample Paper.Q1
• A smaller page size leads to smaller page tables – False – need more entries because we have more pages
smaller page size leads to more TLB misses – True – less
likely that page will encompass address we are after.
• A smaller page size leads to fewer page faults – True
In practice, initial faulting-in is usually less important than page faults generated once the application is up and running.
Once the app is up and running, reducing the page size results in a
more accurate determination of work set, which is in-turn smaller,
which requires less memory, which in-turn leads to a lower page fault
• A smaller page size reduces paging I/O throughput – True
• Threads are cheaper to create than processes – True
• Kernel-scheduled threads are cheaper to create than user-level threads – False
• A blocking kernel-scheduled thread blocks all threads in the process – False. This is true for user level threads
• Threads are cheaper to context switch than processes – True – don’t have to save the address space
• A blocking user-level thread blocks the process - True
• Different user-level threads of the same process can have different
scheduling priorities – False. User level threads aren’t scheduled,
they yield() the CPU
• All kernel-scheduled threads of a process share the same virtual address space – True
• The optimal page replacement algorithm is the best choice in practice – False - it’s impossible to implement
• The operating system is not responsible for resource allocation
between competing processes – False – it is responsible for this
• System calls do not change to privilege mode of the processor –
False – we trap into the kernel so we do change the privilege mode
• The Challenge-Response authentication protocol is
susceptible to replay attacks by intruders snooping on the network
• A scheduler favouring I/O-bound processes usually does not
significantly delay the completion of CPU-bound processes – True – the
I/O processes get the I/O and then yield the CPU again.
99 TLB hits, which needs only a single memory access (the actual one required)
.0095 TLB miss, one read from memory to get the page table entry to load TLB, then one read to read actual memory.
.0005 pagefault plus eventual read from memory plus something like one of the following (I'd take a few variation here)
1) A memory reference to update the page table
2) A memory reference to update the page table and a memory reference
for the hardware to re-read the same entry to refill the TLB
3) Any reasonable scebario that results in valid page table and refilled TLB.
I'll assume option 2 for final answer
.99 * 100ns + .0095 *2 * 100ns + .0005 (3 * 100ns + 5ms)
would be one answer I would accept.
i) FCFS order traversed: 119,58,114,28,111,55,103,30,75
tracks traversed: 547
ii) SSTF order traversed: 75,58,55,30,28,103,111,114,119
tracks traversed: 143
iii) SCAN order traversed: 103,111,114,119,75,58,55,30,28
tracks traversed: 130
iv) C-SCAN order traversed: 103,111,114,119,28,30,55,58,75
tracks traversed: 177
It is in the multi process lecture notes.
Starting at page 30.
Just some notes that may be good to point out
Hardware locks the bus during the TSL instruction to
prevent memory accesses by any other CPU
Spinning on a lock requires bus locking which
slows all other CPUs down
– Independent of whether other CPUs need a lock or not
– Causes bus contention
Caching does not help this test and set.
Hence to reduce bus contention.
• Read before TSL
– Spin reading the lock variable
waiting for it to change
– When it does, use TSL to acquire
• Allows lock to be shared read-only
in all caches until its released
– no bus traffic until actual release
• No race conditions, as acquisition
is still with TSL.
Answers to Sample Questions.
i) high-level abstractions
- more friendly to programmers
- provides common core for all applications
- hides details of hardware to make application code portable
ii) resource manager
- divides resources amongst competing programs or users according to
some system policy to ensure fairness and no starvation where possible.
Its all about system calls, and has the required info.
Page 63 has a nice diagram of the proceducers.
The steps may be:
- Set up the required syscall arguments
- Call syscall execption
– Change to kernel stack
– Preserve registers by saving to memory (the stack)
– Leave saved registers somewhere accessible to
• Read arguments
• Store return values
– Do the “read()”
– Restore registers
– Switch back to user stack
– Return to application
3. Why must the operating system be
more careful when accessing input to a system call (or producing the
result) when the data is in memory instead of registers?
putting kernel security checks in user-land is bad as they can easily be bypassed.
5. Describe the three state process model, describe what transitions are valid between the three states, and describe an event that might cause such a transition.
On a uniprocessor we only have one CPU so only one process can be using
the CPU at a time. The cpu is rapidly switched between tasks by the operating system at a very fast rate
giving the user the illusion that several processes are executing
1. a program in execution
2.an instance of running program
3. an owner of the resource allocated to program execution
4. a task or a job
5. emcompass one or more threads
attribute of a process:
Open files - (could be argued are part of resources)
attributes of threads:
Program Status Word
If the OS does not support multi-threaded applications, then thread attributes become process attributes.
8. What is the function of the ready queue?
9. What is the relationship between threads and processes?
10. Describe how a multi-threaded application can be supported by a user-level threads package. It may be helpful to consider (and draw) the components of such a package, and the function they perform.
11. Name some advantages and disadvantages of user-level threads.
The answer is that usually timer ticks (at
reasonably fine granularity) are unavailable to user-level schedulers,
hence they usually rely on cooperative scheduling.
13. Enumerate the advantages and disadvantages of supporting multi-threaded applications with kernel-level threads.
Describe a sequence the sequence of step that occur when a timer
interrupt occurs that eventually results in a context switch to another
For a real example of such a function look at the OS/161 mips_switch code
In general, assembly language context swith code does:
- Saves enough registers on the stack to eventually return back to the calling C function
- stores the stack pointer in the current thread's control block
- load the stack pointer from the destinations thread's control block
- restores the destination threads registers from its stack
- returns to 'C' in the destination thread.
A race condition occurs when there is an
uncoordinated access to resources (e.g. memory or device registers), which leads to ancorrect
behaviour of the program, deadlocks or lost work.
An example would be two process updating a counter simultaneously.
Say the counter has a value of 1. Process A reads the variable but
before updating Process B reads and updates the counter to 2. Process
A, having no knowledge of what Process B does, updates the counter to
2. The correct behaviour of the program would have the counter being
incremented to 3, not 2.
17. What is a critical region? How do they relate to controlling access to shared resources?
18. What are three requirements of any solution to the critical sections problem? Why are the requirements needed?
19. Why is turn passing a porr solution to the critical sections problem?
Interrupt disabling and enabling is a common approach to implementing
mutual exclusion, what are its advantages and disadvantages?
What is a test-and-set instruction? How can it be used to implement
mutual exclusion? Consider using a fragment of psuedo-assembly language
aid you explanation.
Given a single, fix-sized queue, the producer process(es) geenerate(s)
an item to put into the queue while the consumer(s) take(s) the item
out of the queue and consume(s) it.
Give an example of its occurence in operating systems.
Take file system buffer cache as example, the file system writes
are produced by the application requests. OS has to find a free entry
in the buffer cache to store the write or blocks the request until a
free slot is available on the bounded buffer cache.
The interrupt handler can be considered as the consumer as after
the write is completes, it marks the buffer cache entry as
clean(consumed) and free it up for futher writes.
23. A semaphore
is a blocking synchronisation primitive. Describe how they work with
the aid of pseudo-code. You can assume the existance of a
thread_block() and a thread_wakeup() function.
24. Describe how to implement a lock using semaphores.
25. What are monitors and condition variables?
26. What is deadlock? What is startvation? How do they differ from each other?
27. What are the four condtions required for deadlock to occur?
initial count = 1
acq = P()
rel = V()
When given a resource graph (example on Page 169 of txtbook), you
simply have to look at the graph to see if there are loops in the
graph. So in the case of the example in the textbook, the loop between
D,R,E,V,G, U is existent. Therefore the system is deadlocked.
The system in a resource graph is not deadlocked as long as there
is no loops between the graphed resources. One or more loops means the processes involved the the loop are deadlocked.
When avail vector is 1 4, P 2 and P 4 Deadlocked
When avail vector is 2 3, P2, P3, P4 deadlocked
When avail vector is 2 4, then it the system is in safe state
a) look for a process whose requests <= the availability.
we know we can then satisfy the requirements for this process, so we
assume it gets its resources required and terminates. Thus, we can
b) release all resources *currently allocated* to that process, and add then to the pool.
c) repeat for all processes. If you eventually reach a point where
you cannot do this, and there are still processes remaining, the system
is deadlocked. If you release them all, you are safe.
Assuming the operating system detects the system is deadlocked,
what can the operating system do to recover from deadlock?
32. What must the banker's algorithm know a priori in order to prevent deadlock?
The general approach of _prevention_ is to
negate one of the conditions required for deadlock (careful allocation
is deadlock _avoidance_)
Practical method is ordered resource aquisition (i.e. ordered lock aquisition).
This means filesystems support this kind of file that if some entire
blocks of one file contains nonmeaningful data(should be null), these
blocks need not be allocated on the disk.
Some database applications that lseek to large offsets obtained from large hash values may benefits for sparse files.
35. Give an example of a scenario that might benefit from a file system supporting an append-only access write.
Big block size:
- for a disk that is going to be used mostly to store multimedia files. Mpegs, avis, etc etc.
Small block size:
- for disk that will contain mostly txt files, log files, program codes, etc2.
I would think that by using big block size we can promote locality on
big files, however if the files are small then it would cause an internal fragmentation as such.
Performance related examples might be: a) small
block size might be advantageous for an application random access to
small records in a large file (load less with small blocks, fill up
less buffer cache). b) Larger blocks would give better sequential
37. Give an example where contiguous allocation of file blocks on disks can be used in practice.
38. What file access pattern is particularly suited to chained file allocation on disk?
39. What file allocation strategy is most appropriate for random access files?
40. Compare bitmap-based allocation of blocks on disk with a free block list.
How can the block count in an inode differ from the (file size / block
size) rounded up to the nearest integer. Can the block count be
greater, smaller, or both.
42. Why might the direct blocks be stored in the inode itself?
Given that the maximum file size of combination of direct, single
indirection, double indirection, and triple indirection in an
inode-based filesystem is approximately the same as a filesystem soley
using triple indirection, why not simply use only triple indirection to
locate all file blocks?
block size = 512
number of block numbers in an indirection block
= block size / 4
number of blocks for file data in that file object
= 16 + 128 + 128^2 + 128^3
max file size
= (number of blocks for file data that file object)*(block size)
= (16 + 128 + 128^2 + 128^3)*(512)
45. The berkely fast filesystem
(and Linux Ext2fs) use the idea of block groups. Describe what this
idea is and what improvements block groups have over the simple
filesystem layout of the System V file system (s5fs).
What is the reference count field in the inode? You should
consider its relationship to directory entries in you answer.
47. The filesystem buffer cache
does both buffering and caching. Describe why buffering is needed.
Describe how buffering can improve performance (potentially to the
detriment of file system robustness). Describe how the caching
component of the buffer cache improves performance.
Basically flushd is a flush daemon.
Data blocks are scheduled for write back to disk at a periodic time.
Therefore, flushd in UNIX modifies this blocks to disk every 30secs.
flushd ensures that dirty blocks within the
buffer cache are written back to disk periodically to avoid significant
data loss on unexpect OS shutdown/powerloss.
External devices have no guarentee of connectivity. To ensure
filesystem consistency writes should be made without caching and be
made as atomic as possible in case the drive is removed before the
write has been committed to the drive.
- Internal fragmentation: the space wasted internal to the allocated
region.Allocated memory might be slightly larger than requested memory.
- External fragmentation: the space wasted external to the
allocated region.memory exists to satisfy a reqest but it's unsuable as
it's not contiguous.
Stattic partitioning is more likely to suffer from internal fragmentation.
Dynamic partitioning is more likely to suffer from external fragmentation.
Scan memory region list from start for first fit.
Must always skip over potentially many regions at the start of list.
Scan memory region list from point of last allocation to next fit.
Breaks up large block at the end of memory
Pick the closest free region in the entire list
Leaves small unusable regions and slower due to searching of entire list.
Finds the worst fit in the entire list
Slower as it searches entire list. Fragmentation still an issue.
First-fit and next-fit most commonly used as it is easier to implement and works out better.
Swapping is the act of running each whole process
in main memory for a time then placing back onto disk and vice versa.
It is used when the system does not have enough main memory to hold all
the currently active processes.
Assuming that an application is one program and hence a single
process, swapping will not permit an application(process) requiring 16M
of memory to run on a machine with 8M RAM (main memory) as the whole
process is too large to fit into main memory.
53. Describe page-based virtual memory. You should consider pages, frames, page tables, and Memory Management Units in your answer.
Give some advantages of a system with page-based virtual memory
compared to a simply system with base-limit registers that
55. Describe segmentation-based virtual memory. You
should consider the components of a memory address, the segment table
and its contents, and how the final physical address is formed in your
56. What is a translation look-aside buffer? What is contained in each entry it contains?
57. Some TLBs support address space identifiers (ASIDS), why?
assume we got 32-bits virtual address and 4k page size, top level table
A, and second level table B, first 10 is to locate A's index, and next
10-bits is the offset to locate B's index, using A's content to locate
the B's base address, and plus the offset to B's index, we got the
physical frame index; then using the last 12 bits plus the B's content,
finally the physical address located.
The two-level table avoids allocating
pagetables for all possible translations, if the translations are not
required.. A disadvantage is that it requires 2 memory references to
look up a page table entry, instead of one.
Inverted page table is an array of page numbers sorted (indexed) by frame number.
address is hashed to locate the entry in the frame table. The most
important advantage is that its size is related to physical memory
size, not virtual memory. Inverted page table is good for system with large addressing space but
significantly less physical memory (e.g. 64-bit addressing with 2GB of
60. What are temporal locality and spatial locality?
61. What is the working set of a process?
62. How does page size of a particular achitecture affect working set size?
Thrashing occurs when too many processes are run on a processor at a
given time. What occurs is the the number of page faults increase
dramatically and the virtual memory subsystem is constantly paging
pages in and out of memory. This occurs when the working set of all
processes is larger than the amount of RAM available on a system.
This can be detected by monitoring the page fault frequency and CPU
utilisation. If increasing the number of processes results in
increasing page fault rate and decreasing CPU utilisation, then the
system is thrashing.
To recover from this condition the number of processes currently in
the running/ready queue must be reduced. This can be accomplised by
suspending processes (pushing them onto the sleeping queue), so that
pressure on physical memory is reduced (suspended processes eventually
get swapped out), and thrashing subsides.
- decrease the page table size due to less pages
- increase TLB coverage
- increase swapping I/O throughput
- increase internal fragmentation
- increase page fault latency
Demanding paging (or fetch on demand) : load pages when page fault occur, and is more common.
Prepaging policy : Pre-paging brings in more pages than needed at the
moment. IO is improved due to reading large chunks but waste bandwith
if pages aren't used. Especially bad if we eject pages in working set
in order to pre-fetch unused pages. Hard to get in right in practice.
What operating system event might we observe and use as input to an
algorithm that decides how many frames an application receives
(i.e. an algorithm that determines the application's resident set size)?
67. Name and describe four page replacement algorithms. Critically compare them with each other.
68. Describe buffering in
the I/O subsystem of an operating system. Give reasons why it is
required, and give a case where it is an advantage, and a case where it
is a disadvantage.
Pushing more I/O functionality into device controllers relieves the
operating system from having to perform it (e.g. adding DMA to a device
controller relieve the OS from having to copy data to memory). This
results in improved performance as the OS only has to supervise the
device, instead of doing all the work itself in the device driver, also
the I/O functionality can now happen in parallel with the
OS/application doing somthing else. It may also reduce device driver
complexity and improve reliability, but that is dependent on whether
the complex device is actually reliable itself.
In polling based I/O, the OS simply busy waiting on a loop, continuly
checking for I/O, whereas in interrupt-driven I/O, when an I/O job
arrive an interrupt is generated and the OS runs the
interupt-handler, after that it return to what it was doing before the
If the cost for interrupt handling (the cost of switching to
kernel-mode and preserving the user-level context and then eventually
returning again) is bigger than the time spent busy-waiting in polling
and the rate of I/O jobs arrive is high then polling is prefered,
otherwise the latter is a better choice.
Many I/O devices utilise a buffer to store incoming information. Upon
an event, such as entering the 'new line' character, it notifies the OS
/ user program. Data is then copied from the buffer to a location which
it can be used, and the consumed data is cleared from the buffer.
This is an example of a bounded-buffer producer-consumer problem,
where the producer is the I/O device, the consumer is the OS / user
program and the buffer is bounded by its size. Therefore, concurrency
control must be implemented to ensure that race conditions do not
occur. Additionally, the OS / program must consume the buffer quickly
enough to prevent it from overflowing and lose information.
You could also mention blocking, e.g. when the buffer is empty.
72. What is disk interleaving? What problem is it trying to solve?
73. What is cylinder skew? What problem is it trying to solve?
74. Name four disk-arm scheduling algorithms. Outline the basic algorithm for each.
75. What are the three general goals of computer security?
76. Which of the three goals of computer security is the following an attack on:
a) Network snooping
b) A distributed denial of service attack
c) Modifiying your marks in the student records database
Give an example of why it is important to consider the skill and
resources available to likely intruders when designing computer
security mechanisms and policies to defend against those intruders?
Three general goals of data security: Confidentiality, Integrity, Availability.
Denial of Service; attack on Availability
Interception; attack on Confidentiality
Modification; attack on Integrity
79. Describe what a buffer overrun attack is.
80. What is the principle of least privilege?
Why is the setuid root facility in UNIX generally a violation of the
principle? Give an illustrative example of that violation.
advantage: Able to check addresses are valid at run-time
disavantage: Run slow compared to running code natively
advantage: Faster than interpretation
disavantage: Doesn't protect the user from bad/buggy code
82. What is the difference between mandatory access control and discretionary access control?
Access control lists define what users /
processes are able to perform certain actions on a resource. For
example, UNIX permissions: read, write, execute. Capabilities define,
for each user / process, what actions they can perform on different
resources. They are both ways to represent the protection matrix model
of authority in a system.
ACLs represent the protection matrix stored by
column, capabilities represent the protection matrix stored by row
(asusming, like in the notes that each rows is labelled by process and
each column is labelled by an object/resource).
The imprtant point is that with ACLs, all processes owned by the user have the same privileges, thus is difficult to apply POLP.
With capabilities, each process has capabilties to the objects it can
access. It is easier when creating a new process to only give the
process the caps it needs, i.e. the least privilege it requires.
As ACL's (Access control lists) are done on the
actual resources (files, printers etc), these access permissions allow
the user to make use of the resources. Hence any process with the
User's ID would also have acess to these resources.
To apply Principle of Least Privaledge to the process we would have to
remove the right for this process to acess every single resource before
run time (this is the difficult part). That would envlove looking for
every single resource the process has access to (VERY HARD TO DO with
ACL) and then modifying every single resource (also time consuming).
The better way to do it would be with capabilites.
85. What is a trusted computing base?
The Bell-La Padula Multilevel security policy is a security policy
designed to keep secret information secret. Describe the model
including the properties that must be guaranteed for secrecy to be
A covert channel is an unauthorised and implicit communication channel
created via influencing and observing shared resources in the system.
Any shared system resource (CPU, disk seeks) can
be used for signalling to send secrets. As a process with a secret
alternates between busy and sleeping, a process who wishes to obtain a
secret can monitor how fast it is does this to obtain the secret.
a) A transaction database that performs many thousands of updates per second.
When using a database the prefered raid to use would be RAID 1. The
reason for this is that the write and update performace of RAID 1 is
better than that of RAID 5.
b) A web server that serves almost entirely static web content.
RAID 5 would be more beneficial here, as the data can be accessed
fast. As the pages are static, and assuming no backend database there
are no real writes to the disk, this means that the update performance
of RAID 5 is not an issue, and you might as well save on the number of disks and use raid 5.
Compare RAID 0, RAID 1, and RAID 5 in terms of performance improvement,
ability to withstand failure, and space overhead require to implement
the particular RAID level.
90. Why is it generally correct to favour I/O bound processes over CPU-bound processes?
91. What is the difference between preemptive scheduling and non-preemptive scheduling? What is the issue with the latter?
assume for the following processes thse execution times:
* A: a
* B: b
* C: c
* D: d
Process A finishes at time a, B finishes at time a+b, C at a+b+c and so on
ave turn around time is then: (4a+3b+2c+d)/4
* it can be seen from above equation that a contributes the most to the
average turnaround time, also since a is the shortest time therefore
SJF minimises turn around time
93. Describe round robin scheduling. What is the parameter associated with the scheduler? What is the issue in chosing the parameter?
The traditional UNIX scheduler is a priority-based round robin
scheduler (also called a multi-level round robin schduler). How does
the scheduler go about favouring I/O bound jobs over long-running
95. In a lottery scheduler with 40 tickets. How
how I distribute the tickets amongst 4 processes (A, B, C, D) such that
each process gets 10%, 5%, 60%, and 25% respectively?
In a situation where one user have much more tasks (process or threads)
to run than the other, he could potentially consume most of the CPU
time. The fair share scheduler try to ensure the fairness of CPU time
between differents users on the same system.
2 algorithm to assign priorities to peridic tasks:
+ Rate monotonic : the shorter period, the higher priority the process is
+ EDF : the earlier deadline, the higher priority.
EDF is guaranteed to produce a feasible schedule if CPU utilisation is <= 1.
RMS only provides such a guarantee if the utilisation is less than that
specified in the formula in the lecture notes, which is significantly
less than 1.
Describe why the use of spinlocks might be more appropriate
than blocking locks on a multiprocessor when compared to a
uniprocessor. Is there a trade-off between spinning and blocking on a
100. Is a single ready queue on a multiprocessor a good idea? Why?
101. What is thread afinity. Why might it improve performance?