处理机调度与死锁：资源分配与调度算法解析

"资源分配图化简-chapter3处理机调度和死锁" 在操作系统中，资源分配图化简是分析和解决死锁问题的一种方法。这个过程主要包含两个步骤： 1）首先，寻找图中一个非孤立的进程节点，这个节点只有分配边，即它已经获得了某些资源但没有等待其他资源。将这样的节点的分配边去除，将其变成孤立节点。这样做的目的是简化资源分配状态，便于进一步分析。 2）接着，将这个节点的资源分配给一个正在等待这些资源的进程。这意味着将某个进程的申请边转化为分配边，这有助于我们理解资源的流动和可能的资源释放情况。 处理机调度是操作系统中的关键功能，它分为三个层次： - 高级调度（作业调度）：在多道程序系统中，决定哪些作业可以从外存的后备队列中调入内存，成为就绪状态的进程。 - 中级调度（交换调度）：管理内存中的进程，决定哪些进程应该被换出到外存，以便为新的作业或进程腾出空间。 - 低级调度（进程调度）：在就绪队列中选择一个进程，分配处理机执行，并负责进程的上下文切换。 处理机调度的目标主要包括提高资源利用率、保证公平性、实现负载均衡以及策略强制性。不同类型的系统有不同的调度目标： - 批处理系统：追求平均周转时间短、系统吞吐量高和处理机利用率高。 - 分时系统：关注响应时间快和执行的均衡性，以提供良好的交互体验。 - 实时系统：首要目标是满足任务的截止时间并确保系统的可预测性。 作业与作业调度在批处理系统中扮演着核心角色。作业是用户提交给系统的完整任务，由多个作业步组成，例如编译、连接和运行。作业控制块（JCB）存储了关于作业的各种信息，如作业的状态、资源需求等。 作业调度负责监控所有作业的状态，从后备队列中选择合适的作业进行执行，并在作业完成后进行善后处理。调度算法有多种，例如： - FCFS（先来先服务）：按照作业到达的顺序进行调度，简单但可能导致短作业等待时间过长。 - SJF（最短作业优先）：优先调度预计执行时间最短的作业，可以减少平均周转时间，但可能导致长作业的等待时间增加。 FCFS算法虽然简单，但可能导致作业等待时间不均，不利于短作业的快速执行。相反，SJF算法则更注重效率，但可能牺牲了作业的公平性。在实际操作中，操作系统通常会采用更复杂的混合调度策略，以兼顾效率、公平性和响应时间等因素。