操作系统课程设计实战：五大核心算法详解与C语言实现-深圳市維司達科技有限公司

引言

操作系统是计算机系统的核心，理解其底层原理对于软件工程师至关重要。理论学习往往抽象，而动手实践则是将知识内化的最佳途径。本文将基于一份完整的《操作系统课程设计报告》，深入剖析其中五个核心实验的实现细节，包括动态优先权进程调度、银行家算法、生产者-消费者同步、动态分区分配以及页面置换算法。我们将聚焦于每个实验的核心逻辑与C语言代码片段，并分享从调试到成功运行的心得体会，为读者提供一份可参考的实践指南。

实验一：动态优先权进程调度

实验原理

本实验模拟了基于动态优先级的进程调度算法。每个进程用一个进程控制块（PCB）表示，包含进程名、优先级、所需总运行时间、已运行时间及状态（就绪W、运行R、完成F）。调度规则为：每个时间片将CPU分配给就绪队列中优先级最高的进程；运行一个时间片后，若进程未完成，则其优先级减1并重新放回就绪队列尾部，以此实现动态优先级调整，平衡长短作业。

核心数据结构与代码片段

typedefstruct{charname[10];intprio;// 优先数越大优先级越高intneed_time;// 需要总运行时间片intused_time;// 已占用CPU时间片charstate;// W就绪 / R运行 / F完成}PCB;// 查找就绪队列中优先级最高的进程下标intgetMaxPrioPos(){if(rear==0)return-1;intmaxPos=0;for(inti=0;i<rear;i++){intcur=readyQueue[i];intmaxIdx=readyQueue[maxPos];if(proc[cur].prio>proc[maxIdx].prio){maxPos=i;}}returnmaxPos;}// 调度循环核心逻辑while(!allDone()){intmaxPos=getMaxPrioPos();if(maxPos==-1)break;intrunIdx=readyQueue[maxPos];delQueue(maxPos);// 移出就绪队列proc[runIdx].state='R';// 运行一个时间片proc[runIdx].used_time+=1;if(proc[runIdx].used_time==proc[runIdx].need_time){proc[runIdx].state='F';// 完成}else{proc[runIdx].prio-=1;// 动态降低优先级proc[runIdx].state='W';enQueue(runIdx);// 重新入队}timeSlice++;}

实验心得

通过亲手实现PCB结构体和调度循环，我深刻理解了操作系统如何通过就绪队列管理进程状态。调试中发现，优先级比较逻辑和进程状态切换的时机是易错点。例如，必须在进程移出队列后再打印就绪队列，否则会出现“当前运行进程仍在队列中”的逻辑错误。实验让我认识到，调度算法的细微差别会显著影响进程执行顺序。

实验二：银行家算法

实验原理

银行家算法用于避免死锁，通过预判资源分配后系统是否处于安全状态来决定是否满足进程的请求。核心数据结构包括：Available（可用资源）、Max（最大需求）、Allocation（已分配）、Need（还需要）。算法步骤为：1) 检查请求是否小于等于Need和Available；2) 尝试分配；3) 执行安全性检查算法；4) 安全则正式分配，否则回滚。

安全性检查算法核心代码

intSafe(){memcpy(Work,Available,sizeof(Work));memset(Finish,0,sizeof(Finish));intcnt=0;intseq[PROC_NUM],seq_idx=0;while(1){intfind=0;for(inti=0;i<PROC_NUM;i++){if(!Finish[i]){intok=1;// 检查 Need[i] <= Workfor(intj=0;j<RES_NUM;j++){if(Need[i][j]>Work[j]){ok=0;break;}}if(ok){// 找到可分配进程for(intj=0;j<RES_NUM;j++){Work[j]+=Allocation[i][j];}Finish[i]=1;seq[seq_idx++]=i;// 记录安全序列cnt++;find=1;}}}if(!find)break;}// 判断是否所有进程都能完成if(cnt==PROC_NUM){printf("系统处于安全状态，安全序列为：");for(inti=0;i<seq_idx;i++)printf("P%d ",seq[i]);printf("\n");return1;// 安全}else{printf("系统处于不安全状态，拒绝分配！\n");return0;// 不安全}}

实验心得

试分配与回滚机制是本实验的关键。最初编码时，我忘记在安全性检查前用memcpy备份资源矩阵，导致检测不通过后系统状态被永久破坏。修复后，程序能正确拒绝如P2请求(1,2,2,2)这类会导致不安全的分配请求。这让我体会到，系统安全性的保障依赖于对共享资源状态的原子性操作和可回滚设计。

实验三：生产者-消费者问题（进程同步）

实验原理

该实验使用POSIX信号量模拟经典的同步问题。设置三个信号量：sem_empty（空缓冲区数，初值为缓冲区大小）、sem_full（满缓冲区数，初值为0）、sem_mutex（互斥锁，初值为1）。生产者等待sem_empty，然后获取sem_mutex进行生产，之后释放sem_mutex并增加sem_full。消费者行为与之对称。

核心线程函数代码片段

sem_tsem_empty,sem_full,sem_mutex;intbuffer[BUF_SIZE],in_idx=0,out_idx=0;void*producer_task(void*arg){while(!should_exit){sem_wait(&sem_empty);// P(empty)sem_wait(&sem_mutex);// P(mutex)// 生产物品放入buffer[in_idx]buffer[in_idx]=product_id++;in_idx=(in_idx+1)%BUF_SIZE;sem_post(&sem_mutex);// V(mutex)sem_post(&sem_full);// V(full)usleep(production_interval);}returnNULL;}void*consumer_task(void*arg){while(!should_exit){sem_wait(&sem_full);// P(full)sem_wait(&sem_mutex);// P(mutex)// 从buffer[out_idx]消费物品intitem=buffer[out_idx];out_idx=(out_idx+1)%BUF_SIZE;sem_post(&sem_mutex);// V(mutex)sem_post(&sem_empty);// V(empty)usleep(consumption_interval);}returnNULL;}

实验心得

P操作顺序至关重要。我曾错误地将sem_wait(&sem_mutex)放在sem_wait(&sem_empty)之前，这可能导致死锁（例如，生产者持有互斥锁但缓冲区已满，消费者无法进入临界区释放缓冲区）。正确的顺序（先同步信号量，后互斥锁）是保证并发程序正确性的基石。此外，为线程安全退出设计全局标志位和安全的信号量等待函数，也是本次实验的重要收获。

实验四：动态分区分配算法

实验原理

模拟连续内存管理，实现首次适应（First Fit）和最佳适应（Best Fit）算法。使用一个空闲分区链表，每个节点记录分区起始地址、大小和状态。分配时，首次适应从链表头开始找第一个足够大的分区；最佳适应则遍历链表找大小最匹配的分区。回收内存时，需考虑与相邻空闲分区合并的四种情况。

首次适应算法分配核心逻辑

// 空闲分区结构体structfree_block{intstart_addr;intsize;intstatus;// 0:空闲， 1:已分配structfree_block*next;};structfree_block*first_fit(intrequest_size){structfree_block*p=head;while(p!=NULL){if(p->status==0&&p->size>=request_size){// 找到可用的空闲块if(p->size-request_size<=MIN_SIZE){// 剩余空间太小，全部分配p->status=1;}else{// 分割空闲块structfree_block*new_block=(structfree_block*)malloc(sizeof(structfree_block));new_block->start_addr=p->start_addr+request_size;new_block->size=p->size-request_size;new_block->status=0;new_block->next=p->next;p->next=new_block;p->size=request_size;p->status=1;}returnp;// 返回分配的分区}p=p->next;}returnNULL;// 分配失败}

实验心得

内存碎片是动态分区分配的核心问题。首次适应算法简单快速，但容易在低地址产生大量外部碎片；最佳适应算法虽能减少外部碎片，但会产生难以利用的微小内部碎片。在实现回收函数时，与相邻空闲分区的合并逻辑是调试难点，需要仔细处理前合并、后合并、前后都合并、不合并四种情况。通过对比同一申请序列下两种算法的分配结果，能直观感受到算法选择对内存利用率的影响。

实验五：页面置换算法

实验原理

在请求分页存储管理中，当访问的页面不在内存中时会发生缺页中断，此时需要从外存调入新页面。如果内存已满，则需根据特定算法选择一个旧页面置换出去。本实验模拟了三种经典算法：

FIFO（先进先出）：淘汰最早进入内存的页面。
LRU（最近最久未使用）：淘汰最长时间没有被访问的页面。
OPT（最佳置换）：淘汰未来最长时间内不再被访问的页面（理论最优，无法实际实现）。

LRU算法模拟核心代码片段

// 使用时间戳实现LRUintlru_replace(intpage_seq[],intseq_len,intframe_num){intframes[frame_num];intlast_used[frame_num];// 记录页面最近一次被访问的时间inttime=0;intpage_fault=0;for(inti=0;i<frame_num;i++){frames[i]=-1;// -1表示空帧last_used[i]=-1;}for(inti=0;i<seq_len;i++){intpage=page_seq[i];intfound=0;// 检查页面是否已在内存中for(intj=0;j<frame_num;j++){if(frames[j]==page){found=1;last_used[j]=time++;// 更新访问时间break;}}if(!found){page_fault++;// 寻找空闲帧intempty_idx=-1;for(intj=0;j<frame_num;j++){if(frames[j]==-1){empty_idx=j;break;}}if(empty_idx!=-1){// 有空闲帧，直接放入frames[empty_idx]=page;last_used[empty_idx]=time++;}else{// 无空闲帧，需置换：找到最近最久未使用的页面intlru_idx=0;for(intj=1;j<frame_num;j++){if(last_used[j]<last_used[lru_idx]){lru_idx=j;}}frames[lru_idx]=page;last_used[lru_idx]=time++;}}}returnpage_fault;}

实验心得

通过运行标准的页面访问序列并计算缺页率，可以量化比较三种算法的性能：OPT ≤ LRU ≤ FIFO。FIFO实现简单，但会出现Belady异常（增加物理块数，缺页率反而可能升高）。LRU是实际系统中常用的近似算法，但其精确实现开销较大，通常需要硬件支持（如访问位）。OPT算法虽然性能最好，但需要预知未来的页面访问序列，仅用于理论研究和性能比较的上界。这个实验让我深刻理解了局部性原理在虚拟存储管理中的重要性。