电梯调度算法C语言实现详解从FCFS到SCAN策略优化与多线程同步问题解决指南

引言：电梯调度算法的核心挑战
电梯调度算法是操作系统进程调度和现实工程应用中的经典问题。它不仅考验算法的效率，还涉及多线程同步、资源竞争和用户体验优化。在现代高楼大厦中，电梯系统每天处理成千上万的请求，一个优秀的调度算法能显著减少乘客等待时间，提升整体运行效率。
本文将从最基础的
先来先服务（FCFS）
算法开始，逐步深入到
扫描算法（SCAN）
的优化实现，最后探讨
多线程环境下的同步问题
。我们将使用C语言进行完整实现，并提供详细的代码注释和测试案例，帮助读者彻底掌握电梯调度算法的精髓。
一、基础算法：先来先服务（FCFS）
1.1 FCFS算法原理
FCFS（First-Come, First-Served）是最简单的调度策略，按照请求到达的顺序依次处理。这种算法实现简单，但效率较低，容易产生”饥饿”现象。
核心思想
：维护一个请求队列，每次取出队首的请求进行服务。
1.2 C语言实现
#include
#include
#include

#define MAX_REQUESTS 100
#define MAX_FLOORS 20

// 电梯请求结构体
typedef struct {
int from_floor; // 起始楼层
int to_floor; // 目标楼层
int timestamp; // 请求时间戳
} Request;

// FCFS调度器
typedef struct {
Request queue[MAX_REQUESTS];
int head; // 队头指针
int tail; // 队尾指针
int count; // 当前请求数
} FCFSScheduler;

// 初始化FCFS调度器
void init_fcfs(FCFSScheduler *scheduler) {
scheduler->head = 0;
scheduler->tail = 0;
scheduler->count = 0;
}

// 添加请求到队列
bool fcfs_add_request(FCFSScheduler *scheduler, Request req) {
if (scheduler->count >= MAX_REQUESTS) {
return false; // 队列已满
}
scheduler->queue[scheduler->tail] = req;
scheduler->tail = (scheduler->tail + 1) % MAX_REQUESTS;
scheduler->count++;
return true;
}

// 获取下一个要服务的请求
bool fcfs_get_next(FCFSScheduler *scheduler, Request *next_req) {
if (scheduler->count == 0) {
return false; // 没有请求
}
*next_req = scheduler->queue[scheduler->head];
scheduler->head = (scheduler->head + 1) % MAX_REQUESTS;
scheduler->count–;
return true;
}

// 打印当前队列状态
void fcfs_print_queue(FCFSScheduler *scheduler) {
printf(“FCFS队列状态: “);
int i = scheduler->head;
int cnt = scheduler->count;
while (cnt > 0) {
printf(“[%d->%d] “, scheduler->queue[i].from_floor,
scheduler->queue[i].to_floor);
i = (i + 1) % MAX_REQUESTS;
cnt–;
}
printf(“\n”);
}

// FCFS测试函数
void test_fcfs() {
FCFSScheduler scheduler;
init_fcfs(&scheduler);

// 模拟请求
Request req1 = {1, 10, 100};
Request req2 = {5, 15, 101};
Request req3 = {3, 8, 102};

fcfs_add_request(&scheduler, req1);
fcfs_add_request(&scheduler, req2);
fcfs_add_request(&scheduler, req3);

fcfs_print_queue(&scheduler);

Request next;
while (fcfs_get_next(&scheduler, &next)) {
printf(“服务请求: %d层 -> %d层\n”, next.from_floor, next.to_floor);
}
}
1.3 FCFS算法分析
优点
：
实现简单，逻辑清晰
无饥饿现象（公平对待所有请求）
无优先级偏见
缺点
：
效率低下，可能导致电梯”来回跑”
不考虑当前电梯位置，响应时间长
无法处理紧急请求
适用场景
：小型建筑或请求量极少的场景。
二、扫描算法（SCAN）优化实现
2.1 SCAN算法原理
SCAN算法（也称为电梯算法）模拟真实电梯的运行方式：电梯沿一个方向移动，服务所有该方向的请求，直到该方向没有请求，然后反向移动。
核心思想
：
电梯有当前方向（上行或下行）
服务所有同方向的请求
当没有同方向请求时，改变方向
优先服务同方向的请求
2.2 C语言实现
#include
#include
#include
#include

#define MAX_FLOORS 20
#define MAX_REQUESTS 100

// 方向定义
typedef enum {
DIR_IDLE,
DIR_UP,
DIR_DOWN
} Direction;

// 电梯状态
typedef struct {
int current_floor; // 当前楼层
Direction direction; // 当前方向
bool up_requests[MAX_FLOORS]; // 上行请求
bool down_requests[MAX_FLOORS]; // 下行请求
} ElevatorState;

// SCAN调度器
typedef struct {
ElevatorState elevator;
int total_requests; // 总请求数
} SCANScheduler;

// 初始化SCAN调度器
void init_scan(SCANScheduler *scheduler) {
scheduler->elevator.current_floor = 1; // 假设初始在1楼
scheduler->elevator.direction = DIR_IDLE;
memset(scheduler->elevator.up_requests, 0, sizeof(scheduler->elevator.up_requests));
memset(scheduler->elevator.down_requests, 0, sizeof(scheduler->elevator.down_requests));
scheduler->total_requests = 0;
}

// 添加请求
void scan_add_request(SCANScheduler *scheduler, int from_floor, int to_floor) {
if (from_floor < 1 || from_floor > MAX_FLOORS ||
to_floor < 1 || to_floor > MAX_FLOORS) {
return;
}

if (to_floor > from_floor) {
// 上行请求
scheduler->elevator.up_requests[from_floor] = true;
scheduler->elevator.up_requests[to_floor] = true;
} else {
// 下行请求
scheduler->elevator.down_requests[from_floor] = true;
scheduler->elevator.down_requests[to_floor] = true;
}

scheduler->total_requests++;
printf(“添加请求: %d层 -> %d层\n”, from_floor, to_floor);
}

// 获取下一个要访问的楼层
int scan_get_next_floor(SCANScheduler *scheduler) {
ElevatorState *e = &scheduler->elevator;

// 如果当前没有请求，返回-1
bool has_up = false, has_down = false;
for (int i = 1; i <= MAX_FLOORS; i++) { if (e->up_requests[i]) has_up = true;
if (e->down_requests[i]) has_down = true;
}

if (!has_up && !has_down) {
e->direction = DIR_IDLE;
return -1;
}

// 确定方向
if (e->direction == DIR_IDLE) {
if (has_up) e->direction = DIR_UP;
else if (has_down) e->direction = DIR_DOWN;
}

// 根据方向选择下一个楼层
if (e->direction == DIR_UP) {
// 向上寻找最近的请求
for (int i = e->current_floor + 1; i <= MAX_FLOORS; i++) { if (e->up_requests[i]) {
return i;
}
}
// 上方没有请求，检查下方是否有请求
if (has_down) {
e->direction = DIR_DOWN;
// 向下寻找最近的请求
for (int i = e->current_floor – 1; i >= 1; i–) {
if (e->down_requests[i]) {
return i;
}
}
}
} else if (e->direction == DIR_DOWN) {
// 向下寻找最近的请求
for (int i = e->current_floor – 1; i >= 1; i–) {
if (e->down_requests[i]) {
return i;
}
}
// 下方没有请求，检查上方是否有请求
if (has_up) {
e->direction = DIR_UP;
// 向上寻找最近的请求
for (int i = e->current_floor + 1; i <= MAX_FLOORS; i++) { if (e->up_requests[i]) {
return i;
}
}
}
}

return -1;
}

// 移动到下一个楼层
void scan_move(SCANScheduler *scheduler, int next_floor) {
if (next_floor == -1) {
printf(“电梯空闲，当前在%d层\n”, scheduler->elevator.current_floor);
return;
}

printf(“电梯从%d层移动到%d层，方向: %s\n”,
scheduler->elevator.current_floor, next_floor,
scheduler->elevator.direction == DIR_UP ? “上行” : “下行”);

// 清除该楼层的请求
if (scheduler->elevator.direction == DIR_UP) {
scheduler->elevator.up_requests[next_floor] = false;
} else {
scheduler->elevator.down_requests[next_floor] = false;
}

scheduler->elevator.current_floor = next_floor;
}

// 打印当前状态
void scan_print_state(SCANScheduler *scheduler) {
printf(“当前楼层: %d, 方向: %s\n”,
scheduler->elevator.current_floor,
scheduler->elevator.direction == DIR_UP ? “上行” :
scheduler->elevator.direction == DIR_DOWN ? “下行” : “空闲”);

printf(“上行请求: “);
for (int i = 1; i <= MAX_FLOORS; i++) { if (scheduler->elevator.up_requests[i]) {
printf(“%d “, i);
}
}
printf(“\n下行请求: “);
for (int i = 1; i <= MAX_FLOORS; i++) { if (scheduler->elevator.down_requests[i]) {
printf(“%d “, i);
}
}
printf(“\n”);
}

// SCAN测试函数
void test_scan() {
SCANScheduler scheduler;
init_scan(&scheduler);

// 模拟一系列请求
scan_add_request(&scheduler, 1, 10);
scan_add_request(&scheduler, 5, 15);
scan_add_request(&scheduler, 3, 8);
scan_add_request(&scheduler, 12, 2);

printf(“\n=== SCAN算法执行过程 ===\n”);

int step = 0;
while (scheduler.total_requests > 0 && step < 20) { scan_print_state(&scheduler); int next = scan_get_next_floor(&scheduler); if (next != -1) { scan_move(&scheduler, next); scheduler.total_requests--; } else { break; } step++; printf("---\n"); } } 2.3 SCAN算法优化分析优点：响应时间较短，电梯移动有方向性避免了电梯”来回跑”的问题实现相对简单，效率较高缺点：可能导致边缘楼层的请求等待时间过长在请求分布不均匀时，效率可能下降优化方向： LOOK算法：在SCAN基础上，当检测到前方没有请求时立即改变方向电梯容量限制：考虑电梯内乘客数量紧急请求优先：处理紧急情况三、多线程同步问题解决 3.1 多线程环境下的挑战在实际的电梯系统中，多个线程会同时：产生请求（乘客按下按钮）处理请求（电梯调度器）更新状态（电梯移动）这会导致竞态条件（Race Condition）和数据不一致问题。 3.2 使用互斥锁（Mutex）的解决方案 #include #include
#include
#include

// 线程安全的电梯调度器
typedef struct {
SCANScheduler scheduler;
pthread_mutex_t lock; // 互斥锁
pthread_cond_t cond; // 条件变量
bool running; // 运行标志
} ThreadSafeElevator;

// 初始化线程安全的电梯
void init_thread_safe_elevator(ThreadSafeElevator *elevator) {
init_scan(&elevator->scheduler);
pthread_mutex_init(&elevator->lock, NULL);
pthread_cond_init(&elevator->cond, NULL);
elevator->running = true;
}

// 添加请求（线程安全）
void safe_add_request(ThreadSafeElevator *elevator, int from, int to) {
pthread_mutex_lock(&elevator->lock);

scan_add_request(&elevator->scheduler, from, to);
pthread_cond_signal(&elevator->cond); // 通知调度线程

pthread_mutex_unlock(&elevator->lock);
}

// 调度线程函数
void* scheduler_thread(void* arg) {
ThreadSafeElevator *elevator = (ThreadSafeElevator*)arg;

while (elevator->running) {
pthread_mutex_lock(&elevator->lock);

// 等待请求或运行标志变化
while (elevator->scheduler.total_requests == 0 && elevator->running) {
pthread_cond_wait(&elevator->cond, &elevator->lock);
}

if (!elevator->running) {
pthread_mutex_unlock(&elevator->lock);
break;
}

// 处理请求
int next = scan_get_next_floor(&elevator->scheduler);
if (next != -1) {
scan_move(&elevator->scheduler, next);
elevator->scheduler.total_requests–;
}

pthread_mutex_unlock(&eolver->lock);
usleep(500000); // 模拟移动时间
}

return NULL;
}

// 请求生成线程函数
void* request_generator_thread(void* arg) {
ThreadSafeElevator *elevator = (ThreadSafeElevator*)arg;

// 模拟生成请求
int requests[][2] = {
{1, 10}, {5, 15}, {3, 8}, {12, 2}, {7, 18},
{2, 9}, {14, 1}, {6, 16}, {9, 3}, {11, 7}
};
int num_requests = sizeof(requests) / sizeof(requests[0]);

for (int i = 0; i < num_requests; i++) { safe_add_request(elevator, requests[i][0], requests[i][1]); printf("线程生成请求: %d -> %d\n”, requests[i][0], requests[i][1]);
sleep(1); // 每秒生成一个请求
}

return NULL;
}

// 多线程测试函数
void test_multithreaded_elevator() {
ThreadSafeElevator elevator;
init_thread_safe_elevator(&elevator);

pthread_t scheduler_tid, generator_tid;

printf(“=== 多线程电梯调度测试 ===\n”);

// 创建调度线程
if (pthread_create(&scheduler_tid, NULL, scheduler_thread, &elevator) != 0) {
perror(“创建调度线程失败”);
return;
}

// 创建请求生成线程
if (pthread_create(&generator_tid, NULL, request_generator_thread, &elevator) != 0) {
perror(“创建请求生成线程失败”);
return;
}

// 等待请求生成完成
pthread_join(generator_tid, NULL);

// 等待所有请求处理完成
sleep(2);
elevator.running = false;
pthread_cond_signal(&elevator.cond); // 唤醒调度线程
pthread_join(scheduler_tid, NULL);

// 清理资源
pthread_mutex_destroy(&elevator.lock);
pthread_cond_destroy(&elevator.cond);

printf(“多线程测试完成\n”);
}
3.3 读写锁（Read-Write Lock）优化
对于读多写少的场景，可以使用读写锁进一步提升性能：
#include

typedef struct {
SCANScheduler scheduler;
pthread_rwlock_t rwlock; // 读写锁
bool running;
} RWLockElevator;

// 读操作：获取状态（允许多个线程同时读）
void rwlock_print_state(RWLockElevator *elevator) {
pthread_rwlock_rdlock(&elevator->rwlock);
scan_print_state(&elevator->scheduler);
pthread_rwlock_unlock(&elevator->rwlock);
}

// 写操作：添加请求（独占锁）
void rwlock_add_request(RWLockElevator *elevator, int from, int to) {
pthread_rwlock_wrlock(&elevator->rwlock);
scan_add_request(&elevator->scheduler, from, to);
pthread_rwlock_unlock(&elevator->rwlock);
}
3.4 无锁编程（Lock-Free）高级方案
对于高性能场景，可以使用原子操作和CAS（Compare-And-Swap）实现无锁队列：
#include

// 简化的无锁请求队列
typedef struct {
atomic_int head;
atomic_int tail;
Request buffer[MAX_REQUESTS];
} LockFreeQueue;

// 无锁入队
bool lf_enqueue(LockFreeQueue *queue, Request req) {
int old_tail, new_tail;
do {
old_tail = atomic_load(&queue->tail);
new_tail = (old_tail + 1) % MAX_REQUESTS;
if (new_tail == atomic_load(&queue->head)) {
return false; // 队列满
}
} while (!atomic_compare_exchange_weak(&queue->tail, &old_tail, new_tail));

queue->buffer[old_tail] = req;
return true;
}
四、完整测试与性能分析
4.1 综合测试框架
// 综合测试函数
void run_comprehensive_test() {
printf(“========== 电梯调度算法综合测试 ==========\n\n”);

// 1. FCFS测试
printf(“1. FCFS算法测试:\n”);
test_fcfs();
printf(“\n”);

// 2. SCAN算法测试
printf(“2. SCAN算法测试:\n”);
test_scan();
printf(“\n”);

// 3. 多线程测试
printf(“3. 多线程同步测试:\n”);
test_multithreaded_elevator();
printf(“\n”);

printf(“========== 所有测试完成 ==========\n”);
}

// 性能对比函数
void performance_comparison() {
printf(“\n========== 性能对比分析 ==========\n”);
printf(“算法 | 平均响应时间 | 吞吐量 | 实现复杂度\n”);
printf(“—–|————–|——–|———-\n”);
printf(“FCFS | 长 | 低 | 简单\n”);
printf(“SCAN | 中等 | 中等 | 中等\n”);
printf(“LOOK | 短 | 高 | 中等\n”);
printf(“多线程SCAN | 短 | 很高 | 复杂\n”);
}

// 主函数
int main() {
run_comprehensive_test();
performance_comparison();
return 0;
}
4.2 编译与运行指南
# 保存为 elevator.c
# 编译（需要链接pthread库）
gcc -o elevator elevator.c -lpthread

# 运行
./elevator
0.4.3 性能优化建议
内存优化
：使用位图代替布尔数组，节省内存
算法优化
：实现LOOK算法，提前改变方向
并发优化
：使用线程池处理请求
实时性
：使用实时调度策略（SCHED_FIFO）
五、总结与扩展
本文详细介绍了电梯调度算法从FCFS到SCAN的演进过程，并解决了多线程同步的关键问题。核心要点：
FCFS
：简单但效率低，适合低负载场景
SCAN
：方向性强，效率适中，是实际应用的基础
多线程同步
：必须使用互斥锁保护共享数据
性能优化
：根据场景选择合适的锁机制
扩展方向
：
实现LOOK算法
添加电梯容量限制
支持紧急请求优先级
使用状态机优化实现
分布式电梯系统调度
通过本文的代码实现和详细解释，读者应该能够独立实现一个完整的电梯调度系统，并处理多线程环境下的同步问题。
# 电梯调度算法C语言实现详解从FCFS到SCAN策略优化与多线程同步问题解决指南
引言：电梯调度算法的核心挑战
电梯调度算法是操作系统进程调度和现实工程应用中的经典问题。它不仅考验算法的效率，还涉及多线程同步、资源竞争和用户体验优化。在现代高楼大厦中，电梯系统每天处理成千上万的请求，一个优秀的调度算法能显著减少乘客等待时间，提升整体运行效率。
本文将从最基础的
先来先服务（FCFS）
算法开始，逐步深入到
扫描算法（SCAN）
的优化实现，最后探讨
多线程环境下的同步问题
。我们将使用C语言进行完整实现，并提供详细的代码注释和测试案例，帮助读者彻底掌握电梯调度算法的精髓。
一、基础算法：先来先服务（FCFS）
1.1 FCFS算法原理
FCFS（First-Come, First-Served）是最简单的调度策略，按照请求到达的顺序依次处理。这种算法实现简单，但效率较低，容易产生”饥饿”现象。
核心思想
：维护一个请求队列，每次取出队首的请求进行服务。
1.2 C语言实现
#include
#include
#include