2026年进程同步与通信作业习题与答案

2026年进程同步与通信作业习题与答案1.简述记录型信号量与整型信号量的核心差异，并说明记录型信号量如何解决“忙等”问题。答案：整型信号量仅允许信号量值为非负整数，其P操作（wait）实现为“while(s≤0);s--;”，若s≤0则进程持续循环检查，导致“忙等”。记录型信号量引入进程阻塞队列，其数据结构包含信号量值s和等待该信号量的进程队列L。P操作实现为：若s>0则s--并继续执行；若s≤0则将当前进程状态置为阻塞，加入L队列并调用调度程序切换进程。V操作（signal）中，若s+1≤0（说明队列L非空），则唤醒L中的一个进程。通过阻塞替代循环等待，记录型信号量彻底消除了“忙等”。2.假设有4个进程P1-P4共享某临界资源，系统采用信号量mutex（初值1）实现互斥。若P1执行P(mutex)后进入临界区，此时P2、P3、P4依次执行P(mutex)，请描述各进程的状态变化及信号量值的演变过程。答案：初始mutex=1。P1执行P(mutex)，mutex减为0，P1进入临界区。P2执行P(mutex)时，mutex=0≤0，P2被阻塞并加入mutex的等待队列，mutex值保持0。P3执行P(mutex)时，同样因mutex=0被阻塞，加入队列（队列顺序P2→P3）。P4执行P(mutex)时，同理阻塞，队列变为P2→P3→P4。此时mutex值仍为0，P1在临界区，P2-P4均处于阻塞状态。当P1退出临界区执行V(mutex)时，mutex增为1，检查到等待队列非空（存在P2），唤醒P2；P2被唤醒后获取mutex（mutex减为0），进入临界区，此时队列剩余P3→P4。二、经典同步问题变种3.某系统有2个A类生产者（PA1、PA2）、3个B类生产者（PB1-PB3）、4个A类消费者（CA1-CA4）、5个B类消费者（CB1-CB5）。A类生产者仅生产类型A产品，B类生产者仅生产类型B产品；A类消费者仅消费A产品，B类消费者仅消费B产品。共享缓冲区总容量为15，其中A产品最多存放8个，B产品最多存放7个（两类产品存放位置独立）。要求用记录型信号量实现该场景的同步，给出信号量定义并写出生产者、消费者的伪代码逻辑。答案：信号量定义：mutexA：A产品缓冲区互斥访问，初值1；mutexB：B产品缓冲区互斥访问，初值1；emptyA：A缓冲区剩余容量，初值8；emptyB：B缓冲区剩余容量，初值7；fullA：A缓冲区已存数量，初值0；fullB：B缓冲区已存数量，初值0。A类生产者PA伪代码：while(true){生产一个A产品；P(emptyA);//等待A缓冲区有空位P(mutexA);//互斥访问A缓冲区将产品放入A缓冲区；V(mutexA);//释放互斥V(fullA);//通知A消费者有产品}B类生产者PB伪代码：while(true){生产一个B产品；P(emptyB);//等待B缓冲区有空位P(mutexB);//互斥访问B缓冲区将产品放入B缓冲区；V(mutexB);//释放互斥V(fullB);//通知B消费者有产品}A类消费者CA伪代码：while(true){P(fullA);//等待A缓冲区有产品P(mutexA);//互斥访问A缓冲区从A缓冲区取出一个产品；V(mutexA);//释放互斥V(emptyA);//通知A生产者有空位消费A产品；}B类消费者CB伪代码逻辑与CA类似，将信号量替换为emptyB、fullB、mutexB即可。关键点：通过emptyA/emptyB限制两类产品的最大存放量，避免混合存放导致的容量冲突；mutexA/mutexB确保同一类产品缓冲区的互斥访问；fullA/fullB分别通知对应消费者可取用。4.考虑读者-写者问题的“写者优先”变种：当写者申请写操作时，后续到达的读者必须等待，直到所有当前写者完成且无新写者等待。请用信号量设计该同步机制，要求写出信号量定义、读者与写者的伪代码，并分析如何实现“写者优先”。答案：信号量定义：rw_mutex：读写互斥信号量，初值1（写者使用）；read_count_mutex：读者计数互斥信号量，初值1；write_wait_mutex：写者等待标记信号量，初值1（用于标记是否有写者等待）；read_wait：读者等待信号量，初值0（当有写者等待时，读者在此阻塞）；write_count：写者计数，初始0（需配合互斥信号量保护，此处简化为用write_wait_mutex互斥）。读者伪代码：while(true){P(write_wait_mutex);//检查是否有写者等待if(write_count>0){//存在写者等待，读者需等待V(write_wait_mutex);P(read_wait);//阻塞在读者等待队列}else{V(write_wait_mutex);}P(read_count_mutex);//互斥修改读者计数read_count++;if(read_count==1){//第一个读者需获取rw_mutexP(rw_mutex);}V(read_count_mutex);//执行读操作P(read_count_mutex);read_count--;if(read_count==0){//最后一个读者释放rw_mutexV(rw_mutex);}V(read_count_mutex);}写者伪代码：while(true){P(write_wait_mutex);//互斥修改写者计数write_count++;//标记有写者等待V(write_wait_mutex);P(rw_mutex);//等待获取写权限（若被读者占用则阻塞）P(write_wait_mutex);write_count--;//写者开始执行，减少等待计数if(write_count>0){//仍有写者等待，唤醒下一个写者（此处需结合其他机制，简化处理）V(rw_mutex);//立即释放，让后续写者获取}else{V(write_wait_mutex);//执行写操作V(rw_mutex);//写完成后释放}}实现“写者优先”的关键：当写者申请时，通过write_count标记存在等待的写者，后续读者在检查到write_count>0时会阻塞在read_wait，直到所有写者完成且write_count=0。写者通过直接竞争rw_mutex，若当前有读者在读，写者会阻塞在P(rw_mutex)，但新到达的读者因检测到write_count>0而无法进入，从而优先让写者获取权限。三、管程与消息传递5.简述管程的基本结构，并说明如何用信号量模拟管程的互斥与条件变量机制。答案：管程由四部分组成：局部变量声明、操作这些变量的过程（函数）、初始化代码、条件变量（用于进程同步）。管程的特性是同一时间仅允许一个进程进入管程执行内部过程，其他进程需等待。用信号量模拟管程的步骤：（1）互斥机制：使用一个信号量mutex（初值1），进程进入管程时执行P(mutex)，退出时执行V(mutex)，确保互斥。（2）条件变量：每个条件变量对应一个信号量（如condition_sem）和一个计数器（记录等待该条件的进程数）。当进程在管程内需要等待条件C时，执行：V(mutex);//释放管程互斥P(condition_sem);//阻塞在条件C的信号量P(mutex);//重新获取管程互斥（被唤醒后）当另一进程使条件C满足时，执行：if(condition_count>0){//有进程等待条件CV(condition_sem);//唤醒一个等待进程condition_count--;}6.设计一个基于消息传递的客户-服务器系统，其中客户端发送“计算请求”（包含两个整数a、b和操作符op），服务器接收后返回计算结果（aopb）。要求：（1）用邮箱机制描述通信流程；（2）写出客户端与服务器的伪代码（假设支持send(receiver,msg)、receive(sender,msg)原语）；（3）分析如何处理消息丢失问题。答案：（1）通信流程：服务器启动后创建邮箱（如ServerMailbox），持续监听该邮箱；客户端创建临时邮箱（ClientMailbox），构造包含a、b、op及ClientMailbox标识的消息，发送至ServerMailbox；服务器从ServerMailbox接收消息，解析a、b、op，执行计算（需处理非法操作符等异常），构造包含结果的响应消息，发送至ClientMailbox；客户端从ClientMailbox接收响应消息，获取计算结果。（2）伪代码：服务器端：ServerMailbox=create_mailbox("Server");while(true){receive(Client,request_msg);//从任意客户端接收请求parserequest_msgtogeta,b,op,client_mailbox;if(opisvalid){result=compute(a,b,op);}else{result="ERROR:invalidoperator";}send(client_mailbox,result);//发送结果至客户端临时邮箱}客户端：ClientMailbox=create_mailbox("Client_123");//唯一标识a=5;b=3;op='+';request_msg=(a,b,op,ClientMailbox);send("Server",request_msg);receive(Server,response_msg);//等待服务器响应print("Result:",response_msg);（3）消息丢失处理：客户端设置超时机制：发送请求后启动定时器，若超时未收到响应，重新发送请求（需限制重发次数，避免无限循环）；服务器对请求添加序列号：客户端重发时使用相同序列号，服务器检测重复请求后直接返回缓存结果，避免重复计算；引入确认机制：服务器收到请求后先发送“确认接收”消息，客户端收到确认后再等待结果，若未收到确认则重发请求。四、死锁与同步机制综合7.某系统有进程P1-P3，共享资源R1（2个）、R2（2个）、R3（1个）。当前资源分配情况如下：P1已占用R1=1，R2=1，请求R3=1；P2已占用R1=1，请求R2=1；P3已占用R2=1，请求R1=1；系统剩余资源：R1=0，R2=0，R3=1。（1）画出资源分配图；（2）判断是否存在死锁，说明理由；（3）若存在死锁，提出一种解除死锁的方案。答案：（1）资源分配图：资源节点R1（2实例）：已分配P1(1)、P2(1)，剩余0；R2（2实例）：已分配P1(1)、P3(1)，剩余0；R3（1实例）：剩余1；进程节点P1→R3（请求边）；P2→R2（请求边）；P3→R1（请求边）；分配边：R1→P1、R1→P2；R2→P1、R2→P3。（2）死锁判断：当前剩余资源仅R3=1。P1请求R3，可满足（分配后R3=0），P1执行完成后释放R1=1、R2=1。此时剩余资源R1=1、R2=1。P2请求R2=1，可用R2=1满足，P2执行完成释放R1=1（总剩余R1=2）。P3请求R1=1，可用R1=2满足，P3执行完成释放R2=1。因此系统无死锁，存在安全序列P1→P2→P3。（3）若假设剩余资源R3=0（修改条件），则P1无法获取R3，P2请求R2（无剩余），P3请求R1（无剩余），此时资源分配图存在循环等待（P2→R2→P3→R1→P2