司机与售票员.doc

甘肃政法学院 本科课程设计报告题 目 司机与售票员（信号量操作）计算机科学学_院_计算机科学与技术_专业_2008 级_计本1 _班学 号：_200881010126_姓 名：_王亚彬_指导教师：_何珍祥_成 绩：_ _完成时间：_ _2011 _年 _06_月 目录一、设计思想基于理论3（一）设计要求：3（二）、信号量和PV原语4（三）、进程的同步互斥4（四）利用PV原语实现司机与售票员问题5二、数据结构流程图5（一）、理论分析5（二）、总体设计5三、开发环境6四、程序分析引用到的系统调用8（一）、Semaphore类8（二）、Thread类8(三)、sleep系统调用9（四）wait系统调用10(五)、ReleaseSemaphore调用10(六)、CreateProcess调用10（七）、CreateSemaphore调用11五、运行结果12六、分析总结13七、程序清单13参考文献.15 司机与售票员（信号量操作） 王亚彬 独立完成一、设计思想基于理论掌握信号的使用方法和PV操作的定义，掌握使用PV操作实现进程之间同步和互斥的方法，加深对进程同步互斥概念的理解（一）设计要求：设计程序模拟在公共汽车上，司机和售票员操作的同步。司机：启动车辆，正常行车，到站停车。售票员：上乘客，关车门，售票，开车门，下乘客。用PV操作对其控制。（二）、信号量和PV原语信号量(Semaphore)，有时被称为信号灯，是在多线程环境下使用的一种设施，是可以用来保证两个或多个关键代码段不被并发调用。在进入一个关键代码段之前，线程必须获取一个信号量；一旦该关键代码段完成了，那么该线程必须释放信号量。其它想进入该关键代码段的线程必须等待直到第一个线程释放信号量。为了完成这个过程，需要创建一个信号量VI，然后将Acquire Semaphore VI以及Release Semaphore VI分别放置在每个关键代码段的首末端。确认这些信号量VI引用的是初始创建的信号量。信号量是最早出现的用来解决进程同步与互斥问题的机制， 包括一个称为信号量的变量及对它进行的两个原语操作。每个信号量至少须记录两个信息：信号量的值和等待该信号量的进程队列。对一个信号量变量可以进行两种原语操作：p操作和v操作。p操作和v操作是不可中断的程序段，称为原语。如果将信号量看作共享变量，则pv操作为其临界区，多个进程不能同时执行。由此也可以看到，信号量机制必须有公共内存，不能用于分布式操作系统，这是它最大的弱点。一个信号量只能置一次初值，以后只能对之进行p操作或v操作。其基本思路是用信号量（semaphore）来记录当前可用资源的数量。信号量sem是一整数，sem大于等于零时代表可供并发进程使用的资源实体数，但sem小于零时则表示正在等待使用临界区的进程数。P原语操作的动作是：（1） sem减1；（2） 若sem减1后仍大于或等于零，则进程继续执行；（3） 若sem减1后小于零，则该进程被阻塞后进入与该信号相对应的队列中，然后转进程调度。 V原语操作的动作是：（1） sem加1；（2） 若相加结果大于零，则进程继续执行；（3） 若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。（三）、进程的同步互斥进程的互斥和同步进程同步：主要源于进程合作，是进程间共同完成一项任务时直接发生相互作用的关系。为进程之间的直接制约关系。在多道环境下，这种进程间在执行次序上的协调是必不可少的。如：相互合作的两个进程之间需要在某些确定点协调它们的工作，一个进程到达了该点后，除非另一进程已经完成了某些操作，否则就不得不停下来，等待这些操作的完成。这就是进程间的同步。进程互斥：主要源于资源共享，是进程之间的间接制约关系。在多道系统中，两个进程由于不能同时使用同一临界资源，只能在一个进程使用完了，另一进程才能使用，这种现象称为进程间的互斥。同步的主要特征是：一个进程在某一点上等待另一进程提供信息，两进程之间存在直接制约关系，其表现形式为进程进程。互斥的主要特征是争用资源，两进程间存在间接制约关系，其表现形式是进程资源进程。（四）利用PV原语实现司机与售票员问题设公共汽车上，司机和售票员的活动分别是：司机的活动：启动车辆； 正常行车； 到站停车；售票员的活动： 关车门； 售票； 开车门； 在汽车不断地到站、停车、行驶过程中，这两个活动有什么同步关系？用P、V操作实现它们的同步。 设两个信号量S和C，初值为S0；C0；司机： L1： 正常行车 售票员： L2： 售票到站停车 P（S）V（S） 开车门P（C） 关车门启动开车 V（C）GO TO L1 GO TO L2二、数据结构流程图（一）、理论分析司机与售票员之间必须协调工作。即售票员把车门关好了司机才能开车，所以售票员关门后应该通知司机可以开车；然而只有当汽车停了之后，售票员才能开门让乘客上下车，因此司机停车后应该通知售票员可以售票。因此，对于司机和售票员这两个进程有必要分别设两个私有信号量。 （二）、总体设计 设S1,S2分别为司机和售票员输入和输出的信号量：赋初值为S1=0S2=0P司机 P售票员 正常行车 售票 到站，停车 P(S2)V(S2) 开车门 P(S1) 关车门 离站开车 V(S1) 三、开发环境开发平台：WindowsXP+Visual C+6.0开发语言：VC+建立界面过程如图（1-3）所示 图（1） 图（2） 图(3)四、程序分析引用到的系统调用（一）、Semaphore类限制可同时访问某一资源或资源池的线程数见表（1）。 名称说明Semaphore(Int32, Int32) 初始化 Semaphore 类的新实例，并指定最大并发入口数，还可以选择保留某些入口。 Semaphore(Int32, Int32, String) 初始化 Semaphore 类的新实例，并指定最大并发入口数，还可以选择为调用线程保留某些入口，以及选择指定系统信号量对象的名称。 Semaphore(Int32, Int32, String, Boolean%) 初始化 Semaphore 类的新实例，并指定最大并发入口数，还可以选择为调用线程保留某些入口，选择指定系统信号量对象的名称，以及指定一个变量来接收指示是否创建了新系统信号量的值。 Semaphore(Int32, Int32, String, Boolean%, SemaphoreSecurity) 初始化 Semaphore 类的新实例，并指定最大并发入口数，还可以选择为调用线程保留某些入口，可以选择指定系统信号量对象的名称，指定一个变量来接收指示是否创建了新系统信号量的值，以及指定系统信号量的安全访问控制。 表（1）（二）、Thread类Thread类是创建并控制线程，设置其优先级并获取其状态最为常用的类。他有很多的方法，在这里我们将就比较常用和重要的方法做一下介绍：Thread. Start（）：启动线程的执行；Thread.Suspend（）：挂起线程，或者如果线程已挂起，则不起作用；Thread.Resume（）：继续已挂起的线程；Thread.Interrupt（）：中止处于 Wait或者Sleep或者Join 线程状态的线程；Thread.Join（）：阻塞调用线程，直到某个线程终止时为止Thread.Sleep（）：将当前线程阻塞指定的毫秒数；Thread.Abort（）：以开始终止此线程的过程。如果线程已经在终止，则不能通过Thread.Star（）来启动线程。通过调用Thread.Sleep，Thread.Suspend或者Thread.Join可以暂停/阻塞线程。调用Sleep()和Suspend()方法意味着线程将不再得到CPU时间。这两种暂停线程的方法是有区别的，Sleep()使得线程立即停止执行，但是在调用Suspend()方法之前，公共语言运行时必须到达一个安全点。一个线程不能对另外一个线程调用Sleep()方法，但是可以调用Suspend()方法使得另外一个线程暂停执行。对已经挂起的线程调用Thread.Resume（）方法会使其继续执行。不管使用多少次Suspend()方法来阻塞一个线程，只需一次调用Resume()方法就可以使得线程继续执行。已经终止的和还没有开始执行的线程都不能使用挂起。Thread.Sleep（int x）使线程阻塞x毫秒。只有当该线程是被其他的线程通过调用Thread.Interrupt（）或者Thread.Abort（）方法，才能被唤醒。如果对处于阻塞状态的线程调用Thread.Interrupt（）方法将使线程状态改变，但是会抛出ThreadInterupptedException异常，你可以捕获这个异常并且做出处理，也可以忽略这个异常而让运行时终止线程。在一定的等待时间之内，Thread.Interrupt（）和Thread.Abort（）都可以立即唤醒一个线程。下面我们将说明如何从一个线程中止另外一个线程。在这种情况下，我们可以通过使用Thread.Abort（）方法来永久销毁一个线程，而且将抛出ThreadAbortException异常。使终结的线程可以捕获到异常但是很难控制恢复，仅有的办法是调用Thread.ResetAbort（）来取消刚才的调用，而且只有当这个异常是由于被调用线程引起的异常。因此，A线程可以正确的使用Thread.Abort（）方法作用于B线程，但是B线程却不能调用Thread.ResetAbort（）来取消Thread.Abort（）操作。Thread.Abort（）方法使得系统悄悄的销毁了线程而且不通知用户。一旦实施Thread.Abort（）操作，该线程不能被重新启动。调用了这个方法并不是意味着线程立即销毁，因此为了确定线程是否被销毁，我们可以调用Thread.Join（）来确定其销毁，Thread.Join（）是一个阻塞调用，直到线程的确是终止了才返回。但是有可能一个线程调用Thread.Interrupt（）方法来中止另外一个线程，而这个线程正在等待Thread.Join（）调用的返回。尽可能的不要用Suspend()方法来挂起阻塞线程，因为这样很容易造成死锁。假设你挂起了一个线程，而这个线程的资源是其他线程所需要的，会发生什么后果。因此，我们尽可能的给重要性不同的线程以不同的优先级，用Thread.Priority（）方法来代替使用Thread.Suspend（）方法。Thread类有很多的属性，这些重要的属性是我们多线程编程必须得掌握的。Thread.IsAlive属性：获取一个值，该值指示当前线程的执行状态。如果此线程已启动并且尚未正常终止或中止，则为 true；否则为 false。Thread.Name 属性：获取或设置线程的名称。Thread.Priority 属性：获取或设置个值，该值指示线程的调度优先级。Thread.ThreadState 属性：获取一个值，该值包含当前线程的状态。(三)、sleep系统调用 调用Sleep，可使线程自愿放弃它剩余的时间片。 系统将在大约的指定秒数内使线程不可高度。不错，如果告诉系统，想睡眠100MS，那么可以睡大约这么长的时间，但也也可能睡眠数秒或数分钟。记住，WINDOWS不是个实时操作系统。虽然线程可能在规定的时间被唤醒，但是它能否做到，取决于系统中还有什么操作正在进行。 可以调用Sleep(INFINITE)，告诉系统永远不要调用这个线程。但最好不要这样，让线程退出就行了。反正你都不再需要它。或者调用Sleep(0);告诉系统线程将放弃剩于的时间片，并使系统调度另一个线程。但是，系统可以对刚刚调用Sleep的线程重新调度。如果不存在多个拥有相同优先级的可调度线程。就会出现这种情况。（四）wait系统调用进程一旦调用了wait，就立即阻塞自己，由wait自动分析是否当前进程的某个子进程已经退出，如果让它找到了这样一个已经变成僵尸的子进程，wait就会收集这个子进程的信息，并把它彻底销毁后返回；如果没有找到这样一个子进程，wait就会一直阻塞在这里，直到有一个出现为止。(五)、ReleaseSemaphore调用对指定的信号量增加指定的值原型：BOOL ReleaseSemaphore( HANDLE hSemaphore, LONG lReleaseCount, LPLONG lpPreviousCount);参数：hSemaphore 输入参数所要操作的信号量对象的句柄，这个句柄是CreateSemaphore或者OpenSemaphore函数的返回值。这个句柄必须有SEMAPHORE_MODIFY_STATE 的权限。lReleaseCount 【输入参数】这个信号量对象在当前基础上所要增加的值，这个值必须大于0，如果信号量加上这个值会导致信号量的当前值大于信号量创建时指定的最大值，那么这个信号量的当前值不变，同时这个函数返回FALSE;lpPreviousCount 输出参数指向返回信号量上次值的变量的指针，如果不需要信号量上次的值，那么这个参数可以设置为NULL;返回值：如果成功返回TRUE,如果失败返回FALSE,可以调用GetLastError函数得到详细出错信息；(六)、CreateProcess调用当使用CreateProcess调用时，系统将创建一个进程和一个主线程。CreateThread将在主线程的基础上创建一个新线程，大致做如下步骤： 1在内核对象中分配一个线程标识/句柄，可供管理，由CreateThread返回 2把线程退出码置为STILL_ACTIVE，把线程挂起计数置1 3分配context结构 4分配两页的物理存储以准备栈，保护页设置为PAGE_READWRITE，第2页设为PAGE_GUARD 5lpStartAddr和lpvThread值被放在栈顶，使它们成为传送给StartOfThread的参数 6把context结构的栈指针指向栈顶（第5步）指令指针指向startOfThread函数 MSDN中CreateThread原型： HANDLE CreateThread( LPSECURITY_ATTRIBUTES lpThreadAttributes, DWORD dwStackSize, LPTHREAD_START_ROUTINE lpStartAddress, LPVOID lpParameter, DWORD dwCreationFlags, LPDWORD lpThreadId); lpThreadAttributes：指向SECURITY_ATTRIBUTES型态的结构的指针。在Windows 98中忽略该参数。在Windows NT中，它被设为NULL，表示使用缺省值。 dwStackSize，线程堆栈大小，一般=0，在任何情况下，Windows根据需要动态延长堆栈的大小。 lpStartAddress，指向线程函数的指针，形式：函数名，函数名称没有限制，但是必须以下列形式声明： DWORD WINAPI ThreadProc (LPVOID lpParam) ，格式不正确将无法调用成功。 lpParameter：向线程函数传递的参数，是一个指向结构的指针，不需传递参数时，为NULL。 dwCreationFlags ：线程标志,可取值如下 CREATE_SUSPENDED： 创建一个挂起的线程 0 ：创建后立即激活。 lpThreadId:保存新线程的id。 返回值： 函数成功，返回线程句柄；函数失败返回false。 函数说明： 创建一个线程。 语法： hThread = CreateThread (&security_attributes, dwStackSize, ThreadProc,pParam, dwFlags, &idThread) ; 一般并不推荐使用 CreateThread函数，而推荐使用RTL 库里的System单元中定义的 BeginThread函数，因为这除了能创建一个线程和一个入口函数以外，还增加了几项保护措施。 LPTHREAD_START_ROUTINE 指向的函数是回调函数，并且必须由承载应用程序的编写器实现。（七）、CreateSemaphore调用创建一个新的信号机 返回值Long，如执行成功，返回信号机对象的句柄；零表示出错。会设置GetLastError。即使返回一个有效的句柄，但倘若它指出同名的一个信号机已经存在，那么GetLastError也会返回ERROR_ALREADY_EXISTS 参数lpSemaphoreAttributes SECURITY_ATTRIBUTES，指定一个SECURITY_ATTRIBUTES结构，或传递零值（将参数声明为ByVal As Long，并传递零值）表示采用不允许继承的默认描述符。该参数定义了信号机的安全特性 lInitialCount Long，设置信号机的初始计数。可设置零到lMaximumCount之间的一个值 lMaximumCount Long，设置信号机的最大计数 lpName String，指定信号机对象的名称。用vbNullString可创建一个未命名的信号机对象。如果已经存在拥有这个名字的一个信号机，就直接打开现成的信号机。这个名字可能不与一个现有的互斥体、事件、可等待计时器或文件映射的名称相符五、运行结果见图（45） 图（4） 图（5）六、分析总结通过本次使用信号量PV原语完成司机与售票员的设计的过程 掌握了信号的使用方法和PV操作的定义，掌握使用PV操作实现进程之间同步和互斥的方法，加深对进程同步互斥概念的理解。在此过程中还理解了一些函数类的意义和用法如Semaphore，Thread以及常用的系统调用如CreateSemaphore调用、sleep系统调用、ReleaseSemaphore调用、wait系统调用、CreateProcess调用。七、程序清单#include #include #include#include 311.h#include random.husing namespace std;HANDLE Semaphore_dirver; /司机信号量的句柄HANDLE Semaphore_condutor;/售票员信号量的句柄int num_station=0;/司机进程void Thread_Driver() while(true) if(WaitForSingleObject(Semaphore_dirver,INFINITE)=WAIT_OBJECT_0) /相当与P(Semaphore_dirver)操作 cout汽车行驶中，请您扶稳坐好！endlendl; Sleep(5000);/行车时间 ReleaseSemaphore(Semaphore_condutor, 1, NULL); /相当与V(Semaphore_condutor)操作提醒售票员可以售票了 /售票员进程void Thread_Conductor() while(true) if(WaitForSingleObject(Semaphore_condutor,INFINITE)=WAIT_OBJECT_0) /判断车是否已停 if(!num_station) /第一站 cout没人下车endl; num_station+; NUM_ON=random_num(NUM_MAX); Sleep(3000);/乘客上车时间 coutNUM_ON 名乘客上车endl; NUM_CURRENT=NUM_ON+NUM_INITIAL;/起始站上车的人数 else cout车辆进站，请您注意安全！开门请当心，下车请走好！下车后请勿从车前绕行！endlendl; Sleep(3000);/乘客下车时间 NUM_DOWN=random_num(NUM_CURRENT);/下车人数 coutNUM_DOWN 名乘客下车end