实验二 进程调度算法和信号量.doc

实验二 进程调度算法和信号量（9学时）实验目的：1 掌握进程调度的基本原理以及调度算法2 掌握信号量的使用方法和实现原理实验方法：1. 进程调度实验要求：用JAVA Thread 模拟进程，自己设计并实现调度算法，模拟进程的调度。需要实现的调度算法都是非抢占式的，包括：l RandomScheduler.java: Random 方法,随机从就绪进程中选一个执行l RoundRobinScheduler.java: Round Robin 轮转法,轮流执行就绪进程l PriorityScheduler.java: 动态优先级算法,为进程设定优先级，该优先级可以随时间而变化具体实现说明：1) 测试所用仿真线程SimProc.javaa) 构造函数：SimProc(Scheduler sch, String name, int i)，三个参数分别为调度算法类，线程的名称，整数值（在优先级调度中用于说明优先级）b) collatz 算法：根据正整数n是偶数还是奇数，分别用n/2或3n+1替换它，并重复这个过程。人们猜测但尚未证明：无论从哪个整数n开始，最终都将到达1。通常用这个算法来测量程序的性能，给一个随机数序列作为输入，该算法相应的运行的时间也是一个随机数序列。c) 在该程序中用getCount()方法返回优先级算法中的优先级。测试调度算法的程序TestScheduler.java，测试程序的参数只是一个例子，需要自己设计参数来测试。2) 调度算法的抽象类程序Scheduler.java，它的run方法在每个具体的调度算法类中定义。3) 用到的关键函数：l 随机数Randoml 线程同步：n 同步块synchronized(syncObject) n 同步方法Public synchronized void method()/. n wait(),notify(),notifyAll(); 这三个方法只能在同步块或同步方法中调用。1 信号量的使用实验要求：实现信号量模拟批处理，即控制所有的线程都产生后在一起执行。要求实现：Semaphore.java中的P()和V()。具体实现说明：尽管Java实现线程间的同步和操作系统不同，但我们仍然可以用Java学习实现信号量的方法。实现的关键在于，调度程序需要被告知如果一个进程正在等待一个信号量那么这个进程将不被运行。 这里我们定义一个信号量sem的数据结构为记录型信号量，即包含一个整形sem.value和一个等待队列sem.queue。 相关P()和V()的实现伪码如下：P(): decrement sem.value; if (sem.value=0 ) return ;将当前线程从调度程序的就绪队列中移出，加入信号量的等待队列sem.queue； 通知调度程序调度其他线程。V(): increment sem.value; if(sem.value0) return; 将信号量的等待队列sem.queue中前面的线程从信号量的等待队列移出，加入调度程序的就绪队列中。 实现一个barrier，即 所有的线程到达这个barrier时都停止，等待本批的最后一个线程到达。然后所有的本批的线程一起运行。Barrier再重新初始化，等待下一批进程。这样，本批次的线程不论底层的调度机制如何，开始执行的时间不会差太多。给出的程序：l 测试信号量所用仿真线程：SemProc.java l 调度程序：SemScheduler.j