Operating Systems Exam - CP 226
University of Dodoma
College of Informatics and Virtual Education
Department of Computer Science and Engineering
End of Semester Two (II) University Examination for the 2020/2021 Academic Year
Course Name: Operating Systems
Paper Code Number: CP 226
Date of Examination: 29th July 2021
Time: 15:30-18:30
Duration: 3 Hours
Venue(s): Cive_Auditorium
Sitting Programme(s): HIS2, CS2, IS2, MTA2, IDIT2, BIS2, SE2, CNISE2, CE2TE2, CSDFE, SE
INSTRUCTIONS TO CANDIDATES
- This examination paper consists of TWO (2) sections with SEVEN (7) questions in FIFTEEN (15) printed pages.
- Answer all questions in Section A and THREE (3) questions in Section B.
- The total score for this examination is 60 points. Marks are allocated at the end of each question.
- ALL responses should be written in the answer book provided. Insert the examination paper into the answer book after the examination. Students should not take any examination papers out of the examination room.
- All regulations guiding the administration of university examinations apply.
SECTION A: (15 MARKS)
Attempt ALL questions in this section.
Question One
Read each question carefully and choose the most correct response.
(0.5 Marks Each)
i. In which type of the following operating systems, the response time is very crucial?
A. Real Time Operating System
B. Network Operating System
C. Batch Operating System
D. Unix Operating System
E. Windows Operating System
ii. Which scheduling policy is best suited for time-sharing operating systems?
A. Shortest job first
B. Round robin
C. First come first serve
D. Elevator
E. Priority scheduling
iii. Multiple threads when are used in multi-threading systems share:
A. Program counter
B. Heap
C. File descriptors
D. Call stack
E. Both Heap and File descriptors
iv. Consider a simple paging system with the following parameters: 2Ā³Ā² bytes of physical memory; page size of 2Ā¹ā° bytes; 2Ā¹ā¶ pages of logical address space. How many bits in each page table entry? Assume each page table entry contains a valid/invalid bit.
A. 23 bits
B. 22 bits
C. 20 bits
D. 26 bits
E. 16 bits
v. Given three processes A, B, and C with corresponding burst times 10, 5, and 1, what is the average waiting time with a round-robin scheduler and a time slice of 5? All processes are ready to run at the same time but they arrived in the order A, B, then C.
A. 11
B. 10
C. 5
D. 5.33ā¦
E. 7
vi. Which of the following answers best explains the Wound-Wait deadlock prevention scheme?
A. Processes can take resources from younger processes. Processes must restart rather than waiting for resources held by older processes.
B. Processes can take resources from older processes. Processes may wait for resources held by younger processes.
C. Processes must restart rather than waiting for resources held by older processes. Processes may wait for resources held by younger processes.
D. Processes can take resources from younger processes. Processes may wait for resources held by older processes.
E. Both A and C
vii. Why are page sizes powers of 2?
A. The page number is determined by the n most significant bits of the virtual address. So the page size is ( 2^n ).
B. It doesnāt have to be but manufacturers only make memory in those sizes.
C. The displacement within the page is determined by the n least significant bits of the virtual address. So the page size is ( 2^n ).
D. Pages need to be repeatedly able to be halved.
E. For easy conversion
viii. Which of the following disk scheduling algorithms prevents new disk requests from slowing down older ones during a traversal of the disk surface?
A. SCAN - elevator algorithm
B. N-step SCAN
C. SSTF - shortest seek time first
D. C-SCAN - circular SCAN
E. FCFS-First come first served
ix. Consider the following incomplete implementation of a spin-lock used in synchronization problems:
typedef struct lock_t {
int flag;
} lock_t;
void init(lock_t *lock) {
lock->flag = m;
}
void acquire(lock_t *lock) {
while (xchg(&lock->flag, x) == x);
}
void release(lock_t *lock) {
lock->flag = 1;
}To what value could lockāflag be initialized (shown as m) to obtain a correct implementation?
A. 0
B. 1
C. 2
D. 0 or 2
E. 0 or 1
x. To what value could lockāflag be compared in acquire() (shown as x) to obtain a correct implementation?
A. 0
B. 1
C. 2
D. 0 or 2
E. 0 or 1
Question Two
Match the item in Column A with its corresponding item in Column B.
(0.5 Marks Each)
| Column A | Column B |
|---|---|
| i. Convoy effect | A. Program that initiates a security incident under certain circumstance. |
| ii. Trap door | B. Run all the time when the computer is on. |
| iii. Memory Management Unit | C. OS is aware of the state of each thread. |
| iv. Logic bomb | D. Segmentation |
| v. fork() system call | E. Base and limit registers. |
| vi. Internal fragmentation | F. Failure to check bounds on input, or arguments. |
| vii. Kernel-level threads | G. Address space randomization |
| viii. Trojan Horse | H. Malicious program that disguises itself as a legitimate file. |
| ix. Kernel | I. Paging. |
| J. If one thread of a process blocks, all the threads of that process will also be blocked. | |
| K. Computer that has been affected with malware so it can be controlled remotely by a hacker. | |
| L. The hole in software left by designer that can only be access by him/her. | |
| M. Shorter jobs must wait for longer jobs. | |
| N. Return 0 in child process and process id of child process in parent process. | |
| O. Memory allocated dynamically | |
| P. Code segment embedded in legitimate program. | |
| Q. Longer jobs wait for shorter jobs. | |
| R. Return 1 in child process and process id of parent in child process. |
Question Three
i. With example differentiate sequential from direct file access methods. (2 Marks)
SOME OTHER QUESTIONS MISSING : If you have them please send them to me via watsap and your contribution will be ATTRIBUTED and your name mentioned at the botton of the PAPER.
SECTION B: (45 MARKS)
Attempt THREE (3) out of FOUR (4) questions in this section
Question Four
b. Consider the sleeping barber problem: A barbershop consists of a waiting room with n chairs, and the barber room containing the barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy, but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. After cutting the customerās hair, they either sit down (if there are empty chairs) or leave the shop (if all chairs are full). The problem is to program the barber and the customers without getting into race conditions.
i. By considering the above problem, briefly explain the meaning of race condition. (2 Marks)
ii. Use Semaphore and Mutex to implement a solution for the above problem. Your solution should handle busy waiting. (5 Marks)
Question Five
a. Which scheduling criteria need to be maximized and which need to be minimized? Justify your answer. (2 Marks)
b. Operating System schedulers are said to be pre-emptive or non-pre-emptive.
i. State the principal problem with non-pre-emptive schedulers. (1 Mark)
ii. Explain how pre-emptive schedulers solve the problem stated in i). (1 Mark)
c. Consider four CPU-bound processes in Table 1 arriving to a Shortest Remaining Time First (SRTF) scheduler as follows:
Table 1: CPU-Bound Processes
| Process | Arrival Time | Duration |
|---|---|---|
| Pā | 0 | 8 |
| Pā | 3 | 3 |
| Pā | 5 | 1 |
| Pā | 9 | 4 |
i. Give a schedule computed by the SRTF scheduler, and compute the average waiting time across all four processes. Your answer should be explicit about the state of each process and the ready queue at all times. (2 Marks)
ii. Explain why SRTF is difficult to implement in practice, and suggest how to address this difficulty. (2 Marks)
iii. Assume that jobs are no longer CPU-bound but also perform blocking and non-blocking I/O. Discuss how this can affect the effectiveness and fairness of the SRTF scheduler. (2 Marks)
iv. By using any high level programming language, implement SRTF scheduling algorithm. Use data in Table 1 as your input to the program and return average waiting time and turnaround time. (5 Marks)
Question Six
Carefully observe the following program:
#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 %d\n", n, *m);
free(m);
}Use the above program to answer the following questions:
i. Identify how the above program could be mapped into main memory to become a process. (4 Marks)
ii. Imagine the system uses segmentation memory management scheme and the CPU has generated segment number 1 and offset 30, with the help of diagram determine the physical address for the requested instruction if the size of the segment is 10 bytes and the starting address in main memory is 1670. (2 Marks)
iii. If the page reference string for the process in i) are
1,2,3,4,5,3,4,1,6,7,8,9,7,8,9,5,4,2, and 5, how many page faults would occur for the LRU and Optimal page replacement algorithms? Assume there are four frames and all frames are initially empty. (3 Marks)
iv. With the help of diagram, show the action that could be taken by kernel to handle the page fault determine in iii). (3 Marks)
v. Consider a computer system with a physical memory of 8 GB, a page size of 8 KB, and a page table entry size of 4 bytes. How many levels of page tables would be required to map a 46-bit virtual address space if every page table fits into a single page? Be explicit in your explanation. (3 Marks)
Question Seven
a. 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 2. Carefully study the Table 2 and use it to answer questions that follow:
Table 2: 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 execution successfully. If the system is unsafe, show how deadlock might occur. (3 Marks)
ii. Suppose the total resources in Table 2 are changing frequently, will the Bankerās Algorithm continue avoiding the deadlock effectively? Briefly explain. (2 Marks)
iii. By using any high level programming language, implement the bankerās algorithm. (5 Marks)
b. By using any high level programming language write a program that implements the SCAN disk-scheduling algorithm. Your program will service a disk with 5,000 cylinders numbered 0 to 4,999. The program will generate a random series of 1,000 cylinder requests and service them according to each of the algorithms listed above. The program will be passed the actual position of the disk head (as a parameter on the command line) and report the total amount of head movement required by each algorithm. (5 Marks)
END OF EXAMINATION PAPER