优先级调度算法四.PPT

Y=COUNT Y=Y+1 COUNT=Y 临界区 V(S) P(S) 进程B X=COUNT X=X+1 COUNT=X 临界区 V(S) P(S) 进程A S=1 进程P1 … L1:P(s) {获取信息} … 进程P2 … {产生信息} L2:V(s) … 同步条件 S=0 同步点 四、用P，V原语操作实现简单同步 1.用P，V操作描述前趋关系 五、P、V原语在进程同步/互斥问题中的应用 int f2=0,f3=0,f4=0,f5=0,f6=0; void main() { cobegin P1();P2();P3();P4();P5(); coend } ? P1() { ... v(f2);v(f3); } P2() { p(f2); ... v(f4);v(f5); } ? P3() { p(f3); ... v(f6); } ? P4() { p(f4); ... v(f6); } ? P5() { p(f5); ... v(f6); } ? P6() { p(f6); } 1 2 3 ……… N P1 P2 P3 Pm C1 C2 C3 Cn 有 界 缓 冲 池 … … 生产者 消费者 五、P、V原语在进程同步/互斥问题中的应用 2.生产者—消费者问题 同步条件： 当有界缓冲区中至少有一个单元是满的时，消费者才能接收数据；当有界缓冲区中至少有一个单元是空的时，生产者才能发送数据 。 互斥条件： 有界缓冲区是临界资源，必须互斥使用 。 设置信号量： 互斥信号量Mutex：初值为1。 同步信号量Full ：初值为0。 同步信号量Empty ：初值为n。 生产者进程P1 P(Empty ) P(Mutex) 缓冲区 产品 V(Full) V(Mutex) 消费者进程C1 P(Full) P(Mutex) 取产品 V(Empty ) V(Mutex) 8.4 处理器调度 一、高级调度（作业调度、宏观调度） 二、中级调度（交互调度） 三、低级调度（进程调度、微观调度） 四、三级调度之间的关系 一、高级调度 1、功能 按照一定的调度算法对外存上处于后备状态的作业进行选择； 给选中的作业分配内存、输入输出设备等必要的资源，并建立相应的进程； 作业运行完毕时，回收该作业占用的资源，输出必要的信息，撤销该作业的JCB与相应的进程。 2、调度时机 设m为系统支持的在主机上运行的最大作业数，n为在主机上运行的当前作业数。若nm，且存在后备作业，则启动作业调度。 当一作业运行终止而被撤消后，若存在后备作业，则立即启动作业调度。 在分时系统中，当一用户在某终端上通过交互会话被核准其注册的登录作业名及其口令后，立即启动调度。 一、高级调度 3、常用的调度算法 先来先服务法FCFS：将用户作业按提交的顺序排成队列。 最短作业优先法SF：选择估计运行时间短的作业投入运行。 最高优先级法HPF：优先级高者优先调度。 最高响应比优先法HRN：同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入运行。 一、高级调度 二、中级调度 主要任务是按照给定的原则和策略，将处于外存交换区中的那些重新具备运行条件的就绪进程调入内存，或将内存中处于阻塞状态的进程交换到外存交换区。 三、低级调度 1、功能 记录系统中所有进程的执行情况； 按照某种调度算法从就绪进程队列中挑选一个进程，将它移出就绪队列并置成执行态； 进行进程上下文切换，启动CPU执行该进程； 当进程需要放弃使用CPU时，收回CPU，将CPU有关寄存器的内容送入该进程的进程控制块内的相应单元，从而使该进程让出CPU。 三、低级调度 2、调度时机 进程被阻塞 时间片到 有更高优先级的进程要占用CPU 三、低级调度 3、常用的调度算法 先来先服务法FCFS：将就绪进程按进入就绪状态的先后排成队列。 轮转法RR：将所有就绪进程按先进先出原则排序，每个进程一次执行一个时间片。 最高优先级法HPF：优先级高者优先被调度。 多级反馈轮转法：就绪进程按优先级排队；每队有不同的时间片；进程在当前队列执行一个时间片后，若没有执行完则进入下一级队列末尾；高优先级队列优先执行。 计算机软件技术基础　机械工业出版社 * Count是公共变量，在临界区，只有当进程A执行完后，进程B才能进行。 * *