• Win32 API用于Windows
• POSIX API用于POSIX-based systems(包括UNIX,LINUX,Mac OS X的所有版本)
• Java API用于JAVA虚拟机
• 函数调用：在一个栈空间完成的
• 系统调用：用户态和内核态有不同的堆栈空间，系统调用涉及到了不同堆栈空间的转换

3.1 计算机体系结构及内存分层体系

3.2 地址空间和地址生成

3.3 连续内存分配：内存碎片与分区的动态分配

• 第一分配
• 最佳分配
• 最差匹配

3.4 连续内存分配：压缩式与交换式碎片整理

4.1 非连续内存分配：分段

4.2 非连续内存分配：分页

4.3 非连续内存分配：页表-概述、TLB

4.4 非连续内存分配：页表-二级、多级页表

4.5 非连续内存分配：页表-反向页表

5.1 虚拟内存的起因

5.2 覆盖技术

5.3 交换技术

5.4 虚存技术

6.1 最优页面置换算法

6.2 先进先出算法

6.3 最近最久未使用算法

6.4 时钟页面置换算法

6.5 二次机会法

6.6 最不常用法

6.7 Belady现象、LRU、FIFO、Clock的比较

6.8 局部页替换算法的问题、工作集模型

6.9 两个全局页面置换算法

6.10 抖动问题

7.1 进程的定义

进程：一个具有一定独立功能的程序在一个数据集合上的一次动态加载的过程。

7.2 进程的组成

一个进程应该包括：

• 程序的代码
• 程序处理的数据
• 程序计数器中的值，指示下一条将运行的指令
• 一组通用的寄存器的当前值，堆、栈；
• 一组系统资源（如打开的文件）
  总之，进程包含了正在运行的一个程序的所有状态信息

7.3 进程的特点

• 动态性
• 并发性
• 独立性
• 制约性

7.4 进程控制结构

7.5 进程的生命周期管理

7.6 进程状态变化模型

7.7 进程挂起

7.8 为什么使用线程

7.9 什么是线程

进程中的一条执行流程

7.10 线程的实现

7.11 上下文切换

7.13 进程控制-加载和执行进程

7.14 进程控制-等待和终止进程

8.1 背景

8.2 调度原则

8.3 调度算法1

8.4 调度算法2

8.5 实时调度

8.6 多处理器调度与优先级反转

9.1 背景知识

9.2 一些概念part

9.3 临界区

前进、互斥、有限等待

9.4 方法1:禁用硬件中断

9.5 方法2:基于软件的解决方案

9.6 方法3:更高级的抽象

10.1 背景

10.2 信号量

10.3 信号量的使用

10.4 信号量的实现

10.5 管程

10.6 经典同步问题

11.1 死锁问题

11.2 系统模型

• 使用资源
  • 创建和销毁
  • 在I/O缓冲区的中断，信号，消息，信息
  • 如果接收消息阻塞可能会发生死锁
  • 可能少见
• 资源分配图
  • 一组
• V有两种
  • P
  • R
• requesting
• assignment/holding edge
• 进程
• 4种实例资源类型
• Pi请求Rj
• Pi分配了
• 资源分配图例子
• 资源分配图 有死锁
• 有循环的资源分配图没有死锁
• 基本情况
  • 如果图中
  • 如果图中
    • 如果每个资源类只有一个实例，那么死锁。
    • 如果

11.3 死锁特征

• 死锁可能出现如果四个条件同时成立
  • 互斥：在一个时间只能有一个进程使用资源。
  • 持有并等待：进程保持至少一个资源正在获取其他进程持有的额外资源。
  • 无抢占：一个资源只能被进程自愿释放，进程已经完成了它的任务之后。
  • 循环等待：存在等待进程集合{P0,P1,…,PN},P0正在等待P1锁占用的
• 死锁
• 没有死锁

11.4 死锁的处理方法

• 确保系统永远不会进入死锁状态。
• 运行系统进入死锁状态，然后恢复。
• 忽略这个问题，假装系统宏从来没有发生死锁；用于大多数操作系统，包括UNIX.

11.5 死锁预防和死锁避免

• 限制申请方式
  • 互斥-共享资源不是必须的，必须占用非共享资源。
  • 占用并等待-必须保证当前一个进程请求的资源，它不持有任何其他资源。
    • 需要进程请求并分配其所有资源，它开始执行之前或允许进程请求资源仅当进程没有资源。
    • 资源利用率低：可能发生饥饿。
  • 无抢占
    • 如果进程占有某些资源，并请求其它不能被立即分配的资源，则释放当前正占有的资源
    • 被抢占资源添加到资源列表中。
    • 只有当它能够
  • 循环等待
    • 对所有资源类型进行排序，并要求每个进程按照资源的顺序进行申请。
• 需要系统具有一些额外的先验信息提供
  • 最简单和最有效的模式是要求每个进程声明
  • 资源的
  • 死锁避免算法动态检查的资源分配状态，以确保永远不会有一个环形等待
  • 当
  • 系统处于安全状态指：针对所有进程，存在安全序列。
  • 序列<P1,P2,…,PN>是安全的：针对每个Pi,Pi要求的资源能够由当前可用的资源+所有的Pj持有的资源来满足，其中j<i。
    • 如果
    • 当Pi
    • 用同样的方法，Pi+2,Pi+3
• 如果
• 如果
• 避免死锁：确保系统

11.6 银行家算法

• 银行家算法是一个死锁避免的著名
• 背景
  • 在银行系统中，客户完成项目
• 前提条件
  • 多个实例
  • 每个
  • 当一个
  • 当
• 基于上述前提条件，银行家算法通过
• 银行家算法数据结构
  • n = 进程数量，m=资源类型数量。
  • Max（总需求量）
  • Available（剩余空闲量）：长度为m的向量
  • Allocation（已分配量）：
  • need（未来需要量）：n×

11.7 死锁检测和死锁恢复

• 允许系统进入死锁状态
• 死锁检测算法
• 恢复机制
• 每个资源类型单一实例
• 资源类型的几个实例
• 检测算法使用
  • 何时
    • 死锁多久可能
  • 如果检测算法多次被调用，有可能是资源图有多个循环，所以我们无法分辨出
• 终止所有的死锁进程
• 在一个时间内终止一个进程直到死锁消除
• 终止进程的顺序应该是
  • 进程的优先级
  • 进程运行了多久以及需要多少时间才能完成
  • 进程占用的资源
  • 进程完成需要的资源
  • 多少进程需要被终止
  • 进程是交互还是批处理
• 选择一个受害者-最小的成本
• 回滚-返回到一些安全状态，重启进程到安全状态
• 饥饿-同一进程可能一直被选作受害者，包括回滚的数量。

11.8 IPC概述

• 进程通信的机制及同步
• 不使用共享变量的进程通信
• IPC facility提供2个操作：
  • send - 消息大小固定
• 直接通信
  • 进程必须正确的命名对方：
    • send - 发送信息到进程P
    • receive - 从进程Q接受消息
  • 通信
• 间接通信
  • 定向从
• 通信链路的属性
  • 只有
  • 连接
  • 操作
    • 创建
    • 通过
  • 原语的定义如下：
    • send - 发送消息
• 消息传递可以是阻塞
• 阻塞被认为是同步的
• 非阻塞被认为是异步的

11.9 信号、管道、消息队列和共享内存

• 队列的消息被附加到链路；可以是以下3种方式之一：
  • 1.0容量 发送方必须等到接收方
  • 2.有限容量 发送方必须等待，如果队列满
  • 3.无线容量-无限长度 发送方不需要等待
• 信号
  • Signal(信号)
    • 软件中断通知事件处理
    • Examples:SIGFPE,SIGKILL,
  • 接收到信号时会发生什么
    • Catch:指定信号处理函数
    • Ignore:
    • Mask:闭塞信号因此不会传送
  • 不足
    • 不能传输要交换的任何数据
• 管道
  • 子进程从父进程继承文件描述符
  • 进程不知道（或不关心）从键盘，文件，程序读取或写入到终端，文件，程序。
• 消息队列
  • 消息队列按FIFO的来管理信息
    • Message:作为一个字节序列存储
    • Message Queues:消息数组
    • FIFO&FILO configureation
• 共享内存
  • 进程
    • 每个进程都有私有地址空间
    • 在每个地址空间内，明确地设置了共享内存段
  • 优点
    • 快速、方便地共享数据
  • 不足
    • 必须同步数据访问

12.0 文件系统：总体介绍

12.1 基本概念

• 文件系统和文件
• 文件描述符
• 目录
• 文件别名
• 文件系统种类

12.1.2 基本概念–文件系统和文件

• 文件系统：一种用于持久性存储的系统抽象
  • 在存储器上：组织、控制、导航、访问和检索数据
  • 大多数计算机系统包含文件系统
  • 个人电脑、服务器、笔记本电脑
  • iPod、Tivo/机顶盒、手机/掌上电脑
  • Google可能是由一个文件系统构成的
• 文件：文件系统中一个单元的相关数据在操作系统中的抽象

12.1.2.1 基本概念–文件系统和文件–文件系统的功能

• 分配文件磁盘空间
  • 管理文件块
  • 管理空闲空间
  • 分配算法
• 管理文件集合
  • 定位文件及其内容
  • 命名：通过名字找到文件的接口
  • 最常见：分层文件系统
  • 文件系统类型
• 提供的便利及特征
  • 保护：分层来保护数据安全
  • 可靠性/持久性：保持文件的持久即使发生崩溃、媒体错误、攻击等

12.1.2.2 基本概念-文件和块

• 文件属性
  • 名称、类型、位置、大小、保护、创建者、创建时间、最近修改时间、…
• 文件头

12.1.3 基本概念–文件描述符

• 文件使用模式
  • 使用程序必须在使用前先“打开”文件
• 内核跟踪每个进程打开的文件
  • 操作系统为每个进程维护一个打开文件表
  • 一个打开文件描述符是这个表中的索引
• 需要元数据数据来管理打开文件：
  • 问加指针：指向最近的一次读写位置，每个打开了这个文件的进程
  • 文件打开计数：记录文件打开的次数-当最后一个进程关闭了文件时
  • 文件磁盘位置：缓冲数据访问信息
  • 访问权限：每个程序访问模式信息
• 用户视图：
  • 持久的数据结构
• 系统访问接口
  • 字节的集合
  • 系统
• 操作系统内部视角
  • 块的集合
  • 块大小<>扇区大小；在UNIX中，块的大小是4KB
• 当用户说：给我2-12字节空间
  • 获取字节所在的块
  • 返回块内对应部分
• 如果说要写2-12字节呢？
  • 获取块
  • 修改块内对应部分
  • 写回块
• 用户怎么访问文件
  • 在系统
• 顺序访问
• 随机访问
• 基于内容访问：通过特征
  • 许多系统不提供此种访问方式，相反，数据库都是建立在索引内容的磁盘访问上
• 无结构
  • 单词、比特的队列
• 简单记录结构
  • 列
  • 固定长度
  • 可变长度
• 复杂结构
  • 格式化的文档（如，MS Word,PDF）
  • 可执行文件
  • …
• 多用户系统中的文件共享是很必要的
• 访问控制
  • 谁能够获取哪些文件的哪些访问权限
  • 访问模式：
• 文件访问控制列表（ACL）
  • <文件实体，权限>
• Unix模式
  • <用户|组|所有人，读|写|可执行>
• 指定多用户/
• Unix文件系统语义
• 会话语义
  • 写入内容只有当文件关闭时可见
• 锁
  • 一些操作系统和文件系统提供该功能

12.1.4 基本概念-目录

• 文件以目录的方式组织起来
• 目录是一类特殊的文件
  • 每个目录都包含了一张表<name,pointer to >
• 典型操作
  • 搜索文件
  • 创建文件
  • 删除文件
  • 枚举目录
  • 重命名文件
• 操作系统应该
• 文件名的线性列表，包含额
• 名字解析：
  • 在文件系统中：
  • 遍历文件
• 举例
• 当前工作目录
  • 每个进程都会指向一个文件目录用于解析文件名
• 一个文件系统需要先挂载才能被访问
• 一个未挂载的文件系统被挂载在挂载点上

12.1.5 基本概念-文件别名

• 两个或多个文件名关联同一个文件
• 硬链接：
• 软链接：以“快捷方式”指向其他文件
• 通过存储真实文件的逻辑名称来实现
• 如果删除一个有别名的文件会
  • 这个别名将成为一个“悬空指针”
• Backpointers方案：
  • 每个文件有一个包含多个backpointers的列表

12.1.6 基本概念-文件系统种类

• 磁盘文件系统
• 数据库文件系统
• 日志文件系统
• 网络/分布式文件系统
  • 例如：NFS,SMB,AFS,GFS
• 特殊/虚拟文件系统
• 分布式文件系统的问题
  • 客户端和客户端上的用户辨别起来很复杂
  • 例如，NFS是不安全的
  • 一致性问题
  • 错误处理模式

12.2 虚拟文件系统

• 分层结构
  • 上层：虚拟（逻辑）文件系统
  • 底层：特定文件系统模块
• 目的
• 功能
  • 提供相同的文件
• 卷控制块
• 文件控制块
  • 每个文件一个
  • 文件详细信息
  • 许可、拥有者、大小、数据库位置等
• 目录节点
  • 每个目录项一个（目录和文件）
  • 将目录项数据结构及树型布局编码
• 文件系统数据结构
• 持续存储在二级存储中
• 当需要时加载进内存
  • 卷控制模块：当文件系统挂载时进入内存
  • 文件控制块：当文件被访问

12.3 数据块缓存

• 数据块按需读入内存
• 数据块使用后被缓存
• 两种数据块缓存方式
• 文件数据块的页缓存

12.4 打开文件的数据结构

• 打开文件描述
  • 每个被打开的文件一个
  • 文件状态信息
  • 目录项、当前文件指针、文件操作设置等
• 打开文件表
  • 一个进程一个
  • 一个系统级的
  • 每个卷控制块也会保存一个列表
  • 所以如果有文件
  • 一些操作系统和文件系统提供该功能
  • 调节对文件的访问。
  • 强制和劝告：
    • 强制 -
    • 劝告

12.5 文件分配

• 大多数文件都很小
• 一些文件非常大
• 如何为一个文件分配数据块
• 分配方式
  • 连续分配
• 文件头指定起始块和长度
• 位置/分配策略
• 优势
  • 文件读取表现好
  • 高效的顺序和随机访问
• 劣势
  • 碎片
  • 文件增长问题
    • 预分配
    • 按需分配
• 文件以数据块链表方式存储
• 文件头包含了第一块和最后一块的指针
• 优点
  • 创建、增大、缩小很容易
  • 没有碎片
• 缺点
  • 不可能进行真正的随机访问
  • 可靠性
    • 破坏一个链然后…
• 为每个文件创建一个名为索引数据块的非数据数据块
  • 到
• 文件头包含了索引数据块
• 优点
  • 创建、增大、缩小很容易
  • 没有碎片
  • 支持直接访问
• 缺点
  • 当文件很小时，存储索引的开销
  • 如何处理大文件？
• 链式索引块
• 多级索引块
• 文件头包含13个指针
  • 10个指针指向数据块；
  • 第11个指针指向简介
• 影响

12.6 空闲空间列表

• 跟踪在存储中的所有
• 空闲空间列表
• 用位图代表空间数据块列表：
  • 111111111
  • 如果i=0表明数据块i是空闲，反之则已分配
• 使用简单但是可能会是一个big vector:
• 需要保护：
  • 指向空闲列表的指针
  • 位图

12.7 多磁盘管理-RAID

• 通常磁盘通过分区来最大限度减少寻道时间
  • 一个分区是一个柱面的集合
  • 每个分区
• 分区：硬件磁盘的一种适合操作系统指定格式的划分
• 卷：一个拥有一个文件系统实例的可访问的存储空间
  • 通常常驻在磁盘的单个分区上
• 使用多个并行硬盘拉增加
• RAID-冗余磁盘阵列
  • 各种磁盘管理技术
  • RAID levels:不同
• 实现
  • 在操作系统内核：存储/卷管理
  • RAID硬件控制器(I/O)
• 数据块分成多个子块，存储在独立的磁盘中
  • 和内存交叉相似
• 通过更大的有效块大小来提供更大的磁盘带宽
• 可靠性成倍增长
• 读取性能线性增加
  • 向两个磁盘写入，从任何
• 数据块级磁带配有专用
• 条带化和
• RAID 0+1
• RAID 1+0

12.8 磁盘调度

• 读取或写入时，磁头必须被定位在期望
• 寻道
• 访问时间
• 寻道时间
• 旋转延迟
• 传输时间
• 传输的比特数
• 磁道上的比特数
• 寻道时间是细能上区别的
• 对单个磁盘
• 如果请求是随机的，那么会表现很差
• 按顺序处理请求
• 公平对待所有进程
• 选择从磁臂当前位置需要移动最少的I/O请求
• 总是选择最短寻道时间
• 磁壁在一个方向上移动，满足所有为完成的请求，直到磁壁到达该方向最后的磁盘
• 调换方向
• 有时被称为ele
• 限制了仅在一个方向上的扫描
• 当最后一个磁盘也被访问过了后，磁壁返回到磁盘的另外一端再次进行扫描
• C-SCAN的改进版本
• 磁壁先到达该方向上最后一个请求处，然后立即反转
• 在SSTF
• N-Step-SCAN算法是将磁盘请求队列分成若干个长度为N的子队列
• 当正在处理某子队列时，如果又出现新的磁盘I/O请求

lab0-part1