Section A

Memory

Regarding page replacement algorithms:

1. What is a page replacement algorithm?

An algorithm that replaces pages to avoid page faults

An algorithm that is used to replace a fault

An algorithm that is consulted when a page is needed to satisfy a page fault

An algorithm that is consulted when a page is no longer needed

2. When is a page replacement algorithm used?

Whenever there are no free pages available

Whenever a page fault occurs OR there are no free pages available.

Whenever a page fault occurs AND there are no free pages available.

Whenever a page fault occurs

You have been asked to select an appropriate page replacement algorithm for a high-performance computing cluster that supports a single CPU-intensive application consisting of many processes (1 per node in the cluster). Each process updates elements of a 2 GB array (on a 32-bit architecture machine) with good locality of reference.

3. Should this be a global or local algorithm?

Global

Both would be fine

Local

4. What is the effect of page faults on the processes running on each node?

When a page fault occurs, other processes are not affected.

When a page fault occurs, pages from other processes can be swapped out.

It depends on the choice of the page replacement algorithm.

5. What would be a suitable and practical page replacement algorithm?

FIFO

Optimal Page Replacement

Second-Chance Algorithm

One equivalence class of page replacement algorithms consists of the second-chance algorithms.

Consider the clock algorithm:

Given a set of 8 pages with their reference bits set as follows:

Assume the victim hand is at P3 and the queue is traversed towards the right.

6. When a frame is needed, what will be the situation after the new page has been inserted?

Assuming the enhanced, two-handed clock second-chance algorithms

Given a set of 8 pages with their reference and modify bits set as follows:

Assume the victim hand is at P3 and the queue is traversed towards the right.

7. When a frame is needed, which page will be replaced?

8. Under which circumstances would the clock variant (two-handed clock second-chance algorithm) be preferred over the standard second-chance algorithm.

If an application is rapidly updating contiguous elements in a small array

If an application is rapidly updating random elements in a large array

If an application is rapidly updating random elements in a small array

If an application is rapidly updating contiguous elements in a large array

Section B

Synchronization of tasks in a constrained environment.

Semaphores are a concurrency control primitive which enable protection of critical sections.

9. Which is the correct pseudocode for two tasks using semaphores to perform mutual exclusion of a critical section.

sem mutual_exclusion; /* must initialise this to 1 */
task_A(){
    do { ........
        wait(mutual_exclusion);
        <execute critical section>
        signal(mutual_exclusion);
    } FOREVER
}
task_B(){
    do { ........
        signal(mutual_exclusion);
        <execute critical section>
        wait(mutual_exclusion);
    } FOREVER
}

sem mutual_exclusion; /* must initialise this to 1 */
task_A(){
    do { ........
        wait(mutual_exclusion);
        <execute critical section>
        signal(mutual_exclusion);
    } FOREVER
}
task_B(){
    do { ........
        wait(mutual_exclusion);
        <execute critical section>
        signal(mutual_exclusion);
    } FOREVER
}

sem mutual_exclusion; /* must initialise this to 1 */
task_A(){
    do { ........
        signal(mutual_exclusion);
        <execute critical section>
    } FOREVER
}
task_B(){
    do { ........
        wait(mutual_exclusion);
        <execute critical section>
    } FOREVER
}

sem mutual_exclusion; /* must initialise this to 1 */
task_A() {
    do { ........
        signal(mutual_exclusion);
        <execute critical section>
        wait(mutual_exclusion);
    } FOREVER
}
task_B(){
    do { ........
        signal(mutual_exclusion);
        <execute critical section>
        wait(mutual_exclusion);
    } FOREVER
}

10. Which is the correct pseudocode to synchronise two tasks. Include semaphore initialization.

sem condSynchronise; /* initially 0 */
task_A() {
    do {
        wait(condSynchronise);
    } FOREVER
}
task_B() {
    do {
        signal(condSynchronise);
    } FOREVER
}

sem condSynchronise; /* initially 0 */
task_A() {
    signal(condSynchronise);
    do {
        wait(condSynchronise);
    } FOREVER
}
task_B() {
    wait(condSynchronise);
    do {
        signal(condSynchronise);
    } FOREVER
}

sem condSynchronise; /* initially 0 */
task_A() {
    wait(condSynchronise);
    do {
        signal(condSynchronise);
    } FOREVER
}
task_B() {
    signal(condSynchronise);
    do {
        wait(condSynchronise);
    } FOREVER
}

sem condSynchronise; /* initially 0 */
task_A() {
    do {
        signal(condSynchronise);
    } FOREVER
}
task_B() {
    do {
        wait(condSynchronise);
    } FOREVER
}

11. Specify the possible order of the code executed by these two tasks on a uniprocessor system.

B waits first for A to signal OR A signals first and B doesnâ€™t wait
A waits first for B to signal OR B waits first and A doesnâ€™t signal

B waits first for A to signal OR A signals first and B doesnâ€™t wait
A waits first for B to signal OR B signals first and A doesnâ€™t wait

A waits first for B to signal OR B waits first and A doesnâ€™t signal
A signals first and B waits OR B signals first and A doesnâ€™t wait

A waits first for B to signal OR B waits first and A doesnâ€™t signal
A waits first for B to signal OR B signals first and A doesnâ€™t wait

B waits first for A to signal OR A signals first and B doesnâ€™t wait
A signals first and B waits OR B signals first and A doesnâ€™t wait

12. What Pthreads concept is provided to enable meeting such synchronization requirements? Select pseudocode for how a typical task uses this concept?

lock the mutex
wait(condition, mutex) while (state does not possess the desired value)
manipulate shared state
signal appropriate condition
unlock the mutex

lock the mutex
wait(condition, mutex) while (state does not possess the desired value)
signal appropriate condition
manipulate shared state
unlock the mutex

wait(condition, mutex) while (state does not possess the desired value)
lock the mutex
manipulate shared state
signal appropriate condition
unlock the mutex

lock the mutex
signal appropriate condition
wait(condition, mutex) while (state does not possess the desired value)
manipulate shared state
unlock the mutex

13.
Is the following system deadlocked?

Deadlocked

It is not possible to tell from the diagram

Not deadlocked

Section C

Scheduling

Consider the following set of processes, with the length of the CPU burst given in milliseconds:

Which is the correct Gantt chart for the execution of these processes:

14. using First-Come First-Serve

15. Using Shortest Job First

16. Using non-preemptive Priority scheduling (a smaller priority number implies a higher priority) Here Burst Time for P4 = 3, for P3 = 1

17. Using Round-Robin (quantum = 1)

18. What is the average waiting time (over all processes) for the algorithm with minimal average waiting time?

3.6

8.6

19. What algorithm makes P5 finish the earliest?

SJF

Priority

FCFS

Operating Systems (H) - 2015 Exam