Complete the following four problems. Both the syllabus rules and ADJ Ruleset 1v2 are in e ect.
M7: Process Synchronization I
1. [Silberschatz, Acuæa] Assume that a context switch takes time T . Propose an algoithm to determine how long a process to hold a spinlock, based on the process load of a system and T. If the spinlock is held for long, switching to a mutex lock (where waiting threads are put to sleep) would give the system better CPU utilization by decreasing wasted cycles (i.e, the busy waiting in a spinlock). Analyze the problem, design an algorithm for computing the bound, and justify the algorithm’s optimality.
[5A+3D+5J points]
M9: CPU Scheduling
2. [Acuæa] Design an e cient (i.e., Big-Oh of a polynomial) algorithm for determining the time quantum t for a round robin scheduler. The algorithm must consider the current process load and compute t, where system throughput is maximized for some interval. Analyze the problem, design an algorithm for computing the bound, and justify the algorithm’s optimality. [5A+3D+5J points]
M11: Virtual Memory
3. [Acuæa] Consider the following fragment of code:
#define OFFSET(x , y , columns) = (y ∗ columns + x)
//check i f two matrices are the same . int equals ( IntMatrix∗ this , IntMatrix∗ other ) { i f ( other == NULL) return 0;
i f ( other−cols != this−cols | | other−rowsls != this−rows) return 0;
for ( int y = 0; y < this−rows ; y++) for ( int x = 0; x < this−cols ; x++)
//no intentational magic ; pointer arithmetic since C won’ t allow [ ] [ ] i f (∗( this−data + OFFSET(x , y , this−cols )) !=
∗( other−data + OFFSET(x , y , this−cols )) return 0;
return 1;
}
What page replacement scheme (of FIFO, OPR, LRU, MFU) should be used for this code? Analyze the problem, design a choice, and justify the choice
