《操作系统设计与实现》简要笔记4

norn_larry

第四章 存储器管理
存储管理器任务：跟踪哪些存储器正在被使用，哪些存储器空闲，在进程需要时为它分配存储器，使用完毕后释放存储器，并且在主存无法容纳所有进程时管理主存和磁盘间的交换。
4.1 基本的内存管
存储管理器的分类：在运行期间将进程在主存和磁盘之间移动的系统（交换和分页）和不移动的系统。
4.1.1 没有交换和分页的单道程序
       最简单的存储器管理方案是同一时刻只运行一道程序，应用程序和OS共享存储器，这样组织的系统，同一时刻只能有一个进程在存储器中运行。
4.1.2 固定分区的多到程序
       把主存简单地划分为n个分区（不一定相等），分区的划分可以在系统启动时手工完成。当一个作业到达时，可以把它放到能够容纳它的最小的分区的输入队列中。
4.2 交换
       在没有足够的主存以容纳所有当前活动的进程时，多出的进程必须被保存在磁盘上并动态地调入主存运行。在硬件的支持下，有两个通用的内存管理方法可以使用，最简单的策略称为交换（swapping），它把各个进程完整地调入主存，运行一段时间，再放到磁盘上；另一种策略称为虚拟存储器（virtual memory）,它使进程在只有一部分在主存的情况下也能运行。
       当交换在主存中生成了多个空洞时，可以把所有的进程向下移动至相互靠紧，从而把这些空洞结合成一大块，这种技术称为内存紧缩（memory compaction）
4.2.1 使用位图的内存管理
       跟踪内存使用情况的两种方法：位图和自由链表。
使用位图方法时，内存被划分为可能小到几个字或大到几千字节的分配单位，每个分配单位对应位图中的一位，0表示空闲，1表示占用（或者反过来）。
缺点：当它决定把一个占K个分配单位的进程调入内存时，内存管理器必须搜索位图以找出一串K个连续的0，在位图中查找指定长度的连续0串是一个缓慢的操作（因为串可能跨越字边界）。
4.2.2 使用链表的内存管理
       维持一个已分配和空闲的内存段的链表。这里，一个段或者是一个进程，或者是两个进程间的一个空洞。
4.3 虚拟存储器
虚拟存储器（virtual memory）的基本思想：程序，数据，堆栈的总的大小可以超过可用物理存储器的大小，OS把程序当前使用的那些部分保留在存储器中，而把其他部分保存在磁盘上，并在需要时在内存和磁盘间交换程序的片段。
4.3.1 分页
       由程序产生的地址被称为虚地址（virtual addresses），他们构成了一个虚地址空间（virtual address space）。在没有虚拟存储器的计算机上，虚地址被直接送到内存总线上，使具有同样地址的物理存储器字被读写，而在使用虚拟存储器的情况下，虚地址不是被直接送到内存总线上，而是送到内存管理单元（MMU），它由一个或一组芯片组成，其功能是把虚地址映射为物理地址。
4.3.2 页表
       页表的目的是把虚页映射为页框，从math角度讲，页表是一个以虚页号为参数，物理页框号为结果的函数。通过这个函数可以把虚地址中的虚页域替换成页框域，从而形成物理地址。
使用页表面对的两个主要问题：
1 页表可能会非常大
2 地址映射必须十分迅速
多级页表
见Intel manual
4.3.3 TLBs——翻译后援存储器
方案基础：大部分程序倾向于对较少的页面进行大量的访问，因此只有一小部分页表项经常被用到，其他的很少被使用。
       采取的解决方法是为计算机装备一个不需要经过页表就能把虚拟地址映射成物理地址的小的硬件设备，这个设备叫做TLB（Translation Lookaside Buffer），通常存在域MMU内部，条目的个数一般不超过64个，每个条目包含一个页的信息，主要有虚页号，在页被修改时将被设置的一个位，保护码（读/写/执行）,页所在的物理页框号，这些域和页表中的域是一一对应的。
TLB工作流程：当一个虚地址被送到MMU翻译时，硬件首先把它和TLB中的所有条目同时（并行地）进行比较，看它的虚页号是否在TLB中，如果找到了并且这个访问没有违反保护位，它的页框号将直接从TLB中取出而不用去查页表，如果虚页号在TLB中但当前指令试图写一个只读的页面，这是将发生一个保护故障，与直接访问页表时相同。如果MMU发现在TLB中没有命中，它将即进行一次常规的页表查找，然后从TLB中淘汰一个条目并把它替换为刚刚找到的页表项。
当TLB从页表中装入时，所有的域都从内存中取得。
软件TLB管理
4.4 页面替换算法
4.4.1 最优页面替换算法
       不容易被实现
4.4.2 最近使用页面替换算法
       NRU（最近未使用）算法随机地从编号最小的非空类中挑选出一个页淘汰，意思是：淘汰一个在最近一时钟周期中（典型时间为20ms）没有被访问的已修改页要比淘汰一个被频繁访问的干净页好。
4.4.3 先进先出页面替换算法（FIFO）
       OS维持一个所有当前内存中的页的链表，最老的页在头上，最新来的页在表尾，当发生页面故障时淘汰表头的页并把新调入的页加到表尾。
4.4.4 第二次机会页面替换算法
       在FIFO算法中，避免把经常使用的页替换出去，我们对老页面的R位进行检查，如果R位是0，那么这个页既老又没用，应该被立刻替换掉，如果是1，就清除这个位，把这个页放到页链表的尾端，修改它的装入时间让它就像刚装入的一样，然后继续搜索。
4.4.5 时钟页面替换算法
       把所有的页面保存在一个类似钟表面的环形链表中，有一个表指针指向最老的页面，当页面故障时，算法首先检查表针指向的页面，如果它的R位是0就淘汰掉这个页，并把新页插入这个位置，然后把表针前移一个位置，如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到一个R位为0的页为止。
4.4.6 最久未使用页面替换算法
LRU（最久未使用）算法：在页面故障发生时，淘汰掉没有使用的时间位最长的页。
4.5 分页系统中的设计问题
4.5.1 工作集模型
请调（demand paging）:页是在需要时调入，不是预先装入。
大部分进程都表现出一种访问的局部性（locality of reference）：在进程运行的任何阶段，它都只访问它的页面中较小的一部分。
       一个进程当前使用的页的集合叫做它的工作集（working set）
       一个每隔几条指令就发生一次页面故障的程序被称为是在颠簸
       许多分页系统都试图跟踪进程的工作集，并保证在进程运行以前它的工作集就已经在内存中了，这样一种方法称为工作集模型。它旨在大大减少页面故障，在进程运行之前先装入页面也叫做预调。
4.5.2 局部与全局分配策略
       局部算法实际上对应于为每个进程分配固定的内存片段，全局算法在可运行进程之间动态地分配页框，因此分配各个进程的页框数是随时间变化的。
       PFF（page fault frequency）分配算法：控制进程的颠簸
4.5.3 页面大小
4.6 分段
见Intel Manual

第五章 文件系统

对于长期的信息存储，有下列三个基本要求：
1 必须能够存储大量的信息
2 在使用信息的进程终止时，信息必须保存下来
3 多个进程可以并发地存储信息
5.1 文件
5.1.1 文件命名
5.1.2 文件结构
5.1.3 文件类型
       正规文件（regular file）：包含有用户信息
       目录（directory）：管理文件系统结构的系统文件
       字符设备文件（character special file）：和I/O有关，用于模仿串行I/O设备
       块设备文件（block special file）：用于模仿磁盘
正规文件是ASCII文件或者二进制文件。
ASCII文件：可以原样地显示和打印，也可以用文本编辑器进行编辑
二进制文件：打印出来是乱码，二进制文件往往具有一定的内部结构
5.1.4 文件存取
顺序存取（sequential access）；进程可以从文件开始处顺序读取文件中所有字节或则记录，但不能够跳过某些内容，也不能非顺序读取，多用于磁带媒体
随机存取文件（random access file）：用磁盘存储文件后，可以非顺序地读取文件中的字节或记录，或者根据关键字而不是位置来存取记录
       有两种方法指明从哪儿开始读取文件：
       1 每次READ操作都给出文件中开始读的位置
       2 提供一个特殊的SEEK操作来设置当前位置
5.1.5 文件属性
5.1.6 文件操作
1 CREATE
2 DELETE
3 OPEN:在使用文件之前，进程必须打开文件，OPEN调用目的：将文件属性和磁盘地址表载入主存，便于以后系统调用的快速存取
4 CLOSE：当存取结束后，文件属性和磁盘地址就不再需要了，这时应该关闭文件以释放内部表空间。
5 READ
6 WRITE
7 APPEND
8 SEEK
9 GET ATTRIBUTES
10 SET ATTRIBURES
11 RENAME
5.2 目录
5.2.1 层次目录系统
5.2.2 路径名
绝对路径名（absolute path name）：由根目录到文件的路径组成。
相对路径名（relative path name）：和工作目录（当前目录）一起使用
5.2.3 目录操作
5.3 文件系统的实现
5.3.1 实现文件
一、连续分配
       把每个文件作为连续数据块存储在磁盘上。
       缺点：1. 必须预先知道文件大小。
                2. 容易造成磁盘碎片
二、链接表分配
       为每个文件构造磁盘块的链接表，每个块的第一个字用于指向下一块的指针，块的其他部分存放数据。
       没有浪费空间，但是随机存取却相当缓慢，而且指针占去了一些字节，每个磁盘块存储数据的字节数不再是2的幂，这样降低了系统的运行效率，因为大多数程序都是以长度为2的幂来读写磁盘块的。
三、使用索引的链接表分配
       取出上述方案中每个磁盘块的指针字，把它放在内存的表或索引中，消除上述中的不足。
       主要缺陷：必须把整个链表都存放在内存中，对于大磁盘而言，浪费内存空间。
四、i 节点
5.3.2 实现目录
一、CP/M中的目录
二、MS-DOS中的目录
三、UNIX中的目录
5.3.3 磁盘空间管理
一、块大小
二、记录空闲块
       使用磁盘块的链接表，每个块包含尽可能多的空闲磁盘块号。
       使用位图
5.3.4 文件系统的可靠性
5.4 安全性

5.4.1 安全环境




本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u1/39425/showart_369196.html