题型

单选题 1*20

判断题 1*20

填空题 1*20

  • 死锁
  • 标题性

简答题 5*2

  • 第一题

    • 死锁

  • 第二题

    • 处理机状态
    • 特权指令、普通指令
    • 进程的正常执行、异常执行

算法题 6*5

  • PV操作应用题

  • 进程调度；进程状态转换图（边的含义）

  • 调度

    • 进程调度（时间片）
    • 作业调度（顺序执行）
    • 三种不同的调度算法
    • 计算中转时间

  • 死锁

    • 计算题
    • 操作系统必考题

  • 阅读程序题

    • 系统功能调用
    • 并发
    • 信号量
    • 说明系统功能调用的功能、用法
    • 程序执行结果？进程数？

操作系统引论

操作系统的目标和作用

  • 操作系统的目标

    • 方便性
    • 有效性
    • 可扩充性
    • 开放性

  • 操作系统的作用

    • 用户与计算机硬件系统之间的接口
    • 计算机系统资源的管理者
    • 实现对计算机资源的抽象

  • 推动操作系统发展的主要动力

    • 不断提高计算机资源利用率
    • 方便用户
    • 器件的不断迭代更新
    • 计算机体系结构的不断发展
    • 不断提出新的应用需求

操作系统的发展过程

  • 批处理系统 Batch Processing System

    • 单道批处理系统 Simple

      • 解决人机矛盾和CPU与I/O设备速度不匹配矛盾
      • 旨在提高系统资源的利用率和系统吞吐量
      • 系统中的资源得不到充分的利用

    • 多道批处理系统 Multiprogrammed

      • 进一步提高系统资源的利用率和系统吞吐量

      • 资源利用率高；系统吞吐量大

      • 平均周转时间长；无交互能力

      • 问题

        • 处理机争用
        • 内存分配和保护
        • I/O设备分配
        • 文件的组织和管理
        • 作业管理
        • 用户与系统的接口

  • 操作系统是一组能有效地组织和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合。

  • 分时系统 Time Sharing System

    • 满足用户对人—机交互的需求

    • 特征

      • 多路性

        • 系统允许将多台终端同时连接到一台主机上
        • 按分时原则为每个用户服务

      • 独立性

        • 每个用户在各自的终端上进行操作，彼此之间互不干扰

      • 及时性

        • 及时接收

          • 系统中配置一个多路卡（分时多路复用）

        • 及时处理

          • 作业直接进入内存
          • 采用轮转运行方式

      • 交互性

        • 用户可通过终端与系统进行广泛的人机对话

          • 用户可以请求系统提供多方面的服务

  • 实时系统 Real Time System

    • 实时计算

      • 系统的正确性，不仅由计算的逻辑结果来确定，而且还取决于产生结果的时间。

    • 实时任务类型

      • 截止时间

        • 开始截止时间 - 某时间以前必须开始
        • 完成截止时间 - 某时间以前必须完成

      • 周期性实时任务

      • 非周期性实时任务

      • 硬实时任务 - 严格遵守截止时间

      • 软实时任务 - 不必完全严格遵守截止时间

    • 特征

      • 多路性

        • 系统周期性地对多路现场信息进行采集
        • 系统对多个对象或多个执行机构进行控制

      • 独立性

        • 对信息的采集和对对象的控制彼此互不干扰

      • 及时性

        • 以控制对象所要求的截止时间来确定（秒级到毫秒级）

      • 交互性

        • 仅限于用户发送某些特定的命令，由系统立即响应

      • 可靠性

        • 高度可靠

操作系统的基本特性

  • 并发 Concurrence

    • 有效地提高系统中的资源利用率，增加系统的吞吐量

    • 并行性

      • 两个或多个事件在同一时刻发生

    • 并发性

      • 两个或多个事件在同一时间间隔内发生

    • 进程 Process

      • 在系统中能独立运行并作为资源分配的基本单位
      • 由一组机器指令、数据和堆栈等组成的
      • 一个能独立运行的活动实体

  • 共享 Sharing

    • 系统中的资源可供内存中多个并发执行的进程共同使用（资源共享/资源复用）

    • 互斥共享方式

      • 临界资源（独占资源）

    • 同时访问方式

  • 虚拟 Virtual

    • 时分复用技术

      • 利用处理机的空闲时间运行其它程序，提高处理机的利用率
      • 虚拟处理机技术
      • 虚拟设备技术

    • 空分复用技术

      • 利用存储器的空闲空间分区域存放和运行其它的多道程序，提高内存的利用率

  • 异步 Asynchronism

    • 进程是以人们不可预知的速度向前推进的

操作系统的主要功能

  • 处理机管理功能

    • 进程控制

    • 进程同步

    • 进程通信

    • 调度

      • 作业调度
      • 进程调度

  • 存储器管理功能

    • 内存分配

      • 静态分配方式
      • 动态分配方式

    • 内存保护

    • 地址映射

      • 空间分离
      • 地址重定位

    • 内存扩充

      • 请求调入功能
      • 置换功能

  • 设备管理功能

    • 缓冲管理
    • 设备分配
    • 设备处理

  • 文件管理功能

    • 文件存储空间的管理
    • 目录管理
    • 文件的读/写管理和保护

  • 与用户之间的接口

    • 用户接口

      • 联机用户接口
      • 脱机用户接口
      • 图形用户接口

    • 程序接口 - 系统功能调用

OS结构设计

  • 无结构操作系统

  • 模块化结构OS

  • 分层式结构OS

  • 客户/服务器模式（C/S）

  • 面向对象程序设计技术

  • 微内核 MicroKernel

    • 基本概念

      • 足够小的内核

      • 基于客户/服务器模式

      • 应用“机制与策略分离”原理

        • 机制 mechanism
        • 策略 policy

      • 采用面向对象技术

        • 操作系统是一个极其复杂的大型软件系统

    • 基本功能

      • 进程（线程）管理
      • 低级存储器管理
      • 中断和陷入处理

    • 优点

      • 提高了系统的可扩展性
      • 增强了系统的可靠性
      • 可移植性强
      • 提供了对分布式系统的支持
      • 融入了面向对象技术

    • 缺点

      • 运行效率低（多次上下文切换）

进程的描述与控制

前趋图和程序执行

  • 程序顺序执行

    • 顺序性
    • 封闭性
    • 可再现性

  • 程序并发执行

    • 间断性
    • 失去封闭性
    • 不可再现性

进程的描述

  • 进程的定义

    • 进程控制块 PCB

      • Process Control Block
      • 为了使参与并发执行的每个程序（含数据）都能独立地运行，在操作系统中必须为之配置一个专门的数据结构，称为PCB。
      • 系统利用PCB来描述进程的基本情况和活动过程，进而控制和管理进程。

    • 进程实体（进程映像）

      • 程序段
      • 相关的数据段
      • PCB

    • 典型定义

      • 进程是程序的一次执行
      • 进程是一个程序及其数据在处理机上顺序执行时所发生的活动
      • 进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位

    • 进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。

  • 进程的特征

    • 动态性
    • 并发性
    • 独立性
    • 异步性

进程的基本状态

  • 就绪状态 Ready

  • 执行状态 Running

  • 阻塞状态 Block

  • 进程三种基本状态的转换

    • 处于就绪状态的进程，在调度程序为之分配了处理机之后便可执行，状态由就绪态转变为执行态
    • 正在执行的进程（当前进程）如果因分配给它的时间片已完而被剥夺处理机暂停执行时，其状态便由执行转为就绪
    • 如果因发生某事件，致使当前进程的执行受阻，使之无法继续执行，则该进程状态由执行转变为阻塞

  • 创建状态

    • 创建一个进程

      • 进程申请一个空白PCB
      • 向PCB中填写用于控制和管理进程的信息
      • 为该进程分配运行时所必需的资源
      • 把该进程转入就绪状态并插入就绪队列中

    • 为保证进程的调度必须在创建工作完成后进行，确保对进程控制块操作的完整性

    • 增加了管理的灵活性，OS根据系统性能或主存容量的限制推迟新进程的提交

    • 处于创建状态的进程，当其获得了所需的资源以及对其PCB的初始化工作完成后，由创建状态转入就绪状态

  • 终止状态

    • 终止一个进程

      • 等待操作系统进行善后处理
      • 将其PCB清零并将PCB空间返还系统

    • 进入终止状态

      • 到达了自然结束点
      • 出现了无法克服的错误
      • 被操作系统所终结
      • 被其它有终止权的进程所终结

    • 进入终止状态的进程不能再执行，但在操作系统中依然保留一个记录，其中保存状态码和一些计时统计数据，供其它进程收集，其它进程完成信息提取后，善后处理完毕。

  • 挂起操作

进程管理中的数据结构

  • 内存表
  • 设备表
  • 文件表
  • 用于进程管理的进程表

有关PCB

  • PCB的作用

    • 作为独立运行基本单位的标志
    • 能实现间断性运行方式
    • 提供进程管理所需要的信息
    • 提供进程调度所需要的信息
    • 实现与其它进程的同步与通信

  • PCB的信息

    • 进程标识符

      • 外部标识符
      • 内部标识符

    • 处理机状态（处理机的上下文）

      • 通用寄存器
      • 指令计数器
      • 程序状态字PSW
      • 用户栈指针

    • 进程调度信息

      • 进程状态
      • 进程优先级
      • 进程调度所需的其它信息
      • 事件（阻塞原因）

    • 进程控制信息

      • 程序和数据的地址
      • 进程同步和通信机制
      • 资源清单
      • 链接指针

  • PCB的组织方式

    • 线性方式

      • 实现简单、开销小
      • 适合进程数目不多的系统

    • 链接方式

      • 就绪队列
      • 若干个阻塞队列
      • 空白队列

    • 索引方式

      • 就绪索引表
      • 阻塞索引表

进程控制

  • 操作系统内核

    • 系统态 - 管态

    • 用户态 - 目态

    • 功能

      • 支撑功能

        • 终端处理
        • 时钟管理
        • 原语操作

      • 资源管理功能

        • 进程管理
        • 存储器管理
        • 设备管理

  • 进程的创建

    • 引起创建进程的事件

      • 用户登录
      • 作业调度
      • 提供服务
      • 应用请求

    • 进程创建过程

      • 申请空白PCB

      • 为新进程分配其运行所需的资源（物理资源+逻辑资源）

      • 初始化进程控制块PCB

        • 初始化标识信息

          • 将系统分配的标识符和父进程标识符填入新PCB中

        • 初始化处理机状态信息

          • 使程序计数器指向程序的入口地址
          • 使栈指针指向栈顶

        • 初始化处理机控制信息

          • 将进程的状态设置为就绪状态或静止就绪状态
          • 设置为最低优先级（除非用户以显式方式提出高优先级要求）

      • 将新进程插入就绪队列（进程就绪队列能够接纳新进程）

  • 进程的终止

    • 引起进程终止的事件

      • 正常结束

      • 异常结束

        • 越界错
        • 保护错
        • 非法指令
        • 特权指令错
        • 运行超时
        • 等待超时
        • 算术运算错
        • I/O故障

      • 外界干预

        • 操作员或操作系统干预
        • 父进程请求
        • 因父进程终止

    • 进程终止过程

      • 根据被终止进程的标识符，从PCB集合中检索出该进程PCB，读出该进程状态

      • 被终止进程正处于执行状态

        • 立即终止该进程的执行

        • 置调度标志为真

          • 指示该进程被终止后应重新进行调度

      • 该进程还有子孙进程

        • 将其所有子孙进程都予以终止

          • 以防它们成为不可控的进程

      • 将被终止进程所拥有的全部资源归还给其父进程/系统

      • 将被终止进程（PCB）从所在队列/链表中移出，等待其它程序来搜集信息

  • 进程的阻塞与唤醒

    • 引起

      • 向系统请求共享资源失败
      • 等待某种操作的完成
      • 新数据尚未到达
      • 等待新任务的到达

    • 进程阻塞过程

      • 通过调用阻塞原语block将自己阻塞（进入block过程）

        • 阻塞是进程的主动行为

      • 立即停止执行，把PCB中现行状态改为阻塞

      • 将PCB插入相应事件的阻塞队列

      • 转调度程序进行重新调度

      • 将处理机分配给另一就绪进程并切换

    • 进程唤醒过程

      • 由有关进程调用唤醒原语wakeup

        eg. 提供数据的进程

      • 把被阻塞的进程从等待该事件的阻塞队列中移出

      • 将其PCB中现行状态改为就绪

      • 将PCB插入就绪队列

    • block原语和wakeup原语是一对作用刚好相反的原语，必须成对使用

  • 进程的挂起与激活

    • 进程挂起过程

      • OS利用挂起原语suspend

      • 检查被挂起进程的状态

        • 处于就绪状态，改为静止就绪
        • 处于阻塞状态，改为静止阻塞

      • 把该进程的PCB复制到某指定的内存区域（方便用户或父进程考察该进程运行情况）

      • 转向调度程序重新调度（被挂起的进程正在执行）

    • 进程激活过程

      • OS利用激活原语active

      • 将进程从外存调入内存

      • 检查该进程的现行状态

        • 处于静止就绪，改为就绪状态
        • 处于静止阻塞，改为阻塞状态

      • 检查是否要进行重新调度，即优先级比较（抢占调度策略）

进程同步

  • 基本概念

    • 制约关系

      • 间接相互制约关系

        • 共享系统中的资源

      • 直接相互制约关系

        • 为完成某一任务而相互合作

    • 临界资源 Critical Resource

      • 进程间采取互斥方式，实现临界资源共享

    • 临界区 Critical Section

      • 每个进程中访问临界资源的代码

      • 进入区 entry section

        • 检查预访问的临界资源是否正被访问

          • 未被访问

            • 进入临界区对该资源进行访问
            • 设置正被访问的标志

          • 正被访问

            • 不得进入临界区

      • 退出区 exit section

        • 将临界区正被访问的标志恢复为未被访问的标志

    • 同步机制应遵循的规则

      • 空闲让进

      • 忙则等待

      • 有限等待

        • 对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态

      • 让权等待

        • 进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态

  • 硬件同步机制

    • 关中断

      • 保证了对锁的测试和关锁操作的连续性和完整性

      • 缺点

        • 滥用权力可能导致严重后果
        • 时间过长，影响系统效率，限制了处理器交叉执行程序的能力
        • 不适用于多CPU系统

    • Test-and-Set

    • Swap

    • 硬件指令能有效实现进程互斥，但当临界资源忙碌时，会陷入“忙等”

  • 信号量机制 Semaphore

    • 整型信号量
    • 记录型信号量
    • AND型信号量
    • 信号量集

  • 信号量应用

    • 进程互斥

    • 前趋关系（上课例题）

      • 为每个进程设置一个信号量，初值0
      • 有几个输入边，开始执行时，执行几个P操作
      • 有几个输出边，对后序信号量执行几个V操作

经典进程的同步问题

  • 生产者-消费者问题

    • The producer-consumer problem
    • 缓冲区管理问题

  • 哲学家进餐问题

    • The Dinning Philosophers Problem

  • 读者-写者问题

    • Reader-Writer Problem

    • 保证数据一致性

      • 允许读个读者
      • 只允许一个写者
      • 读写不可同时进行

  • 理发师睡觉问题

进程通信

  • 进程通信的类型

    • 共享存储器系统

      • 基于共享数据结构的通信方式
      • 基于共享存储区的通信方式

    • 管道通信系统

      • 互斥
      • 同步
      • 确定对方是否存在

    • 消息传递系统

      • 直接通信方式
      • 间接通信方式

    • 客户机-服务器系统

      • 套接字 Socket

        • 基于文件型
        • 基于网络型

      • 远程过程调用 RPC Remote Procedure Call / 远程方法调用（采用面向对象编程）

  • 消息传递通信的实现方式

    • 信箱通信

      • 信箱的结构

        • 信箱头
        • 信箱体

      • 信箱通信原语

        • 邮箱的创建和撤销
        • 消息的发送和接收

      • 信箱的类型

        • 私用信箱

        • 公用信箱

        • 共享信箱

      • 发送进程和接收进程的关系

        • 一对一
        • 多对一 - C/S
        • 一对多 - 广播
        • 多对多 - 公用邮箱

线程的基本概念

  • 引入

    • 使多个程序更好地并发执行
    • 尽量减少系统的开销
    • 作为调度和分派的基本单位
    • 具有传统进程所具有的特征 - 轻型进程

  • 调度性

    • 能独立运行的基本单位
    • 线程切换只需保存和设置少量寄存器内容
    • 切换代价远低于进程

  • 并发性

    • 进程之间可以并发执行
    • 一个进程中的多个线程之间可以并发执行
    • 一个进程中的所有线程可以并发执行
    • 不同进程中的线程可以并发执行

  • 系统开销

  • 拥有资源

    • 线程仅有一点必不可少的、能保证独立运行的资源
    • 允许多个线程共享该进程所拥有的资源

  • 独立性

    • 同一进程中的不同线程之间的独立性要比不同进程之间的独立性低得多

  • 支持多处理机系统

    • 多线程进程可以将一个进程中的多个线程分配到多个处理机

线程的实现

  • 内核支持线程 KST Kernel Supported Threads

    • 优点

      • 多处理器系统，内核能够同时调度同一进程中的多个线程并行执行
      • 如果进程中的一个线程被阻塞了，内核可以调度该进程中的其他线程占有处理器运行，也可以运行其它进程中的线程
      • 支持线程具有很小的数据结构和堆栈，线程切换快、开销小
      • 本身可以采用多线程技术，提高系统的执行速度和效率

    • 缺点

      • 对于用户的线程切换而言，其模式切换的开销较大（用户态转到核心态）

  • 用户级线程 ULT User Level Threads

    • 优点

      • 线程切换不需要转换到内核空间
      • 调度算法可以是进程专用的
      • 用户级线程的实现与OS平台无关

    • 缺点

      • 系统调用的阻塞问题
      • 单纯的用户级线程实现方式中，内核每次分配给一个进程的只有一个CPU，进程中仅有一个线程能执行

  • 组合方式

    • 多对一模型

      • 线程管理开销小、效率高
      • 一个线程访问内核阻塞，整个进程阻塞
      • 任一时刻，只有一个线程能访问内核

    • 一对一模型

      • 一个线程阻塞时，允许调度另一个线程运行
      • 允许多个线程并行地运行在多处理机系统上
      • 每创建一个用户线程，对应创建一个内核线程，开销较大

    • 多对多模型

处理机调度与死锁

处理机调度

  • 处理机调度的层次

    • 高级调度 High Level Scheduling

      • 长程调度/作业调度
      • 调度对象是作业
      • 用于多道批处理系统
      • 运行频率最低 ?min

    • 低级调度 Low Level Scheduling

      • 进程调度/短程调度
      • 调度对象是进程/内核级进程
      • 用于多道批处理系统、分时系统、实时系统
      • 运行频率最高 10-100ms

    • 中级调度 Intermediate Scheduling

      • 内存调度/中程调度
      • 提高内存利用率和系统吞吐量
      • 运行频率中等

  • 处理机调度算法的目标

    • 共同

      • 资源利用率

        • CPU利用率=CPU有效工作时间/(CPU有效工作时间+CPU空闲等待时间)

      • 公平性

      • 平衡性

      • 策略强制执行

    • 批处理系统

      • 平均周转时间短

        • 平均周转时间
        • 平均带权周转时间

      • 系统吞吐量高

      • 处理机利用率高

    • 分时系统

      • 响应时间快
      • 均衡性

    • 实时系统

      • 截止时间的保证
      • 可预测性

  • 作业调度

    • 批处理系统中的作业

      • 作业 Job

        • 通常的程序和数据
        • 作业说明书
        • 从外存调入内存的基本单位（批处理系统）

      • 作业步 Job Step

        • “编译”作业步
        • “链接装配”作业步
        • “运行”作业步

      • 作业控制块 Job Control Block JCB

        • 作业标识

        • 用户名称

        • 用户账号

        • 作业类型

          • CPU繁忙型
          • I/O繁忙型
          • 批量型
          • 终端型

        • 作业状态

        • 调度信息

          • 优先级
          • 作业运行时间

        • 资源需求

          • 预计运行时间
          • 要求内存大小

        • 资源使用情况

      • 三个阶段和三种状态

        • 收容阶段 - 后备状态
        • 运行阶段 - 运行状态
        • 完成阶段 - 完成状态

    • 先来先服务调度算法

      • First-Come First-Served FCFS

      • 最简单的调度算法

      • 作业到达的先后次序（系统中等待时间最长的作业）

      • 作业调度的FCFS

        • 从后备作业队列中选择若干个最先进入该队列的作业
        • 将选择的作业调入内存，分配资源和创建进程
        • 将选择的作业放入就绪队列

      • 进程调度的FCFS

        • 从就绪进程队列中选择一个最先进入该队列的进程
        • 分配处理机，使进程投入运行
        • 直到运行完成或发生阻塞，调度程序重新分配处理机

    • 短作业优先调度算法

      • Shortest Job First SJF

      • 以作业运行时间的长短计算优先级

      • 作业调度的SJF

        • 从外存的作业后备队列中选择若干个估计运行时间最短的作业
        • 优先将选择的队列调入内存运行

      • 进程调度的SJF

      • 缺点

        • 必须预知作业的运行时间
        • 对长作业非常不利，完全忽视作业等待时间
        • 人—机无法进行交互
        • 完全未考虑作业的紧迫程度

    • 优先级调度算法

      • Priority-Scheduling Algorithm PSA

      • 作业的紧迫程度（由外部赋予作业相应的优先级）

      • 作业调度的PSA

        • 系统从后备队列中选择若干个优先级最高的作业调入内存

      • 进程调度的PSA

    • 高响应比优先调度算法

      • Highest Response Ratio Next HRRN

      • 作业的等待时间 和 作业的运行时间

      • 动态优先级=(等待时间+要求服务时间)/要求服务时间

        • =响应比R_p=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间

      • 等待时间相同时，类似于SJF，有利于短作业

      • 要求服务时间相同时，类似于FCFS

      • 长作业的优先级岁等待时间的增加而提高

      • 每次进行调度之前要先进行响应比的计算，增加系统开销

  • 进程调度

    • 主要任务

      • 保存处理机的现场信息
      • 按某种算法选取进程
      • 把处理器分配给进程

    • 调度机制

      • 排队器

      • 分派器

      • 上下文切换器

        • 第一对上下文切换

          • 保存当前进程的上下文
          • 装入分派程序的上下文

        • 第二对上下文切换

          • 移出分派程序的上下文
          • 装入新选进程的CPU现场信息至处理机的相应寄存器

    • 调度方式

      • 非抢占方式 Nonpreemptive Mode

        • 实现简单，系统开销小，适用于大多批处理系统

        • 不适用分时系统和大多实时系统

        • 引起进程调度的因素

          • 正在执行的进程执行完毕或因某事件阻塞
          • 正在执行的进程因提出I/O请求暂停执行
          • 在进程通信或同步过程中，执行了某种原语操作

      • 抢占方式 Preemptive Mode

        • 允许调度程序根据原则暂停某个正在执行的进程，并将其处理机重新分配给另一进程

        • 能实现人—机交互（分时系统），比较复杂，系统开销较大

        • 主要原则

          • 优先权原则

            • 允许新到的优先级高的抢占当前进程

          • 短进程优先原则

            • 允许新到的短进程抢占当前长进程

          • 时间片原则

            • 按时间片轮转运行时，当正在执行的进程的一个时间片用完时，停止该进程并重新调度

    • 轮转调度算法

      • Round Robin RR

      • 让就绪队列上的每个进程每次仅运行一个时间片

      • 进程切换时机

        • 一个时间片未用完，正在运行的进程已完成，立即激活调度程序，从就绪队列中删除并调度就绪队列的队首，启动一个新的时间片
        • 一个时间片已用完，计时器中断处理程序被激活，正在运行的进程未完成，调度程序送其至就绪队列队尾

      • 时间片确定

        • 时间片小

          • 频繁执行进程调度和上下文切换
          • 增加系统开销

        • 时间片大

          • RR退化为FCFS
          • 无法满足短作业和交互式用户需求

        • 合适的时间片 - 略大于一次典型的交互所需要的时间

          • 大多数交互式进程能在一个时间片内完成
          • 获得很小的响应时间

    • 优先级调度算法

      • 相比较RR，引入优先级

      • 优先级调度算法的类型

        • 非抢占式优先级调度算法
        • 抢占式优先级调度算法

      • 优先级的类型

        • 某一范围内的一个整数 - 优先数

        • 确定优先级的依据

          • 进程类型
          • 进程对资源的需求
          • 用户要求

        • 静态优先级

          • 在创建进程时确定

          • 在进程运行期间保持不变

          • 优缺点

            • 简单易行，系统开销小
            • 不够精确，可能出现优先级低的进程长期未被调度

        • 动态优先级

          • 在创建进程时赋予一个优先级
          • 在进程运行期间改变

    • 多队列调度算法

      • 将系统中的进程就绪队列拆分为若干个
      • 不同的就绪队列采用不同的调度算法

    • 多级反馈队列调度算法

      • Multilevel Feedback Queue

      • 调度机制

        • 设置多个就绪队列，每个队列赋予不同的优先级，优先级越高时间片越小
        • 每个队列都采用FCFS算法，新进程进入第一队列队尾，一个时间片结束进程未完成，调入下一队列队尾，第n队列采取RR方式
        • 按队列优先级调度

      • 性能 - 满足的用户类型

        • 终端型用户
        • 短批处理作业用户
        • 长批处理作业用户

    • 基于公平原则的调度算法

      • 必须具有的功能

        • 跟踪计算每个进程自创建以来已经执行的处理时间

        • 计算每个进程应获得的处理机时间

        • 计算进程获得处理机时间的比率

        • 比较各进程获得处理机时间的比率

        • 调度程序选择比率最小的进程并分配处理机，一直运行直至超过最接近它的进程比率

      • 保证调度算法

      • 公平分享调度算法

死锁

  • 死锁概述

    • 资源

      • 可重用性资源

        • 可供用户重复使用多次的资源

        • 其中的单元不允许多个进程共享

        • 进程使用顺序

          • 请求资源（利用系统调度实现）

            • 失败 - 被阻塞/循环等待

          • 使用资源

          • 释放资源（利用系统调度实现）

        • 每一类该资源的单元数目相对固定，运行时进程不能创建/删除

        • eg. 大多数资源

      • 可消耗性资源 - 临时性资源

        • 进程运行期间，由进程动态地创建和消耗
        • 每一类该资源的单元数目可不断变化
        • 运行时进程可不断创造单元，将它们放入资源类的缓冲区
        • 运行时进程可请求消耗若干单元，用于进程自己的消耗
        • 通常由生产者进程创建，由消费者进程消耗
        • eg. 进程间通信的消息

      • 可抢占性资源

        • 某进程在获得这类资源后，该资源可以再被其它进程或系统抢占
        • 不会引起死锁
        • CPU和主存

      • 不可抢占性资源

        • 系统把这类资源分配给某进程，就不能强行收回，只能在进程用完后自行释放

    • 死锁的起因

      • 竞争不可抢占性资源

        • 资源分配图

          • 圆圈 - 进程
          • 方框 - 资源
          • 圆圈 → 方框 - 请求
          • 方框 → 圆圈 - 分配

      • 进程推进顺序不当

        • 进程推进顺序合法 - 不会引起死锁的推进顺序
        • 进程推进顺序非法 - 引起死锁的推进顺序

    • 死锁的定义 Deadlock

      • 一组进程中的每一个进程都在等待仅由该组进程中的其它进程才能引发的事件

    • 产生死锁的必要条件（同时具备）

      • 互斥条件

      • 请求和保持条件

      • 不可抢占条件

      • 循环等待条件

    • 处理死锁的方法

      • 预防死锁
      • 避免死锁
      • 检测死锁
      • 解除死锁
      • 从上至下 - 防范程度逐渐减弱，资源利用率提高，并发程度提高

  • 预防死锁

    • 破坏“请求和保持”条件

      • 第一种协议

        • 所有进程在开始运行之前，必须一次性地申请其在整个运行过程中所需的全部资源

        • 运行过程中不再提出资源请求（破坏“请求”）

        • 资源未全就不分配，等待期间不占有任何资源（破坏“保持”）

        • 优缺点

          • 简单 易行 安全
          • 资源被严重浪费
          • 进程经常会发生饥饿现象

      • 第二种协议

        • 允许一个进程只获得运行初期所需的资源，便开始运行

        • 运行过程中释放已用完的资源，再请求新的所需资源

        • 优点

          • 进程更快完成任务
          • 提高设备利用率
          • 减少进程发生饥饿的几率

    • 破坏“不可抢占”条件

      • 一个已经保持了某些不可被抢占资源的进程，提出新的资源请求不能被满足时

      • 必须释放已经保持的所有资源，待以后需要时再重新申请

      • 缺点

        • 复杂 代价大
        • 反复申请和释放导致进程的执行无限推迟
        • 延长进程的周转时间
        • 增加系统开销
        • 降低系统吞吐量

    • 破坏“循环等待”条件

      • 对系统所有资源类型进行线性排序，赋予不同的序号

      • 规定每个进程必须按序号递增的顺序请求资源

      • 资源分配图不可能出现环路

      • 输入设备规定较低的序号，输出设备规定较高的序号

      • 优缺点

        • 资源利用率提高
        • 系统吞吐量提高
        • 序号必须相对稳定，限制新类型设备增加
        • 作业使用顺序与系统规定顺序不同，造成资源浪费
        • 限制用户编程自由度

  • 避免死锁

    • 系统安全状态

      • 系统处于安全状态时，可避免发生死锁

      • 系统处于不安全状态时，可能进入死锁状态

      • 安全状态

        • 系统能按某种进程推进顺序为每个进程分配其所需资源
        • 直至满足每个进程对资源的最大需求
        • 使每个进程都可顺利完成
        • 此时进程推进顺序为安全序列

    • 银行家算法

      • 数据结构

        • 可利用资源向量 Available

          • 含有m个元素的数组
          • 每个元素代表一类可利用的资源数目
          • 初始值是系统中所配置的该类全部可用资源的数目
          • 数值随该类资源的分配和回收动态地改变
          • Available[j] = K

        • 最大需求矩阵 Max

          • n×m的矩阵
          • 系统中n个进程中每个进程i对m类资源j的最大需求
          • Max[i, j] = K

        • 分配矩阵 Allocation

          • n×m的矩阵
          • 系统中每一类资源j已分配给每一进程i的资源数
          • Allocation[i, j] = K

        • 需求矩阵 Need

          • n×m的矩阵
          • 每一个进程i尚需的各类资源j数
          • Need[i, j] = K

        • Need[i, j] =Max[i, j] - Allocation[i, j]

      • 银行家算法

        • 进程P_i的请求向量Request_i

          • Request_i[j] = K
          • 进程P_i需要K个R_j类型资源

        • 算法描述

          • Request_i[j] <= Need[i, j] 转2 否则出错

          • Request_i[j] <= Available[j] 转3 否则等待

          • 系统试探分配

            • Available[j] -= Request_i[j]
            • Allocation[i, j] += Request_i[j]
            • Need[i, j] -= Request_i[j]

          • 系统执行安全性算法

            • 安全 - 完成分配
            • 不安全 - 转2

      • 安全性算法

        • 工作向量Work

          • 含有m个元素
          • 系统可提供给进程继续运行所需的各类资源数目

        • 判断向量Finish

          • 系统是否有足够资源分配给进程，使之运行完成

        • 算法描述

          • 初始化

            • Work = Available
            • Finish[i] = false

          • 找出满足下述条件的进程

            • Finish[i] = false
            • Need[i, j] <= Work[j]
            • 找到 转3 否则 转4

          • 进程P_i获得资源后，可顺利执行直至完成并释放资源

            • Work[j] += Allocation[i, j]
            • Finish[i] = true
            • 转2

          • 所有进程Finish[i] = true

            • 满足 - 安全状态
            • 否则 - 不安全状态

      • 举例（大题填表）

  • 死锁检测

    • 资源分配图 Resource Allocation Graph

    • 死锁定理

      • 从既不阻塞又非独立的进程结点开始简化 - 消去请求边和分配边
      • S为死锁状态的充分条件是：当且仅当S状态的资源分配图是不可完全简化的

    • 数据结构 类似 银行家算法的数据结构

      • 可利用资源向量 Available

      • 不占用资源的进程（Allocation = 0）记入L表

      • 从进程集合中找到一个Request_i <= Work的进程

        • 将其资源分配图简化
        • 释放资源
        • 增加工作向量Work += Allocation
        • 记入L表

      • 不能把所有进程都计入L表 - 状态S资源分配图不能被完全简化 - 死锁

  • 死锁解除

    • 抢占资源

    • 终止（或撤销）进程

      • 终止所有死锁进程
      • 逐个终止进程

操作系统接口

用户接口

  • 字符显示式联机用户接口

    • 命令行方式
    • 批命令方式

  • 图形化联机用户接口

    • Graphics User Interface

    • WIMP

      • Window
      • Icon
      • Menu
      • Pointing device

  • 脱机用户接口

  • 联机命令的类型

    • 系统访问类
    • 文件操作命令
    • 目录操作命令
    • 其它命令

Shell命令语言

  • 简单命令的类型

    • 进入与退出系统

    • 文件操作命令

      • cat - 显示文件内容命令

        cat filename

      • cp - 复制文件副本的命令

        cp source target

      • mv - 对已有文件改名的命令

        mv oldname newname

      • rm - 撤销文件的命令

      • file - 确定文件类型的命令

    • 目录操作命令

      • mkdir - 建立目录的命令
      • rmdir - 撤销目录的命令
      • cd - 改变工作目录的命令

    • 系统询问命令

      • date - 访问当前日期和时间命令
      • who - 询问系统当前用户的命令
      • pwd - 显示当前目录路径名的命令

  • 重定向与管道命令

    • 重定向命令

      • < - 输入转向

        wc<file3 // 把从文件file3中读出的行中的字和字符进行计数

        • 输出转向

        cat file1>file2 // 把文件file1的内容打印输出到文件file2上
        cat file4>>file2 // 除复制的file1的内容外，附加上file4的内容

      • 同时使用输入输出

        a.outfile0 // 可执行文件a.out执行时，将从文件file1中提取数据，而把a.out的执行结果数据输出到文件file0中

    • 管道命令

      • 符号“|”连接两条命令 使前一条命令的输出作为后一条命令的输入

  • 通信命令

    • mail - 信箱通信命令

      • 各用户间非交互式通信的工具
      • 发送信件/读取信件

    • write - 对话通信命令

      write user[ttyname]

      • 使用户与当前系统中的其他用户直接进行联机通信

    • mesg - 允许或拒绝接收消息命令

      mesg[-n][-y]

      • 选项n - 拒绝对方的写许可
      • 选项y - 恢复对方的写许可

  • 后台命令

联机命令接口的实现

系统调用的概念和类型

  • 系统调用的基本概念

    • 特权指令 - 在系统态运行的指令

      • 对内存空间的访问范围不受限制：用户空间和系统空间
      • 只允许OS使用，不允许应用程序使用

    • 非特权指令 - 在用户态运行的指令

      • 对内存空间的访问范围：用户空间
      • 不能对系统中的硬件和软件直接进行访问

    • 系统调用与一般的过程调用的区别

      • 运行在不同的系统状态

        • 调用程序运行在用户态
        • 被调用程序运行在系统态

      • 状态的转换

        • 软中断机制，由用户态转换为系统态，内核分析后转向相应的系统调用处理子程序

      • 返回问题

        • 优先权分析
        • 就绪队列

      • 嵌套调用

    • 中断机制

  • 系统调用的类型

    • 进程控制类系统调用
    • 文件操纵类系统调用
    • 进程通信类系统调用

UNIX系统调用

  • 进程控制

    • 进程的创建和终止

      • fork - 创建进程
      • exit - 终止进程

    • 改变进程映像和等待

      • exec - 执行一个文件
      • wait - 等待子进程结束

    • 其它进程调用

      • getpgrp - 获得调用进程的进程组ID
      • getppid - 获得调用进程的父进程ID
      • getuid - 获得真正的用户ID
      • geteuid - 获得有效用户ID
      • getgid - 获得真正用户组ID
      • pause - 进程赞同

  • 文件操纵

    • 文件的创建和删除

      • creat - 创建文件
      • 没有专门的删除文件的系统调用，无人可对文件进行删除

    • 文件的打开和关闭

      • open - 打开文件

        • 把有关的文件属性从磁盘拷贝到内存中
        • 在用户和指名文件之间简历一条快捷的通路
        • 给用户返回一个文件描述符fd
        • 用户打开后使用fd对文件进行操作

      • close - 关闭文件

        • 断开用户程序与该文件之间已经建立的快捷通路
        • UNIX中，表示已无进程再访问该文件时，才能真正关闭该文件

    • 文件的读和写

      仅当用户利用open打开指定文件后，方可调用

      • 要求用户提供三个输入参数

        • 文件描述符fd
        • buf缓冲区首址
        • 用户要求传送的字节数nbyte

      • read - 试图从fd所指示的文件中去读入nbyte个字节的数据，并将它们送至由指针buf所指示的缓冲区中

      • write - 试图把nbyte个字节数据从指针buf所指示的缓冲区中写到由fd所指向的文件中

    • 建立文件的连接和去连接

      • i.link - 文件索引结点设置的连接计数
      • link - 建立该用户（进程）与此文件之间的连接
      • unlink - 断开该用户（进程）与此文件之间的连接

  • 进程通信和信息保护

    • 进程通信

      • 消息机制
      • 共享存储器机制
      • 信号量机制

    • 信息维护

      • 设置和获得时间 - stime（超级用户）、time
      • 获得进程和子进程时间 - times
      • 设置文件访问和修改时间 - utime
      • 获得当前UNIX系统的名称 - uname

系统调用的实现

  • UNIX
  • Linux

实验内容

Linux命令

  • ls
  • ps
  • vi/vim
  • gcc
  • kill（也是系统功能调用）
  • cat
  • cp
  • mv
  • chmod
  • mail
  • grep

系统功能调用

  • fork
  • execl
  • wait
  • exit
  • sleep
  • signal
  • kill
  • getpid