Is the state safe? – Operating Systems Practice

Use the banker's algorithm safety check to decide whether the system is in a safe state.

Work starts as Available. Go through the processes in order P0, P1, ..., Pn−1. Each unfinished process whose Need (Max − Allocation) is at most Work in every resource can finish: add its Allocation to Work and mark it finished. Repeat these passes until a whole pass finishes nobody.

Input

The first line has n and m (1 ≤ n ≤ 10 processes, 1 ≤ m ≤ 5 resource types). Then n lines of Allocation, n lines of Max (each with m numbers), and one line with the m numbers of Available.

Output

SAFE: followed by the processes in the order they finish (such as SAFE: P1 P3 P4 P0 P2), or UNSAFE if some process can never finish.

Examples

Example 1 · Input

Expected output

SAFE: P1 P3 P4 P0 P2

Example 2 · Input

Expected output

UNSAFE

Hints

Hint 1

Need = Max − Allocation, for every process and resource.

Hint 2

Work starts as Available. Make passes over P0, P1, ...: a process whose Need fits in Work finishes and adds its Allocation to Work.

Hint 3

Stop when a whole pass finishes nobody. The state is safe if everyone finished.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>

int main(void) {
    int n, m, alloc[10][5], max[10][5], work[5], finished[10] = {0}, order[10], count = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++)
        for (int r = 0; r < m; r++) scanf("%d", &alloc[i][r]);
    for (int i = 0; i < n; i++)
        for (int r = 0; r < m; r++) scanf("%d", &max[i][r]);
    for (int r = 0; r < m; r++) scanf("%d", &work[r]);
    int progress = 1;
    while (progress) {
        progress = 0;
        for (int i = 0; i < n; i++) {
            if (finished[i]) continue;
            int fits = 1;
            for (int r = 0; r < m; r++)
                if (max[i][r] - alloc[i][r] > work[r]) fits = 0;
            if (fits) {
                for (int r = 0; r < m; r++) work[r] += alloc[i][r];
                finished[i] = 1;
                order[count++] = i;
                progress = 1;
            }
        }
    }
    if (count < n) {
        printf("UNSAFE\n");
    } else {
        printf("SAFE:");
        for (int k = 0; k < n; k++) printf(" P%d", order[k]);
        printf("\n");
    }
    return 0;
}

Lesson: Deadlock →