|
|
#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;
|
|
|
}
|
