Process Management Exercises

Approach: Compare the two along the dimensions that actually differ — who owns the memory, what a switch costs, and how the two communicate — and then map those differences back onto application requirements.

Steps:

1. List the dimensions to compare: resource allocation, creation overhead, switching overhead, communication, concurrency, independence, and fault containment.
2. For each dimension, decide which mechanism is cheaper or stronger, and say why in terms of memory ownership and kernel work.
3. Turn the result into a selection rule: isolation, security, and fault containment point to processes; high concurrency, shared data, and fast response point to threads.

Answer:

Differences between processes and threads:

Application scenarios:

Processes are the right choice for:

• Applications that need a high degree of security and isolation
• Programs that need an independent memory space
• System service programs
• Scenarios that require fault isolation

Threads are the right choice for:

• Applications that need high concurrency performance
• Programs that share a large amount of data
• User interfaces that need to respond quickly
• Splitting up computation-intensive tasks

Approach: Start from the three states, then enumerate the transitions between them and attach the event that causes each one. The result is a diagram plus a table of triggers.

Steps:

1. Draw the three states — ready, running, and blocked — and the arrows between them.
2. For each arrow, name the event that triggers it: scheduling, an expired time slice, a request for I/O or a resource, and the completion of that event.
3. Check the diagram against reality by matching each transition to a concrete situation from a real program.

Answer:

Process state transition diagram:

State transition conditions:

1. Ready → Running:

   • The CPU scheduler selects the process for execution
   • The process is given a time slice
   • A higher-priority process gives up the CPU

2. Running → Ready:

   • The time slice expires
   • A higher-priority process preempts it
   • The process voluntarily gives up the CPU

3. Running → Blocked:

   • The process requests an I/O operation
   • It waits for an event or a resource
   • The process calls a blocking system call

4. Blocked → Ready:

   • The awaited event occurs
   • The requested resource becomes available
   • The I/O operation completes

Concrete examples:

• A user program waits for keyboard input: running → blocked
• A disk I/O completes: blocked → ready
• The time slice expires: running → ready
• The scheduler picks a process: ready → running

Approach: Evaluate the three algorithms against the same set of metrics, then derive the scenario for each one from the metric it wins or loses on.

Steps:

1. Fix the metric set: average turnaround time, average waiting time, response time, fairness, and implementation complexity.
2. Score each algorithm on every metric, and give the reason behind each score.
3. Derive the applicable scenario from the trade-off, and finish with how the size of the time slice changes RR.

Answer:

Comparison of algorithm characteristics:

Detailed analysis:

1. First Come, First Served (FCFS):

• Advantages: simple to implement, fair in appearance
• Disadvantages: long average waiting time, unfavourable to short processes, can cause starvation
• Suitable for: batch systems and systems whose jobs are of similar length

2. Shortest Job First (SJF):

• Advantages: shortest average turnaround time, high system throughput
• Disadvantages: unfair to long processes, requires the length of each job to be known in advance
• Suitable for: batch systems and systems whose jobs vary a lot in length

3. Round Robin (RR):

• Advantages: good response time, fair, a good fit for interactive systems
• Disadvantages: expensive context switches, performance depends on the choice of time slice
• Suitable for: time-sharing systems and interactive systems

The effect of the time slice:

• Too small: context switches happen constantly and the system overhead grows
• Too large: the algorithm degenerates into FCFS and response time suffers
• A good time slice is typically 10-100ms

Approach: Define the semaphore and its two atomic operations, then solve the problem by counting the free and full slots of the buffer and protecting the buffer itself with a mutex.

Steps:

1. State what a semaphore is and what the P and V operations do to its value and to waiting processes.
2. Identify the three semaphores the problem needs: empty for free slots, full for occupied slots, and mutex for the buffer itself.
3. Write the producer and the consumer, and check that every P operation has a matching V operation.

Answer:

The semaphore concept:

A semaphore is an integer variable that, apart from initialization, may only be accessed through two atomic operations:

• P operation (wait): request a resource, the semaphore is decremented by 1
• V operation (signal): release a resource, the semaphore is incremented by 1

What the P and V operations mean:

• P operation: if the semaphore is greater than 0, decrement it and carry on; if it is 0, block the process and wait
• V operation: increment the semaphore, and if a process is waiting, wake one up

Solution to the producer-consumer problem:

#define N 100
semaphore mutex = 1;    // mutual exclusion semaphore
semaphore empty = N;    // number of empty buffer slots
semaphore full = 0;     // number of full buffer slots

// Producer
void producer() {
    while (true) {
        item = produce_item();
        P(&empty);      // wait for an empty slot
        P(&mutex);      // enter the critical section
        insert_item(item);
        V(&mutex);      // leave the critical section
        V(&full);       // one more full slot
    }
}

// Consumer
void consumer() {
    while (true) {
        P(&full);       // wait for a full slot
        P(&mutex);      // enter the critical section
        item = remove_item();
        V(&mutex);      // leave the critical section
        V(&empty);      // one more empty slot
        consume_item(item);
    }
}

Types of semaphore:

1. Binary semaphore: the value is 0 or 1; used for mutual exclusion
2. Counting semaphore: the value may be any non-negative integer; used for synchronization

Approach: Name the four necessary conditions, then show that deadlock prevention works by destroying one of them, and that avoidance works by checking whether an allocation keeps the system in a safe state.

Steps:

1. List the four necessary conditions and explain each in one line.
2. For each condition, give the concrete mechanism that breaks it.
3. Show the deadlock that arises in the dining philosophers problem and the ordered allocation that removes it.
4. Close with the Banker’s algorithm as the alternative that permits more concurrency than prevention does.

Answer:

The four necessary conditions for deadlock:

1. Mutual exclusion: a resource cannot be used by several processes at the same time
2. Hold and wait: a process does not release the resources it holds while waiting for other resources
3. No preemption: a resource cannot be forcibly taken away
4. Circular wait: a chain of waiting processes forms a cycle

Ways to avoid deadlock:

1. Breaking mutual exclusion:

• Use shareable resources
• Use virtualization
• Use resource pools

2. Breaking hold and wait:

• Allocate all resources at once
• Release every held resource before requesting a new one

3. Breaking no preemption:

• Allow resources to be preempted
• Assign priorities to resources
• Use timeouts

4. Breaking circular wait:

• Ordered resource allocation
• A resource numbering scheme
• A hierarchical structure of resources

A concrete example:

How the dining philosophers problem deadlocks:

1. All philosophers pick up their left chopstick at the same time
2. They then wait for the right chopstick
3. A circular wait forms

Solution:

// Use ordered resource allocation
void philosopher(int i) {
    int left = i;
    int right = (i + 1) % 5;

    // always request the lower-numbered chopstick first
    if (left < right) {
        acquire_chopstick(left);
        acquire_chopstick(right);
    } else {
        acquire_chopstick(right);
        acquire_chopstick(left);
    }

    eat();

    release_chopstick(left);
    release_chopstick(right);
}

The Banker’s algorithm:

• Check before allocating whether the allocation would lead to an unsafe state
• Allocate resources only in a safe state
• Requires the maximum resource demand of each process to be known in advance

Approach: Track how many readers are currently inside, let the first reader take the writer lock and the last reader release it, and then show how the same scheme is inverted to give writers priority.

Steps:

1. Introduce readcount protected by mutex, plus a wrt semaphore that only one writer at a time may hold.
2. Write the reader so that it takes wrt only when it is the first reader, and the writer so that it simply takes and releases wrt.
3. Repeat the scheme with a read semaphore and a writecount to obtain the writer-preference variant.
4. Compare the two variants with respect to starvation.

Answer:

The readers-writers problem:

• Several readers may read the shared data at the same time
• A writer must have exclusive access
• Readers and writers may not access the data at the same time

Reader-preference solution:

semaphore mutex = 1;    // protects readcount
semaphore wrt = 1;      // writer mutual exclusion
int readcount = 0;      // number of readers

// Reader
void reader() {
    P(&mutex);          // enter the critical section
    readcount++;
    if (readcount == 1)
        P(&wrt);        // the first reader keeps writers out
    V(&mutex);          // leave the critical section

    read_data();        // read the data

    P(&mutex);          // enter the critical section
    readcount--;
    if (readcount == 0)
        V(&wrt);        // the last reader lets writers in
    V(&mutex);          // leave the critical section
}

// Writer
void writer() {
    P(&wrt);            // wait for the writer lock
    write_data();       // write the data
    V(&wrt);            // release the writer lock
}

Writer-preference solution:

semaphore mutex = 1;    // protects readcount
semaphore wrt = 1;      // writer mutual exclusion
semaphore read = 1;     // reader queue
int readcount = 0;      // number of readers
int writecount = 0;     // number of writers

// Reader
void reader() {
    P(&read);           // wait in the reader queue
    P(&mutex);
    readcount++;
    if (readcount == 1)
        P(&wrt);        // the first reader keeps writers out
    V(&mutex);
    V(&read);           // release the reader queue

    read_data();

    P(&mutex);
    readcount--;
    if (readcount == 0)
        V(&wrt);        // the last reader lets writers in
    V(&mutex);
}

// Writer
void writer() {
    P(&mutex);
    writecount++;
    if (writecount == 1)
        P(&read);       // the first writer keeps readers out
    V(&mutex);

    P(&wrt);
    write_data();
    V(&wrt);

    P(&mutex);
    writecount--;
    if (writecount == 0)
        V(&read);       // the last writer lets readers in
    V(&mutex);
}

The difference between the two schemes:

• Reader preference: readers may enter one after another, and writers can starve
• Writer preference: writers go first, and readers can starve

Approach: Describe each process with a structure that records its static attributes and its timing results, then simulate the scheduler one unit of time at a time.

Steps:

1. Define the Process structure with the fields needed for scheduling and for the metrics, and the state constants.
2. Implement add_process to fill in a new ready process.
3. Implement find_highest_priority_ready_process to pick the best candidate that has already arrived.
4. Implement the main loop: admit arrivals, pick a process, run it for one unit, record its completion metrics, and repeat until every process has finished.

Answer:

Process structure definition:

typedef struct {
    int pid;            // process ID
    char name[32];      // process name
    int priority;       // priority
    int arrival_time;   // arrival time
    int burst_time;     // burst time
    int remaining_time; // remaining time
    int state;          // process state
    int start_time;     // start time
    int completion_time; // completion time
    int turnaround_time; // turnaround time
    int waiting_time;   // waiting time
} Process;

// Process states
#define READY 0
#define RUNNING 1
#define BLOCKED 2
#define COMPLETED 3

Implementation of the priority scheduling algorithm:

#define MAX_PROCESSES 100

Process processes[MAX_PROCESSES];
int process_count = 0;
int current_time = 0;

// Add a process
void add_process(int pid, char* name, int priority, int arrival_time, int burst_time) {
    if (process_count < MAX_PROCESSES) {
        processes[process_count].pid = pid;
        strcpy(processes[process_count].name, name);
        processes[process_count].priority = priority;
        processes[process_count].arrival_time = arrival_time;
        processes[process_count].burst_time = burst_time;
        processes[process_count].remaining_time = burst_time;
        processes[process_count].state = READY;
        processes[process_count].start_time = -1;
        processes[process_count].completion_time = -1;
        processes[process_count].turnaround_time = -1;
        processes[process_count].waiting_time = -1;
        process_count++;
    }
}

// Find the ready process with the highest priority
int find_highest_priority_ready_process() {
    int highest_priority = -1;
    int selected_process = -1;

    for (int i = 0; i < process_count; i++) {
        if (processes[i].state == READY &&
            processes[i].arrival_time <= current_time &&
            processes[i].priority > highest_priority) {
            highest_priority = processes[i].priority;
            selected_process = i;
        }
    }

    return selected_process;
}

// Main priority scheduling function
void priority_scheduling() {
    int completed = 0;
    int current_process = -1;

    while (completed < process_count) {
        // check whether new processes have arrived
        for (int i = 0; i < process_count; i++) {
            if (processes[i].arrival_time == current_time) {
                processes[i].state = READY;
            }
        }

        // if no process is running, select a new one
        if (current_process == -1 || processes[current_process].state != RUNNING) {
            current_process = find_highest_priority_ready_process();
            if (current_process != -1) {
                processes[current_process].state = RUNNING;
                if (processes[current_process].start_time == -1) {
                    processes[current_process].start_time = current_time;
                }
            }
        }

        // run the current process
        if (current_process != -1) {
            processes[current_process].remaining_time--;

            // check whether the process has finished
            if (processes[current_process].remaining_time == 0) {
                processes[current_process].state = COMPLETED;
                processes[current_process].completion_time = current_time;
                processes[current_process].turnaround_time =
                    processes[current_process].completion_time -
                    processes[current_process].arrival_time;
                processes[current_process].waiting_time =
                    processes[current_process].turnaround_time -
                    processes[current_process].burst_time;
                completed++;
                current_process = -1;
            }
        }

        current_time++;
    }
}

// Print the scheduling results
void print_scheduling_results() {
    printf("Process scheduling results:\n");
    printf("PID\tName\tPriority\tArrival\tBurst\tStart\tCompletion\tTurnaround\tWaiting\n");

    for (int i = 0; i < process_count; i++) {
        printf("%d\t%s\t%d\t%d\t\t%d\t\t%d\t\t%d\t\t%d\t\t%d\n",
               processes[i].pid,
               processes[i].name,
               processes[i].priority,
               processes[i].arrival_time,
               processes[i].burst_time,
               processes[i].start_time,
               processes[i].completion_time,
               processes[i].turnaround_time,
               processes[i].waiting_time);
    }
}

Usage example:

int main() {
    // Add the test processes
    add_process(1, "P1", 3, 0, 6);
    add_process(2, "P2", 1, 2, 4);
    add_process(3, "P3", 4, 4, 2);
    add_process(4, "P4", 2, 6, 8);

    // Run the scheduler
    priority_scheduling();

    // Print the results
    print_scheduling_results();

    return 0;
}

Approach: Build a graph that records both the allocations and the outstanding requests, then reduce it: whenever a process whose requests can be satisfied is found, pretend it finishes and release what it holds.

Steps:

1. Define the edge structure and the graph structure that holds the available and total amount of every resource.
2. Implement the functions that add an allocation edge and a request edge.
3. Implement can_process_complete and release_process_resources so that a satisfiable process can be removed from the graph.
4. Detect the deadlock: if the reduction stops while some process is still unfinished, a deadlock exists.

Answer:

The structure of the resource allocation graph:

#define MAX_PROCESSES 10
#define MAX_RESOURCES 10

typedef struct {
    int process_id;
    int resource_id;
    int allocation;  // amount allocated
    int request;     // amount requested
} Edge;

typedef struct {
    int process_count;
    int resource_count;
    Edge edges[MAX_PROCESSES * MAX_RESOURCES];
    int edge_count;
    int available[MAX_RESOURCES];
    int total[MAX_RESOURCES];
} ResourceAllocationGraph;

Implementation of the deadlock detection algorithm:

// Initialize the resource allocation graph
void init_graph(ResourceAllocationGraph* graph, int processes, int resources) {
    graph->process_count = processes;
    graph->resource_count = resources;
    graph->edge_count = 0;

    for (int i = 0; i < resources; i++) {
        graph->available[i] = 0;
        graph->total[i] = 0;
    }
}

// Add an allocation edge
void add_allocation_edge(ResourceAllocationGraph* graph, int process_id, int resource_id, int amount) {
    graph->edges[graph->edge_count].process_id = process_id;
    graph->edges[graph->edge_count].resource_id = resource_id;
    graph->edges[graph->edge_count].allocation = amount;
    graph->edges[graph->edge_count].request = 0;
    graph->edge_count++;
}

// Add a request edge
void add_request_edge(ResourceAllocationGraph* graph, int process_id, int resource_id, int amount) {
    graph->edges[graph->edge_count].process_id = process_id;
    graph->edges[graph->edge_count].resource_id = resource_id;
    graph->edges[graph->edge_count].allocation = 0;
    graph->edges[graph->edge_count].request = amount;
    graph->edge_count++;
}

// Check whether a process can finish
bool can_process_complete(ResourceAllocationGraph* graph, int process_id) {
    for (int i = 0; i < graph->edge_count; i++) {
        if (graph->edges[i].process_id == process_id &&
            graph->edges[i].request > 0) {
            // check whether enough resources are available
            if (graph->edges[i].request > graph->available[graph->edges[i].resource_id]) {
                return false;
            }
        }
    }
    return true;
}

// Release the resources held by a process
void release_process_resources(ResourceAllocationGraph* graph, int process_id) {
    for (int i = 0; i < graph->edge_count; i++) {
        if (graph->edges[i].process_id == process_id &&
            graph->edges[i].allocation > 0) {
            graph->available[graph->edges[i].resource_id] += graph->edges[i].allocation;
            graph->edges[i].allocation = 0;
        }
    }
}

// The deadlock detection algorithm
bool detect_deadlock(ResourceAllocationGraph* graph) {
    bool finish[MAX_PROCESSES];
    int work[MAX_RESOURCES];

    // initialization
    for (int i = 0; i < graph->process_count; i++) {
        finish[i] = false;
    }
    for (int i = 0; i < graph->resource_count; i++) {
        work[i] = graph->available[i];
    }

    // look for a process that can finish
    bool found;
    do {
        found = false;
        for (int i = 0; i < graph->process_count; i++) {
            if (!finish[i] && can_process_complete(graph, i)) {
                // release the resources of the process
                for (int j = 0; j < graph->edge_count; j++) {
                    if (graph->edges[j].process_id == i &&
                        graph->edges[j].allocation > 0) {
                        work[graph->edges[j].resource_id] += graph->edges[j].allocation;
                    }
                }
                finish[i] = true;
                found = true;
            }
        }
    } while (found);

    // check whether every process has finished
    for (int i = 0; i < graph->process_count; i++) {
        if (!finish[i]) {
            return true; // a deadlock exists
        }
    }

    return false; // no deadlock exists
}

// Print the resource allocation graph
void print_graph(ResourceAllocationGraph* graph) {
    printf("Resource allocation graph:\n");
    printf("Process\tResource\tAllocation\tRequest\n");

    for (int i = 0; i < graph->edge_count; i++) {
        printf("P%d\tR%d\t%d\t%d\n",
               graph->edges[i].process_id,
               graph->edges[i].resource_id,
               graph->edges[i].allocation,
               graph->edges[i].request);
    }

    printf("Available resources: ");
    for (int i = 0; i < graph->resource_count; i++) {
        printf("R%d=%d ", i, graph->available[i]);
    }
    printf("\n");
}

Usage example:

int main() {
    ResourceAllocationGraph graph;

    // Initialize the graph
    init_graph(&graph, 3, 3);

    // Set the available resources
    graph.available[0] = 1;
    graph.available[1] = 1;
    graph.available[2] = 0;

    // Add the allocations and the requests
    add_allocation_edge(&graph, 0, 0, 1);  // P0 holds R0
    add_allocation_edge(&graph, 1, 1, 1);  // P1 holds R1
    add_request_edge(&graph, 0, 1, 1);     // P0 requests R1
    add_request_edge(&graph, 1, 0, 1);     // P1 requests R0

    // Print the graph
    print_graph(&graph);

    // Detect the deadlock
    if (detect_deadlock(&graph)) {
        printf("Deadlock detected!\n");
    } else {
        printf("No deadlock detected.\n");
    }

    return 0;
}