操作系统代写 hw4

Version 1.3

Homework 4

Due Nov 19^th, midnight

1. For each of the following decimal virtual addresses, compute the virtual page number and offset for a 4-KB page and for a 8-KB page:
   • 20,000
   • 32,768
   • 60,000
2. The relationship between virtual addresses and physical memory is given by the page table shown below. Every page begins on a multiple of 4K.

Using the page table, give the physical address corresponding to the following virtual addresses:

• 20
• 4100
• 8300

3. You are given the following information about the memory system (1 clock = 1 nsec):
   • The TLB can hold 1024 entries and can be accessed 1 clock cycle
   • A page table entry can be found in 100 clock cycles
   • The average page replacement time is 6msec.

If page references are handled by the TLB 99% of the time, and only 0.01% lead to a page fault, what is the effective address-translation time? How is the address-translation time change if we double the size of the TLB?

4. Can you think of situations when supporting virtual memory is a bad idea, and what would be gained by not having to support virtual memory? Explain your answer?

5. The CEO of the bank has come up with a (illegal) get-rich-scheme: the bank charges a fee whenever an account is over drafted (i.e., the balance < 0). The bank will reorder a customer’s transitions over the last 30 minutes to prioritize withdraws over deposits to increase the likelihood of an overdraft. As an example, consider the following sequence of events:
   • balance = $100
   • at 10:00, you deposit $100
   • at 10:28: you withdraw $105
   • balance = $95

The implementations of deposit and withdraw functions in the greedy bank’s systems will modify the order of transactions (subject to the 30 minute constraint) as follows:

• balance = $100
• at 10:28: you withdraw $105
• balance = -$5 [bank charges you a hefty overdraft fee]
• at 10:00, you deposit $100
• balance = $95

You are employed by the greedy bank to modify the implementations of  deposit and withdraw to implement this scheme. Note that the solution must also meet the previous requirement of correctly handling concurrent transactions.

Hint: Consider adding a data structure to keep track of the transactions.

The code should be structured as follows:

int balance;

transactions_t history; // keep track of some transactions

void deposit(int amount) {

… your code …

}

void widthdraw(int amount) {

… your code …

}

6. Suppose a workload trace on a processor when dynamic power management is not applied is as follows:

15, 35, 300, 300, 10, 1000, 50, 110, 1200 (ms)

Non-underlined numbers refer to the duration of an inactive period, and underlined numbers refer to the duration of an active period. The power state machine of the processor is included below:

What is the (1) total run time processor spends in RUN, SLEEP, and Transition, and (2) total energy consumption if each of the following dynamic power management policies are used?

1. Fixed time-out with a timeout threshold of 40 ms.
2. Fixed time-out with a timeout threshold of 350 ms.
3. Threshold-based predictive shutdown with a threshold of 60 ms?
4. If the workload is performance critical (but less energy constrained), which policy should we use? What if the workload is energy constrained (but less performance critical)? The analysis should be based on the above quantitative analysis.

7. Write a program (in C or Python) that simulates the paging system using the aging algorithm. The program takes the following arguments:

• The number of bits used to track the age of a page
• The number of pages that may be stored in memory
• The name of a file that includes the sequence of page references.

After each memory references, display the following information:

• the pages that are in memory and their bits. The output should be formatted as follows:
  • mem <PAGEID> <R-bits>
• the number of faults. The output should be formatted as follows:
  • fault <number>