🏫 National Institute of Technology Silchar

Click to view the Question Paper

Answer any five questions (The questions are self-explanatory and need no explanation)

Question	Details	Marks	CO
1(a)	With a neat sketch, draw the process state diagram, explain various states the process may undergo from its creation to its termination. Mark all possible transitions and states and clearly explain the details of states and state-transitions.	5	CO1
1(b)	What is the difference between a process and a thread?	2	CO1
1(c)	Explain what happens when a program makes a system call.	3	CO1
2(a)	Consider the following page reference string: 7, 2, 3, 1, 2, 5, 3, 4, 6, 7, 7, 1, 0, 5, 4, 6, 2, 3, 0, 1. Assume demand paging with 3 frames. How many page faults would occur for the following replacement algorithms? Show your work. • LRU replacement • FIFO replacement • Optimal replacement	6	CO2
2(b)	Mention the various parameters (criteria) considered for CPU scheduling.	4	CO2
3(a)	Define the term race condition. What is the key to avoid race conditions?	3	CO3
3(b)	Why can't a single lock variable guarantee mutual exclusion? How does TestAndSet() achieve this?	3	CO3
3(c)	Name the four necessary conditions for a deadlock to hold. What is the approach commonly used to prevent each condition?	4	CO3
4(a)	What is TLB? What is the usage of TLB?	2	CO4
4(b)	Show the process of paging (conversion of logical address to physical address) with TLBs using a neat diagram.	4	CO4
4(c)	What is a page fault? With appropriate diagram, clearly discuss the steps involved in handling the page fault by an operating system.	4	CO4
5(a)	Explain SCAN disk scheduling algorithm.	5	CO5
5(b)	What are the advantages of the variant of linked allocation that uses a FAT to chain together the blocks of a file?	5	CO5
6(a)	Consider a 32-bit machine with a multi-level virtual memory system with 32-bit pointers and 4096 byte pages that supports two levels of page tables. All Page Table Entries (PTEs) are 4 bytes. (i) Show the complete format of a virtual address. (ii) How many memory operations are required to read or write a single 32-bit word? (iii) List the fields of a Page Table Entry (PTE).	5	CO6
6(b)	Write a C program to create a child process from its parent. Once the child process is created, immediately replace the binary image of the child process with a different task of your choice. Include all the required header files and provide appropriate documentation. You have to use fork() and exec() system calls.	5	CO6

Click to view the Question Paper

Answer any three questions (The questions are self-explanatory and need no explanation)

Question	Details	Marks	CO
1(a)	Compare and contrast between: system call and context switch.	2	CO1
1(b)	Mention any three attributes that the operating system maintains to keep track of information about a process and a thread.	2	CO1
1(c)	Identify any two differences between the following terms: (a) process and processor (b) fork and exec (c) preemptive and non-preemptive (d) CPU-bound and I/O-bound	4	CO1
2(a)	Given the table of process burst times, arrival times, and priorities shown below, calculate the turnaround time, waiting time, and number of preemptions for each process using the following scheduling algorithms: • SJF • SRT • RR (with a time slice of 3 ms) • Priority Scheduling Algorithm (note that the lower the priority value, the higher the priority). Process Table: Process Burst Time Arrival Time Priority P1 7 ms 0 ms 2 P2 5 ms 0 ms 3 P3 5 ms 1 ms 1 P4 6 ms 4 ms 2	6	CO2
2(b)	Consider the following snapshot of a system: Allocation / Maximum / Available Allocation Maximum Available Process A B C D A B C D A B C D P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 6 i. Is the system in a safe state? Show all calculations. ii. If a request from process P1 arrives for (0, 4, 2, 0), can the request be immediately granted?	3 + 3	CO3
3(a)	Consider the following information about resources in a system: • Six classes of allocatable resources labelled R1 through R6. • Five processes labelled P1 through P5. • Two instances of each resource. Currently allocated resources: • One instance of R1 held by P1, another by P2. • One instance of R3 held by P3, another by P4. • One instance of R4 held by P3. • One instance of R5 held by P3, another by P4. • Two instances of R6 held by P5. Requested resources: • P1 wants one instance of R4. • P2 wants one instance of R1 and one of R2. • P3 wants one instance of R1. • P4 wants one instance of R6. • P5 wants one instance of R3. (a) Draw the resource allocation graph for this system. (b) Is the system deadlocked? If so, which processes are involved? If not, give an execution sequence that eventually ends, showing resource acquisition and release at each step.	2 + 3	CO4
4	Consider Peterson’s algorithm for mutual exclusion between two concurrent processes i and j. The program executed by process i is shown below: Flag[i] = true; Turn = j; while (p) do no-op; Enter CS; Flag[i] = false; RS; Until false; In order to guarantee mutual exclusion, what should the conditions be set to and why?	5	CO5

Click to view the Question Paper

Answer any three questions (The questions are self-explanatory and need no explanation)

Question	Details	Marks	CO
1(a)	Write a C program to create a child process from its parent process. Once the child process is created, immediately replace the binary image of the child process with a different task of your choice. Include all the required header files and provide appropriate documentation. You have to use fork() and exec() system calls.	5	CO1
1(b)	With a neat sketch draw the process state diagram. Explain various process states the process may undergo from its creation to its termination. Mark all possible state transitions and explain them clearly.	5	CO1
1(c)	What are the necessary conditions for deadlock? Explain. What is the difference between deadlock prevention and deadlock avoidance? What category does Banker’s algorithm fall in and why?	5	CO1
2(a)	Consider the following page reference string: 7,2,3,1,2,5,3,4,6,3,3,1,0,5,4,6,2,3,0,1. Using demand paging with 4 frames, calculate the number of page faults for each of the following replacement algorithms: • FIFO replacement • LRU replacement • Optimal replacement Show calculations for each case.	6	CO2
2(b)	A computer has three page frames. The time of loading, time of last access, and the R and M bits for each page are shown below (time in clock ticks): Page Loaded Last Ref R Bit M Bit 0 126 280 1 0 1 230 265 0 1 2 140 270 0 0 3 110 285 1 1 i. Which page will Optimal Page Replacement (OPR) replace? ii. Which page will Second-Chance (Clock) algorithm replace? iii. Explain SCAN Disk Scheduling algorithm.	4	CO2
3(a)	What are the advantages of the variant of linked allocation that uses a File Allocation Table (FAT) to chain together the blocks of a file?	4	CO3
3(b)	Suppose we have resources A, B, and C and processes P1, P2, P3, and P4. The total number of each resource and the current/max allocations are given below: Total: A B C 7 8 9 Current / Max Allocations: Process Current A Current B Current C Max A Max B Max C P1 0 2 2 4 3 3 P2 2 2 1 3 6 9 P3 3 0 4 3 1 5 P4 1 3 1 3 3 4 i. Is the system in a safe state? If so, show a non-blocking sequence of thread executions. ii. Repeat the question if total number of C instances is 8 instead of 9.	10	CO3
7(a)	Consider a non-contiguous memory allocation scheme in which a logical memory address is represented using 12 bits for the page number and remaining bits for page offset. Answer the following: i. What is the total logical memory space? ii. How many pages are there? iii. What is the page size? iv. What is the frame size? v. If a process requires 78,901,234 bytes of memory, how many pages will it require? Explain internal fragmentation and external fragmentation with examples.	6	CO4
8	What are logical and physical addresses of a process? How is the logical address converted to a physical address using the Memory Management Unit (MMU)? With a diagram, discuss how the hardware protection mechanism prevents access to memory space of other processes and the operating system.	5	CO4
9(a)	What is a page fault? With an appropriate diagram, discuss the steps involved in handling a page fault by an operating system.	5	CO5
9(b)	What is thrashing? What is the Working-Set Model (WSM) of a process? How do you track the working set? Comment on the relation between WSM and size of physical memory in view of thrashing.	5	CO5
10	Explain the concept and purpose of page directories. Explain segmentation and paging techniques with proper diagrams.	10	CO5

Click to view the Question Paper

Answer all the questions (The questions are self-explanatory and need no explanation)

Question	Details	Marks	CO
1(a)	Five processes namely A, B, C, D, and E arrive at different times with CPU requirements as shown below: Process Arrival Time CPU Requirements A 0.0000 7 B 1.0001 7 C 4.0001 5 D 7.0001 5 E 8.0001 3 Table 1: (For waiting and turnaround time) A B C D E FCFS wait FCFS turn SJF wait SJF turn RR wait RR turn SRTF wait SRTF turn Questions: a. Show the scheduling order for the above processes under 4 policies: First Come First Serve (FCFS) Shortest Job First (SJF) Round Robin (RR) with a time quantum of 1 Shortest Remaining Time First (SRTF) Assume context switch overhead = 1. b. For each process, find the waiting time and turnaround time as indicated in Table 1.	8	CO1
2(a)	Consider the code on the right-hand side: int main(void) { for(i = 0; i < 3; i++) { pid_t pid = fork(); } } i. Find the total number of processes that will be created assuming all calls to fork() succeed. ii. When a new child process is created as part of handling fork(), what does the kernel/system stack of the new child contain after the fork finishes creating it, but just before the CPU switches away from the parent?	4	CO2
2(b)	Consider a process executing on a CPU. Give an example scenario that can cause the process to undergo — i. a voluntary context switch. ii. an involuntary context switch.	2	CO2
3(a)	The first known correct software solution to the critical-section problem for two processes was developed by Dekker. The two processes, P0 and P1, share the following variables: boolean flag[2]; // initially false int turn; The structure for process Pi (i = 0 or 1, with Pj being the other) is given below: repeat flag[i] = true; while(flag[j]) { if (turn == j) { flag[i] = false; while(turn == j) do nothing; flag[i] = true; } } critical section turn = j; flag[i] = false; remainder section until false; i. What is the meaning of the term busy waiting? ii. What other kinds of waiting are there in an operating system? iii. Can busy waiting be avoided altogether? Explain. iv. What do you mean by race condition? Give an example.	6	CO3

Click to view the Question Paper

Answer any eight questions (The questions are self-explanatory and need no explanation)

Question	Details	Marks	CO
1	Explain the concept of process synchronization using semaphore. How the Readers/Writers problem can be solved using semaphore?	7 + 3	CO1
2	Consider the following page reference and reference time strings for a program: 5,4,3,2,1,4,3,5,4,3,2,1,5,... a) Show how pages will be allocated using the FIFO page replacement policy. b) Calculate the total number of page faults when allocated page blocks are 3 and 4 respectively.	5 + 5	CO2
3	Discuss Dining Philosophers solution using Monitors. Illustrate the monitor concept assuming five philosophers.	10	CO3
4	A system having five processes and four resource classes. The current resource allocation state is shown below: Process Allocation (A B C D) Maximum (A B C D) Available (A B C D) P0 0 0 1 2 0 0 1 2 1 5 2 0 P1 1 0 0 0 1 7 5 0 P2 1 3 5 4 2 3 5 6 P3 0 6 3 2 0 6 5 2 P4 0 0 1 4 0 6 5 2 Answer the following: i. What is the content of the need matrix? ii. Is the system in safe state? Explain and show calculations. iii. If a request for process P1 arrives for (0,4,2,0), can it be granted immediately?	3 + 3 + 4	CO3
5	Explain in detail the following disk scheduling strategies: FCFS, SCAN, C-SCAN and C-LOOK.	10	CO4
6	When a detection algorithm determines that a deadlock exists, several alternatives are available. What are those alternatives? Explain.	10	CO3
7	Suppose that we have a two-level page translation scheme with 4K-byte pages and 4-byte page table entries (includes a valid bit, a couple permission bits, and a pointer to another page/table entry). a) What is the format of a 32-bit virtual address? b) Sketch the paging architecture required to translate a 32-bit virtual address (ignore the TLB).	10	CO4
8	You have devised a new page-replacement algorithm that you think may be optimal. In some conducted test cases, Belady's anomaly occurs. Is the new algorithm optimal? Explain your answer.	10	CO2
9	Explain and describe the four ways systems might provide for users to protect their files against other users.	10	CO5

Click to view the Question Paper

Answer all the questions (The questions are self-explanatory and need no explanation)

Question	Details	Marks	CO
1(a)	Draw the block diagram of a multi-core microprocessor indicating the placement of L1, L2, and L3 caches on the chip.	2	CO1
1(b)	What is meant by single-user mono programming system? What are its drawbacks?	1 + 1	CO1
1(c)	What is a zombie process and how do I kill it?	1 + 1	CO1
1(d)	Draw the 5-state diagram of a system of resident processes. Explain each state briefly. (Include New, Ready, Running, Waiting, and Terminated states.)	2	CO1
1(e)	Which scheduler comes into play when the degree of multiprogramming becomes less? Explain briefly.	2	CO1
2(a)	Explain briefly how to use counting semaphores for gaining access to a resource having a finite number of instances.	2	CO2
2(b)	Write a short note on the concept of a pipe in UNIX. Explain its purpose in inter-process communication.	2	CO2
2(c)	Give a solution to the Dining Philosophers problem using monitors. Illustrate with suitable pseudocode or diagram.	3	CO3
2(d)	Suggest modifications in the Round Robin scheduling policy so that it can give a fair chance to I/O-bound processes to execute efficiently.	3	CO3
3(a)	What are the situations where it becomes necessary for concurrent processes to communicate with each other? Discuss Peterson’s solution to the critical-section problem for two processes.	2 + 2	CO4
3(b)	Give reasons to prefer multi-threaded over single-threaded processes in modern operating systems.	2	CO4
3(c)	Consider the following set of processes. Draw the Gantt Chart for execution under: (i) Non-preemptive Shortest Job First (SJF) scheduling (ii) Preemptive Shortest Remaining Time First (SRTF) scheduling. Calculate the average waiting time for the system. Process Arrival Time CPU Burst Time P1 0 72 P2 50 10 P3 60 84 P4 70 30 P5 100 56	4	CO5