Consider an application with a total memory requirement of 1 megabyte, a working set of 100 kilobytes, and pages that may be compressed to an average of 2/3 of their original size, but with considerable variance from one page to the next.
Part A: If the heap manager used to store the (variable sized) compressed pages wastes, on average 10% of the heap to fragmentation, what minimum physical memory resources would you expect to be needed to run the application under consideration under the simplified model of RAM Doubler being considered here.
Part B: Consider the problem of storing compressed copies of pages. Some part of the physical memory will have to be used for this. Describe how you would organize this part of the memory, answering the following questions:
Part A: With reference to typical modern hardware, what data structures would you use to represent an address sapce, how would you handle the allocation of storage for those address spaces, and how would you handle the problem posed by the potentially large size of some address spaces?
Part B: With reference to typical modern hardware, how would you detect and prevent attempts by users to apply conventional machine instructions to objects that are not pages?
Part C: Describe the implementation of the Move Capability operation on typical modern hardware:
Part A: Given that all lock operatons must be completed before any record is read during a transaction, describe a simple deadlock avoidance algorithm that will prevent all deadlocks in this system.
Part B: Given that lock operations are performed one at a time, and that, after locking each record, that record may be read to determine the next record that must be locked:
head = 0 tail = 0 repeat receive( channel, msg ) if msg = "enqueue" receive( channel, msg ) buffer[tail] = msg tail = (tail + 1) mod size else assert msg = "dequeue" send( channel, buffer[head] ) head = (head + 1) mod size endif foreverNote that channel is a single memoryless channel used to communicate with both the processes doing the enqueueing and the processes doing the dequeueing.
The Problem: Write pseudocode, at this level of detail, for the procedures the user would use to enqueue and dequeue buffers full of data on this queue. You will need to use the send and receive primitives (as illustrated in the example) to move data between processes, and you will need to use some semaphores with the wait and signal operations to control that movement. In addition to your code for enqueue and dequeue procedures, you must clearly document the number of semaphores required, and their initial values!
After the sector size was optimized, a new improved disk scheduler was written for this system using the circular elevator algorithm.
The Problem: Would you expect the use of the new improved disk scheduler to change the optimal sector size? If so, would the new optimal sector size be larger or smaller than the original, and how big an impact on system performance would you expect from rewriting all the applications to use this new sector size?
The Question: Would it be better to first build a large virtual disk out of multiple disk devices and then build a disk scheduler on top of this, or would it be better to insert separate disk schedulers between the large virtual disk implementation and the individual disks? Why?