Operating Systems Exam - CP 226
University of Dodoma
College of Informatics and Virtual Education
Department of Computer Science and Engineering
Course Name: Operating Systems
Paper Code Number: CP 226
Date of Examination: 10th July, 2023
Time: 08:00 – 11:00
Duration: 3 Hours
Venue(s): CIVE_Auditorium, LRB 104, LRB 105
Sitting Programme(s): BSc. SE2, CS2, CE2, CNISE2, CSDFE2, IS2, IDIT2, MTA2, DCBE2, TE2, BIS2
INSTRUCTIONS TO CANDIDATES
- This examination paper consists of TWO (2) sections with SEVEN (7) questions in TWELVE (12) printed pages.
- Answer all questions in Section A and THREE (3) questions in Section B.
- The total score for this examination is 100 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 paper(s) out of the examination room.
- All regulations guiding the administration of university examinations apply.
SECTION A: (40 MARKS)
Attempt ALL questions in this section.
Question One
Read each question carefully and choose the most correct response.
(1 Mark Each)
i. What are the two types of Semaphore?
A. Digital Semaphores and Binary Semaphores
B. Analog Semaphores and Octal Semaphores
C. Counting Semaphores and Binary Semaphores
D. Critical Semaphores and System Semaphores
ii. Multiple threads when are used in multi-threading systems share:
A. Program counter
B. Heap
C. File descriptors
D. Call stack
E. Heap and File descriptors
iii. Disk scheduling includes deciding
A. Which should be accessed next
B. The order in which disk access requests must be serviced
C. The physical location of the file
D. The logical location of the file
E. The physical and logical location of the file
iv. A state is safe, if:
A. The system does not crash due to deadlock occurrence
B. The state keeps the system protected and safe.
C. The system can be allowed to enter into deadlock state after it has allocated at least half of the entire system’s processes.
D. If no circular wait
E. The system can allocate resources to each process in some order and still avoid a deadlock
v. Belady anomaly occurs in which page replacement algorithms?
A. Optimal
B. FIFO algorithm
C. LRU
D. Optimal and FIFO
E. both in FIFO and LRU
vi. In a system where round robin is used for CPU scheduling, the following is true when a process cannot finish its computation during its current time quantum:
A. The process will terminate itself
B. The process will be terminated by the operating system
C. The process’s state will be changed from running to ready
D. The process’s rate will change from running to waiting
E. The process will wait for I/O completion.
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. To avoid the race condition, the number of processes that may be simultaneously inside their critical section is
A. 8
B. 1
C. 16
D. 0
E. 2
ix. Three important design principals in operating systems are:
A. Caching, virtualisation, and support for concurrency
B. Abstraction, fairness and context switching
C. Caching, response time, and virtualisation
D. Throughput, response time and support for priority
E. Policy, mechanism and super-user control
x. How did a time-sharing operating system differ from a batch operating system?
A. Time-sharing systems allowed multiple processes to be running simultaneously.
B. Security was simpler in time-sharing systems.
C. Many of the scheduling decisions could no longer be made by the operating system.
D. No need for synchronization in time-sharing systems
E. The response time was slower on a time-sharing system.
Question Two
Match the item in Column A with its corresponding item in Column B.
(1 Mark Each)
| Column A | Column B |
|---|---|
| i. Initially both parent and child processes share the same pages | A. Dynamic loading |
| ii. Internal fragmentation | B. Limit the types of file access permitted to users |
| iii. Semaphore | C. Run all the time when the computer is on. |
| iv. Protection mechanism | D. Copy-on-Write |
| v. Convoy effect | E. Base and limit registers. |
| vi. Allocate the smallest hole | F. Dynamic linking. |
| vii. External fragmentation | G. Paging. |
| viii. Kernel | H. Only one process wakeup at a time. |
| ix. The routine is loaded only when it is needed | I. Segmentation |
| x. Memory Management Unit | J. Shorter jobs must wait for longer jobs. |
| K. Return 0 in child process and process id of child process in parent process. | |
| L. Best-Fit | |
| M. Longer jobs wait for shorter jobs. | |
| N. First-Fit | |
| O. down() and up() operations. |
Question Three
a. Modern operating systems typically support both threads and processes. What is the basic difference between thread and process? (3 Marks)
b. Neither threads/processes that are in the ready state nor threads/processes that are in the blocked state are running. What is the difference between these two states? (2 Marks)
c. What role(s) do device drivers and system calls play in computer systems? (3 Marks)
d. List any four (4) attributes that an Operating System needs to maintain so as to keep track of information about a process. (2 Marks)
Question Four
a. List four (4) necessary conditions for deadlock to occur. (2 Marks)
b. Assuming a 1-KB page size, what are the page numbers and offsets for 42095 address reference (provided as decimal number)? (3 Marks)
c. Consider a paging system with the page table stored in memory.
i. If a memory reference takes 50 nanoseconds, how long does a paged memory reference take? (2 Marks)
ii. If TLBs is added, and 75 percent of all page-table references are found in the TLBs, what is the effective memory reference time? (Assume that finding a page-table entry in the TLBs takes 2 nanoseconds, if the entry is present.). (3 Marks)
SECTION B: (60 MARKS)
Attempt THREE (3) out of FOUR (4) questions in this section
Question Five
The given solution to Critical Section Problem (CSP) does not guarantee mutual exclusion because there is no atomic execution such as exchange (xchg) instructions. Carefully study this solution and use it to answer the questions that follow:
lock = 0;
Process 1
while(TRUE){
while(lock != 0);
lock = 1;
Critical section
lock = 0;
}
Process 2
while(TRUE){
while(lock != 0);
lock = 1;
Critical Section
lock = 0;
}a. Write the implementation of the xchg instruction and briefly explain how it would guarantee atomicity on the given solution. (4 Marks)
b. By using the implementation of xchg in (a), rewrite the given solution to produce: (5 Marks Each)
i. spinlocks
ii. mutex locks
c. For each implementation in (b) briefly explain one problem that might occur and suggests how can each be resolved. (3 Marks)
d. Despite of the problem identified in (c) there are some scenario where spinlocks would be more efficient than mutex locks. Briefly describe two of those scenarios. (3 Marks)
Question Six
a. Consider the following set of processes as shown in Table 1, with the length of the CPU burst given in milliseconds:
| Process | Burst Time (ms) | Priority | Arrival Time |
|---|---|---|---|
| P1 | 50 | 4 | 0 ms |
| P2 | 20 | 1 | 20 ms |
| P3 | 100 | 3 | 40 ms |
| P4 | 40 | 2 | 60 ms |
i. Draw three Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: Shortest Remaining Time First (SRTF), non-preemptive priority (a smaller priority number implies higher priority) and Round Robin with quantum 30 ms. (6 Marks)
ii. What is the average waiting time of the above scheduling policies? (6 Marks)
b. By using any high level programming language, implements First Come First Serve (FCFS) CPU scheduling algorithm. (8 Marks)
Question Seven
a. 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. (4 Marks)
b. Consider the following process for generating binaries. A compiler is used to generate the object code for individual modules, and a linkage editor is used to combine multiple object modules into a single program binary.
i. How does the linkage editor change the binding of instructions and data to memory addresses? (3 Marks)
ii. What information needs to be passed from the compiler to the linkage editor to facilitate the memory-binding tasks of the linkage editor? (2 Marks)
c. With respect to paging technique for memory management
i. With the help of diagram, briefly describe the actions that follow after a page fault occurs. You should include those performed in hardware prior to a handler being started, and those that are taken within the handler. (5 Marks)
ii. Why is handling a page fault more complex than handling an interrupt or software trap? (3 Marks)
iii. If the page reference strings are: -
1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,2,5
How many page faults would occur if LRU page replacement algorithm is used with four frames initially empty? (3 Marks)
Question Eight
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? (5 Marks Each)
i. SSTF
ii. C-LOOK
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 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) |
|---|---|---|---|
| P1 | 1 0 2 0 | 3 2 4 2 | 3 4 0 1 |
| P2 | 0 3 1 2 | 3 5 1 2 | |
| P3 | 2 4 5 1 | 2 7 7 5 | |
| P4 | 3 0 0 6 | 5 5 0 8 | |
| P5 | 4 2 1 3 | 6 2 1 4 |
i. Calculate matrix Need. (2 Marks)
ii. 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)
iii. Suppose the total resources in Table 2 are changing frequently, will the Banker’s Algorithm continue avoiding the deadlock effectively? Briefly explain. (2 Marks)
iv. Given the request (2, 3, 1, 7) from process P4. Can this request be granted immediately? Justify your answer. (3 Marks)
END OF EXAMINATION PAPER