Elian's blog page

交互式调度算法交互式系统要让用户的操作尽快得到反应，因此更关心算法的响应时间、公平性和任务紧急程度。 算法 主要依据 抢占性 适合解决的问题 RR 到达就绪队列的顺序、时间片 抢占 让每个进程周期性获得 CPU 优先级调度 优先级 可抢占，也可非抢占 区分任务紧急程度 多级队列调度 进程类型所属队列 取决于队列间策略 按系统进程、交互进程、批处理进程等分类管理 多级反馈队列调度 队列优先级、时间片、运行反馈 抢占 在响应、公平、短进程优先之间折中 算法 是否区分优先级 是否使用时间片 是否允许队列迁移 主要优点 主要风险 RR 否 是 否 公平、响应快 时间片过小会增加切换开销 优先级调度 是 不一定 否 能表达任务紧急程度 低优先级进程可能饥饿 多级队列调度 是，按队列区分 可按队列设置 通常不迁移 不同类型进程分开管理 低优先级队列可能饥饿 多级反馈队列调度 是，按队列动态区分 是 是 综合响应、公平和短进程优先 规则复杂，低级队列仍可能饥饿 RR...

批处理调度算法这一组算法主要关注公平性、平均等待时间、平均周转时间等整体指标。它们不强调交互式系统里的快速响应，也不区分任务紧急程度。 下面统一使用这一组进程： 进程 到达时间 运行时间 P1 0 8 P2 1 4 P3 2 9 P4 3 5 P5 6 2 ↻ + − 总览 算法 主要依据 优点 缺点 饥饿 FCFS 到达顺序 公平，实现简单 对短作业不利 不会 SJF / SPF 运行时间 平均等待和周转通常较小 对长作业不利，需要预估运行时间 可能 SRTN 剩余运行时间 平均等待和周转可进一步降低 切换更频繁，对长作业更不利 可能 HRRN 等待时间和运行时间的比值 兼顾短作业和等待较久的作业 每次调度要计算响应比 通常不会 非抢占和抢占抢占是指当前进程正在 CPU 上运行时，操作系统可以因为新事件发生而强行暂停它，把 CPU 分配给另一个就绪进程。被抢占的进程没有结束，也不一定阻塞，而是回到就绪队列，等待以后继续运行。 非抢占式调度不会打断正在运行的进程。只要一个进程已经获得...

调度指标不同指标观察的角度不同： 系统角度：CPU 是否充分忙碌，单位时间能完成多少作业。 用户角度：自己的作业多久完成，多久第一次得到响应。 算法角度：等待时间是否过长，短作业和长作业是否被公平对待。 ↻ + − CPU 利用率CPU 利用率是 CPU 忙碌时间占总时间的比例。 $$\text{CPU 利用率}=\frac{\text{CPU 忙碌时间}}{\text{总时间}}$$ CPU 忙碌时间是 CPU 真正在执行进程的时间。若某段时间 CPU 空闲、等待 I/O 或没有可运行进程，则不计入忙碌时间。 类似地，也可以计算打印机、磁盘等设备的利用率： $$\text{设备利用率}=\frac{\text{设备忙碌时间}}{\text{总时间}}$$ Example 一个作业先占用 CPU 5 秒，再使用打印机 5 秒，最后再占用 CPU 5 秒。总时间为 15 秒。 CPU 利用率为 $\frac{5+5}{15}=66.67%$；打印机利用率为...

调度时机低级调度从就绪队列中选择一个进程，为它分配 CPU。 需要进行进程调度与切换的情况，可以分成两类。 类型 触发情况 含义 当前进程主动放弃 CPU 正常终止 进程执行结束，不再需要 CPU 当前进程主动放弃 CPU 异常终止 运行中发生错误，被迫结束 当前进程主动放弃 CPU 主动阻塞 请求 I/O、等待资源或事件，暂时无法继续运行 当前进程被动放弃 CPU 时间片用完 分时系统用时钟中断周期性收回 CPU 当前进程被动放弃 CPU 有更紧急事件需要处理 例如 I/O 中断到达 当前进程被动放弃 CPU 更高优先级进程进入就绪队列 抢占式调度下，当前进程可能被暂停 主动放弃 CPU 时，当前进程自己已经无法或不需要继续运行。被动放弃 CPU 时，当前进程本来还可以继续执行，但系统为了响应性、公平性或优先级，强行收回...

调度当系统中有多个任务都想使用有限资源时，操作系统必须决定谁先使用资源。这个选择过程就是调度。 一个程序要真正运行，通常要先从外存进入内存，再进入就绪队列，最后才可能被分配 CPU。因此，处理机调度要分成三个层次理解。 高级调度高级调度也称作业调度。 用户提交的作业最初通常位于外存的后备队列。由于内存空间有限，系统不能把所有作业一次性装入内存。高级调度按照一定规则，从外存后备队列中选择作业调入内存，并为它创建进程。 高级调度的关键动作是： 从外存后备队列选择作业。 将作业调入内存。 为该作业创建进程和 PCB。 让新建进程进入创建态，再进入就绪态。 高级调度面向的是作业。一个作业通常只被高级调度调入一次，作业结束后再调出一次。因此，高级调度发生频率最低。 低级调度低级调度也称进程调度或处理机调度。 低级调度从内存中的就绪队列选择一个进程，把 CPU...

IPC进程间通信即 IPC，Inter-Process Communication，讨论的是不同进程之间如何交换数据。 进程是资源分配单位，通常拥有相互独立的地址空间。为了安全，一个进程不能直接读写另一个进程的地址空间。因此，进程通信必须由操作系统提供受控机制。 常见 IPC 方式主要有三类：共享存储、消息传递、管道通信。 共享存储共享存储让多个进程把同一片物理内存映射到各自地址空间中。这样，进程 P 写入共享区的数据，进程 Q 可以从自己的地址空间中读到。 类型 做法 特点 基于数据结构的共享 共享区只能按系统规定的数据结构使用，例如固定大小数组 限制多，速度相对慢，属于低级通信方式 基于存储区的共享 操作系统划出共享存储区，数据格式和位置由通信进程决定 灵活、速度快，属于高级通信方式 共享存储速度快，但不自动保证访问顺序。多个进程同时读写同一共享区时，需要互斥和同步机制，否则会出现覆盖、读到半成品数据等问题。 共享存储的地址映射细节可联系 Memory-Mapped-Files-And-mmap。这里关注的是 IPC...

进程的概念程序是静态的，是存放在磁盘中的可执行文件，例如 .exe 文件或 ELF 文件。 进程是动态的，是程序的一次执行过程。同一个程序可以被多次运行，每次运行都对应一个独立进程。 同一个程序的多个进程可以拥有相同的程序段，但它们的 PCB、数据段、资源占用和执行位置不同。比如同时登录多个账号，本质上是同一程序对应多个进程。 引入进程实体后，可以更准确地定义进程： Important 进程是进程实体的运行过程，是系统进行资源分配和调度的独立单位。 进程的组成进程运行前，程序指令要装入主存，运行中产生的数据也要有存放位置。操作系统还要保存管理该进程所需的信息。 进程实体也称进程映像，由程序段、数据段、PCB 三部分组成。 组成 内容 使用者 程序段 程序指令 CPU 取指并执行 数据段 运行中产生和使用的数据 进程自身 PCB 进程标识、状态、资源、调度和运行现场信息 操作系统 程序段和数据段与进程自己的运行逻辑有关；PCB 与操作系统的管理逻辑有关。 PCBPCB 是 Process Control...

信号信号是进程级异步事件通知机制。其目的是在目标进程的控制信息中标记某类事件发生。 信号机制的核心是三类控制信息： 信息 含义 待处理信号集 哪些信号已经到达，但还没有被处理 信号屏蔽字 哪些信号暂时被屏蔽，暂不投递给进程处理 信号处理动作表 每种信号采用默认处理、忽略，还是调用用户注册的处理函数 每种信号在目标进程 PCB 中表示为 1 bit：某位为 1 表示该类信号处于待处理状态。 一次典型信号处理过程： 信号产生。来源可能是终端输入、定时器、异常、I/O...

线程线程是一个基本的 CPU 执行单元，也是程序执行流的最小单位。线程也常被称为轻量级进程。 引入线程后： 对象 主要角色 进程 系统资源分配单位，例如地址空间、打开文件、I/O 资源 线程 处理机调度和分配单位 同一进程内的线程共享进程资源，例如地址空间、全局变量、打开文件等；但每个线程有自己的执行现场，例如线程 ID、程序计数器、寄存器、栈等。 线程和进程 角度 进程 线程 资源拥有 拥有独立地址空间和资源集合 共享所属进程资源 调度单位 传统系统中是调度单位 引入线程后成为基本调度单位 切换开销 切换地址空间和资源环境，开销较大 同进程内线程切换开销较小 通信 进程间地址空间隔离，需要 IPC 同进程线程共享地址空间，通信更方便 影响范围 一个进程崩溃通常不直接破坏其他进程 一个线程错误可能破坏同进程共享数据 同一进程内线程切换成本较低，是因为很多资源环境不需要更换；但线程共享地址空间，也意味着共享数据更容易发生竞争，后面同步与互斥会专门处理这个问题。 用户级线程用户级线程 ULT，User-Level...

缓冲区是什么缓冲区是一个临时存储区域，可以由硬件寄存器组成，也可以由主存中的一段空间组成。操作系统 I/O 管理讨论的缓冲区通常是主存缓冲区，由设备独立性软件组织和管理。 缓冲区的作用： 缓和 CPU、内存与 I/O 设备之间的速度差异； 协调不同设备或进程之间的数据单位差异； 减少进程因 I/O 等待而被频繁阻塞； 支持异步 I/O、DMA、SPOOLing 等机制。 以输出为例，用户进程可以把一块数据快速放入缓冲区，之后继续执行；慢速设备再从缓冲区逐步取走数据。输入时方向相反，设备先把数据放入缓冲区，进程再从缓冲区取数据。 单缓冲单缓冲是在主存中为 I/O 分配一个缓冲区。若题目没有特别说明，一个缓冲区大小通常等于一个数据块。 单缓冲读入时涉及三个时间： 符号 含义 $T$ 设备把一块数据输入到缓冲区的时间 $M$ 缓冲区到用户工作区的传送时间 $C$ CPU...