“操作系统”课程中进程同步互斥教学研究

金海东　徐云龙

摘要:“操作系统”是计算机专业的核心课程之一。由于涉及的学科多、知识点多、课程内容难理解等,该课程的教与学一直是学科难点。成人教育学生普遍起点较低,对纯理论性知识不太乐于接受。本文以该课程的一个核心知识点——进程同步与互斥为实例,探讨如何从学习者的角度设计循序渐进的教学内容,并通过编写程序验证书本理论,提高成教学生的兴趣和实践能力。

关键词:进程;同步;互斥;信号量;多线程

中图分类号:G642 文献标识码:B

计算机专业中,“操作系统”课程非常重要。操作系统直接高效地管理着计算机的各种软硬件资源,为用户提供使用接口。操作系统是最复杂的系统软件,涉及了程序设计语言、计算机系统结构/硬件、软件设计、网络、算法等。由于该课程内容多而杂,普通高校学生特别是成人教育学生学习比较困难。传统教学方式下,只给学生讲解操作系统原理,学生感到抽象、难懂,近些年来,很多高校加大实验(实践)教学力度,在讲授理论的同时,加入操作系统内核代码分析,如一些学校让学生分析Linux内核。但这势必加大教学工作量,教师无法在五六十学时内完成课程教学。

为了既让学生深入掌握理论知识,又能通过编码验证理论,本文根据实际教学经验,结合普通高校学生学习该课程的状况,以进程同步互斥为例,从以下四个方面讨论如何循序渐进地展开教学。

1 “进程同步与互斥”的引入

教学中,首先带领学生回忆在DOS环境下的C语言编程,使学生明白什么是单道程序环境。然后就提高系统的利用率,提出了程序并发执行的载体——进程。程序并发执行时,涉及到相同资源会引起一些问题,但抽象的理论并不利于学生的深入理解,笔者设计了一个银行存取款问题的案例:

某一银行账户M,尚有存款100元;用户P、Q同时对该账户进行操作,可能会导致数据不一致,操作过程如图1所示:

① 时间T2>T1>T0;

② T0时刻,p0操作读出Mp0=100;

③ T0时刻,q0操作读出Mq0=100;

④ T1时刻,p1操作写入数据:存款100,M=Mp0+ 100=200;Q未能获得更新后的数据;

⑤ T2时刻,q1操作写入数据:存款100,M=Mq0+ 100=200;

应该是300元的账户余额,由于操作的并发执行,造成只有200元余额。通过这一具体、直观的例子,让学生明白并发执行与顺序执行有很多不一样的地方,即并发环境中的共享资源,不能同时访问,只可互斥访问。然后带领学生学习并发操作的Bernstein条件、临界资源等知识。

2信号量描述

怎样才能做到在某一时刻,只有一个进程访问该资源呢,这就是临界资源的管理方法。在介绍了部分不成熟的管理方案后,引入Dijkstra提出的信号量和P、V操作机制。

(1) 信号量定义

信号量是进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值。进程使用P、V两个原语操作发送和接受信号,如信号没有送到,进程被挂起,直到信号到达。

信号量按其用途可分为:用于进程互斥访问临界资源的公用信号量;用于进程同步时协调相互关系的私有信号量。

信号量按其取值可分为:整型信号量、可用资源数目的记录型信号量。

(2)P、V操作定义描述

信号量结构中需要一个整型计数和一个等待对象。

P操作表示现行进程向系统申请资源,将信号量值减1,如结果小于0,则调用进程被置成等待信号量的状态。

V操作表示现行进程释放该类资源,信号量值加1,系统可用资源数也增加一个,如果s.value≤0,等待队列中有等待进程,则唤醒其中一个。

信号量定义,PV操作算法C语言描述如下:

typedef struct {

int value; //信号量值

QueueType waitQueue; //等待队列

} semaphore;

void P(semaphore s){

--s.value;

if (s.value<0){

阻塞调用进程;

进程进入等待队列s. waitQueue;

}

}

void V(semaphores){

++s.value;

if(s.value<=0){

从等待队列s. waitQueue中取出一个进程;

将该进程入就绪队列;

}

}

(3) 关于信号量与PV操作的几个结论

结论1:若信号量s为正值,则该值等于在封锁进程之前对信号量s可施行的P操作数,亦等于s所代表的实际还可以使用的物理资源数。

结论2:若信号量s为负值,则其绝对值等于排列在该信号量s队列中等待的进程个数,亦等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数。

结论3:PV操作一定要成对使用。

(4) 进程中信号量操作模型

通过对临界区访问过程的分析,信号量机制中P原语相当于进入临界区操作,V原语相当于退出临界区操作。用P、V原语实现进程互斥就是将临界区置于P和V两个原语操作之间。

示例算法如下:

void ProcessExecute( 参数列表 ){

……

P(s);//进入区

临界区;

V(s); //退出区

…… //剩余区

}

3进程同步与互斥算法编写过程

初学者能够看懂他人编写的进程同步互斥算法,但是自己动手编写很困难。学生在写该类算法时,总想一次完成,但是很多时候写不好;或者不知道如何解决该类问题。针对这一现象,笔者分析了算法编写过程,给学生总结了分析问题、解决问题的步骤:

(1) 找出问题中的执行进程,再描述其余各进程的执行过程。

以“多生产者——多消费者——多缓冲”问题为例,通过分析就会发现,该问题中生产者、消费者各是一类进程。执行过程为:

生产者的执行过程:

请求生产指标;

请求缓冲区使用权;

生产;

归还缓冲区使用权;

消费者过程:

请求消费指标;

请求缓冲区使用权;

消费;

归还缓冲区使用权;

(2) 分析进程中的同步、互斥关系,设置信号量。

本问题中缓冲区是临界资源,需要互斥访问。“生产指标”就是空白缓冲区数目,每减少一个,产品就增加一个,“消费指标”就增加一个。每消费一个产品,空白缓冲区就增加一个,产品就减少一个。

用mutex信号量来保证对缓冲区的互斥访问,emptyBufferCount记录空白缓冲区数目,fullBufferCount记录产品数目。

(3) 利用PV操作写出同步互斥关系。用算法替换前面描述的执行过程。

生产者进程Producer:

P(mutex);//申请使用缓冲区, ①

P(emptyBufferCount); //生产许可申请, ②

生产

V(mutex); //离开,释放!PV操作成对使用

V(emptyBufferCount);//⑤

消费者进程Consumer:

P(mutex); //申请使用缓冲区, ③

P(fullBufferCount); //消费许可申请,消费 ④

V(mutex); //离开,释放

V(fullBufferCount); // ⑥

(4) 选择并确定信号量的初值。

整型信号量mutex初值为1,记录型信号量emptyBufferCount初值为缓冲区大小。

(5) 给出几个进程,人工模拟算法执行,检测算法并改正错误。

用一个生产者、一个消费者模拟进程执行,发现emptyBufferCount的PV操作②⑤,fullBufferCount的PV操作③⑥,在同一个进程中,不能发挥同步作用,所以⑤⑥位置互换。

互换后,如果生产者进程先一步执行,算法没有问题。如果消费者先一步执行,就会被阻塞,由于生产者不能生产,产生死锁。因此生产者进程中①②位置互换,消费者进程中③④互换,即一般情况同步信号量在前,互斥信号量在后。改正后再测试,算法无误。

4生产者消费者的多线程仿真

“操作系统”的课程实验旨在加深学生对理论的理解。很多高校“操作系统”实验基于Unix/Linux平台,学习该

系统会对学生来说是很大负担。笔者在课程实验中,选择学生更为熟悉也更容易使用的Windows平台和VC++6.0开发环境,用线程模拟生产者消费者问题。这样学生既容易上手编程,又能通过编程切实理解进程的同步与互斥理论。学生以调试该程序入手,独立完成哲学家进餐问题的模拟。生产者消费者问题的线程函数原型如下:

DWORD WINAPI ProducerThread(LPVOID lpvThreadParm) { //生产者线程函数

BOOL fHasDone=FALSE;

while(!fHasDone){

EnterCriticalSection

(&g_CriticalSection);

//进入临界区函数

if(producerRunTimes>=MAX_RUN_TIMES){

fHasDone=TRUE;

}else{

g_Buffer[in]=rand();

in=(in+1)%BUFFER_SIZE;

//循环队列

producerRunTimes++;

//线程执行次数计数,防止死循环

}

LeaveCriticalSection

(&g_CriticalSection);

//退出临界区函数

}

return 0;

}

DWORD WINAPI ConsumerThread(LPVOID lpvThreadParm)

{ //消费者线程函数

BOOL fHasDone=FALSE;

while(!fHasDone){

EnterCriticalSection (&g_CriticalSection);

if(consumerRunTimes>= MAX_RUN_TIMES){

fHasDone=TRUE;

}else{

g_Buffer[out]=rand();

out=(out+1)% BUFFER_SIZE;

consumerRunTimes++;

}

LeaveCriticalSection

(&g_CriticalSection);

}

return 0;

}

在上述程序中除掉同步互斥部分,学生就能实际理解图1中银行账户存款例子。多线程仿真实验不但能让学生深入理解进程同步互斥的理论和实现,还让学生学会和理解了多线程的编程。

5结论

在“操作系统”课程中,笔者将知识点理清脉络,并围绕操作系统的五大管理功能展开教学。介绍操作系统的每个功能时,以知识点的内在特性为线索,连接看似不相关的知识。如在进程管理时,以单机环境下的程序执行为切入点,描述在多道程序中,每道程序模拟单机运行环境,需要完成哪些工作;为了多道程序的协调工作,如何进行同步和互斥;为了让每个进程都能有机会运行,如何确定进程调度原则。特别是在介绍进程同步与互斥时,实例结合理论,由浅入深,以“银行账户操作”实例让学生明白并发操作与顺序执行的不同之处,随后提出操作系统中常用的并发处理方法——信号量机制。并就学生的学习难点——并发互斥操作的算法编写,给出问题的解决步骤。在实验中,用Windows多线程验证课堂所学知识,学生既方便上手编程,又容易理解理论。

本教学方案充分照顾到了成教学生的实际基础,调动了学生的积极性,设计的多线程实验也使学生有能力实际动手参与。在本校教学中,笔者采用该方案后,学生对教学内容非常感兴趣,也很容易接受理论性的知识。笔者在实际教学中,也发现一些问题,如该方案对学生的主动性要求较高,并要求学生有一定的编程能力,这不在本文探讨范围。

参考文献:

[1] 汤小丹,梁红兵,哲凤屏,等. 计算机操作系统(修订版)[M]. 西安:西安电子科技大学出版社,2003.

[2] 孙仲秀,费翔林,骆斌. 操作系统教程[M]. 北京:高等教育出版社, 2008.

[3] William Stallings. 操作系统——精髓与设计原理[M]. 5版. 北京:电子工业出版社,2006.

[4] 陈向群,杨芙清. 操作系统教程[M]. 2版. 北京:北京大学出版社,2006.

[5] 孟静. 操作系统教程-原理和实例分析[M]. 2版. 北京:高等教育出版社,2006.

[6] 杨燕. 操作系统课程双语教学的探讨[J]. 北京大学学报:哲学社会科学版,2007(S2):174-175.

[7] 张坤.“操作系统”课程的教学方法研究[J]. 高等工程教育研究,2007(S1):151-152.

[8] 郝继升. 计算机操作系统原理课程的教学探索[J]. 教育与职业,2007(8):99-101.

[9] Jeffrey Richter. Windows高级编程指南[M]. 北京:清华大学出版社,1999.