Soluzioni Hardware con e senza starvation per il corso SisOp

swap.c

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <signal.h>
#include <errno.h>

/**
 * Soluzioni Hardware:
 * Swap
 *
 * Molto simile al testAndSet, ma lo fa facendo lo swap.
 *
 * Soffre di busy waiting su spinlock, e può mandare in starvation il processo.
 * Qui va in starvation di brutto... Va solo il T1. Fa niente, il prossimo sarà senza starvation.
 */

#define FALSE 0
#define TRUE !0

char lock = FALSE;

void swap(char *v1, char *v2) {
    char tmp;
    tmp = *v1;
    *v1 = *v2;
    *v2 = tmp;
}

void testMilk(char *prefix);

_Noreturn void *t1(void *arg) {
    while (1) {
        char key = TRUE;
        while (key) {
            swap(&key, &lock);
        }
        testMilk("T1");
        lock = FALSE;

//        sleep(1);
    }
}

_Noreturn void *t2(void *arg) {
    while (1) {
        char key = TRUE;
        while (key) {
            swap(&key, &lock);
        }
        testMilk("T2");
        lock = FALSE;

//        sleep(3);
    }
}

int main() {
    printf("[Main] Starting threads...\n");

    pthread_t ts[2];
    if (pthread_create(&ts[0], NULL, t1, NULL) != 0) {
        printf("[Main] Could not create thread T1.\n");
        return 1;
    }

    sleep(1);
    if (pthread_create(&ts[1], NULL, t2, NULL) != 0) {
        printf("[Main] Could not create thread T2.\n");
        return 1;
    }

    int ts_size = sizeof(ts) / sizeof(ts[0]);
    printf("[Main] %d threads created. Waiting for threads to terminate...\n", ts_size);

//    while (1) {
//        sleep(1);
//        for (int i = 0; i < ts_size; i++) {
//            if (pthread_kill(ts[i], 0) == ESRCH) {
//                printf("[Main] T%d is dead.", i + 1);
//            }
//        }
//    }

    for (int i = 0; i < ts_size; i++) {
        if (pthread_join(ts[i], NULL) != 0) {
            printf("[Main] Could not join thread T%d.\n", i + 1);
            return 1;
        }
    }

    printf("[Main] All threads returned. Exiting...\n");

    return 0;
}

int milk = 0;

void testMilk(char *prefix) {
    if (milk < 1) {
        printf("[%s] Not enough milk! Buying some...\n", prefix);
        sleep(1);
        milk++;
        printf("[%s] Bought!\n", prefix);
    } else {
        printf("[%s] Milk available. Using some...\n", prefix);
        sleep(1);
        milk--;
        printf("[%s] Used!\n", prefix);
    }

    printf("[%s] Fridge: %d milk\n", prefix, milk);
}

swap_no_starvation.c

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <signal.h>
#include <errno.h>

/**
 * Soluzioni Hardware:
 * Swap senza starvation
 *
 * Soffre di busy waiting su spinlock.
 */

#define FALSE 0
#define TRUE !0

#define TS_SIZE 2
int waiting[TS_SIZE] = {FALSE, FALSE};
char lock = FALSE;

char swap(char *v1, char *v2) {
    char tmp = *v1;
    *v1 = *v2;
    *v2 = tmp;

    return *v1;
}

void testMilk(char *prefix);

_Noreturn void *t1(int i) {
    while (1) {
        char key = TRUE;
        waiting[i] = TRUE;
        // Aspetto fintanto che sono in lista d'attesa, e la SC è bloccata
        while (waiting[i] && swap(&key, &lock));
        // Se arrivo qui è perché la SC è stata sbloccata, oppure qualcuno mi ha lasciato passare impostando il mio waiting[i] a falso
        waiting[i] = FALSE;

        testMilk("T1"); // SC

        for (int j = i + 1;; j++) {
            j %= TS_SIZE;

            if (j == i) {
                lock = FALSE;
                break;
            }

            if (waiting[j]) {
                waiting[j] = FALSE;
                break;
            }
        }

        sleep(1);
    }
}

_Noreturn void *t2(int i) {
    while (1) {
        char key = TRUE;
        waiting[i] = TRUE;
        while (waiting[i] && swap(&key, &lock));
        waiting[i] = FALSE;

        testMilk("T2"); // SC

        int j = i + 1;
        for (; j != i; j++) {
            j %= TS_SIZE;

            if (waiting[j]) {
                break;
            }
        }

        if (j == i) {
            lock = FALSE;
        } else {
            waiting[j] = FALSE;
        }

        sleep(1);
    }
}

int main() {
    printf("[Main] Starting threads...\n");

    pthread_t ts[TS_SIZE];
    if (pthread_create(&ts[0], NULL, (void *(*)(void *)) t1, (void *) 0) != 0) {
        printf("[Main] Could not create thread T1.\n");
        return 1;
    }

    sleep(5);
    if (pthread_create(&ts[1], NULL, (void *(*)(void *)) t2, (void *) 1) != 0) {
        printf("[Main] Could not create thread T2.\n");
        return 1;
    }

//    int ts_size = sizeof(ts) / sizeof(ts[0]);
    printf("[Main] %d threads created. Waiting for threads to terminate...\n", TS_SIZE);

//    while (1) {
//        sleep(1);
//        for (int i = 0; i < ts_size; i++) {
//            if (pthread_kill(ts[i], 0) == ESRCH) {
//                printf("[Main] T%d is dead.", i + 1);
//            }
//        }
//    }

    for (int i = 0; i < TS_SIZE; i++) {
        if (pthread_join(ts[i], NULL) != 0) {
            printf("[Main] Could not join thread T%d.\n", i + 1);
            return 1;
        }
    }

    printf("[Main] All threads returned. Exiting...\n");

    return 0;
}

int milk = 0;

void testMilk(char *prefix) {
    if (milk < 1) {
        printf("[%s] Not enough milk! Buying some...\n", prefix);
        sleep(3);
        milk++;
        printf("[%s] Bought!\n", prefix);
    } else {
        printf("[%s] Milk available. Using some...\n", prefix);
        sleep(3);
        milk--;
        printf("[%s] Used!\n", prefix);
    }

    printf("[%s] Fridge: %d milk\n", prefix, milk);
}

test_and_set.c

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <signal.h>
#include <errno.h>

/**
 * Soluzioni Hardware:
 * Test and Set
 *
 * Soffre di busy waiting su spinlock, e può mandare in starvation il processo.
 * Basta mi sono scocciato ci sono da un'ora su sta merda.
 */

#define FALSE 0
#define TRUE !0

char lock = FALSE;

char testAndSet(char *lockIn) {
    char val;
    val = *lockIn;
    *lockIn = TRUE;
    return val;
}

void testMilk(char *prefix);

_Noreturn void *t1(void *arg) {
    while (1) {
        while (testAndSet(&lock));
        testMilk("T1");
        lock = FALSE;

        sleep(1);
    }
}

_Noreturn void *t2(void *arg) {
    while (1) {
        while (testAndSet(&lock));
        testMilk("T2");
        lock = FALSE;

        sleep(3);
    }
}

int main() {
    printf("%d", lock);
    printf("[Main] Starting threads...\n");

    pthread_t ts[2];
    if (pthread_create(&ts[0], NULL, t1, NULL) != 0) {
        printf("[Main] Could not create thread T1.\n");
        return 1;
    }

    if (pthread_create(&ts[1], NULL, t2, NULL) != 0) {
        printf("[Main] Could not create thread T2.\n");
        return 1;
    }

    int ts_size = sizeof(ts) / sizeof(ts[0]);
    printf("[Main] %d threads created. Waiting for threads to terminate...\n", ts_size);

//    while (1) {
//        sleep(1);
//        for (int i = 0; i < ts_size; i++) {
//            if (pthread_kill(ts[i], 0) == ESRCH) {
//                printf("[Main] T%d is dead.", i + 1);
//            }
//        }
//    }

    for (int i = 0; i < ts_size; i++) {
        if (pthread_join(ts[i], NULL) != 0) {
            printf("[Main] Could not join thread T%d.\n", i + 1);
            return 1;
        }
    }

    printf("[Main] All threads returned. Exiting...\n");

    return 0;
}

int milk = 0;

void testMilk(char *prefix) {
    if (milk < 1) {
        printf("[%s] Not enough milk! Buying some...\n", prefix);
        sleep(5);
        milk++;
        printf("[%s] Bought!\n", prefix);
    } else {
        printf("[%s] Milk available. Using some...\n", prefix);
        sleep(1);
        milk--;
        printf("[%s] Used!\n", prefix);
    }

    printf("[%s] Fridge: %d milk\n", prefix, milk);
}

test_and_set_no_starvation.c

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <signal.h>
#include <errno.h>

/**
 * Soluzioni Hardware:
 * Test and set senza starvation
 *
 * Soffre di busy waiting su spinlock.
 */

#define FALSE 0
#define TRUE !0

#define TS_SIZE 2
int waiting[TS_SIZE] = {FALSE, FALSE};
char lock = FALSE;

char testAndSet(char *lockIn) {
    char previous = *lockIn;
    *lockIn = TRUE;
    return previous;
}

void testMilk(char *prefix);

_Noreturn void *t1(int i) {
    while (1) {
        waiting[i] = TRUE;
        while (waiting[i] && testAndSet(&lock));
        waiting[i] = FALSE;

        testMilk("T1"); // SC

        for (int j = i + 1;; j++) {
            j %= TS_SIZE;

            if (j == i) {
                lock = FALSE;
                break;
            }

            if (waiting[j]) {
                waiting[j] = FALSE;
                break;
            }
        }

//        int j = i;
//        for (int times = 0; times < TS_SIZE; times++) {
//            j = (j + 1) % TS_SIZE;
//
//            if (waiting[j]) {
//                break;
//            }
//        }

//        int j;
//        for (j = i + 1; j != i; j++) {
//            j %= TS_SIZE;
//
//            if (waiting[j]) {
//                break;
//            }
//        }
//
//        if (j == i) {
//            lock = FALSE;
//        } else {
//            waiting[j] = FALSE;
//        }

        sleep(1);
    }
}

_Noreturn void *t2(int i) {
    while (1) {
        waiting[i] = TRUE;
        while (waiting[i] && testAndSet(&lock));
        waiting[i] = FALSE;

        testMilk("T2"); // SC

        int j = i + 1;
        for (; j != i; j++) {
            j %= TS_SIZE;

            if (waiting[j]) {
                break;
            }
        }

        if (j == i) {
            lock = FALSE;
        } else {
            waiting[j] = FALSE;
        }

//        int j = (i + 1) % TS_SIZE;
//        while (j != i && !waiting[j]) {
//            j = (j + 1) % TS_SIZE;
//        }
//
//        if (i == j) {
//            lock = FALSE;
//        } else {
//            waiting[j] = FALSE;
//        }

        sleep(1);
    }
}

int main() {
    printf("[Main] Starting threads...\n");

    pthread_t ts[TS_SIZE];
    if (pthread_create(&ts[0], NULL, (void *(*)(void *)) t1, (void *) 0) != 0) {
        printf("[Main] Could not create thread T1.\n");
        return 1;
    }

    sleep(5);
    if (pthread_create(&ts[1], NULL, (void *(*)(void *)) t2, (void *) 1) != 0) {
        printf("[Main] Could not create thread T2.\n");
        return 1;
    }

//    int ts_size = sizeof(ts) / sizeof(ts[0]);
    printf("[Main] %d threads created. Waiting for threads to terminate...\n", TS_SIZE);

//    while (1) {
//        sleep(1);
//        for (int i = 0; i < ts_size; i++) {
//            if (pthread_kill(ts[i], 0) == ESRCH) {
//                printf("[Main] T%d is dead.", i + 1);
//            }
//        }
//    }

    for (int i = 0; i < TS_SIZE; i++) {
        if (pthread_join(ts[i], NULL) != 0) {
            printf("[Main] Could not join thread T%d.\n", i + 1);
            return 1;
        }
    }

    printf("[Main] All threads returned. Exiting...\n");

    return 0;
}

int milk = 0;

void testMilk(char *prefix) {
    if (milk < 1) {
        printf("[%s] Not enough milk! Buying some...\n", prefix);
        sleep(3);
        milk++;
        printf("[%s] Bought!\n", prefix);
    } else {
        printf("[%s] Milk available. Using some...\n", prefix);
        sleep(3);
        milk--;
        printf("[%s] Used!\n", prefix);
    }

    printf("[%s] Fridge: %d milk\n", prefix, milk);
}