专业课程设计I报告-B09040203

专业课程设计I报告(2011/2012学年第二学期)题目1：进程的同步与互斥题目2：最短路径算法专业计算机科学与技术学生姓名张亚萍班级学号B09040203指导教师黄海平指导单位计算机学院日期2012.4.16-4.26指导教师成绩评定表学生姓名张亚萍班级学号B09040203专业计算机科学与技术评分内容评分标准优秀良好中等差平时成绩认真对待课程设计，遵守实验室规定，上机不迟到早退，不做和设计无关的事设计成果设计的科学、合理性功能丰富、符合题目要求界面友好、外观漂亮、大方程序功能执行的正确性程序算法执行的效能设计报告设计报告正确合理、反映系统设计流程文档内容详实程度文档格式规范、排版美观验收答辩简练、准确阐述设计内容，能准确有条理回答各种问题，系统演示顺利。评分等级指导教师简短评语该同学出勤率(满勤、较高、一般，较低)，学习态度(端正、较端正、一般、较差)，演示程序(未)达到了(基本要求、提高要求1或/和2)，撰写报告格式(规范、一般)、表述(清晰、一般、不清楚)，圆满(较好、基本)完成了课题任务。(可选：尚存在……缺陷。)指导教师签名日期2012-4-30备注评分等级有五种：优秀、良好、中等、及格、不及格进程的同步与互斥一、课题内容和要求（1）课题内容：在一个班上有S个学生。每个学生都要做一个项目，每一个项目由K个老师一起评分。总共有M个老师。每个老师最多给N个项目评分。其中，S*K=M*N。在项目结束后，老师们提供T分钟用来检查学生们的项目。检查每一个学生的项目需要用时D分钟。其中，TD。每一个学生的项目由K个老师共同来检查。在T分钟的时间段内，学生可以在任何时间进入教室(random)，除了在最后的D分钟内。所有的老师一直保持工作状态直到他检查完N个项目或者是T分钟过去后。T分钟过去后，所有的老师和同学都必须离开教室。另外，在T分钟结束前的D分钟内(即在最后的D分钟内)，如果有任何老师或者是学生都处在没有任务的状态下，都必须离开教室，因为已经没有时间让他完成任务了(因为一个项目检查的时间是整整D分钟)。用一个程序来模拟上面描述的作业检查过程。每一个学生和每一个老师应该用不同的线程来完成。当一个学生进入教室后，他立即开始找K个没有任务的老师(一次找一个老师，假如没有空闲的老师，则等到有老师为止)，找齐K个老师之后给老师检查，然后离开教室。刚开始每一个老师都是处于空闲状态直到他被学生找到，被学生找到后只能等待，直到学生找齐K个老师(在等待学生找其他老师的时间里，他是不能接受其他同学检查作业的请求的)，当学生找齐K个老师后，老师们执行完检查任务，然后重新变成空闲状态。每个老师在总共检查了N个学生的作业后，离开教室。（2）课题要求：①用一个程序来模拟上面描述的作业检查过程。每一个学生和每一个老师应该用不同的线程来完成（可以选用C、C++和Java作为开发语言，但是考虑到专业课程设计I的实验大纲，请尽可能使用Java语言）；②考虑到跨平台的特性，请尽量使用posix线程标准；③实现良好的图形用户界面；④在程序演示过程中能清晰的展示多个学生线程和多个老师线程的同步和互斥流程。二、需求和思路分析1.java线程本次课程设计采用java线程，线程是一个程序内部的顺序控制流，一个进程相当于一个任务，一个线程相当于一个任务中的一条执行路径。多进程：在操作系统中能同时运行多个任务(程序)；多线程：在同一个应用程序中有多个顺序流同时执行；Java线程是通过java.lang.Thread类来实现的；VM启动时会有一个由主方法(publicstaticvoidmain(){})所定义的线程；以通过创建Thread的实例来创建新的线程每个线程都是通过某个特定Thread对象所对应的方法run()来完成其操作的,方法run()称为线程体通过调用Thread类的start()方法来启动一个线程。（1）Java线程的创建和启动有两种方式创建新的线程：第一种：①定义线程类实现Runnable接口②ThreadmyThread=newThread(target);//target为Runnable接口类型③Runnable中只有一个方法：publicvoidrun();用以定义线程运行体④使用Runnable接口可以为多个线程提供共享的数据⑤在实现Runnable接口的类的run()方法定义中可以使用Thread的静态方法publicstaticThreadcurrentThread();获取当前线程的引用第二种：①可以定义一个Thread的子类并重写其run方法如：classMyThreadextendsThread{publicvoidrun(){...}}②然后生成该类的对象：MyThreadmyThread=newMyThread();调用线程的start（）方法启动线程。在本次课程设计中采用的是第二种创建线程的方法。（2）同步互斥机制Java关键字synchronized是Java语言提供的对多线程和同步的一种机制。synchronized可以作为函数的修饰符，也可作为函数内的语句。本次课程设计主要用到synchronized关键字修饰代码块，给代码段加锁，下面简单介绍synchronized关键字的这种用法。整个语法形式表现为synchronized(同步锁){//访问共享资源，需要同步的代码段}这里尤其要注意的就是，同步锁本身一定要是共享的对象。f(){Objectlock=newObject();//产生一个同步锁synchronized(lock){//代码段A//访问共享资源resource//需要同步}}上面这段代码没有任何意义。因为那个同步锁是在函数体内部产生的。每个线程调用这段代码的时候，都会产生一个新的同步锁。那么多个线程之间，使用的是不同的同步锁。根本达不到同步的目的。所以同步代码一定要写成如下的形式，才有意义。publicstaticfinalObjectlock=newObject();…f1(){synchronized(lock){//lock是公用同步锁//代码段A//访问共享资源resource//需要同步}不一定要把同步锁声明为static或者public，但是一定要保证相关的同步代码之间，一定要使用同一个同步锁，线程只有拿到这把锁才能访问上锁的代码段，这样才能实现几个线程之间的同步，保证同一时刻只有一个线程获得执行上锁代码的权力。成功获取同步锁的线程，执行完同步代码段之后，会释放同步锁，该同步锁的就绪队列中的其他线程就继续下一轮同步锁的竞争，成功者就可以继续运行，失败者需要在就绪队列中等待。2.总线程模块①通过人机交互，获取本次模拟的数据（S、M、K、N、T、D）②创建学生线程；③创建老师线程；④等待；⑤时间到，程序退出。3.学生线程模块①随机选择一个时间r（0=rT-D），并等待r分钟（程序中以1000ms作为一分钟）；②等待结束，进入教室；③选择K个空闲的老师，若不齐则等待；④找齐后，做D分钟的项目检查；⑤项目检查完毕，学生离开教室。4.老师线程模块①老师进入教室；②空闲等待；③被一个学生找到后，标记为忙状态，等待K个老师找齐；④K个老师聚齐后，为学生做D分钟的项目检查；⑤老师完成N个项目的检查或T分钟时间到，离开教室，否则回到步骤②；5.注意事项①在剩余时间小于D时，学生线程必须退出，执行离开教室操作；②在剩余时间小于D时，一个老师进程只能在执行(4)—(5)步或者直接执行第(5)步；③在时间T到达时，所有的老师、学生线程都必须退出，执行离开教室操作；④对于所有合理的S,M,K,N,T,D数值(这些数必须都是正整数并且满足条件：S*K=M*NandTD)，程序都能够运行成功；⑤程序对所有的时间安排策略都必须运行成功。例如不管线程的相对速度，例如要把握好sleep的毫秒数；⑥在每一个线程的生命周期内，每一步都要有一个合理的说明信息，来表明这个线程中包括哪个老师，哪个学生，进行到什么程度了；⑦要特别注意防范死锁问题的发生。三、概要设计仔细分析课题，可以分为以下几个模块实现：1、总线程通过人机对话获得所需要的学生人数S，老师人数M，学生需要接受检查的老师数K，老师最多检查学生数N，总时间T，学生接受检查所需时间D。然后产生老师线程，接着产生学生线程（学生进入教室的时间由每一个学生线程自行决定，并不在主线程中决定），时间T到达时，结束所有未结束的老师和学生线程。2、老师线程开始人机交互，获取用户输入数据创建老师线程长江学生线程T时间到？结束是否如图所示，通过获取公共同步锁come执行进入教室部分代码，获得进入教室的权力，打印老师进入信息表明老师已进入教室，教室中处于空闲状态的老师人数加1。接着利用while循环判断结束时间T是否到达和老师检查次数是否到达N，两个条件都不满足则继续循环判断这两个条件，老师即处于等待状态，否则如果老师检查学生的次数到达N，说明老师已完成规定的检查任务，已经离开，如果开始获得come锁？输出老师进入信息教室空闲老师数加1时间T到达或N次检查已完成？获得leave锁？结束打印老师离开信息否是是否否是时间T到达，说明所有线程都要结束，所以这两种情况都要跳出循环，准备离开。最后通过获取公共同步锁leave执行离开教室部分代码，打印老师离开信息，这里没有对教室中处于空闲状态的老师数目进行修改，而是在学生释放老师资源的时候进行修改，防止出现错误。老师线程结束。线程执行完上锁代码后，会自动释放公共锁，流程图中没有显式写出对锁的释放。3、学生线程如图所示，学生线程开始时，先随机选择一个进入时间r(00rT-D)，通过sleep对应毫秒数达到随机进入的效果。判断当前时刻是否大于T-D，若大于则说明剩余时间不够老师检查，学生通过获取公共同步锁leave执行离开教室部分代码，离开即学生线程结束，否则通过获取公共同步锁come执行进入教室部分代码，打印学生进入信息表明学生已经入教室。接着通过获取公共同步锁choose获得尝试选择老师的权力（保证同一时刻只有一个学生正在尝试选择老师，避免死锁），在寻找K个老师检查之前，先利用while循环判断目前教室中处于空闲状态的老师人数是否小于K，若小于表明目前该学生无法找到K个老师为他检查，则继续判断该条件，学生即处于等待状态，否则立即把教室中处于空闲状态的老师人数减去K，跳出循环，寻找K个老师检查。寻找K个老师通过for循环K次，每次循环调用随机函数寻找随机下标index老师，利用while循环判断该老师已检查次数是否到达N和老师是否正在检查别人即状态是否处于忙，两个条件只要有一个不满足，就再调用随机函数寻找其他老师，否则就立即修改老师的忙闲状态，将该老师的下标index保存到该学生项目的老师检查队列。找齐K个老师后，开始检查，调用sleep函数阻塞D。开始产生随机进入教室的时间rSleep时间r对应的毫秒数判断时间T-D是否到达获得come锁？获得leave锁？输出学生进入教室信息获得choose锁？教室中空闲老师数KiK？产生一个随机老师下标indexindex老师空闲且已检查项目数N将index老师状态置忙，当前教室空闲老师数减1，index进入该学生的项目检查老师队列输出index老师将检查该学生信息i++调用sleep函数阻塞时间D输出该学生项目开始检查信息输出学生离开信息（2）是否是否是否是否否是否是（1）等检查完毕，利用K次for循环，将这K个老师的忙闲状态置闲，并把这些老师的检查次数加1，对于释放的每一个老师先判断该老师是否尚未完成N个项目的检查，若是，教室中的空闲老师数加1，否则空闲老师数不作修改（这么做是为了防止空闲老师数目与实际可用的老师数出现暂时不相等的情况）。iK？（2）取出老师序号j将j老师状态置闲，已检查项目数加1j老师已检查N个项目？教室空闲老师数加1输出老师j完成该学生项目检查信息获得leave锁？输出学生离开教室信息结束（1）是否是否是否最后通过获取公共同步锁leave执行离开教室部分代码，打