Operating Systems Concepts Question 1 (6 + 8 + 18 = 30 marks) a) Consider a scenario where a computer system has a small number of active processes using a large amount of their virtual address space, i.e., the system is running a small number of very large applications/processes. Most modern computers support more than one size for page frames, e.g., modern x86-64 capable CPUs can support 4KB, 2MB, or even 1GB. Discuss how (i) a smaller page frame size and (ii) a larger page frame size would impact the performance of the above system. b) Each page that is mapped into the virtual memory of a process has permissions such as read, write, and/or execute associated with it. Explain the benefits of having such permissions associated with each page, and what would happen if these permissions were breached, e.g., a process attempted to write to a page that did not have the write permission granted. c) Consider a scenario where the memory of the computer has a total of three physical page frames and the following sequence of page references are generated: 1, 2, 3, 4, 1, 2, 3, 2, 1, 4, 1, 2, 3, 4, 5, 6, 5, 4, 3, 1 i) Prepare tables/diagrams demonstrating the operation of the optimal, FIFO, and LRU page replacement algorithms for the above scenario; ii) Identify how many page faults occur for each algorithm; and iii) LRU is commonly used because its performance is close to optimal. Explain why (1) optimal itself is not used, and (2) why LRU's performance is close to optimal. Question 2 (8 + 6 + 11 + 15 = 40 marks) a) Explain the concept of a critical region and how critical regions occur (i) when pseudo-concurrency is used, and (ii) when physical concurrency is used. b) In the class slides for Week 6, on Slide 31 a scenario is presented demonstrating where a deadlock could occur using two semaphores. Explain how deadlock could occur if only one semaphore were used. c) Consider a scenario where an organization has been using the same software reliably for many years. The software does not include any mechanisms for managing deadlock, i.e., there is no deadlock recovery, avoidance, or prevention mechanisms in place. Recently the organization upgraded their hardware, which among other improvements also included an upgrade from a single-core CPU to a multi-core CPU. After the upgrade, the software the organization has been using reliably now regularly experiences deadlock. Explain why this scenario is possible and recommend an approach to solving it. d) Consider the following information about resource usage: Allocation A B C A Max B C Available A B C P0 1 2 2 9 8 8 2 2 2 P1 1 1 2 4 3 3 P2 2 1 1 2 1 7 P3 2 2 1 3 3 2 P4 2 2 2 7 7 7 Using the Banker's Algorithm: i. Demonstrate that the system is in a safe state. ii. Demonstrate that the system would not be in a safe state if a request for one C resource was granted to P2. iii. If process P2 were to request one C resource, as suggested in (ii), the system would not deadlock. Explain. Question 3 (5 + 6 + 6 + 13 = 30 marks) a) Executable files are regular files that follow a particular format (see Week 8 Slide 11). Would it be possible for two different operating systems running on the same type of hardware to share the same executables, e.g., Linux and FreeBSD running on an x86-64 PC? Explain. b) A friend of yours has made an amazing discovery when searching their computer for a file. They are looking for a file that they modified some time ago. They attempted to search for the file using the file name, then attempted to search for the file using the approximate date/time the file was last modified. Although both searches were unsuccessful, returning no results, they were surprised to discover that searching based on the approximate date/time, which would be a numerical comparison, took much longer than the file name comparison, which would be a string comparison. Given that comparing numbers should be much faster than textual strings, explain how each of these searches would work, and why there is a difference between the times. c) A file system can be configured to use a block size independent of any disk sector size (see Week 9 Slide 6). Consider a scenario where the file system is reconfigured to use a smaller block size in an attempt to increase the available/free disk space, however the disk space is actually reduced. Explain how this scenario could occur. In your answer, explain the relationship between file system block size and disk space wasted per file. d) Consider partitioning the disk for a Linux installation to maximize performance with the following partition requirements: the boot partition (1GB), the root file system (5GB), the /user folder (20GB), the /home folder (100GB), and the swap partition used for paging to disk (24GB). The disk will be used in a system used to run large computation tasks which regularly use more memory than the computer has RAM. Your tasks are as follows: i) Consider how the partitions should be laid out on the disk and draw a figure illustrating the logical layout you have designed, e.g., the following figure shows how you might draw the logical layout (note that this example also represents an incorrect answer). / /user /home Swap Boot ii) Explain why you laid out the partitions of the disk in the manner you chose and why it is suitable for a computer running large computation tasks. Marking Scheme Question 1 – 30 marks • Part (a) o (3 marks) Explanation of how smaller page frame size impacts performance. o (3 marks) Explanation of how larger page frame size impacts performance. • Part (b) o (3 marks) Explanation of benefits for associating permissions with each page. o (5 marks) Explanation of what happens upon breach of permission. • Part (c) o (i) (3x3 marks) Correct optimal / FIFO / LRU diagrams. o (ii) (3x1 mark) Correct number of page faults for optimal / FIFO / LRU. o (iii) (2x3 marks) Explanation of why optimal is not used; explanation of why LRU is close to optimal. Question 2 – 40 marks • Part (a) o (2 marks) Explanation of critical regions. o (3 marks) Explanation for critical regions and pseudo-concurrency. o (3 marks) Explanation for critical regions and physical concurrency. • Part (b) o (2 marks) Correctly identify how deadlock could occur with one semaphore. o (4 marks) Explanation of how deadlock could occur. • Part (c) o (3 marks) Explanation of why deadlock didn't occur previously. O (3 marks) Explanation of why deadlock occurs after upgrade. O (5 marks) Discussion of proposed solution. • Part (d) o (i) (5x2 marks) correct working for each step of execution for safe state. o (ii) (2 marks) Correct working demonstrating unsafe state. o (iii) (3 marks) Explanation of why the system will not deadlock. Question 3 – 30 marks • Part (a) o (2 marks) Correctly identifies whether executable files could be shared between different operating systems. o (3 marks) Explanation of why executable files could/could not be shared. • Part (b) o (3 marks) Explanation of how filename vs date/time searches work. o (3 marks) Explanation of why file name searches would take less time. • Part (c) o (3 marks) Explanation of the relationship between file system block size and disk space wasted per file. o (3 marks) Explanation of how reducing the file system block size could reduce the available/free disk space. • Part (d) o (3 marks) Design of partition layout illustrated in reasonable figure/diagram. o (5 marks) Explanation/justification of design of partition layout. o (5 marks) Explanation of suitability of partition layout for large computation tasks.