Operating Systems Sample Exam Answers

Note: 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
• A 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 rate.

• 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 – False
• 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.
Q2 a)

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

thus

.99 * 100ns + .0095 *2 * 100ns + .0005 (3 * 100ns + 5ms)

would be one answer I would accept.


Q3 a)

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

Q5 b)

It is in the multi process lecture notes.
http://cgi.cse.unsw.edu.au/~cs3231/06s1/lectures/lect21.pdf

Starting at page 30.

Just some notes that may be good to point out

Test-and-Set
Hardware locks the bus during the TSL instruction to
prevent memory accesses by any other CPU
Issue:
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
the lock
• 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.


1.

i) high-level abstractions
why?
- more friendly to programmers
- provides common core for all applications
- hides details of hardware to make application code portable

ii) resource manager
why?
- divides resources amongst competing programs or users according to some system policy to ensure fairness and no starvation where possible.

2. 

http://cgi.cse.unsw.edu.au/~cs3231/06s1/lectures/lect03.pdf
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?

4. 

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.

6.

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 simultaneously.

7.

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:
Address Space
Open files - (could be argued are part of  resources)
Process ID
Process Group
Parent Process
signals
etc.


attributes of  threads:
 Scheduling Parameters
Registers
Program Counter
Program Status Word
Stack Pointer
Thread state

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.

12. 

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.

14. Describe a sequence the sequence of step that occur when a timer interrupt occurs that eventually results in a context switch to another application.

15.

For a real example of such a function look at the OS/161 mips_switch code

In general, assembly language context swith code does:
16. 

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?

20. Interrupt disabling and enabling is a common approach to implementing mutual exclusion, what are its advantages and disadvantages?

21. 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.

22. 

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?

28.

initial count = 1

acq = P()
rel = V()

29.  

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.

30.

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

General approach:

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.

31.  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?

33.  

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).

34.

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.

36. 

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 access performance.

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.

41. 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?

43.  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?

44.  

block size = 512

number of block numbers in an indirection block
= block size / 4
= 128

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)
bytes

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).

46.  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.

48. 

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.

49.

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.

50.

- 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.



51.

First-fit
Scan memory region list from start for first fit.
Must always skip over potentially many regions at the start of list.

Next-fit
Scan memory region list from point of last allocation to next fit.
Breaks up large block at the end of memory 

Best-fit
Pick the closest free region in the entire list
Leaves small unusable regions and slower due to searching of entire list.

Worst-fit
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.



52.

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.

54. Give some advantages of a system with page-based virtual memory compared to a simply system with base-limit registers that implements swapping.

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 answer.

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?

58.

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.

59.

Inverted page table is an array of page numbers sorted (indexed) by frame number.  Virtual 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 ram)

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?

63. 

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.

64.  

Pros:
- decrease the page table size due to less pages
- increase TLB coverage
- increase swapping I/O throughput

Cons:
- increase internal fragmentation
- increase page fault latency

65.

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.

66. 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.

69. 

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.

70.  

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 interrupt came.

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.

71.

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

77. 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?

78.
Lecture Notes
--------------------
Three general goals of data security: Confidentiality, Integrity, Availability.

Threats:
Denial of Service; attack on Availability
Interception; attack on Confidentiality
Modification; attack on Integrity


Answer(?):
a) Confidentiality
b) Availability
c) 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.

81.

JAVA:
advantage: Able to check addresses are valid at run-time
disavantage: Run slow compared to running code natively

ActiveX:
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?

83.
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).

84.

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?

86. 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 preserved.

87.

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.

88. 

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.


89. 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?

92. 

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?

94. 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 CPU-bound jobs?

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?

96.

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.

97.

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.

98.

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.



99.  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 multiprocessor? Discuss.

100. Is a single ready queue on a multiprocessor a good idea? Why?

101. What is thread afinity. Why might it improve performance?