《数据结构与算法》课程第二章关键词汇-奥鹏教育.doc

浙大08秋冬学期《数据结构与算法》课程第二章关键词汇 进程(Process)定义 可并发执行的程序在一个数据集合上的运行过程。 进程的三个基本状态 运行态/执行态（Running） 当一个进程在处理机上运行时，则称该进程处于运行状态。 就绪态（Ready） 一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。 阻塞态（Blocked） （又称挂起状态、等待状态）：一个进程正在等待某一事件发生（例如请求I／O而等待I／O完成等）而暂时仃止运行，这时即使把处理机分配给进程也无法运行，故称该进程处于阻塞状态。 原语（Primitive） 原语是一种特殊的广义指令，它的功能是由系统通过一段不可分割的指令操作来完成，它又称原子操作，原语在核心态下完成。进程控制操作（创建、撤消、阻塞……）大都为原语操作。 进程控制原语 (1)创建原语(Create) (2)撤消原语（Destroy）/ 终止（Termination） (3)阻塞原语（block (4)唤醒原语（wakeup） (5)挂起原语（suspend） (6)激活原语（active） 临界资源 一次只允许一个进程使用的资源称为临界资源。 所有的进程同步机制应遵循以下四条准则 空闲让进 当无进程进入临界区时，相应的临界资源处于空闲状态，因而允许一个请求进入临界区的进程立即进入自己的临界区。 忙则等待 当已有进程进入自己的临界区时，即相应的临界资源正被访问，因而其它试图进入临界区的进程必须等待，以保证进程互斥地访问临界资源。 有限等待 对要求访问临界资源的进程，应保证进程能在有限时间进入临界区，以免陷入“饥饿”状态。 让权等待 当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等。 处理机调度模型 仅有进程调度的调度队列模型 有进程调度和中级调度队列模型 具有高级调度和低级调度的调度队列模型 .同时具有三级调度的调度队列模型 进程调度的方式 非抢占（非剥夺）方式 抢占（剥夺）方式（Preemptive mode） 调度方式和算法的选择准则和评价 1.面向用户(User-oriented)的准则和评价 (1)周转时间(Turnaround Time)短: 它是评价批处理系统的重要性能指标。 作业周转时间Ti是指从作业提交给系统开始，到作业完成为止的这段时间间隔。 周转时间Ti = 完成时间－到达(提交)时间 平均周转时间 平均带权周转时间 一个作业的带权周转时间Wi=Ti/Tsi（作业的周转时间Ti/实际服务时间Tsi） (2)响应时间(Response Time)快 响应时间是评价分时系统的性能指标。响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。 (3)截止时间(Deadline)的保证 它是用来评价实时系统的重要指标，截止时间是某任务必须执行的最迟时间，或完成的最迟时间。 (4)优先权(Enforcing Priorities)准则 在选择批处理、分时和实时系统的调度算法时，都可引用优先权准则，以便让那些紧急的作业（或事件），得到及时的处理。在要求较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业得到及时的处理。 面向系统(System-oriented)的准则 (1)达到系统设计目标 系统的设计目标是选择算法的主要依据。 (2)系统吞吐量(throughput)大 这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系。 (3)处理机利用率(Processor Utilization)高 对于大中型多用户系统，由于CPU价格十分昂贵，所以处理机利用率成为衡量大、中型系统性能的十分重要指标，但对单用户微机或某些实时系统，该准则就不那么重要。 (4)各类资源的平衡利用(Balancing Resources) 在大中型系统中，有效地利用各类资源（包括CPU、外存、I/O设备等）也是一个重要指标，对于微型机和某些实时系统，该准则也不重要。 作业／进程调度算法 1.先来先服务First-Come-First-Served （FCFS）（作业／进程）调度算法 FCFS是一种最简单的调度算法，可用于作业或进程调度。此算法的原则是按照作业到达后备作业队列（或进程进入就绪队列）的先后次序来选择作业（或进程）。 2.短作业／进程优先(SJF/Shortest Process Next)调度算法 这种调度算法主要用于作业调度，它从作业后备队列中挑选所需运行时间（估计值）最短的作业进入主存运行。 3.时间片轮转Round-Robin（