TM298-Final-By ISA-1st Edition

Question 2: [10 marks] Assume having three processes P1, and P2 and the following resources: - One instances of R1 - Two instances of R2 - One instances of R3 And below is the relation between the resources and the processes: - P1 holds one instance of R1 and R2 and waiting for an instance of R3, - P2 holds one instance of R2 and R3 and waiting for R1. Draw a resource graph allocation and find whether it contains deadlock or not and justify your answer. R1 P2 R2 P1 R3 The graph contains a cycle (P1 → R3 → P2 → R1 → P1), there is a deadlock.

Question 3: [9 marks] Based on chapter 9. Consider the following segment table: What are the physical addresses for the following logical addresses? (Show the calculations) Segment Base Limit 0 120 300 1 1000 77 2 50 20 3 1200 96 a) 0,30 30 < 300  30 + 120 = 150 b) 1,60 60 < 77  60 + 1000 = 1060 c) 3,111 111 not < 96  illegal reference, trap to operating system Question 4: [10 marks] Based on Chapter 10. Consider the following page reference string: 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1 Assuming demand paging with three frames, how many page faults would occur using the optimal replacement algorithms? Show this by drawing the placement of pages in the frames after each reference and at the end write the number of page faults. Optimal replacement Algorithm 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 01 7772 2 2 2 27 000 0 4 0 00 11 3 3 3 11 9-page faults

Given the timing information below, calculate the average wait time and the turnaround time for a scheduler using: a. The First Come First Served algorithm b. The non-preemptive shortest job first algorithm c. The preemptive shortest job first algorithm Process Arrival Time Burst time (ms) P1 0 10 P2 5 7 P3 7 2 P4 10 10 P5 14 5 Answer a) ∎ Gantt chart: ������������ ������������ ������������ ������������ ������������ 0 10 17 19 29 34 ∎ Waiting time for P1 = 0; P2 = 10; P3 = 17; P4= 19; P5 = 29 ∎ Average waiting time: 0+10+17+19+29 = 75 = 15 55 Process Turnaround Time = Finishing time – arrival time ������������ 10 - 0 = 10 ������������ 17 – 5 = 12 ������������ 19 – 7 = 12 ������������ 29 – 10 = 19 ������������ 34 – 14 = 20 Average turnaround time 10+12+12+19+20 = 73 = 14.6 55

b) An explanation for the student (doesn’t required in the solution): In non-preemptive scheduling, once the CPU cycle is allocated to the process, the process holds it till it reaches a waiting state or is terminated. During our execution of the process that arrived first, new processes may arrive, so we will add them to wait queue till the execution of the current process end, and then we will compare the burst time of these new processes to hold the process that has less burst time. ∎ Gantt chart: ������������ ������������ ������������ ������������ ������������ 0 10 12 19 24 34 ∎ Waiting time for P1 = 0; P3= 10; P2 = 12; P5= 19; P4 = 24 ∎ Average waiting time: 0+10+12+19+24 = 65 = 13 55 Process Turnaround Time = Finishing time – arrival time ������������ 10 - 0 = 10 ������������ 12 – 7 = 5 ������������ 19 – 5 = 14 ������������ 24 – 14 = 10 ������������ 34 – 10 = 24 Average turnaround time 10+5+14+10+24 = 63 = 12.6 55

c) An explanation for the student (doesn’t required in the solution): In Preemptive SJF Scheduling, jobs are put into the ready queue as they come. A process with shortest burst time begins execution. If a process with even a shorter burst time arrives, the current process is removed or preempted from execution, and the shorter job is allocated CPU cycle.  Gantt chart: ������������ ������������ ������������ ������������ ������������ ������������ 0 79 12 19 24 34  Waiting time for: P1 = 9 – 7 = 2; P3= 7 – 7 = 0; P2 = 12 – 5 = 7; P5= 19 – 14 = 5; P4 = 24 – 10 = 14;  Average waiting time: 2 + 0 + 7 + 5 + 14 = 28 = 5.6 5 5 Process Turnaround Time = Finishing time – arrival time ������������ 12 - 0 = 12 ������������ 9–7=2 ������������ 19 – 5 = 14 ������������ 24 – 14 = 10 ������������ 34 – 10 = 24 Average turnaround time 12+2+14+10+24 = 62 = 12.4 55

Mock Exams

Part 1: Choose the correct answer for each of the following: [5 marks] 1. _______ is a single-tasking operating system. a) Linux b) BSD UNIX c) FreeBSD d) Arduino 2. Which one of the following statements is incorrect? a) Multithreading programming is useful in client-server systems. b) Threads creation is lighter than processes creation. c) Concurrency implies a system can perform more than one task simultaneously. d) Data parallelism – distributes subsets of the same data across multiple cores, same operation on each. 3. Device controller informs CPU that it has finished its operation by causing a) An interrupt b) A deadlock c) Mode bit change d) A race condition 4. _______ refers to where a process is accessing/updating shared data. a) Critical section b) Entry section c) Exit section d) Liveness 5. _____ can be used to prevent busy waiting when implementing a semaphore. a) Spinlocks b) Waiting queues c) Mutex lock d) Allowing the wait() operation to succeed

Part 2: Short and Essay questions: [15 marks] Question 1: [4 marks] Given two processes process 1 and process 2, show how Shared memory and Message passing models are used for intercrosses communication. (Hint: Draw clear representation for the models) Shared memory Message Passing Question 2: [6 marks] Explain the difference between global replacement and local replacement in virtual memory management and their advantages and disadvantages.  Global replacement – process selects a replacement frame from the set of all frames; one process can take a frame from another -ve : But then process execution time can vary greatly +ve : But greater throughput so more common  Local replacement – each process selects from only its own set of allocated frames +ve: More consistent per-process performance -ve: But possibly underutilized memory

Question 3: [5 marks] Explain how it is possible to invalidate the “No Preemption” and “Circular Wait” deadlock conditions in order to prevent deadlocks from taking place. No Preemption:  If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released  Preempted resources are added to the list of resources for which the process is waiting  Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting Circular Wait:  Impose a total ordering of all resource types,  and require that each process requests resources in an increasing order of enumeration Part 3: Problem Solving questions: [30 marks] Question 1: [8 marks] Write a shell program that do the following: a) Print the name of the bash script. b) Print the name of the current directly. c) Print the contents of the current directly with permissions. d) Print the words of the phrase “Welcome to TM298 Final Exam”, each word on a separate line. e) Use meaningful text in the output to understand what you print in a, b, c and d #!/bin/bash echo \"The shell script file name is \" $0 echo \"The current directory is \" pwd echo \"The contents of the current directory with permissions are: \" ls -l phrase=\"Welcome to TM298 Final Exam\" for word in $phrase do echo $word done

Question 2: [12 marks] Consider the following set of processes, with the arrival times and the CPU-burst times given in milliseconds and suppose that shortest-remaining-time-first is used for CPU scheduling. Process ID Arrival time CPU-burst time Completion Turn Around Time Waiting Time Time P1 0 15 P2 2 5 P3 5 3 P4 9 2 a) Draw the Gantt chart. (4 marks) b) Calculate context switches needed. (Do not count the context switches at time zero and at the end). (1 mark) c) Fill in the above table. (6 marks) d) Calculate the average waiting time. (1 mark) a) Gantt chart P1 P2 P3 P4 P1 02 7 10 12 25 b) Context switches needed = 4 c) Filled table Waiting Time 10 Process ID Arrival time CPU- Completion Time Turn Around 0 burst Time 2 P1 0 time 25 1 P2 2 7 25 P3 5 15 10 5 P4 9 5 12 5 3 3 2 d) Average waiting time = (13)/4= 3.25

Question 3: [10 marks] Based on Chapter 9, consider the following memory partitions of 800 KB, 400 KB, 100 KB, 200 and 400 KB (in order), and processes of 190 KB, 200 KB, 450 KB, and 220 KB (in order). Memory Process Partition a) How would each of the first-fit, best-fit and worst-fit algorithms place the above processes in the given memory partitions. Use the below 800 representation of the memory partitions and fill it for every algorithm. 400 (9 marks) 100 200 b) Which algorithm makes the most efficient use of memory? (1 marks) 400 First-fit: Memory Partition Process 800 190 400 200 100 200 400 220 Process 450 KB has no partitions so it will wait. Best-fit: Memory Partition Process 800 450 400 200 100 200 190 400 220 Worst-fit: Memory Partition Process 800 190 400 200 100 200 220 400 Processes 450 KB has no partitions so it will wait c) Best fit is the best

Part 1: Choose the correct answer for each of the following: [6 marks] 1. The two separate modes of operating in a system are a) Supervisor mode and system mode b) Kernel mode and privileged mode c) Physical mode and logical mode d) User mode and kernel mode 2. In Linux, passing parameters to the operating system is through a) Registers b) Stack c) Block in memory and address of the block passed as a parameter in register d) This not implemented in Linux 3. Which of the following scheduling algorithms is nonpreemptive? a) FCFS b) priority algorithms c) SJF d) RR 4. The roll out, roll in variant of swapping is used ____. a) for the round-robin scheduling algorithm b) for priority-based scheduling algorithms c) when the load on the system has temporarily been reduced d) when a backing store is not necessary 5. In Linux, the following command will $touch KSAFinal a) Create file KSAFinal b) Edit file KSAFinal c) Display contents of file KSAFinal d) Create directory KSAFinal

6. Given the following piece of shell script, which of the following statements is incorrect echo \"Please enter the a group of files names in the current directory \" read files for file in $files do cat $file done a) Variables file and files are not defined before this will give an error. b) The for loop is ended by “done”. c) The cat command displays file content. d) The $ means that it is a variable. Part 2: Answer the following questions: [18 marks] Question 1: [5 marks] What are the differences between a trap and an interrupt? How each of them is generated? A trap (or an exception) is a software-generated interrupt caused  either by an error (for example, division by zero or invalid memory access or infinite loop or system call)  Or by a specific request from a user program that an operating-system service. An interrupt is hardware-generated  A device controller informs CPU that it has finished its operation by causing an interrupt

Question 2: [5 marks] Describe the information associated with each process (Process Control Block information)  Process state – running, waiting, etc  Program counter – location of instruction to next execute  CPU registers – contents of all process-centric registers  CPU scheduling information- priorities, scheduling queue pointers  Memory-management information – memory allocated to the process  Accounting information – CPU used, clock time elapsed since start, time limits  I/O status information – I/O devices allocated to process, list of open files Question 3: [4 marks] Explain the solution to critical-section problem. 1. Mutual Exclusion - If process P is executing in its critical section, then no other processes can be executing in their critical sections 2. Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely 3. Bounded Waiting - A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted  Assume that each process executes at a nonzero speed  No assumption concerning relative speed of the n processes

Question 4: [4 marks] Explain the sequence of steps that happens when a page-fault occurs in virtual memory. If there is a reference to a page, first reference to that page will trap to operating system: page fault 1. Operating system looks at another table to decide:  Invalid reference  abort  Just not in memory 2. Find free frame 3. Swap page into frame via scheduled disk operation 4. Reset tables to indicate page now in memory Set validation bit = v 5. Restart the instruction that caused the page fault Part 3: Answer the following questions: [26 marks] Question 1: [6 marks] Compare Many to One and One to One models of multithreading by explaining each one of them and drawing the model. Also, give one example on an operating system that implements that model. 1. Many to One Many user-level threads mapped to single kernel thread if a thread is blocked then all are blocked so multiple threads may not run in parallel on muticore system because only one may be in kernel at a time Examples: Solaris Green Threads GNU Portable Threads

2. One to One Each user-level thread maps to kernel thread so creating a user-level thread creates a kernel thread. More concurrency than many-to-one Examples Windows Linux Question 2: [8 marks] Assume having three processes P1, P2 and P3 and the following resources: - Two instances of R1 - One instances of R2 - Two instances of R3 - One instance of R4 And below is the relation between the resources and the processes: - P1 holds one instance of R1 and R4 and waiting for an instance of R3, - P2 holds one instance of R1, R2 and R3. - P3 holds one instance of R3 and waiting for an instance of R1. Draw a resource graph allocation and find whether it contains deadlock or not and justify your answer.

R1 R4 R2 P2 P3 P1 R3 The graph contains many cycles R1  P1  R3 P3R1 R3  P3  R1  P1  R3 The rule: If graph contains a cycle and there are several instances per resource type, there is a possibility of deadlock In the above graph P2 acquired all its resources so it will terminate then both P1 and P2 get the rest of the resources they need and terminate. So there is no deadlock.

Question 3: [6 marks] Limit 300 Consider the following segment table: 77 Segment Base 20 0 120 96 1 1000 2 50 3 1200 What are the physical addresses for the following logical addresses? (Show the calculations) a) 0,30 30<300  120 + 30 = 150 b) 1,60 60<77 1000 + 60 = 1060 c) 3,111 111 not < 96  illegal reference, trap to operating system Question 4: [6 marks] Calculate the effective access time in milliseconds for a demanding page system, where Memory access time is 190 nanoseconds, the average page-fault service time is 10 milliseconds and the page fault is 2/1000. (Show full steps of calculations) Average page-fault service time = 10 ms x 1000 000 = 107 nanoseconds Effective Access Time (EAT) = (1 – p) x memory access + p (page fault overhead + swap page out + swap page in) Effective access time = (1-0.002) x 190 + 0.002 x 107 = 189.62 + 20 000 = 20,189.62 nanoseconds = 0.02018962 milliseconds =0.02 milliseconds

Question 4: (7 marks) Based on Chapter 8. Assume having four processes P1, P2, P3 and P4 and one instance of each the resources R1, R2, R3 and R4. And below is the relation between the resources and the processes: P1 holds the instance of R2 and R4 and waiting for R3. P2 holds the instance of R1. P3 holds the instance of R3 and waiting for an instance of R1. P4 is waiting for the instances of R1 and R4. Detect if there is a deadlock by drawing a wait for graph then explain your decision (if a deadlock exists or not). R2 R3 P1 P3 R4 R1 P2 P4 wait for graph P2 P4 P1 P3 The graph does not contain any cycle And since If there is a cycle, there exists a deadlock We can say that there is no deadlock at this moment in the system

Question 5: (7 marks) Memory Process Partition Based on Chapter 9, consider the following memory partitions of 300 KB, 200 KB, 600 KB, 200 and 400 KB (in order), and processes of 112 KB, 390 300 KB, 500 KB, and 250 KB (in order). 200 a) How would each of the first-fit, best-fit, and worst-fit algorithms place 600 200 the above processes in the given memory partitions. Use the below 400 representation of the memory partitions and fill it for every algorithm. b) Which algorithm makes the most efficient use of memory? (1 marks) a) First-fit: Memory Process Partition 112 390 300 250 200 600 200 400 Process 500 KB has no partition so it will wait Best-fit: Memory Process Partition 250 112 300 500 200 600 390 200 400 Worst-fit: Memory Partition Process 300 250 200 600 112 200 400 390 Process 500 KB has no partition so it will wait b) Best-fit is the best.

Question 6: (10 marks) Based on Chapter 10. Consider the following page reference string: 6, 7, 5, 1, 7, 3, 5, 0, 2, 6, 6, 1, 4, 3, 0, 2, 7, 3, 4, 1. a) Assuming demand paging with three frames, how many page faults would occur for the following replacement algorithms? Show this by drawing the placement of pages in the frames after each reference for each algorithm and at the end write the number of page faults.  FIFO replacement  LRU replacement (9 marks) b) Which replacement algorithm is better? (1 mark) a) FIFO replacement 6 75 1 7 3 50 2 6 61 4 3 0 2 7 3 4 1 6661 1 122 244422244 777 3 336 663337771 55 5 000 111000333 17 page faults LRU replacement 67 5173 5 02 6614 3 0 2 7341 6661 15556 663337771 777 77000 111000333 55 33322 244422244 18 page faults b) FIFO replacement is slightly better than LRU

Question 4: a) Assuming a 1 KB page size, what are the page numbers and offsets for the following logical addresses references (provided as decimal numbers). Show all calculations steps. (4 marks)  21112  5500050 b) Consider a 1 KB page size and a process size 66800, calculate the internal fragmentation. Show all calculations steps. (3 marks) a) Page size = 2n = 1 KB = 1024 B  21112 Page number = 21112/1024=20.6  so page number =20 Offset =21112-(20 x 1024) =632  5500050 Page number = 5500050/1024=5371.14  so page number = 5371 Offset =5500050-(5371 x 1024) =146 b) Process size = 66800 bytes The Process needs= 66800/1024 = 65 pages + 240 bytes So page 66 will have= 1024-240 = 784 free Bytes Internal fragmentation = 784 bytes