OS (CP 226) UE 2019-2020

Operating Systems Exam - CP 226

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 is an operating system?
A. interface between the hardware and application programs
B. collection of programs that manages hardware resources
C. system service provider to the application programs
D. all of the above

ii. What is the main function of the command interpreter?
A. to provide the interface between the API and application program
B. to handle the files in the operating system
C. to get and execute the next user-specified command
D. none of the above

iii. To access the services of the operating system, the interface is provided by the ______.
A. Library
B. System calls
C. Assembly instructions
D. API

iv. CPU scheduling is the basis of ______.
A. multiprogramming operating systems
B. larger memory sized systems
C. multiprocessor systems
D. none of the above

v. In a timeshare operating system, when the time slot assigned to a process is completed, the process switches from the current state to?
A. Suspended state
B. Terminated state
C. Ready state
D. Blocked state

vi. A deadlock avoidance algorithm dynamically examines the ______ to ensure that a circular wait condition can never exist.
A. operating system
B. resources
C. system storage state
D. resource allocation state

vii. In real time operating system ______
A. process scheduling can be done only once
B. all processes have the same priority
C. kernel is not required
D. a task must be serviced by its deadline period

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

ix. Generally, the size of a process is limited to the size of ______
A. physical memory
B. external storage
C. secondary storage
D. none of the above

x. When the process is loaded into memory, the ______ section contains the program code.
A. Text
B. Data
C. Stack
D. Heap

---

Question Two

Match the item in Column A with its corresponding item in Column B.
(1 Mark Each)

Column A	Column B
i. Internal fragmentation	A. A part of context switching
ii. Interrupt	B. Limit the types of file access permitted to users
iii. Swap-out process to disk	C. Run all the time when the computer is on.
iv. Memory Management Unit	D. Copy-on-Write
v. Allocate the smallest hole	E. Base and limit registers.
vi. External fragmentation	F. Long-term scheduler.
vii. Kernel	G. Paging.
viii. Multiprogramming	H. Having more programs in RAM simultaneously.
ix. fork()	I. Return process id to child process
x. Execute really faster.	J. Returns 0 to the parent, child’s pid to the new child process.
	K. Short-term scheduler.
	L. Segmentation
	M. Best-Fit
	N. Medium-term scheduler.
	O. Shorter jobs must wait for longer jobs.
	P. Returns child’s pid to the parent, 0 to the new child process.
	Q. Two or more processes are waiting indefinitely for an event that can only be caused by one of the waiting processes
	R. First-Fit

---

Question Three

Fill in the blanks with the most correct answer.
(1 Mark Each)

i. In the ______ algorithm, the disk arm goes as far as the final request in each direction, then reverses direction immediately without going to the end of the disk.

ii. The time taken to move the disk arm to the desired cylinder is called the ______.

iii. In the ______ algorithm, the disk head moves from one end to the other, servicing requests along the way. When the head reaches the other end, it immediately returns to the beginning of the disk without servicing any requests on the return trip.

iv. The time taken for the desired sector to rotate to the disk head is called ______.

v. In the ______ algorithm, the disk arm starts at one end of the disk and moves toward the other end, servicing requests till the other end of the disk. At the other end, the direction is reversed and servicing continues.

vi. ______ is the address generated by CPU.

vii. ______ is the memory management technique in which system stores and retrieves data from secondary storage for use in main memory is called.

viii. Logical memory is broken into blocks of the same size called ______.

ix. The address loaded into the memory address register of the memory is referred to as ______.

x. ______disk scheduling algorithm does not provide the fastest service.

---

Question Four

For each of the following statements write True if a statement is correct and False for the incorrect statement.
(1 Mark Each)

i. The kernel uses the Process Control Block to keep track of bookkeeping information about processes, such as the program counter.

ii. A compaction is a technique for overcoming internal fragmentation.

iii. In monolithic kernel structure, there is a direct communication between modules.

iv. Deadlock prevention is a set of methods to ensure that all of the necessary conditions do not hold.

v. Virtual memory space is always smaller than physical memory space.

vi. By default, threads share global memory.

vii. Busy waiting is good as it never allows the CPU to be idle.

viii. The most commonly used scheduling algorithm for interactive systems is FCFS scheduling.

ix. A thread may share data space with its parent.

x. In operating system memory management, page sizes are always power of 2.

---

SECTION B: (60 MARKS)

Attempt any THREE (3) out of FOUR (4) questions in this section

Question Five

a. By giving one example, briefly explain why dynamic loading is essential in memory management? (3 Marks)

b. With the help of a well labelled diagram, briefly explain the concept of address binding. (6 Marks)

c. Consider the segment table in Figure 1, and use it to answer the questions that follow.

Figure 1: Segment Table

Segment	Base	Length
0	219	600
1	2300	14
2	90	100
3	1327	580
4	1952	96

i. Based on the details provided in Figure 1, briefly explain how the main memory is organized to accommodate these segments. (3 Marks)

ii. Which memory allocation technique would efficiently allocate these segments into memory partitions? Briefly explain your response. (4 Marks)

iii. Suppose the following addresses (1, 1) and (4, 97) are generated by the CPU, respectively. What would be their corresponding addresses in main memory? Comment on your responses. (4 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:

Table 1: CPU Scheduling

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. Using any high-level programming language, implement First Come First Serve (FCFS) CPU scheduling algorithm. (8 Marks)

---

Question Seven

a. Given two processes ( P_1 ) and ( P_2 ), write the implementation of Peterson solution for synchronization among these processes. By using comments indicate line of codes that guarantee mutual exclusion, progress and avoid deadlock. (8 Marks)

b. The given solution to the Critical Section Problem (CSP) does not guarantee mutual exclusion because there are no atomic execution for the given 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;
}

i. Write the implementation of the xchg instruction and briefly explain how it guarantees atomicity in the given solution. (4 Marks)

ii. Using the implementation of xchg in b(i), rewrite the given solution to produce: (4 Marks Each)

1. spinlocks
2. mutex locks

---

Question Eight

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 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. 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 P₄. Can this request be granted immediately? Justify your answer. (3 Marks)

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

---

END OF EXAMINATION PAPER