7-3 银行排队问题之单窗口“夹塞",c语言

银行排队问题通常是一个经典的计算机科学问题，用于演示算法设计中的并发控制和同步机制。在这个场景下，假设有一个单窗口服务，同时有若干名顾客排队等候。当一个窗口空闲时，如果有多名顾客等待，系统如何保证公平地让每个顾客都有机会办理业务而不发生插队现象。

"单窗口夹塞"指的是如果有新来的顾客想要插入队伍中，系统需要判断是否允许插入，避免形成不公平的情况。一种常见的解决方案是采用先进先出（FIFO，First In First Out）原则。我们可以使用C语言创建一个简单的模拟：

1. 定义一个数据结构，比如`struct Customer`，包含顾客的ID和到达时间。
2. 创建一个队列（如`queue_t`），用于存储等待的顾客。可以使用`stdlib.h`中的`#include <queue>`来使用`std::queue`或者自定义队列实现。
3. 当窗口空闲时，检查队列头部的顾客是否已经超过了他们应该等待的时间（即当前时间减去他们到达时间）。如果未超过，让他们进入服务；否则，拒绝新来的顾客插队，保持顺序。
4. 使用互斥量（mutex）来保护对队列的操作，防止多个线程同时修改。

示例代码（简化版）：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct {
    int id;
    time_t arrival_time;
} Customer;

// 简化的队列实现
typedef struct {
    Customer* front;
    Customer* rear;
} Queue;

Queue queue_init() { ... }
void queue_push(Queue*, Customer*) { ... }
Customer* queue_pop(Queue*) { ... }

int main() {
    Queue window_queue;
    clock_t start_time;
    while (true) {
        // 模拟服务开始
        if (queue_is_empty(&window_queue)) {
            // 获取当前时间和新顾客信息
            start_time = clock();
            Customer new_customer = generate_random_customer();

            // 判断是否允许夹塞
            if (!can_insert(&window_queue, new_customer.arrival_time, start_time)) {
                printf("新顾客不允许夹塞，继续排队...\n");
            } else {
                queue_push(&window_queue, &new_customer);
                printf("顾客 %d 入队...\n", new_customer.id);
            }
        } else {
            // 服务处理
            Customer* customer = queue_pop(&window_queue);
            process(customer);
            free(customer);  // 不妨清理资源
        }
    }
    return 0;
}

// 插入判断函数
bool can_insert(Queue* queue, time_t arrival_time, clock_t current_time) {
    Customer* front = queue->front;
    return current_time - arrival_time <= get_wait_time(front->arrival_time);
}