UNIVERSITY OF EDINBURGH COLLEGE OF SCIENCE AND ENGINEERING SCHOOL OF INFORMATICS
INFR09047 OPERATING SYSTEMS
May 2020 13:00 to 15:00
INSTRUCTIONS TO CANDIDATES
Answer any TWO of the three questions. If more than two questions are answered, only QUESTION 1 and QUESTION 2 will be marked.
All questions carry equal weight. This is an OPEN BOOK examination.
Year 3 Courses
Convener: S.Ramamoorthy
External Examiners: S.Rogers, S.Kalvala, H.Vandierendonck
THIS EXAMINATION WILL BE MARKED ANONYMOUSLY
1. (a)
(b) (c) (d)
Briefly describe the three classic OS architectures. List the key advantages and drawbacks for each, and mention at least one well-known operating system that implements it.
What is the difference between an operating system and a hypervisor (or virtual machine monitor )?
Why is para-virtualisation a more efficient form of hardware virtualisation?
What is the output of the following snippet of code? Write down what you expect to be printed to the console by the printf() functions, and explain your reasoning in detail.
Assume that all library calls (fork(), getpid(), and printf()) return without any error, and that the main process has PID 4224. The OS will assign the next PIDs sequentially (at increments of one), and there are no other processes or threads running.
int main () {
int x = 1, y = 2;
p r i n t f ( ” x = %d y = %d \ n ” , x , y ) ; pid = getpid ();
am process: %d\n”, pid);
{ =%dy=%d\n”,x,y);
[3 marks ] [2 marks ] [2 marks]
[7 marks ]
1
2
3 int pid ; 4
5
6
7
8
9
x = fork();
if (x == 0) {
printf(”I
10
11
12
13
14
15
16
17
18
19
20
(e)
}
y = fork(); if(y==0) printf(”x
pid = getpid ();
printf (”I am process : %d\n” , pid ); }
return 0 ; }
Explain the differences between kernel-level threading (or one-to-one thread- ing), user-level threading (or many-to-one threading), and N:M threading (or many-to-many threading).
Page 1 of 5
[3 marks ]
(f)
From the following code snippet, identify a sequence of code lines that when executed may result in a deadlock. Write this sequence as a list of line numbers. Explain why this sequence causes the deadlock to occur.
There are multiple sequences that may cause a deadlock, you only have to identify one such sequence.
• Assume the down() and up() operations are atomic. • The deadlock may occur on the down() operation.
This is the producer-consumer problem with one consumer task, and one producer task. The example has three semaphores: two counting semaphores, and one mutex. Assume that the producer starts executing first (from line 6).
1 2 3 4 5 6 7 8 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const int N = 3;
semaphore full = N, empty = 0; semaphore mtx = 1;
Producer Function : while (1) {
produce an item A; down(mtx);
down ( f u l l ) ;
insert item ; up(mtx); up(empty);
}
Consumer Function : while (1) {
down(empty); down(mtx ) ; remove item ; up(mtx);
up ( f u l l ) ;
consume an item ;
}
Page 2 of 5
[8 marks]
2. (a)
(b) (c)
(d)
Of I/O-bound, and CPU-bound programs, which is more likely to incur voluntary context switches (i.e. purposefully give back control of the CPU to the OS), and which is more likely to incur involuntary context switches (i.e. the OS forcibly interrupts the program’s execution)? Explain why this is the case.
Draw a diagram that shows the classic process states, and transitions be- tween them. Briefly describe each state and transition.
Explain the first-come-first-serve (FCFS), round-robin, and multilevel feed- back queue (MLFQ) scheduling algorithms. Which one is fairer, and why?
Consider the following set of processes, with their corresponding execution times (in time units) and priorities:
The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.
i. Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms:
• First-come-first-served (FCFS)
• Non-preemptive shortest job first (SJF)
• Non-preemptive priority (where a higher priority number implies a higher priority)
• Round-robin (with a time quantum of 2 units).
ii. For each of the scheduling algorithms in 2(d)i, what is the turnaround
time of each process?
iii. For each of the scheduling algorithms in 2(d)i, what is the waiting time of each process?
iv. Which of the algorithms in 2(d)i results in the minimum average waiting time (over all processes)?
Page 3 of 5
[2 marks ] [2 marks ]
[3 marks]
Process
Execution Time
Priority
P1 P2 P3 P4 P5
5 2 1 7 4
4 1 2 3 3
[6 marks] [3 marks ]
[3 marks ] [2 marks ]
(e) The following processes are being scheduled using a preemptive, priority- based, round-robin scheduling algorithm – i.e. multilevel queue scheduling.
Each process is assigned a numerical priority, with a higher number indicat- ing a higher relative priority. The scheduler will execute the highest priority process first. For processes with the same priority, a round-robin scheduler will be used with a time quantum of 10 units. If a process is preempted by a higher priority process, the preempted process is placed at the end of the queue.
Draw a Gantt chart that shows the scheduling order of these processes.
[4 marks]
Process
Priority
Execution time
Arrival
P1 P2 P3 P4 P5 P6
8 3 4 4 5 5
15 25 20 20 5 20
0
0 20 25 45 55
Page 4 of 5
3. (a) (b)
(c)
(d)
What is the difference between a virtual page, and a page frame?
What is the difference between a translation lookaside buffer (TLB) miss,
and a page fault? For each concept, explain how it works.
Suppose an OS implements virtual memory with paging. A virtual address is 32 bits long and a page comprises 4kB (212 bytes). A hierarchical two-level page table is used. The first-level and second-level page tables have 1024 (210) entries.
If a process uses the first 1MB (220) of its virtual address space, how much space would be occupied by the page tables for that process? Assume each page table entry occupies 4 bytes.
Consider a hypothetical machine with four pages of physical memory and seven pages of virtual memory (labelled A–G). Given the following page ref- erence requests:
ABCDEFCAAFFGABGDFF
For both the FIFO and LRU page replacement policies:
i. Show the sequence of page swaps, and ii. compute the number of page faults.
Suppose you have a file system where the block size is 1kB, a disk address is 4 bytes, and an i-node structure contains the disk addresses of: (a) 12 direct blocks, (b) a single indirect block, and (c) a double indirect block.
(In answering the following questions, you do not need to simplify arithmetic expressions.)
i. What is the largest file that can be represented by an i-node?
ii. Suppose you want to create a new file of the largest file size. How many free blocks on the disk would there need to be, in order to create that file?
[2 marks ] [2 marks ]
[5 marks ]
(e)
[8 marks]
[5 marks ]
[3 marks ]
Page 5 of 5