#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <stdlib.h>
//线程数
#define N 4 

//资源数
#define M 3 

//算法需要的数据结构，具体的意义可以看wiki里的定义
int avaliable[M] = {4, 5, 6};
int max[N][M] = {2, 3, 4, 1, 2, 1, 0, 1, 2, 3, 0, 0};
int allocation[N][M]; //在main里初始化
int need[N][M];       //在main里初始化

pthread_mutex_t lock; //互斥锁，确保资源读写互斥

int isSafe();                              //安全性算法
int allocate(int iOfThread, int *request); //资源请求算法
void *threadJob(void *index);              //线程任务

int main(int argc, char const *argv[])
{
    //初始化一些参数
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            allocation[i][j] = 0;
            need[i][j] = max[i][j];
        }
    }

    //线程id，在本例中并没有什么用，只是为了构造线程
    pthread_t ps[N];

    //这里给线程设参数，不同线程的参数地址必须不相同，否则会出BUG
    int params[N];
    for (int i = 0; i < N; i++)
    {
        params[i] = i;
    }

    //创建线程开始跑
    for (int i = 0; i < N; i++)
    {
        pthread_create(&ps[i], NULL, threadJob, &params[i]);
    }

    //主线程一直等
    while (1){};

    return 0;
}

int isSafe()
{

    // 1：初始化work和finish
    int work[M];
    for (int i = 0; i < M; i++)
        work[i] = avaliable[i];
    int finish[N];
    for (int i = 0; i < N; i++)
        finish[i] = 0;

    for (int i = 0; i < N; i++)
    {

        // 2：查找i使其满足可结束条件
        int flag = 1;
        for (int j = 0; j < M; j++)
        {
            if (need[i][j] > work[j])
            {
                flag = 0;
                break;
            }
        }

        // 3：如果找到了，使其结束，重新查找
        if (finish[i] == 0 && flag == 1)
        {
            for (int j = 0; j < M; j++)
            {
                work[j] = work[j] + allocation[i][j];
            }
            finish[i] = 1;
            i = 0;
        }
    }

    //4：返回是否所有进程都可以结束
    int flag = 1;
    for (int i = 0; i < N; i++)
    {
        if (finish[i] == 0)
        {
            flag = 0;
            break;
        }
    }

    return flag;
}

int allocate(int iOfThread, int *request)
{
    pthread_mutex_lock(&lock);

    // 1：检查是否超出了最大请求
    for (int j = 0; j < M; j++)
    {
        if (request[j] > need[iOfThread][j])
        {
            pthread_mutex_unlock(&lock);
            return -1;
        }
    }

    // 2：检查资源是否充足
    for (int j = 0; j < M; j++)
    {
        if (request[j] > avaliable[j])
        {
            pthread_mutex_unlock(&lock);
            return 0;
        }
    }

    // 3：假设可以分配，若安全则分配，不安全则不分配
    for (int j = 0; j < M; j++)
    {
        avaliable[j] = avaliable[j] - request[j];
        allocation[iOfThread][j] = allocation[iOfThread][j] + request[j];
        need[iOfThread][j] = need[iOfThread][j] - request[j];
    }
    if (isSafe() == 1)
    {
        pthread_mutex_unlock(&lock);
        return 1;
    }
    else
    {
        for (int j = 0; j < M; j++)
        {
            avaliable[j] = avaliable[j] + request[j];
            allocation[iOfThread][j] = allocation[iOfThread][j] - request[j];
            need[iOfThread][j] = need[iOfThread][j] + request[j];
        }
        pthread_mutex_unlock(&lock);
        return 0;
    }
}

void *threadJob(void *indexOfThread)
{
    int index = *((int *)indexOfThread); //本线程的序号
    srand(((int)index));                 //初始化一下随机值
    int want[M];                         //每次想要请求的资源，相当于allocate算法中的require
    int allocateResult;                  //分配结果
    int success;                         //本线程是否完成了任务

    //开始循环请求资源
    do
    {
        success = 1;

        //理论上这里不需要加锁，但是为了输出好看，还是加上了
        //如果不加锁，输出会串在一起，但不会影响运行
        pthread_mutex_lock(&lock);
        printf("Thread %d want resource: [ ", index);
        for (int i = 0; i < M; i++)
        {
            if (need[index][i] != 0)
                want[i] = rand() % (need[index][i] + 1);
            else
                want[i] = 0;
            printf("%d, ", want[i]);
        }
        printf("]\n");
        pthread_mutex_unlock(&lock);
        
        allocateResult = allocate(index, want);

        if (allocateResult == -1)
        {

            printf("Thread %d allocate result failed: need too much\n", index);
            //超出资源限界，直接终止进程
            return 0;
        }
        else if (allocateResult == 0)
        {
            printf("Thread %d allocate result failed: resource cannot allocate\n", index);
            //需要等待，休息一秒先
            success = 0;
            sleep(1);
        }
        else
        {
            printf("Thread %d allocate result success\n", index);
            sleep(1);
            //成功分配资源，检查是否拿到了所有资源
            for (int i = 0; i < M; i++)
            {
                if (need[index][i] != 0)
                {
                    success = 0;
                    break;
                }
            }
        }
    } while (success == 0);

    //成功拿到了所有的资源，释放掉
    printf("Thread %d get all its need!\n", index);
    pthread_mutex_lock(&lock);

    for (int i = 0; i < M; i++)
    {
        avaliable[i] = avaliable[i] + allocation[index][i];
        allocation[index][i] = 0;
        need[index][i] = 0;
        max[index][i] = 0;
    }

    pthread_mutex_unlock(&lock);
    return 1;
}