Operating Systems Exam - CP 226
University of Dodoma
College of Informatics and Virtual Education
Department of Computer Science and Engineering
SECTION A
Question Three
a. List any four (4) attributes that an Operating System needs to maintain so as to keep track of information about a process. (2 Marks)
b. What is the tradeoff involved in rereading code pages from the file system versus using swap space to store them? (1.5 Marks)
c. Consider a simple paging system with the following parameters:
( 2^{32} ) bytes of physical memory; page size of ( 2^{10} ) bytes and ( 2^{16} ) pages of logical address space.
i. How many entries in the page table? (0.5 Marks)
ii. How many bits in each page table entry? Assume each page table entry contains a valid/invalid bit. (1 Mark)
SECTION B: (45 MARKS)
Attempt THREE (3) out of FOUR (4) questions in this section
Question Four
a. With respect to lock in process synchronisation, what does priority inversion mean and how can it be resolved? (2 Marks)
b. To ensure atomicity of the instruction for Critical Section Problem (CSP) Intel provides exchange (xchg) instructions, write the implementation of the xchg instruction and briefly explain how it guarantees atomicity. (4 Marks)
c. Consider the Producer-Consumer synchronisation problem which describes two processes, the Producer and the Consumer. The processes share a common fixed-sized buffer of size N. Producer produces an item and put into the buffer. If the buffer is already full the producer will have to wait for an empty block in the buffer. On the other hand, the consumer takes an item from the buffer. If the buffer is already empty the consumer will have to wait for an item in the buffer. Suppose you have decided to implement the CSP solution by using semaphore and mutex:-
i. How many semaphores will you need and how should each be initialized for a correct implementation? (2 Marks)
ii. Why do you need to include mutex in your solution? (2 Marks)
iii. Based on your responses in c (i) and c (ii), Write a solution for the stated synchronisation problem. (5 Marks)
Question Five
Consider a single processor system in which multiple processes are running:-
a. What does it mean for a process to be I/O bound and CPU bound? (2 Marks)
b. Consider two processes ( P_1 ) and ( P_2 ) with the following sequential execution patterns:-
( P_1 {CPU4ms; I/O 2ms; CPU 3ms, I/O 2ms, CPU 4ms} )
( P_2 {CPU 1ms; I/O 2ms; CPU 1ms, I/O 2ms, CPU 1ms} )
Where I/O operations for the two processes do not interfere with each other and are blocking.
i. If the processes are executed consecutively one after another, what is the elapsed time for all to complete? (1 Mark)
ii. Sketch the execution pattern under non-preemptive scheduling and determine the total elapsed time for the processes to complete. You may assume that processes are scheduled in the order they become ready to run and that in the event of a tie ( P_1 ) has priority over ( P_2 ). (3 Marks)
iii. Repeat (b)(ii) but for a preemptive scheduler that operates on a time slice of 2 ms, that is, no process can run for more than 2 ms at a time (unless no other process is runnable). (3 Marks)
iv. Is there any evidence from your results for (b)(ii) and (b)(iii) of a significant advantage for either scheduling method? (1 Mark)
c. Using any high-level programming language, implement the First Come First Serve (FCFS) CPU scheduling algorithm. Use the process data provided in Question 5(b) as input to your program. The program should compute and return the average waiting time and average turnaround time.
(5 Marks)
Question Six
a. Suppose that a disk drive has 5,000 cylinders, numbered 0 to 4,999. The drive is currently serving a request at cylinder 2,150, and the previous request was at cylinder 1,805. The queue of pending requests, in FIFO order, is: 2,069, 1,212, 2,296, 2,800, 544, 1,618, 356, 1,523, 4,965, and 3681. Starting from the current head position, what is the total distance (in cylinders) that the disk arm moves to satisfy all the pending requests for each of the following disk-scheduling algorithms?
i. C-SCAN (3 Marks)
ii. LOOK (2 Marks)
b. Consider a system that uses Bankerās Algorithm for deadlock avoidance. The system has five processes (1, 2, 3, 4, and 5) and uses resources of four different types (A, B, C, and D) as depicted in Table 1. Carefully study the Table 1 and use it to answer questions that follow:
Table 1: System State
| Process | Current Allocation (A B C D) | Maximum Demand (A B C D) | Available Resources (A B C D) |
|---|---|---|---|
| Pā | 1 0 2 0 | 3 2 4 2 | 3 4 0 1 |
| Pā | 0 3 1 2 | 3 5 1 2 | |
| Pā | 2 4 5 1 | 2 7 7 5 | |
| Pā | 3 0 0 6 | 5 5 0 8 | |
| Pā | 4 2 1 3 | 6 2 1 4 |
i. Is the state of the system depicted in Table 2 safe? If the system is safe, show how all the processes could complete their executions successfully. If the system is unsafe, show how deadlock might occur. (3 Marks)
ii. Given the request (2, 3, 1, 7) from process Pā. Can this request be granted immediately? Justify your answer. (2 Marks)
iii. By using any high level programming language, implement the bankerās algorithm. (5 Marks)
c. By using any high level programming language, implement First Come First Serve (FCFS) scheduling algorithm. Use data in 5 (b) as your input to the program and return average waiting time and turnaround time. (5 Marks)
Question Seven
Carefully observe the following user program and use it to answer the questions that follow. You may assume that the program is already compiled and generated object file containing symbolic addresses.
#include <stdio.h>
#include <stdlib.h>
int calls;
void fact(int a, int * b)
{
calls++;
if (a == 1) return;
*b = *b * a;
fac(a-1, b);
}
int main () {
int n, *m;
scanf("%d", &n);
m = malloc(sizeof(int));
*m = 1;
fac(n,m);
printf("Factorial(%d) is %dn", n, *m);
free(m);
}a. The address binding problem for the above code can be resolved at compile time, load time or run time. For each case, briefly explain how binding is achieved; include the form of address generated and one advantage in your explanations. (4.5 Marks)
b. If the binding in (a) is completed, the program will be mapped into stack, text, data and heap segments that make up processās address space. Identify which part of the program will be mapped into those segments. (3.5 Marks)
c. For the CPU to access the process instructions in (b), the system implements virtual memory by using demand paging. In each case, briefly explain the action taken by operating system in order to service the CPU requests or comment on the overhead cost related to operating system while servicing the CPU requests. Include the status of page table in your explanations.
i. When the CPU issues the page references that is currently on disk and all frames are occupied. (2 Marks)
ii. If the page reference string are
7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1 and the First in First out (FIFO) page replacement algorithm have been used with four frames initially empty. Limit your explanation on the number of page faults. (3 Marks)
iii. If Translation Look-aside Buffer (TLB) is added to the paged system where it takes ( t_0 ) ns to access TLB, ( t_1 ) ns to access main memory and only 0.4 of all page table references are in main memory. Limit your explanation on the effective access time. (2 Marks)
END OF EXAMINATION PAPER