#include <stdio.h>
#include <windows.h>
#include <process.h>
#include <time.h>

// 全局变量
volatile int parking_spot_available = 1;
volatile int turn = 0;
volatile int flag[2] = { 0, 0 };
volatile int success_count[3] = { 0, 0, 0 };
volatile int cpu_usage[3] = { 0, 0, 0 };  // CPU占用计数器
volatile int conflict_count = 0;

// 算法A：值日法（单标志法）
DWORD WINAPI algorithm_a(LPVOID param) {
    int thread_id = (int)param;
    int attempts = 40;
    for (int i = 0; i < attempts; i++) {
        // 繁忙等待 - 等待轮到自己
        while (turn != thread_id) {
            cpu_usage[thread_id]++;  // 记录CPU占用
        }
        // 进入临界区
        if (parking_spot_available) {
            Sleep(5);  // 模拟使用车位
            success_count[thread_id]++;
            parking_spot_available = 0;
            parking_spot_available = 1;
        }
        // 让下一个线程有机会
        turn = (thread_id + 1) % 3;
        Sleep(1);
    }
    return 0;
}

// 算法B：双标志检查法
DWORD WINAPI algorithm_b(LPVOID param) {
    int thread_id = (int)param;
    int attempts = 40;
    int local_conflicts = 0;
    for (int i = 0; i < attempts; i++) {
        int wait_count = 0;
        int max_wait = 10000;
        // 第一步：设置自己的标志为TRUE
        flag[thread_id % 2] = 1;
        // 第二步：检查其他线程的标志
        int other_thread = (thread_id + 1) % 3;
        while (flag[other_thread % 2] && wait_count < max_wait) {
            cpu_usage[thread_id]++;  // 记录CPU占用
            wait_count++;
            if (wait_count % 1000 == 0) {
                Sleep(1);
            }
        }
        if (wait_count >= max_wait) {
            flag[thread_id % 2] = 0;
            Sleep(10);
            continue;
        }
        // 检查是否违反互斥
        if (!parking_spot_available) {
            local_conflicts++;
            conflict_count++;
        }
        // 进入临界区
        if (parking_spot_available) {
            Sleep(5);
            success_count[thread_id]++;
            parking_spot_available = 0;
            parking_spot_available = 1;
        }
        // 离开临界区
        flag[thread_id % 2] = 0;
        Sleep(1);
    }
    return 0;
}

// 算法C：Peterson算法
DWORD WINAPI algorithm_c(LPVOID param) {
    int thread_id = (int)param;
    int attempts = 40;
    if (thread_id == 2) {
        // 第三个线程使用简单等待
        for (int i = 0; i < attempts; i++) {
            while (!parking_spot_available) {
                cpu_usage[thread_id]++;  // 记录CPU占用
            }
            if (parking_spot_available) {
                Sleep(5);
                success_count[thread_id]++;
                parking_spot_available = 0;
                parking_spot_available = 1;
            }
            Sleep(1);
        }
        return 0;
    }
    // 线程0和1使用Peterson算法
    for (int i = 0; i < attempts; i++) {
        flag[thread_id] = 1;
        turn = 1 - thread_id;
        while (flag[1 - thread_id] && turn == 1 - thread_id) {
            cpu_usage[thread_id]++;  // 记录CPU占用
        }
        if (parking_spot_available) {
            Sleep(5);
            success_count[thread_id]++;
            parking_spot_available = 0;
            parking_spot_available = 1;
        }
        flag[thread_id] = 0;
        Sleep(1);
    }
    return 0;
}

// 测试函数
void test_algorithm(int algorithm_type) {
    HANDLE threads[3];
    DWORD threadIDs[3];
    // 重置计数器
    for (int i = 0; i < 3; i++) {
        success_count[i] = 0;
        cpu_usage[i] = 0;
    }
    parking_spot_available = 1;
    turn = 0;
    flag[0] = 0;
    flag[1] = 0;
    conflict_count = 0;

    printf("\n=== 测试算法 %c ===\n", 'A' + algorithm_type - 1);

    // 创建线程
    for (int i = 0; i < 3; i++) {
        switch (algorithm_type) {
            case 1:
                threads[i] = CreateThread(NULL, 0, algorithm_a, (LPVOID)i, 0, &threadIDs[i]);
                break;
            case 2:
                threads[i] = CreateThread(NULL, 0, algorithm_b, (LPVOID)i, 0, &threadIDs[i]);
                break;
            case 3:
                threads[i] = CreateThread(NULL, 0, algorithm_c, (LPVOID)i, 0, &threadIDs[i]);
                break;
        }
    }

    // 等待所有线程完成
    WaitForMultipleObjects(3, threads, TRUE, INFINITE);

    // 输出结果
    printf("成功抢到次数:\n");
    printf("  线程0: %d次\n", success_count[0]);
    printf("  线程1: %d次\n", success_count[1]);
    printf("  线程2: %d次\n", success_count[2]);
    printf("  总计: %d次\n", success_count[0] + success_count[1] + success_count[2]);

    printf("\nCPU占用(繁忙等待循环次数):\n");
    printf("  线程0: %d次\n", cpu_usage[0]);
    printf("  线程1: %d次\n", cpu_usage[1]);
    printf("  线程2: %d次\n", cpu_usage[2]);
    printf("  总计: %d次\n", cpu_usage[0] + cpu_usage[1] + cpu_usage[2]);

    if (conflict_count > 0) {
        printf("\n*** 检测到%d次冲突（违反互斥） ***\n", conflict_count);
    }

    // 关闭线程句柄
    for (int i = 0; i < 3; i++) {
        CloseHandle(threads[i]);
    }
}

int main() {
    printf("=== 抢车位模拟实验 - 三种繁忙等待算法对比 ===\n");
    printf("量化指标: 成功抢到次数 & CPU占用(繁忙等待循环次数)\n");
    printf("实验配置: 3个线程，每个线程尝试40次，总共120次\n");

    // 测试算法A
    printf("\n算法A：值日法（单标志法）");
    printf("\n特点：严格轮流，保证互斥但效率低\n");
    test_algorithm(1);

    // 测试算法B
    printf("\n算法B：双标志检查法");
    printf("\n特点：可能违反互斥，可能死锁\n");
    test_algorithm(2);

    // 测试算法C
    printf("\n算法C：Peterson算法");
    printf("\n特点：保证互斥，不会死锁\n");
    test_algorithm(3);

    // 实验结果分析
    printf("\n=== 实验结果分析 ===\n");
    printf("\n1. 正确性对比（是否违反互斥）:\n");
    printf("   - 算法A: 保证互斥，无冲突\n");
    printf("   - 算法B: 可能违反互斥，出现冲突\n");
    printf("   - 算法C: 保证互斥，无冲突\n");

    printf("\n2. 公平性对比（成功次数分布）:\n");
    printf("   - 算法A: 严格轮流，最公平\n");
    printf("   - 算法B: 分布不均，可能出现饥饿\n");
    printf("   - 算法C: 相对公平\n");

    printf("\n3. CPU浪费程度对比（繁忙等待循环次数）:\n");
    printf("   - 算法A: CPU占用最高，浪费严重\n");
    printf("   - 算法B: CPU占用中等，但存在正确性问题\n");
    printf("   - 算法C: CPU占用相对较低，效率较好\n");

    printf("\n4. 综合评估:\n");
    printf("   - 算法A: 正确性√ 公平性√ 但CPU浪费严重\n");
    printf("   - 算法B: 正确性× 公平性× CPU浪费中等\n");
    printf("   - 算法C: 正确性√ 公平性○ CPU浪费较低\n\n");

    printf("\n5. 信号量/互斥锁的优势:\n");
    printf("   - 避免繁忙等待，CPU占用大幅降低\n");
    printf("   - 保证正确性和公平性\n");
    printf("   - 现代操作系统推荐使用\n");

    return 0;
}