SE350

Final Study SE350

• The I/O subsystem receives the following track read requests: 132, 44, 139, 163, 22, 129, 180, 133, and 70. The read head is currently located at track 150. Schedule the I/O using SCAN. Show the access behaviour in a figure with time on the x- axis and the track number on the y-axis. The disk’s read head moves 3 tracks per millimetre on the x-axis. Write down how much many millimetres have passed between the initial and the last read request on the x-axis.

• Explain the advantages of kernel-level threads over user-level threads

• Explain the conceptual differences between a process and a thread.

• Explain the dining philosophers problem and give a solution in pseudocode with five philosophers using the primitives of eat() and think(). Choose the concurrency control mechanism you prefer.

• Explain compaction in memory management and whether it tackles internal or external fragmentation.

  • Memory compaction is a technique used in memory management systems to reduce fragmentation, both internal and external, in the memory space. It involves rearranging the allocated memory segments to consolidate free memory blocks into larger contiguous blocks, thereby reducing fragmentation and improving memory utilization.
  • Here’s how memory compaction works and how it addresses fragmentation:
    • Internal Fragmentation: Internal fragmentation occurs when allocated memory blocks are larger than the requested size, resulting in wasted memory within the blocks. Memory compaction does not directly address internal fragmentation since it primarily deals with rearranging allocated memory segments to reduce external fragmentation. However, by consolidating free memory blocks into larger contiguous blocks, memory compaction indirectly reduces the likelihood of internal fragmentation occurring in the future.
    • External Fragmentation: External fragmentation arises when free memory blocks are scattered throughout the memory space, making it difficult to allocate contiguous memory blocks for large processes or data structures. Memory compaction targets external fragmentation directly by rearranging the allocated memory segments to create larger contiguous blocks of free memory. This consolidation of free memory blocks helps alleviate external fragmentation, making it easier to allocate memory for new processes or data structures.

• Discuss the effect of increasing the page size vs the number of page faults. Hint: Draw a figure with one on the x-axis and the other on the y-axis, and then discuss the figure.

• Explain the distinction that people commonly make between an operating system and a kernel

Final 2017

1. Name two important advantages/disadvantages for each of the following I/O handling techniques: programmed I/O, interrupt-drive I/O. [8p]

2. Explain the rationale for moving from a uni-programming batch system (S1) to a multi-programming time-sharing system (S2). Provide an illustrative example that clarifies the rationale and demonstrates two advantages of S2 over S1. [10p]

3. Name and describe at least three processor registers that an operating system must preserve during a context switch between processes. [6p]

   • Process pointer, Stack pointer, program counter, PSR

4. Explain the concept and purpose of a working directory for processes. [3p]

5. Explain a memory placement policy that requires periodic compaction. Justify your answer by describing the policy, the purpose of compaction, and whether the policy tackles internal or external fragmentation. [9p]

   • Buddy system involves compaction

6. List and explain four types of types of files found in the UNIX file system. [8p]

7. Explain the following two techniques for program loading: (1) absolute loading and (2) relocatable loading. For each of them explain their underlying concept and at least one advantage over the other method. [6p]

8. Explain a parameter passed to the compiler in your lab project, and justify why you used this parameter in the compilation process. [3p]

9. Assume a system with three resource types and four active processes. The system uses the banker’s algorithm to determine whether a deadlock exists.(a) Create a configuration where all three resource types together have more than 10 resources, and the resulting configuration should lead to a deadlock that involves at least two processes. (b) Run the bankers’s algorithm to detect the deadlock in the system.

10. Given a magnetic disk with 200 tracks. The last two tracks read in sequence were 99 and then 100. Assume that the system supports two policies: P1 is scheduling in FIFO mode, and P2 uses SCAN.

(a) Explain the purpose of I/O scheduling by enumerating the elements contributing to the timing of disk I/O transfers, and by justifying which portions can be controlled (= optimized) by the operating system. [5p]

(b) Design a sequence of track read requests where P1 takes at least twice as long as P2. You can either draw the answer using a ruler, or calculate the answer. [10p]

13. Wisdom-Ex is a dentist office specializing in removal of wisdom teeth (vestigial third molars). The office employs three dentists who operate in parallel but mutually exclusively on patients (= one patient per dentist). Business is going well, so the office built a waiting area with a sofa that seats five customers. Additional customers have to wait beside the sofa. Luckily the waiting area supports quantum folding, so an infinite number of customers can wait beside the sofa.

Whenever a dentist is available, a customer from the sofa will move on to the dentist chair and get treatment. At this point, one of the customers waiting beside the sofa can take a seat on the sofa.

(a) Write a pseudocode program for the function executed by dentists (named dentist() ) and customers (named customer() ). Also provide the pseudocode program for the function to initialize the system (name init()). You can assume that new customers arrive randomly, so init() doesn’t need to mention customers.

Use semaphores with wait() and signal() to realize mutual exclusion. You can define variables, however, all data is shared among all customers and dentists. Use comments to document in your code when: (1) the customer is waiting, sitting, or getting treatment; and (2) the dentist is operating or waiting for a customer.

You can assume the auxiliary functions: sitdown() finds an empty spot on the sofa and sits down, move from sofa to dentist chair() frees up a spot on the sofa and finds an empty dentist chair, gthooh() to leave the office after treatment, and extract tooth() for the dentist to remove the tooth of the person sitting in the chair. You can define additional functions as long as you explain what they do and they do not defeat the purpose of this question.

The following properties should hold:

• Always at most three customers get treatment.
• Always at most five customers sit on the sofa.
• If one customer is waiting beside the sofa, this implies that five customers are sitting on the sofa. [20p] (b) Discuss your solution with respect to fairness (FIFO) of the underlying scheduling of customers

for access to the sofa and the treatment. If your solution is not fair, then explain why. [7p] 14. Explain the fundamental problem of the following page replacement strategy: global replacement fixed allocation. [5p]