基于恐龙书和苏大ppt的操作系统笔记

发表于 更新于 分类于 ， 阅读次数： 本文字数： 19k 阅读时长 ≈ 1:08

概论

计算机系统可以分为四个部分  
硬件(Hardware) – 提供基本的计算资源  
CPU, memory, I/O devices  
操作系统(Operating System)  
控制和协调各用户的应用程序对硬件的使用  
应用程序(Application programs) – 规定了用户按何种方式使用系统资源  
字处理程序, 编译器, 网络浏览器, 数据库系统, 视频游戏  
用户(Users)  
人, 机器, 其他计算机  
操作系统的目标:  
运行用户程序  ---核心目标  
更方便使用计算机 ---面向用户  
更高效使用计算机 ---面向系统

计算机启动时，会启动引导程序，来初始化系统的各个组件，加载操作系统并开始执行
操作系统加载到内存后，开始为系统和用户提供服务，成为系统进程或者后台程序该阶段完成后系统完全启动并且等待事件发生。
事件发生通过”中断“机制来通知，cpu被中断时，停止正在做的事，并立即转到固定位置继续执行中断服务程序，执行完后继续执行被中断的计算

  • 中断：指当出现需要时，CPU暂时停止当前程序的执行，转而执行处理新情况的程序和执行过程
  • 中断号：外部设备进行I/O操作时产生的中断信号，发送给CPU
  • 中断向量：中断服务程序的入口地址
  • 中断服务程序：执行中断处理的代码
  • 陷阱(trap):是由于出错或用户请求引起的软件生成的中断
    操作系统是中断驱动
在冯·诺依曼体系结构( von Neumann architecture)上执行时，一个典型的指令执行周期是，首先从内存中获取指令，并存到指令寄存器( instruction register)。接着，该指令被解码，也可能会从内存中获取操作数据并且存到内部寄存器。在指令完成对操作数据的执行后，结果也可存到内存。注意:内存单元只能看到内存地址的流，而并不知道它们如何产生(通过指令计数器、索引、间接、常量地址或其他方式)或它们是什么样（指令或数据）的地址。相应地，我们可以忽略程序如何产生内存地址，而只关注由程序运行所生成的地址序列。

集群系统

由两个或多个独立的系统耦合起来
共享数据 storage-area network (SAN)。
提供高可用性。
›一定的冗余
非对称集群(Asymmetric Clustering)：一台机器运行应用程序，而其他机器处于热备份模式。
对称集群(Symmetric Clustering)：多个主机都运行应用程序
提供high-performance computing (HPC)
用专门的应用程序利用集群，并行计算parallelization

多道程序设计：在内存中同时存在多道作业，在管理程序控制下相互穿插运行  
通过作业调度(Job Scheduling)选中一个作业并运行  
当该作业必须等待时 (如等待I/O), 切换到另一个作业  
目的:提高CPU的利用率，充分发挥计算机系统部件的并行性

分时系统：控制响应时间较短，使计算机可交互，›一般采用时间片轮转方式使一台计算机为多个用户服务
并行：两个或者多个作业在同一时刻运行
并发：两个或多个作业在同一时间间隔内依次运行
双重模式：允许OS保护自身和其他系统部件
用户模式(user mode)和内核模式(kernel mode)，由硬件提供模式位
特权指令：可能引起系统崩溃的指令，只能运行在内核模式

如果操作系统不能获得CPU控制权，就无法管理系统  
eg.用户程序死循环，用户程序不调用系统调用  
解决方法：定时器  
在一段时间后发生中断，CPU控制权返回操作系统  
固定时间和可变时间定时器  
利用时钟和计数器实现

I/O保护
防止用户程序执行非法I/O
解决方法：所有I/O指令都是特权指令
用户程序通过系统调用进行I/O操作
内存保护
防止内存非法访问
解决方法：存储保护机制
硬件支持
程序运行必须的存储设备
CPU只能直接访问寄存器、高速缓存和内存
处理前和处理后的所有数据都在内存
执行的指令都在内存
内存管理：提供内存的分配、回收、地址转换、共享和保护等功能
提高内存利用率
提高内存访问速度
从而提高计算机运行效率

操作系统服务提供对用户很有用的函数:

  • 用户界面 – 所有的操作系统都有用户界面(UI)
    形式有命令行界面(CLI)、图形用户界面(GUI)、批界面

  • 程序执行 – 系统必须能将程序转入内存并运行程序。程序必须能结束执行，包括正常或不正常结束（指明错误）

  • I/O 操作 -  运行程序可能需要I/O,这些I/O可能涉及文件或设备.

  • 文件系统操作 -  文件系统特别重要。很明显，程序需要读写文件和目录，创建和删除文件，搜索文件，列出文件信息，访问管理

  • 通信 – 进程间可能需要交换信息，发生同一台计算机运行的进程间或由网络连接的不同计算机上的进程间(消息传递和共享内存)
    通信可以通过共享内存或消息交换技术来实现 (消息包由OS移动)

  • 错误检测 – OS 需要知道可能出现的错误
    错误可能发生在CPU 或内存硬件、I/O设备和用户程序中
    对于每种类型的错误，OS 应该采取适当的动作以确保正确和一致的计算
    调试工具可以在很大程度上加强用户和程序员有效使用系统的能力

层次结构：操作系统划分为若干层，在低层上构建高层，底层（0层）为硬件，最高层（ N层）为用户层，每层只使用低层次的功能和服务
优点
›简化了系统设计和实现，便于调试和升级维护
缺点
层定义困难，效率差
微内核：
问题：内核越来越大，越来越难管理
内核微型化：核内移出尽可能多功能到用户空间
好处:
便于扩充，便于移植操作系统到新架构系统上，更稳定 (更少的代码运行在核心态)，更安全
坏处:
用户空间和内核空间通信的系统开销增加
解决方法：提出消息传递机制
模块化：
大部分现代操作系统采用模块结构(Linux, Solaris)
使用面向对象方法
每个核心部件分开
每个与其他模块的会话被称为接口
每个模块在需要时被加载到内核
总体而言，类似于分层方法，但更灵活

一个程序可对应一个或多个进程，同样一个进程可对应一个或多个程序  
程序是进程的代码部分  
进程是活动(active)实体，程序静止（被动passive）实体  
进程在内存，程序在外存

进程控制块(Process Control Block) PCB包含同进程有关的信息，包括： 进程状态 程序计数器 CPU寄存器 CPU调度信息 内存管理信息 计账信息 I/O状态信息

图片
进程调度队列：
作业队列 - 在系统中的所有进程的集合
就绪队列 - 在主内存中的，就绪并等待执行的所有进程的集合
设备队列 - 等待某一I/O设备的进程队列
在各种队列之间进程的迁移
进程终止：

  • 进程执行最后一项并退出（exit）
    从子进程向父进程输出数据（通过wait）
    操作系统收回进程的资源
    父进程可中止子进程的执行（ abort）
  • 子进程超量分配资源
    赋予子进程的任务不再需要
    若父进程终止，一些系统不允许子进程继续存在
    所有子进程终止-- 级联终止
  • 父进程可以等子进程结束
    调用wait()系统调用
    进程通信
消息传递在微内核中的应用  
远程通信无法采用共享内存  
  
发送send(message) - 固定或可变大小消息  
接收receive(message)  
若P与Q要通信，需要:  
建立通信连接  
通过send/receive交换消息  
通信连接的实现  
物理的（如，共享存储，硬件总线）  
逻辑的（如，逻辑特性）  
消息传递可阻塞（blocking）或非阻塞（non-blocking）  
阻塞-同步  
阻塞send：发送进程阻塞，直到消息被接收  
阻塞receive：接受者进程阻塞，直到有消息可用  
非阻塞-异步  
非阻塞send：发送进程发送消息并继续操作  
非阻塞receive: 接收者收到一个有效消息或空消息  
如果通过信箱，则可分为直接和间接通信

线程（轻型进程lightweight process, LWP ）是CPU使用的一个基本单元，包括

  • 线程ID
  • 程序计数器
  • 寄存器集
    栈空间
    一个线程与它的对等线程共享：
  • 代码段
  • 数据段
  • 操作系统资源
    总体作为一个任务
    多线程的优点：
  • 响应性
  • 资源共享
  • 经济
  • 可伸缩性：可在多处理核上并行运行
调度  
线程是调度的基本单位，同一进程中的线程切换不会引起进程切换。  
并发  
线程可以提高系统的并发性。  
资源  
进程拥有资源，是资源分配的基本单位，而线程则不拥有资源，但它可以访问创建它的进程所拥有的资源  
上下文切换  
线程的上下文切换的代价比进程小。

可分为数据并行和任务并行
图片
图片
图片
//S是应用程序的一部分，N是它在N个处理器上串行运行
线程的分类：

  • 用户线程：由用户线程库进行管理的线程
    内核看不到用户线程
    用户线程的创建和调度在用户空间中，不需要内核的干预
    应用于传统的只支持进程的操作系统
  • 内核线程：内核进行管理的线程
    需要内核支持
    由内核完成线程调度
    由内核进行创建和撤销
    多线程模型的分类：
  • 多对一模型：
    不支持内核线程的操作系统
    内核只有进程
    内核只看到一个进程
    多个线程不能并行运行在多个处理器上
    进程中的用户线程由进程自己管理
    进程内线程切换不会导致进程切换
    一个线程的系统调用会导致整个进程阻塞
  • 一对一模型
    用于支持线程的操作系统
    用户线程一对一映射到内核线程
    操作系统管理这些线程
    并发性好：多个线程可并行运行在多个处理器上
    内核开销大
  • 多对多模型：
    多个用户线程映射为相等或更小数目的内核线程
    并发性和效率兼顾
    增加复杂度
    线程库
    为程序员提供API来创建和管理线程
    两种模式：
  • 用户库（用户线程）
    存在于用户空间
    没有内核支持
    调用线程库不会产生系统调用
  • 内核库（内核线程）
    存在于内核
    操作系统支持
    调用线程库会产生系统调用
    隐式线程：在编译或者运行的时候由编译器或者运行库决定而不是编程者
    线程池：在池中创建一批线程，等待任务
    优点：
    利用线程池中的线程来响应请求比创建一个线程更加快速
    允许一个应用程序中的线程数量达到线程池的上限
    大中央调度:
    Apple 技术用于Mac OS X 和 iOS
    扩展C, C++ languages, API, 和 run-time library
    允许辨认可并行区段
    管理线程的大多数细节
    块格式“^{ }” -   ˆ{ printf("I am a block"); }
    块放置在调度队列中
    在线程池中有可用的线程的时候离开队列
    线程撤销在完成前终止线程
    要取消的线程称为目标线程 target thread
    大体两种方法:
    异步取消Asynchronous cancellation 立刻终止目标线程
    延迟取消Deferred cancellation 允许目标线程周期性检查它是否应该被终止
    调度程序激活
  • 通常用一种中间数据结构在用户和内核线程间 – 轻量级进程 lightweight process (LWP)
    类似虚拟处理器
    每个 LWP 和内核进行相连
    一定数量的LWP
  • 调度器激活提供 upcalls – 一种线程库中内核使用upcall处理句柄 upcall handler 来告知特定事件
    图片
    这种通讯允许一个应用程序保持正确数目的内核线程

需要调度的四种情况

  • 进程从运行状态切换到等待状态
  • 进程从运行切换到就绪状态（eg.出现中断）
  • 进程从等待状态切换到就绪状态(eg.IO完成)
  • 进程终止时
    调度只发生在1，4情况下是非抢占调度
    非抢占调度 ›一旦把CPU分配给某进程后，系统不可以抢占已分配的CPU并分配该其它进程 只有进程自愿释放CPU，才可把CPU分配给其他进程 优点：易实现，调度开销小，适合批处理系统 缺点：响应时间长，不适合交互式系统抢占调度
    ›调度程序可根据某种原则暂停某个正在执行的进程，将已分配给它的CPU重新分配给另一进程
    可防止单一进程长时间独占CPU
    系统开销大
    抢占式与非抢占式的区分
    运行进程是否是自愿放弃CPU
    长程调度 又称作业调度、高级调度 “新建”状态转换到“就绪”状态 ›由调度程序选择 ›控制多道程序的“道/度”（Degree）短程调度
    又称CPU调度、低级调度
    调度程序选择下一个执行进程
  • 切换频率
    短程调度切换频率高
    长程调度切换频率低
  • 切换开销
    短程调度开销小(milliseconds，切换快)
    长程调度开销大(seconds/minutes，切换慢)
  • 操作系统中应用
    短程调度：必需
    长程调度：可选
    中程调度
    又称交换
    将进程在内存和外存间换进换出
    目的：节省内存空间
    就绪队列 - 在主内存中处于就绪状态并等待执行的所有进程集合
    设备队列 - 等待某一I/O设备的进程队列
    进程的执行过程实际上就是进程在各种队列之间的迁移
    基本指标
  • CPU利用率 – 固定时间内CPU运行时间的比例
  • 吞吐量 – 单位时间内运行完的进程数
  • 周转时间 – 进程从提交到运行结束的全部时间
  • 等待时间 – 进程等待调度（不运行）的时间片总和
  • 响应时间 – 从进程提交到首次运行[而不是输出结果]的时间段，也就是第一段的等待时间

进程调度

等待时间=开始处理时间-到达时间
周转时间=等待时间+处理时间

先来先服务-FCFS

优点：实现简单
缺点：长进程在前会使多个短进程等待过久，增加平均等待时间

短作业优先-SJF

SJF是最优的 – 对一组指定的进程而言，它给出了最短的平均等待时间

抢占式调度

有比当前进程所需时间更短进程到达时，更换目前进行进程
常用于长进程调度，缺点在于进程的cpu区间难以估计
通常用指数平均估计

非抢占式调度

进程只在结束后让出cpu

优先级调度

基于进程紧迫程度赋予优先级，cpu分配给最高优先级进程
优点
实现简单，考虑了进程的紧迫程度
灵活，可模拟其它算法

  • 静态优先级
    进程创建时确定，运行期间不变
  • 动态优先级
    优先级随着进程推进或者等待时间增加而改变

问题

  • 饥饿：低优先级进程可能永远无法运行
  • 老化：视进程等待时间延长提高优先级

响应比高者优先调度

响应比=（开始时间-到达时间）/运行时间

  • 如等待时间相同，运行时间越短，优先级越高，类似于SJF
  • 如运行时间相同，优先级取决于其等待时间，类似于FCFS
  • 长进程的优先级可随等待时间的增加而提高，最终可得到服务
  • 缺点：每次调度之前，都需要计算响应比，增加系统开销

轮转调度-RR

将较小的时间单元定义为时间片，就绪队列为循环队列，调度程序循环整个队列，为每个进程分配不超过一个时间片的cpu

多级队列调度

进程分为前台进程（交互进程）和后台进程（批处理进程）
不同类型的进程需要不同策略
交互进程需要短的响应时间
批处理进程需要短的等待时间
›多级队列梯度系统中存在多个就绪队列，每个队列有自己的调度算法

多级反馈序列-MLFQ

(MultiLevel Feedback Queue Scheduling)
多级队列的延伸
不同：

  • 多级队列：进程不能在不同队列间移动
  • 多级反馈队列：进程能在不同队列间移动
  • 多级反馈队列调度需要考虑以下问题：
    队列数
    每一队列的调度算法
    决定进程升级（低级队列到高级队列）的方法
    决定进程降级（高级队列到低级队列）的方法
    决定新进程将进入哪个队列的方法
    `最常用的调度算法
eg.  
Q0-RR时间片8ms  
Q1-RR时间片16ms  
Q2-FCFS

缺点：优先级一开始确定，无法调整

线程调度

区别用户层和内核层
调度线程而不是进程
多对多和多对一模型，线程库在可用的LWP上调度用户层线程
process-contention scope (PCS) 在进程中进行调度竞争
通常由程序员通过优先级设置
内核线程通过system-contention scope (SCS) 在CPU上调度– 系统中统一竞争
一对一模型仅使用SCS，如Windows， Linux

局部调度

[[线程库]]决定哪个线程列入轻量级进程LWP

全局调度

内核决定下一个运行的内核线程

多处理器调度

调度类似单处理器，但需要将任务平均分配

对称多处理器-SMP

单队列多核调度方法(SQMP)

系统有一个就绪队列。当任意一个CPU空闲时，就从就绪队列中选择一个进程到该CPU上运行
优点：
容易从单核调度算法推广到多核/多处理器、
实现简单，负载均衡
缺点：
不具有亲和性
加锁问题

多队列调度方法(MQMP)

系统有多个就绪队列，一般每个CPU一个。每个就绪队列有自己的调度算法，并且每个就绪队列的调度相对独立
优点：
亲和性好
不需要加锁
缺点：
负载不均衡
策略：“偷”进程
每个处理器决定自己调度方式 定期检测每个cpu负载，分配任务给空闲处理器亲和性：进程倾向于在给定cpu上运行

  • 软亲和性：不强制禁止迁移
  • 硬亲和性：禁止迁移

单队列调度

共享队列，分配给不同cpu
不具有亲和性

多队列调度

不同cpu有各自队列
优点：亲和性较好，不需要加锁
缺点：负载不均匀

非对称处理器-ASMP

仅一个处理器处理系统数据结构，减轻共享需求

实时cpu调度

  • 软实时系统：不保证调度关键实时进程
  • 硬实时系统：任务必须在截止期限前完成
    对实时调度，必须支持抢占式、优先级调度
    但仅仅支持软实时
    对硬实时必须提供满足截止时间的能力
    需要调度进程的新特性：
    周期性 periodic 定期需要CPU
    有进程时间 t, 截止时间 d, 周期 p
    0 ≤ t ≤ d ≤ p
    周期任务的速率Rate 1/p

单速速度调度

依照周期倒数分配一个优先级
优点：最大化cpu利用率
缺点：不保证每个进程都赶上截止期限(周期内执行不完)

最早截止期限优先调度-EDF

根据截止时间分配优先级
越早截止期限，优先级越高

比例分享调度

所有应用中分配T股，确保所有进程有固定的cpu时间，如果新加入进程大于T股剩余量，则不允许进入

实例

linux

  • 实时任务有静态优先级（友好值）
  • 抢占式
    没有真正的线程

windows

  • 抢占调度
  • 优先级

对共享数据的并发访问可能导致数据的不一致性，需要保证并发进程正确执行顺序的机制
竞争条件：多个进程并发访问同一共享数据

  • 同步：协调执行次序
  • 互斥：进程排他性运行，可以独占资源
    临界资源：›一次只允许一个进程使用的资源，又称互斥资源、独占资源或共享变量
    共享资源：一次允许多个进程使用的资源

临界区

  • 互斥：临界区执行的进程排斥其他进程（有相同临界资源）
  • 进步:临界区无进程执行，不能无限期延长下一个需要临界区进程的等待时间
  • 优先等待：一个进程进入临界区时，其他进程进入临界区有次数限制
  • 进入区：互斥
  • 退出区：有空让进
  • 每个临界区不能过大：有限等待
    空闲则入：其他进程均不处于临界区；
    忙则等待：已有进程处于其临界区；
    有限等待：等待进入临界区的进程不能"死等"；
    让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）
Peterson算法  
do {  
  
  flag [i]:= true;    
  turn = j;    
  while (flag [j] and turn == j) ;  
  
  critical section  
  
  flag [i] = false;  
  
  remainder section  
  
  } while (1);

锁

acquire() {    
       while (!available)  
          ; /* busy wait */  
       available = false;;  
    }  
   release() {  
       available = true;  
    }  
   do {  
  
    acquire lock  
  
       critical section  
  
    release lock  
  
      remainder section  
  
 } while (true);

互斥锁（自旋锁）

原子执行acquire(),release()
acquire：while(!available) waiting;
available=false
release:available=false

面包店算法

  • 在进入临界区前，每个进程接收一个号码。具有最小号码的进程进入临界区。
  • 如果进程Pi和Pj接收到同样的号码，如果i < j ，则Pi先得到服务，否则Pj先得到服务。
  • 这种号码方案总是以递增序列产生号码；如： 1,2,3,3,3,3,4,5...
do {  
  choosing[i] = true;  
  number[i] = max(number[0], number[1], …, number [n – 1])+1;  
  choosing[i] = false;  
  for (j = 0; j < n; j++) {  
  while (choosing[j]) ;  
  while ((number[j] != 0) && (number[j,j] < number[i,i])) ;  
  }  
  critical section  
  number[i] = 0;  
  remainder section  
} while (1);

信号量（软件解决方案）

  • 保证多个代码段不被并发调用
  • 进入关键代码段前，进程必须获取信号量，否则不能运行
  • 执行完关键代码段，必须释放信号量
  • 信号量有值，说明空闲，为负说明忙碌
信号量S – 整型变量  
提供两个不可分割的[原子操作]访问信号量  
wait (S):  
     while S<= 0 do no-op;    
     S--;    
signal(S):  
     S++;  
wait (S)又称为P(S)  
signal(S)又称为V(S)

`分类

  • 计数信号量：没有限制的整型值›计数信号量=同步信号量
  • 二值信号量：0 || 1 ›二值信号量=互斥信号量
    `使用
    必须取一次且仅有一次初值
    初值不为负
    除了初始化，只能通过执行P、V操作来访问S
例子：P1  和 P2 需要 C1 比C2先运行  
       semaphore s=0  
P1:  
   C1;  
   signal(s);  
  
P2:  
   wait(s);  
   C2;

死锁 – 两个或多个进程无限期地等待一个事件的发生，而该事件正是由其中的一个等待进程引起的.
P0  P1
  P(S);  P(Q);
  P(Q);  P(S);
  V(S);  V(Q);
  V(Q)  V(S);
饥饿 – 无限期地阻塞。进程可能永远无法从它等待的信号量队列中移去.

实例

生产者消费者问题

生产者 把产品放入指定缓冲区 in:所有的生产者对in指针需要互斥 counter：所有生产者消费者进程对counter互斥消费者
从指定缓冲区取出产品
out:所有的消费者对out指针需要互斥
counter：所有生产者消费者进程对counter互斥

buffer[in] = nextProduced;  
in = (in + 1) % BUFFER_SIZE;  
counter++;  
  
nextConsumed = buffer[out];  
out = (out + 1) % BUFFER_SIZE;  
counter--;  
  
生产者：  
 {  
  …  
  生产一个产品  
  …  
  wait(empty);  
  wait(m);  
   …  
  C1：把产品放入指定缓冲区  
   …  
  signal(m);  
  signal(full);  
  }  
  
消费者：  
 {  
  …  
  wait(full)；  
  wait(m);  
   …  
  C2：从指定缓冲区取出产品  
   …  
  signal(m);  
  signal(empty);  
   …  
  消费取出的产品  
   …  
  }

`同步分析

  • 找出需要同步的代码段
  • 分析片段执行顺序
  • 增加同步信号量并赋初始值
  • 关键代码前后加wait和signal操作
    `生产者
  • 判断是否能获得空缓冲区，否则阻塞
  • 满缓冲区数量++，如果有消费者由于等待阻塞，唤醒该消费者
    `消费者
  • 判断能否获得满缓冲区，否则阻塞
  • 空缓冲区数量++，如果有生产者等待，唤醒该生产者

读者写者问题

两组并发进程读者和写者,共享一组数据区进行读写
`要求

  • 允许多个读者同时读
  • 不允许读者、写者同时读写
  • 不允许多个写者同时写
    `读者
  • 无读者写者，新读者可读
  • 有写者等，其他读者读，新读者可读
  • 有写者写，新读者等
    `写者
  • 无读者写者，新写者可写
  • 有读者读，写者等
  • 有其他写者，写者等待
增加一个读者计数器rc，设置初始值为0；  
读者：Repeat  
P(mutex);  
readcount:=readcount+1;  
if readcount=1  
then P (w);  
V(mutex);//mutex为互斥信号量，初始值为1  
读  
P(mutex);  
readcount:=readcount-1;  
if readcount=0  
then V(w);  
V(mutex);  
Until false  
  
  
Writers  
……  
P(W);  
写  
V(W);  
…...

`问题：写者可能饥饿

  • 读者写者互斥，写者直到读者count为0才进入进程

哲学家就餐问题

5个哲学家、5根筷子，每个哲学家左右各有一根筷子，每个哲学家只有拿起左右两个筷子才能吃饭
五个元素数组储存筷子，对每个哲学家有拿起左右筷子，放下左右筷子的函数
`防止死锁

方法1

最多允许四个哲学家同时坐在桌子周围

semephore *chopstick[5];   //初始值为1  
semaphore *seat;  //初始值为4  
哲学家 i:  
  ……  
  P(seat);  //看看4个座位是否有空  
  P(chopStick[i]);  //拿左边筷子  
  P(chopStick[(i + 1) % 5]);  //拿右边筷子  
   吃饭  
   V(chopStick[i]);  //放下左边筷子  
   V(chopStick[(i + 1) % 5]);  //放下右边筷子  
   V(seat);  //释放占据的位置
  • 左右筷子都可用时才拿起筷子
  • 非对称解决，单号哲学家优先拿左边筷子，双号优先拿右边
方法2

仅当一个哲学家左右两边筷子都可用时，才允许他拿筷子
哲学家分为三个状态thinking,hungry,eating
设置5个信号量代表所有哲学家，仅当自身hungry且左右都不在吃饭时才开始eating

void test(int i);  
    {  
        if (state[i] == hungry) &&  //是否饿了  
          (state[(i+4)%5]!=eating) && //左边哲学家是否在吃饭  
          (state[(i+1)%5]!=eating)  //右边哲学家是否在吃饭  
          {  
                 state[i]=eating;  //设置哲学家状态为eating  
                 V(ph[i]);  //ph[i]设置为1  
           }       
     }  
     state[i]=hungry；  
            P(m);  
            test(i);  
            V(m);  
            P(ph[i]);
方法3

›给所有哲学家编号，奇数号哲学家必须首先拿左边筷子，偶数号哲学家则反之

信号量总结

S>0：有S个资源可用
S=0：无资源可用
S<0：则|S|表示S等待队列中的进程个数
P(S)：申请一个资源
V(S)：释放一个资源
互斥信号量初始值：一般为1
同步信号量初始值：0-N
`P、V操作成对出现
互斥操作：P、V操作处于同一进程内
同步操作：P、V操作在不同进程内
两个一起的P操作的顺序至关重要
同步与互斥P操作一起时，同步P操作要在互斥P操作前
两个V操作的次序无关紧要

缺点：同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）
易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序；
不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；
正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；

管程

一个管程定义了一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据
封装数据以及对数据的操作
确保每次只要一个进程在管程内活动
互斥 管程中的变量只能被管程中的操作访问 任何时候只有一个进程在管程中操作 类似临界区 由编译器完成同步
条件变量
唤醒和阻塞操作
x.wait(): 进程阻塞直到另外一个进程调用x.signal()
x.signal()：唤醒另外一个进程

问题

管程内可能存在不止1个进程
如：进程P调用signal操作唤醒进程Q后
存在的可能
P等待直到Q离开管程 （Hoare）
Q等待直到P离开管程（Lampson & Redll，MESA语言）
P的signal操作是P在管程内的最后一个语句 (Hansen，并行Pascal)

内存概念

  • 程序必须装入内存才能被执行
  • CPU可以直接访问的存储器只有主存和寄存器
  • 寄存器通常可以在一个（或少于一个）CPU时钟周期内完成访问
  • 完成主存访问可能需要多个CPU时钟周期
  • CPU暂停（Stall）：在读取内存数据时，CPU空闲
  • Cache 位于主存和CPU寄存器之间，协调速度差异
  • 内存保护需要保证正确的操作
  • 基址寄存器（ Base）：进程最小的合法物理内存地址
  • 界限寄存器（Limit）：进程地址的长度
  • CPU在执行指令时，需要进行地址合法性验证
    给进程提供一段地址：基地址寄存器（最小地址）和界限地址寄存器（地址范围）
    物理地址对进程是隐藏的
    地址绑定（程序加载地址）：可以静态绑定也可以动态绑定，动态绑定生成可重定位代码
    动态加载，所有程序以可重定位格式存储在磁盘，只有在调用时才被加载
    动态链接和共享库:每个库程序都有一个存根，指出如何定位内存驻留库程序，或者程序不在内存时如何家在程序，执行存根时检查程序是否在内存，若不是，则加载程序到内存

地址绑定

地址绑定（重定位）：把程序中的相对地址转换为内存中的绝对地址的过程
指令和数据绑定到内存地址可在三个不同阶段：
›编译时期（ Compile time） 如果内存位置已知，可生成绝对代码 如果开始位置改变，需要重新编译代码加载时期（ Load time）
如果存储位置在编译时不知，则必须生成可重定位（ relocatable ）代码
›`执行时期（ Execution time）
如果进程执行时可在内存移动，则地址绑定可延迟到运行时
需要硬件对地址映射的支持（例如基址和限长寄存器）
大部分操作系统用这个方法

逻辑地址和物理地址

逻辑地址空间的概念同物理地址空间相关联，它是正确内存管理的中心
逻辑地址Logical address
由CPU产生
在进程内的相对地址
也称：虚拟地址、程序地址
物理地址Physical address
内存地址
所有内存统一编址
也称：绝对地址、实地址

内存管理单元

把虚拟地址映射到物理地址的硬件
是CPU用来管理内存的控制线路
在MMU策略中，基址寄存器中的值在其送入内存的时候被加入到由一个用户进程所产生的每个地址中
用户程序所对应到的是逻辑地址，物理地址对它从来都不可见

动态加载和链接

加载 例程在调用之前并不加载 更好的内存空间利用率 没有被使用的例程不被载入 当需大量代码来处理不经常使用的功能时非常有用链接
和各种库文件的链接被推迟到执行时期
需要动态装载技术支持
一小段代码 - 存根，用来定位合适的保留在内存中的库程序
存根用例程地址来替换自己，并开始执行例程
操作系统需要检查例程是否在进程的内存空间，所以需要操作系统支持

交换

一个进程可以暂时被交换（swap）到内存外的一个备份区，随后可以被换回内存继续执行。
备份区—是一个固定的足够大的可以容纳所有用户内存映像拷贝的快速磁盘；必须提供对这些内存映像的直接访问。

滚入，滚出(Roll out, roll in )—交换由于基于优先级的算法而不同，低优先级的进程被换出，这样高优先级的进程可以被装入和执行。  
交换时间的主要部分是转移时间，总的转移时间直接同交换的内存的数量成比例。  
在许多系统如：UNIX，Linux，Windows中，可以找到一些被修正过的交换措施。  
系统维持一个就绪队列，它包括在备份存储或在内存中准备运行的所有进程

连续内存分配

为一个用户程序分配一个连续的内存空间

  • 单一连续分配：单道程序环境下，仅装有一道用户程序，即整个内存的用户空间由该程序独占
  • 固定分区分配
    固定分配多个区域，用于放置单个进程
    预先把可分配的主存空间分割成若干个连续区域，称为一个分区。
    每个分区的大小可以相同也可以不同。但分区大小固定不变，每个分区装一个且只能装一个程序
    内存分配：如果有一个空闲分区, 则分配给进程
  • 可变分区分配：
    用表格记录内存使用情况，根据内存块和孔调度进程
    当一个进程到来的时候，它将从一个足够容纳它分区中分配内存。
    操作系统包含以下信息:
  1. 已分配的分区-已分配分区表   b) 空的分区-空闲分区表

选择孔

  • 首次适应（First-fit）: 分配最先找到的合适的分区
  • 最佳适应（Best-fit）: 搜索整个列表，找到适合条件的最小的分区进行分配
  • 最差适应（Worst-fit）: 搜索整个列表，寻找最大的分区进行分配

碎片：

  • 外部碎片：存储被分为大量小孔
  • 内部碎片：分配给进程的孔，进程不需要使用的部分则成为内部碎片
    外碎片 –整个可用内存空间可以用来满足一个请求，但它不是连续的
    内碎片 –分配的内存可能比申请的内存大一点，这两者之间的差别是在分区内部，但又不被使用
    `可通过紧缩来减少外碎片
    把一些小的空闲内存结合成一个大的块。
    只有重定位是动态的时候，才有可能进行紧缩，紧缩在执行时期进行

分段

一个程序是一些段的集合，一个段是一个逻辑单位
每个段用段名称和段偏移指定位置
一个逻辑地址是两个向量的集合:
<segment-number, offset>

段表 - 映射二维用户地址，每个表项包括:
基址 - 包含内存中段物理地址的起始地址
限长 - 指定段的长度
段表基址寄存器(STBR)指向段表在内存中的地址
段表限长寄存器(STLR)表明被一个程序所使用的段的数目
如果 s < STLR，段号s 是合法的

由于段的长度各不相同，内存分配是一个动态存储-分配问题

`内存分配
首先/最佳适应法
外碎片问题

`重定位
›动态
›由段表来执行

`共享
›共享的段
›同样的段号

分页

允许进程的物理地址不连续
基本方法：将物理内存分为固定大小的块，称为帧或页帧，逻辑内存分为同样大小的块，称为页或页面
进程物理地址空间可能不连续
如果有可用的物理内存，它将分给进程
把物理内存分成大小固定的块，称为帧（Frame）
大小为2的幂
早期：512字节至8192字节
现在：4K-64K
把逻辑内存也分为同样大小的块，称为页（Page）
系统保留所有空闲帧的记录
运行一个有N页大小程序，需要找到N个空帧来装入程序
建立一个页表，把逻辑地址转换为物理地址
存在内碎片
内存保护 内存的保护由与每个帧相连的保护位来实现 有效-无效位附在页表的每个表项中: ›“有效”表示相关的页在进程的逻辑地址空间，并且是一个合法的页 ›“无效”表示页不在进程的逻辑地址空间中共享代码
如果代码是可重入代码（只读），可以在进程间共享 (如文本编辑器, 编译器, 数据库系统)
共享代码必须出现在所有进程的逻辑地址空间的相同位置
`私有代码和数据
每个进程保留一个代码和数据副本
存有私有数据和代码的页能够出现在逻辑地址空间的任意位置

页表的层次结构

二层页表

内存的保护由与每个帧相连的保护位来实现
有效-无效位附在页表的每个表项中:
“有效”表示相关的页在进程的逻辑地址空间，并且是一个合法的页
“无效”表示页不在进程的逻辑地址空间中
图片

哈希页表

虚拟页号被散列到一个页表中。这种页表的每一个条目都包括了一个链表元素，这些元素哈希成同一
虚拟页号与链表中的每个元素相比较，找到匹配项。如果匹配，则相应的物理帧被取出。
虚拟页号与链表中的每个元素相比较，找到匹配项。如果匹配，则相应的物理帧被取出。

反向页表

对于每个真正的内存页或帧有一个条目。
每个条目保存在真正内存位置的页的虚拟地址，以及包括拥有这个页的进程的信息。
`优缺点
减少了需要储存每个页表的内存，但是当访问一个页时，增加了寻找页表需要的时间。
使用哈希表来将查找限制在一个或少数几个页表条目。
实现共享内存困难

段页式原理

分段和分页原理的结合
先将用户程序分成若干个段，再把每个段分成若干个页，并为每个段赋予一个段号
逻辑地址：<段号，页号，页内偏移>
存在内碎片
无外碎片

内存扩充技术

  1. 紧缩Compaction（可变分区）
  2. 覆盖技术Overlaying
  3. 交换技术Swapping
  4. 虚拟内存Virtual Memory

覆盖

解决问题à程序大小超过物理内存总和
程序执行时
›只在内存中保留那些在任何时间都需要的指令和数据
›程序的不同部分在内存中相互替换
由程序员声明覆盖结构，不需要操作系统的特别支持
覆盖结构的程序设计很复杂
应用于早期的操作系统

交换

在多道程序环境下，一方面，在内存中的某些进程由于某事件尚未发生而被阻塞运行，但它却占用了大量的内存空间，甚至有时可能出现在内存中所有进程都被阻塞而迫使CPU停止下来等待的情况
另一方面，却又有着许多作业在外存上等待，因无内存而不能进入内存运行的情况
浪费资源，降低系统吞吐量。
一个进程可以暂时被交换（swap）到内存外的一个备份区，随后可以被换回内存继续执行
备份区—是一个固定的足够大的可以容纳所有用户内存映像拷贝的快速磁盘；必须提供对这些内存映像的直接访问
交换（备份区）：系统指定一块特殊的磁盘区域作为交换空间（swap space），包含连续的磁道，操作系统可以使用底层的磁盘读写操作对其高效访问

系统模型

资源类型 R1, R2, . . ., Rm
CPU周期，内存空间，I/O设备
每一种资源Ri 有Wi  种实例
每一个进程通过如下方法来使用资源
申请，使用，释放
资源动态申请-常用方法
在进程运行过程中申请资源
资源静态申请
在进程运行前一次申请所有资源

必要条件

死锁指一组等待的进程，其中每一个进程都持有资源，并且等待着由这个组中其他进程所持有的资源

  • 互斥：一次只有一个进程可以使用一个资源
  • 占用并等待：一个至少持有一个资源的进程等待获得额外的由其他进程所持有的资源
  • 非抢占：一个资源只有当持有它的进程完成任务后，自由的释放
  • 循环等待：等待资源的进程之间存在环 {P0, P1, …, P0}

资源分配图

被分为两个部分
›P = {P1, P2, …, Pn}, 含有系统中全部的进程
›R = {R1, R2, …, Rm}, 含有系统中全部的资源
请求边：有向边Pi->Rj
分配边：有向边Ri->P

  • 如果图没有环，那么不会有死锁
  • 如果图有环
    如果每一种资源类型只有一个实例，那么死锁发生
    如果一种资源类型有多个实例，可能死锁
    图片

死锁处理的分类

  • 确保系统永远不会进入死锁状态
    死锁预防
    死锁避免
  • 允许系统进入死锁状态，然后检测它，并加以恢复
    死锁检测
    死锁恢复
  • 忽略这个问题，假装系统中从未出现过死锁。
    这个方法被大部分的操作系统采用，包括UNIX、Windows
    由开发人员自行处理死锁

预防

›`抑制死锁发生的必要条件

  • 互斥：可共享资源不涉及死锁，互斥资源必须强制互斥
  • 持有并等待：保证进程申请资源时不占有其他资源，要求进程在执行前一次性申请全部资源，或者只有不占有资源时才可以分配资源，`可能出现饥饿
  • 抢占：›
  1. 如果一个进程的申请没有实现，它要释放所有占有的资源
  2. 先占的资源放入进程等待资源列表中
  3. 进程在重新得到旧的资源的时候可以重新开始
  4. 进程申请资源时，如果资源可用则分配，如果不可用，检查资源是否被分配给等待额外资源的其他进程，如果是，抢占资源，否则，申请进程等待
  • 循环等待:对所有资源完全排序，进程按顺序申请资源
    银行家算法

避免

  • 一个简单而有效的模型要求每一个进程声明它所需要的资源的最大数
  • 死锁避免算法动态检查资源分配状态以确保循环等待条件不可能成立
  • 资源分配状态定义为可用的与已分配的资源数，和进程所需的最大资源量所决定

安全状态

当进程申请一个有效的资源的时候，系统必须确定分配后是安全的
如果存在一个安全序列，系统处于安全态
进程序列<P1, P2, …, Pn>是安全的，如果每一个进程Pi所申请的可以被满足的资源数加上其他进程所持有的该资源数小于系统总数
如果 Pi 需要的资源不能马上获得，那么Pi 等待直到所有的Pi-1进程结束。
当Pi-1 结束后， Pi获得所需的资源，执行、返回资源、结束。
当Pi结束后， Pi+1获得所需的资源执行，依此类推。
`定理
如果一个系统在安全状态，就没有死锁
如果一个系统不是处于安全状态，就有可能死锁
避免=>确保系统永远不会进入不安全状态

银行家算法

  • 多个实例
  • 每一个进程必须事先声明使用的最大量
  • 当一个进程请求资源，它可能要等待
  • 当一个进程得到所有的资源，它必须在有限的时间释放它们
Available:  长度为 m的向量。 如果available[j]=k,那么资源Rj有k个实例有效  
Max: n x m 矩阵。 如果Max[i,j]=k,那么进程Pi最多可以请求k个资源Rj的实例  
Allocation:  n x m 矩阵。 如果Allocation[i,j]=k,那么进程Pj当前分配了k个资源Rj的实例  
Need:  n x m 矩阵。如果Need[,j]=k,那么进程Pj还需要k个资源Rj的实例  
Need [i,j] = Max[i,j] – Allocation [i,j].  
1.让Work和Finish作为长度为m和n的向量初始化：  
Work := Available  
Finish [i] = false for i - 1,2,3, …, n.  
2.  查找i  
(a) Finish [i] = false  
(b) Needi £ Work  
If no such i exists, go to step 4.  
3.  Work := Work + Allocationi    
Finish[i] := true    
go to step 2.  
4.  如果对所有i的 Finish [i] = true, 则系统处在安全状态。

   Requesti =进程 Pi 的资源请求向量.  如果Requesti [m] = k 则进程 Pi 想要资源类型为Rjm的k个实例
1.  如果 Requesti £ Needi 转 step 2.  否则报错, 因为进程请求超出了其声明的最大值
2.  如果 Requesti £ Available, 转 step 3.  否则 Pi  必须等待, 因为资源不可用.
3.  假设通过修改下列状态来分配请求的资源给进程Pi :
  Available := Available - Requesti;
  Allocationi := Allocationi + Requesti;
  Needi := Needi – Requesti;;
 
•如果系统安全 Þ 将资源分配给 Pi.
•如果系统不安全 Þ Pi 必须等待，恢复原有的资源分配状态

死锁检测和恢复

每个资源类型有一个实例：维护进程等待图
每个资源类型有多个实例：用available和finished数组探查是否死锁
允许进入死锁状态并加以恢复
维护等待图
节点是进程
Pi->Pj表明Pi在等待Pj
定期调用算法来检查是否有环
一个检查图中是否有环的算法需要n^2的操作来进行，n为图中的节点数
Available ：一个长度为m的向量，表示每一种资源类型可用的实例数目
Allocation:  一个n x m 的矩阵，定义了当前分配的每一种资源类型的实例数目
Request: 一个n x m 的矩阵，表明了当前的进程请求。如果Request[i，j]=k，那么进程Pi请求k个资源Rj的实例

1.  让Work和Finish作为长度为m和n的向量初始化  
(a) Work = Available  
(b)  For i = 0,2, …, n-1, if Allocationi ¹ 0, thenFinish[i] = false;otherwise, Finish[i] = true.  
  
2.  找到满足下列条件的下标i  
(a)  Finish[i] = false  
(b)  Requesti <= Work  
如果没有这样的i存在，转4  
  
3.  Work = Work + Allocationi    
Finish[i] = true    
转 2.  
  
4.如果有一些i (0 £ i < n) , Finish[i] = false, 则系统处在死锁状态。而且， 如果 Finish[i] = false, 则进程 Pi 是死锁的。

`算法需要m x n^2 次操作来判断是否系统处于死锁状态

恢复

可以一次中断所有进程排查，也可以一个一个终结进程
选择牺牲进程：最小化代价
回滚：返回到安全的状态，然后重新开始进程
饥饿：同样进程的可能总是被选中。在代价因素中加入回滚次数

虚拟内存概念

局部性原理：在一较短的时间内，程序的执行仅局限于某个部分；相应地，它所访问的存储空间也局限于某个区域
一个程序只要部分装入内存就可以运行
整个程序不是同一时间都要运行
`程序部分装入技术优点
进程大小不再受到物理内存大小限制
每个进程需要的内存更小
更多进程可以并发运行
I/O更少

  • 虚拟存储技术：当进程运行时，先将其一部分装入内存，另一部分暂留在磁盘，当要执行的指令或访问的数据不在内存时，由操作系统自动完成将它们从磁盘调入内存执行。
  • 虚拟地址空间：分配给进程的虚拟内存
  • 虚拟地址：在虚拟内存中指令或数据的位置
  • 虚拟内存：把内存和磁盘有机结合起来使用，得到一个容量很大的“内存”，即虚存
    特点 只有部分运行的程序需要在内存中 逻辑地址空间能够比物理地址空间大 允许多个进程享同一地址空间 允许更有效的进程创建虚拟内存能够通过以下手段来执行实现:
    虚拟页式（虚拟存储技术+页式存储管理）
    虚拟段式（虚拟存储技术+段式存储管理）
    `虚拟页式有两种方式
    按需调页（ Demand paging ）
    预调页（Prepaging）

虚拟页式存储管理

基本思想 进程开始运行之前，不是装入全部页面，而是装入一个或零个页面 运行之后，根据进程运行需要，动态装入其他页面 当内存空间已满，而又需要装入新的页面时，则根据某种算法置换内存中的某个页面，以便装入新的页面请求分页（按需调页）
只有在一个页需要的时候才把它换入内存
需要很少的I/O
需要很少的内存
快速响应
多用户
懒惰交换:只有在需要页时，才将它调入内存
交换程序(swapper)对整个进程进行操作
调页程序(pager)只是对进程的单个页进行操作

有效无效位

每一个页表的表项有一个有效- 无效位相关联：
1表示在内存，0表示不在内存
在所有的表项中，这个位被初始化为0
一个页表映象的例子

缺页中断的处理

1.访问指令或数据
2.查看另一个表来决定:
无效引用 Þ 终止
仅仅不在内存
3.找到页在后备存储上的位置
4.得到空的页框，把页换入页框
5.重新设置页表，把有效位设为v
6.重启指令

极端情况：进程执行第一行代码时，内存内没有任何代码和数据  
›进程创建时，没有为进程分配内存，仅建立PCB  
›导致缺页中断  
›纯请求分页（纯粹按需调页）  
  
一条指令可能导致多次缺页（涉及多个页面）  
›幸运的是，程序具有局部性（locality of reference）  
  
请求调页需要硬件支持  
›带有效无效位的页表  
›交换空间  
›指令重启  
  
缺页率（缺页的概率）：0 <= p <= 1.0  
›如果 p = 0 ，没有缺页  
›如果 p = 1， 每次访问都缺页  
  
有效访问时间（ EAT ）  
    EAT = (1 – p) x 内存访问时间+ p x 页错误时间  
  
页错误时间=处理缺页中断  
  + [页交换出去时间 ]  
  + 读入页时间  
  + 重启进程开销

性能优化：
页面转换时采用交换空间，而不是文件系统
›交换区的块大，比文件系统服务快速

在进程装载时，把整个进程拷贝到交换区
›基于交换区调页
›早期的 BSD Unix

利用文件系统进行交换
›Solaris和当前的BSD
›部分内容仍旧需要交换区（堆栈等）
写时复制:允许父进程和子进程在初始化时共享页面
›如果其中一个进程修改了一个共享页面，会产生副本
›更加高效
›应用在Windows，Linux，macOS等系统

需要页置换的情况

页置换—找到内存中当前没有使用的一些页，换出
同一个页可能会被装入内存多次
基本页置换方法

  1. 查找所需页在磁盘上的位置
  2. 查找一空闲帧
    如果有空闲帧，就使用它
    如果没有空闲帧，使用页置换算法选择一个“牺牲”页框
    将“牺牲”帧的内容写到磁盘上，更新页表和帧表
  3. 将所需页读入（新）空闲帧，更新页表和帧表
  4. 重启用户进程

如果发生页置换，则缺页处理时间加倍
使用修改位modify bit或脏 (dirty bit) 来防止页面转移过多—只有被修改的页面才写入磁盘
页置换完善了逻辑内存和物理内存的划分—在一个较小的物理内存基础之上可以提供一个大的虚拟内存

页面置换算法

先进先出(FIFO)算法

置换在内存中驻留时间最长的页面
容易理解和实现、但性能不总是很好
实现：使用FIFO队列管理内存中的所有页
FIFO算法可能会产生Belady异常
更多的页框 =>更多的缺页

最优置换算法OPT

被置换的页是将来不再需要的或最远的将来才会被使用的页
实现？
作用：作为一种标准来衡量其它算法的性能

最近最少使用算法(LRU)

置换最长时间没有使用的页
性能接近OPT
实现：计数器（时间戳）或栈
开销大、需要硬件支持
栈实现—在一个双链表中保留一个记录页数目的栈:
被访问的页:
移到栈顶
需要改变6个指针
没有为置换进行查找

在没有硬件支持的系统中，可使用LRU近似算法访问位
每个页都与一个位相关联，初始值为0
当页访问时设位1

  • 附加引用位算法
  • 二次机会算法
  • 增强型二次机会算法

二次机会算法

需要访问位
如果访问位为0，直接置换
如果将要交换的页访问位是1，则:
把访问位设位0
把页留在内存中
以同样的规则，替换下一个页

实现：时钟置换（顺时针方式）

基于计数的页面置换

用一个计数器记录对每一个页的访问次数
LFU 以最小的计数置换一个页

页面缓冲算法

  1. 总是保留一个空闲帧缓冲池
  • 在缺页错误时有帧可用
  • 读页面到空闲帧，无需等待写出牺牲帧
  • 牺牲帧以后被写出后，添加到缓冲池
  1. 扩展之一，维护一个修改页面的列表
  • 当设备空闲时选择一个修改页面写到磁盘上，然后重置它的修改位
  2. 另一种修改,保留一个空闲帧池，并且记着哪些页面在哪些帧内
  • 如果在重用之前被再次需要，就不需要从磁盘上重新装载了
  • 降低因错误选择牺牲页面而引起的开销

帧分配

两种主要分配策略

  • 固定分配
  • 优先分配

固定分配

平均分配 Equal allocation– 例如，如果有100帧和5个进程，给每个进程20帧
在缓冲池里保存空闲帧
比例分配 Proportional allocation – 根据进程大小分配内存
按照多道程度而动态分配，进程分得的数量变化

优先级分配

优先级分配:用优先级而不是大小来进行比例分配
如果进程 Pi 跑出页面错误,
从自己的帧里选择一个替代
从优先级较低的进程里选择一个替代

全局 vs. 局部分配

全局置换 Global replacement – 允许进程从所有帧的集合中选择一个置换帧；一个进程可以从另一个进程那里获取帧
但是进程执行时间可能变化很大，不能控制缺页错误率
有更好的系统吞吐量，更常用
局部置换 Local replacement – 每个进程只从它自己分配的帧中进行选择
对每个进程的表现更一致
但是可能内存低利用

非均匀内存访问（NUMA）

v以上假设所有内存可以被平等访问  
  
v很多系统如 NUMA – 内存访问速度变化的  
  
›考虑CPU和内存在系统中通过总线互连  
  
v让分配的内存帧‘尽可能地靠近’运行进程的CPU  
  
›通常意味着位于同一系统扳  
  
›Solaris通过在内核中创建延迟组 lgroups  
  
v将相近的CPU和内存聚集在一起  
  
v在组内调度进程的所有线程，并分配它的所有内存  
  
v最大限度减少总体内存延迟，最大化CPU缓存命中率

抖动

如果一个进程没有足够的页，那么缺页率将很高，这将导致:
CPU利用率低下.
操作系统认为需要增加多道程序的道数
系统中将加入一个新的进程
颠簸（抖动）=一个进程的页面经常换入换出
原因：分配的帧数 < 局部大小之和

工作集模型

工作集窗口 º 固定数目的页的引用
WSSi (进程Pi的工作集) = 最近D中所有页的引用 (随时间变化)
图片
vExample: D = 10,000

›每5000个时钟单位时钟中断

›为每个页在内存中保留两个位

›任何时候一个时钟中断拷贝，把所有访问位设为0

›如果一个在内存中的位是0，说明页在工作集

内存映射文件

通过映射一个磁盘块成内存的一页，内存映象文件I/O 允许文件I/O 作为普通内存访问。
开始的文件访问按普通请求分页来进行，一页大小的部分文件从文件系统读入物理页。以后文件的读、写操作就按通常的内存访问来处理。
由于通过内存的文件操作而不是使用系统调用read() write() ，简化了文件访问和使用。
多个进程可以允许将同一文件映射到各自的虚拟内存中，以允许数据共享

内核内存分配

通常从空闲内存池中获取
›内核需要为不同大小的数据结构分配内存
›一些内核内存需要连续的物理页

v内核在使用内存块时有如下特点：  
  
    (1)内存块的尺寸比较小；  
  
    (2)占用内存块的时间比较短；  
  
    (3)要求快速完成分配和回收；  
  
    (4)不参与交换。  
  
    (5)频繁使用尺寸相同的内存块，存放同一结构的数据；  
  
    (6)要求动态分配和回收。  
   ```  
### 伙伴(Buddy)系统  
v主要用于Linux早期版本中内核底层内存管理  
v一种经典的内存分配方案  
v从物理上连续的大小固定的段上分配内存  
v主要思想：内存按2的幂的大小进行划分，即4KB、8KB等，组成若干空闲块链表；查找链表找到满足进程需求的最佳匹配块  
›满足要求是以2的幂为单位的  
›如果请求不为2的幂，则需要调整到下一个更大的2的幂  
›当分配需求小于现在可用内存时，当前段就分为两个更小的2的幂段，继续上述操作直到合适的段大小  
`算法  
›首先将整个可用空间看作一块: 2^n  
›假设进程申请的空间大小为s，如果满足  
2^(n-1)<s<=2^n，则分配整个块  
   否则，将块划分为两个大小相等的伙伴，大小为2^(n-1)  
›一直划分下去直到产生大于或等于s的最小块  
  
### Slab 分配  
v内核分配的另一方案  
vSlab 是由一个或多个物理上连续的页组成  
vCache 含有一个或多个 slab  
v每个内核数据结构都有一个cache  
每个 cache 含有内核数据结构的对象实例  
  
v当创建 cache 时, 包括若干个标记为空闲的对象  
v当内核对象时，从cache上直接获取，并标识对象为使用  
v当一个slab充满了已使用的对象时，下一个对象的分配从空的slab开始分配  
›如果没有空的slab, 则从物理连续页上分配新的slab  
v优点  
①没有因碎片而引起的内存浪费  
  
②内存请求可以快速满足  
  
## 杂项  
`预调页面  
v在进程启动初期，减少大量的缺页中断  
v在引用前，调入进程的所有或一些需要的页面  
v如果预调入的页面没有被使用，则内存被浪费  
`页面尺寸大小  
v碎片 – 需要小的页  
v表大小 – 需要大的页  
vI/O 开销 – 需要大的页  
v程序局部 – 需要小的页  
v缺页次数 – 需要大的页  
v其他因素  
没有最佳答案，总的来说，趋向更大的页  
`TLB 范围  
vTLB 范围 – 通过TLB所访问的内存量  
vTLB 范围 = (TLB 大小) X (页大小)  
v理想情况下，一个进程的工作集应存放在 TLB中  
›否则会有大量的缺页中断  
v增加页的大小  
›对于不需要大页的应用程序而言，这将导致碎片的增加  
v提供多种页的大小  
›这允许需要大页的应用程序有机会使用大页而不增加碎片的大小  
`倒置页表  
v倒置页表降低了保存的物理内存  
v不再包括进程逻辑地址空间的完整信息  
v为了提供这种信息，进程必须保留一个外部页表  
v外部页表可根据需要换进或换出内存  
`I/O 联锁与页面锁定  
v允许某些页在内存中被锁住  
  
vI/O时，正在进行I/O的页面不允许被置换算法置换出内存  
`linux  
vSLAB  
vDemand paging  
vGlobal page replacement(LRU)  
v两个帧列：active_list和inactive_list  
vKswapd daemon  
定期检查  
`windows10  
vBoth IA-32 and x86-64  
v32bit支持4GB，64bit支持128TB内存  
vShared memory, demand paging, copy-on-write, paging和memory compression  
v按需调页-clustering，预调入3-7页  
vWorking-Set 管理（最少50-最多345页）  
  
## 文件概念  
`文件  
›计算机中信息存储的基本组织形式  
›相关信息结合  
›具有文件名  
`文件名  
›按名存取：文件名     存储位置  
›文件名由一串ASCII码或(和)汉字构成  
›名字长度  
v8.3规则：文件名8个字符，类型3个字符，之间有“.”分割  
v长文件名：可以最多输入255多个字符作为文件名  
›文件名可能大小写敏感  
`文件的打开  
v需要数据结构  
›打开文件表：跟踪打开文件  
›文件指针:指向最后一次读写的位置，每个进程1个  
›打开文件计数器：打开文件次数（调用open次数）  
›文件存储位置：文件存放在存储设备上的位置信息  
›访问权限：每个进程的访问权限  
v优点  
›方便文件共享  
›提高文件存取效率  
`文件锁  
›共享锁 Shared lock 类似于读者锁– 多个进程可以并发获取它。  
›独占锁 Exclusive lock 类似于写者锁  
`文件结构  
v目的：便于程序理解文件内容  
›无结构：文字流、字节流等  
›简单记录结构：线性、固定长度、可变长度等  
›复杂结构：格式化文档、多媒体文件等  
v谁决定了文件结构  
›操作系统  
程序  
  
## 文件访问  
  
### 逻辑文件  
v文件呈现在用户面前的组织结构  
v又称为文件逻辑结构  
v逻辑文件决定了文件访问方法  
`文件访问方式  
- 顺序访问  
›最简单的访问方式  
›文件信息按照存放顺序，一个记录一个记录地依次访问  
›顺序文件  
›典型存储设备：磁带  
- 直接（随机）访问  
›可以直接定位到文件的某条记录进行访问  
›直接文件  
典型设备：磁盘  
v访问方式：直接（随机）访问  
v直接通过计算得到需要读写记录的位置，直接跳转进行文件读写  
- 索引文件  
v基本方法：为顺序文件建立索引表

记录平均长度：40B   索引表项大小：4B   1M条记录长度：44MB

访问第1万条记录：

       1）计算得到第1万条记录的索引项在索引表中首址：10000*4=40000

       2）从索引表地址40000处读入4个字节，内容为第1万条记录在顺序文件中的首址P

       3）从顺序文件地址P处读入40个字节（假如第1万条记录长度为40B）

合计读入：4+40=44B

```

目录结构

文件控制块（FCB）

存放操控文件所需的各类文件属性信息
›文件名
›长度
›创建时间
›存放位置
›访问控制权限
类似一个索引项
v目录项
›存放一个文件的各类属性
›有的系统等同于文件控制块
v目录
›包含着所有文件信息的节点集合
›根据文件名检索文件的桥梁
›目录项的有序集合
v目录文件
›目录组织形式
›目录作为一个文件存在于文件系统
v每个目录项中存放了文件在存储设备的存放地址
v目录和文件都驻留在存储设备（如磁盘）

文件检索

v文件检索是一个遍历目录项的过程
1.打开目录文件
2.从磁盘读入该目录文件的1个(物理)块，该块包含若干个目录项
3.根据文件名遍历内存中的该块，如找到则结束
4.判断该目录文件是否还有物理块没有读入，如果是转2；否则，结束。表示该目录中没有此文件名的文件
v目录项由于经常变化，一般不排序
v平均遍历目录项数：       （1+n）/2
  不包括文件查不到的情况
  ›
  目录项大小= ds bytes
›目录中最多文件数 = n
›物理块大小 = b
v那么
›目录文件大小 = ds*n bytes
›目录文件需要的物理块数目 = ds*n/b
检索一个文件需要平均读入的块数=(ds*n/b+1)/2

目录结构

设计目标 v效率 ›快速定位文件位置 ›提高文件访问效率 v命名 ›方便用户使用 ›同名的不同文件 ›不同名的相同文件 v分组 ›文件分组（子目录） ›兼顾效率和方便性单层目录
v所有文件在同一目录中，只有一级目录：根目录
v根目录（/）：一个文件系统最顶层的目录
v优点：结构简单
v缺点
›检索效率差（目录下文件过多）
›不能有同名文件，一个文件只能有一个名称
›不能分组
双层目录 v每个用户有自己的目录结构 v目录下的目录 v缺点：1）无法分组；2）同一用户不能有相同文件名的文件 v优点：1）不同用户可有相同文件名的文件；2）比单层目录提高检索效率（文件分布在多个用户目录中）树形目录
v特点
›检索高效（子目录增多导致每个目录下文件减少）
›可以分组
›允许重名
v当前目录：工作目录
›cd /spell/mail/prog
›type list
v绝对路径
›从根开始的路径名
v相对路径
›从当前目录开始的路径名
›提高检索效率
（有向）无环图目录 v文件共享：不同目录中的文件指向同一个物理文件，也就是它们内容相同 v树型目录不能实现文件共享 v解决方法：图型目录 ›无环图目录 ›通用图目录（有环图） v无环图：有向边无环如何保证无环？
›仅允许指向文件的链接，不允许指向子目录的链接
›垃圾回收
›每当加入新链接时，使用环路检测算法判断是否正确
›优化遍历目录算法，避免对环的重复搜索

杂项

v要访问一个文件系统，必须先安装它。
一个未安装的文件系统将被安装在一个安装点(mount point)上。

远程文件系统

v用网络使得远程计算机之间的联系成为可能
›手动传输文件如 FTP
›自动，直接访问文件用分布文件系统 distributed file systems
›半自动用万维网 world wide web
vClient-server 客户机-服务器模型允许客户机登录远程服务器的文件系统
›服务器可以服务多台客户机
›识别客户可能是不安全和复杂的
›NFS 是标准 UNIX 下客户机-服务器的文件共享协议
›CIFS 是Windows下标准协议
›标准操作系统文件调用翻译为远程调用
v分布式信息系统 (分布式命名服务 distributed naming services) 如LDAP, DNS, NIS。

故障

v所有文件系统都有故障模式
›例如目录结构或者其他磁盘管理信息（元数据 metadata 损坏。
v远程文件系统加入新的故障模式，来自网络故障或者服务器故障
v从故障中恢复包含维护状态信息 state information
vStateless 无状态协议如NFC在每个请求里包含所有信息，允许较为容易的故障恢复但是不够安全

共享

v规定系统的多个用户如何访问共享文件
›类似于第六章的进程同步算法
v由于磁盘和网络的巨大延迟和很慢的传输速率，倾向于没这么复杂
›Andrew File System (AFS) 实现了复杂共享语义
›Unix file system (UFS) 使用:
v一个用户对已打开文件的写入，对于打开同一文件的其他用户立即可见。
v一种共享模式允许用户共享文件的当前位置指针。
›AFS 有会话语义
v一旦文件关闭，对其所作的更改只能被后来打开的会话可见。

访问控制权限和分组

v访问模式：读/写/执行
v三种类型的用户
  RWX
  a) 所有者  7  =>1 1 1    RWX
  b) 组用户  6  =>  1 1 0 RWX
  c) 公共用户  1  =>  0 0 1
v建立一个组，加入一些用户
v对特定的文件或目录(game) ，定义适当的访问权限