第一章 操作系统简介
第一节 什么是操作系统
存储数据是物理地址，外存指硬盘

操作系统是覆盖在逻辑上的第一层软件，为软件提供运行环境

接口分为硬件接口（USB）、软件接口（C语言中的printf()）

操作系统必须完成的两个主要目标
1.与硬件部分相互作用，为包含在硬件平台上的所有底层可编程部件提供服务
2.为运行在计算机系统上的应用程序提供运行环境

现代计算机系统的一个重要特点是：支持多任务，即允许在同一个系统内同时驻留多个应用程序

操作系统管理的资源包括：处理机、内存、设备、文件，网络操作系统中还包括：网卡、带宽

操作系统的主要功能：
1.处理机管理
2.内存管理
3.设备管理
4.文件管理

第二节
操作系统按时间顺序经历了：
无操作系统、单道批处理系统、多道程序系统（多道批处理系统、分时系统）、 微机操作系统、网络操作系统、实时操作系统、嵌入式操作系统、物联网操作系统

第一代计算机使用电子管作为主要电子器件
第二代使用晶体管，开始使用磁性存储设备

监控程序：操作员在专门用于计算的、性能较高的计算机上装入早期的操作系统，能自动从磁带读入作业并使之运行，把作业运行结果写入专门存放输出结果的磁带上

随着电子技术发展，开始使用电路芯片作为主要电子器件（如IBM 360）

实时系统是支持实时计算的系统

批处理系统、分时系统、实时系统的特点：
1.单道批处理系统具有自动性、顺序性、单道性。
2.多道批处理系统具有多道性、无序性、调度性、复杂性。
提高资源利用率和系统吞吐量。
多道程序系统必须具有作业调度和进程调度功能。
作业调度用来从后备作业队列（在外存）中选择一个或多个要被装入内存的作业。
进程调度程序用来从内存中选择一个或多个进程使其在CPU上运行。
3.分时系统允许多个用户通过终端同时使用，具有多路性、独立性、及时性、交互性。
4.实时系统必须及时响应外部事件请求，并在规定时间内完成。具有多路性、独立性、及时性、交互性、可靠性。

分时系统的实现需要解决两个关键问题：及时接收、及时处理

主机操作系统是运行在大型主机上的操作系统，主要提供三类服务：批处理、事务处理、分时处理

批处理系统处理不需要交互式用户干预的周期性作业，如：保险公司的索赔处理、连锁商店的销售报告

事物处理系统负责大量的小请求

分时系统允许多个用户同时在计算机上工作

嵌入式系统的概念出现在20世纪70年代，是宿主于非计算机设备中的计算机系统。嵌入式操作系统是运行与嵌入式设备中的操作系统

第三节 操作系统的特征
操作系统具有并发、共享、虚拟和异步性特征。
1.并发
并发是指两个或多个事件在同一时间间隔内发生。
并行是指多个时间同时发生。
2.共享
指系统中的资源可欧共内存中多个并发执行的进程共同使用。
资源共享有两种方式：互斥共享和同时共享
3.虚拟
指通过某种技术把一个物理实体变成若干逻辑上的对应物。
4.异步性
内存中的每个程序何时执行、暂停，何时完成是不可预知的。

第四节 操作系统的功能
内存管理的主要任务：为多道程序的运行提供良好的环境，方便用户使用内存，提高内存利用率，以及从逻辑上扩充内存以实现虚拟存储

内存管理应具有：内存分配、内存保护、地址映射、内存扩充等功能

内存保护的任务：
1.使操作系统内核的空间不会被用户随意访问，以保证系统的安全和稳定
2.确保每道用户程序都在自己的内存空间中运行，互不干扰

CPU执行程序过程中访问内存时，需要把程序的逻辑地址转变为物理地址，这个转换过程称为地址映射

为了能从逻辑上扩充内存，系统必须具有内存扩充机制，以实现请求调入功能和置换功能

进程管理功能主要包括：进程的描述与组织、进程控制、进程同步、进程通信及进程调度

设备管理应具有的功能：
1.缓冲管理
2.设备分配
3.设备处理
4.设备独立性和虚拟设备

目录项包括：文件名、文件属性、文件的地址等信息

操作系统提供给程序员的接口是系统调用

第五节 操作系统的体系结构
明确清晰的软件体系结构是一条贯穿软件系统整个生命周期的主线，是软件设计成功的基础和关键

单体内核是操作系统中最早、最常见的体系结构，如：Unix系统、MS-DOS、Linux、Mac OS X、BSD等

层次结构的基本思想：
将操作系统分解为多个小的、容易理解的层，系统功能被隔离在不同层中，每一层提供对系统功能的部分抽象，然后采用单向调用的顺序，形成一连串彼此连续对系统功能的“抽象串”，最终形成对整个系统的完整抽象

分层结构最经典的例子：Dijkstra的THE系统

微内核技术是操作系统发展的一个里程碑，核心思想是核心功能外移

微内核结构用一个水平分层的结构代替传统的纵向分层的结构的好处：
1.只要接口规范，操作系统可以方便的增加或删除服务功能，系统具有很好的灵活性
2.服务器进程运行在独立的用户进程空间中，如果某个服务器出现问题，不会引起系统其他服务器甚至是系统的崩溃，可靠性好
3.微内核体积小，便于测试、管理、维护
4.由于微内核技术实现了基于客户/服务器体系结构的操作系统，完全适宜于网络环境及分布计算模型

第六节 指令的执行
一个单一指令需要的处理称为指令周期，一个指令周期可以划分为两个步骤，分别是取指周期和执行周期

在每个指令周期开始时，处理器从存储器中取一条指令

处理器解释指令并执行要求的动作的分类：
1.处理器与存储器之间的指令或数据传送操作
2.处理器与I/O设备之间的指令或数据传送操作
3.算术运算操作或逻辑运算操作
4.控制操作，即修改指令的执行顺序的操作

程序执行的过程是反复取指令和执行指令的过程

指令执行的结果是：使寄存器或内存单元的值发生变化，指令执行的过程也就是存储体内容不断变化的过程

取指令和执行指令是由硬件完成的，不同硬件的体系结构支持不同的指令集合，为某一种硬件平台开发的操作系统不能直接在另一种体系结构的硬件上运行

第二章 进程管理
第一节 进程的描述
程序的顺序执行，特点：顺序性、封闭性、可再现性
程序的并发执行，特点：间断性、失去封闭性、不可再现性

任意时刻一个CPU上只有一个程序在执行

进程的定义：
1.进程是允许并发执行的程序在某个数据集合上的运行过程
2.进程是由正文段、用户数据段、进程控制块共同组成的执行环境

进程代表了程序的执行过程，是一个动态的实体
程序装入内存后就可以运行了，根据指令计数器PC的值，不断将指令从内存取到CPU的指令寄存器中，经过译码后完成各种操作

进程的特征：并发性、动态性、独立性、异步性、结构特征

进程与程序的比较
区别：程序是静态的，进程是动态的；程序是永久的，进程是暂时存在的；程序与进程的存在实体不同。
联系：进程是程序的一次执行，一个程序可以对应多个进程

进程控制块
进程实体存在的标志是操作系统管理进程所使用的数据结构——进程控制块
进程控制块是实体的一部分，是操作系统中最重要的数据结构
操作系统在创建进程时，首先要为进程创建进程控制块，也就是生成一个进程控制块类型的变量，以存储所创建进程的描述信息。
每个进程有唯一的进程控制块，进程控制块是操作系统感知进程存在的唯一标志

进程控制块中包含的信息
1.进程标识符信息
2.处理机状态信息：通用寄存器、指令计数器、程序状态字psw、用户栈指针（栈指针指向该栈的栈顶）
3.进程调度信息
4.进程控制信息

进程的状态（p48页 进程状态转换图）
就绪态、执行态、阻塞态
创建新进程一般设置为就绪态

进程的组织
操作系统组织和管理进程时通过组织和管理进程控制块来实现的
1.链接方式
2.索引方式
3.进程队列

第二节 进程的控制
什么情况下需要创建新进程？
1.用户登录、2.作业调度、3.提供服务、4.应用请求

在Linux系统中，除了0号进程（swapper进程）外的其他进程都是由其父进程创建的

进程可以从操作系统那里直接获得资源，也可能只从其父进程资源子集那里获得资源

当新进程被创建时，有两种执行可能：
1.父进程与子进程并发执行
2.父进程等待，直到某个或全部子进程执行完毕
新进程的地址空间也有两种可能：
1.子进程共享父进程的地址空间
2.子进程拥有独立地址空间

调用创建新进程的系统调用来创建进程的一般步骤：
1.申请空白PCB
2.为新进程分配资源
3.初始化进程控制块
4.将新进程插入就绪队列

什么情况下操作系统进行进程的阻塞和唤醒操作？
1.请求系统服务
2.启动某种操作
3.新数据尚未到达
4.无新工作可做

什么情况下操作系统将阻塞态进程唤醒？
1.将进程从阻塞队列中移出
2.将进程状态由阻塞态改为就绪态
3.将进程插入就绪队列

什么情况下进程被终止？
1.当进程正常执行完毕，调用终止进程的系统调用，请求操作系统删除该进程
2.当一个进程调用适当的系统调用，终止另外一个进程。（父进程终止子进程）

如果是选择硬盘启动，计算机会检查硬盘的0柱面0磁道1扇区。
如果发现该扇区以0xAA55结束，则BIOS认为它是引导扇区

第三节 操作系统内核
资源管理包括进程管理、存储器管理、设备管理

中断的类型：
1.同步中断
2.异步中断

大部分PC中有两个时钟源，分别称为实时时钟（RTC）和OS时钟。
RTC时钟也称为CMOS时钟，是一块时钟芯片，靠电池供电
OS时钟由操作系统控制

系统调用是系统程序与用户程序之间的接口

在类Unix系统中，系统调用多使用C语言提供的库函数作为接口

系统调用的类型：
1.进程控制类系统调用。创建、撤销进程
2.文件操纵类系统调用。创建删改读写文件
3.设备管理类系统调用。请求、释放设备
4.通信类系统调用。打开、关闭连接

第四节 进程同步
同步机制应遵循的准则
1.空闲让进
2.忙则等待
3.有限等待
4.让权等待

自旋锁是用来在多处理器环境中工作的一种特殊的锁。
如果内核控制路径发现自旋锁“开着”，就是相应的整形信号量的值大于0，“关着”表示整形信号量等于或者小于0

整形信号量的值只能由wait和signal操作改变

管程是一个由过程、变量及数据结构等组成的集合，他们组成一个特殊的模块或软件包。

一个管程过程，可以用在某条件变量上执行wait操作，将调用管程的进程阻塞并插入该条件的阻塞队列，用在条件变量上执行signal操作，唤醒在该条件上阻塞的进程

第五节 进程通信
共享存储系统的类型
1.基于共享数据结构的通信方式
2.基于共享存储区的通信方式

在消息传递系统中，根据源进程向目标进程传递消息方式的不同，可分为直接通信方式和间接通信方式

管道文件存在于外存中，其中的消息没有固定长度，能用于进程间大量的信息通信

消息缓冲区是一个结构型数据结构，通常包括发送进程标识符、消息长度、消息正文和指向下一个消息缓冲区的指针

消息缓冲队列需要被当做临界资源，在发送原语和接收原语中对消息缓冲队列的访问要进行互斥与同步

第六节 线程
线程在运行中呈现间断性，有就绪、阻塞和执行三种基本状态

线程的实现可以分为：用户级线程、内核级线程

引起线程终止的原因：
1.正常结束
2.异常结束
3.外界干预

线程的终止过程：
1.根据被终止线程的标识符，从TCB集合中检索出该线程的TCB，从中读出该线程的状态
2.若被终止线程正处于运行状态，应立即终止该线程的执行，并置调度标志为真，用于指示该线程被终止后应重新执行线程调度程序
3.将被终止线程的TCB从所在队列（或链表）中移出，等待其他程序来搜集信息

用户线程的阻塞过程：
1.停止该线程的执行，将该线程的状态改为阻塞态
2.将该线程控制块插入相应的线程阻塞队列
3.将该线程所属进程控制块插入相应的进程阻塞队列
4.将该线程所属进程的进程控制块插入相应的进程阻塞队列
5.将控制传递给进程调度程序，重新进行进程调度

用户线程的唤醒过程：
1.将该线程所属进程的状态由阻塞改为就绪
2.将该线程所属进程的进程控制块进程阻塞队列中移出
3.将该线程所属进程的进程控制块插入进程就绪队列
4.将该线程状态由阻塞改为就绪态
5.将该线程的线程控制块从线程阻塞队列中移出
6.将该线程的线程控制块插入线程就绪队列

内核线程的阻塞过程：
1.停止该线程的执行，将该线程的状态改为阻塞态
2.将该线程控制块插入相应的线程阻塞队列
3.将控制传递给线程调度程序，重新进行线程调度

内核线程的唤醒过程：
1.将该线程状态由阻塞改为就绪态
2.将该线程的线程控制块从线程阻塞队列中移出
3.将该线程的线程控制块插入线程就绪队列

第三章 进程调度与死锁
进程调度的功能：
进程调度功能由操作系统内核的进程调度程序完成；
Linux内核中，进程调度功能的实现从调用内核函数schedule（）开始；
进程调度的功能是按照某种策略和算法从就绪态进程中为当前空闲的CPU选择在其上运行的新进程。

进程调度的时机：
当一个进程运行结束、进程阻塞、中断返回、在支持抢占式调度的系统中有比当前运行进程优先级更高的进程到来、当前运行进 程的时间片用完时

第二节 进程调度算法
选择调度方式和算法的若干准则：
1.周转时间短
2.响应时间快
3.截止时间的保证
4.系统吞吐量高
5.处理机利用率好

优先权调度算法的一个主要问题是无穷阻塞，或称饥饿问题

低优先权进程无穷等待的问题解决方案之一是老化技术

多级反馈队列算法的设计要考虑的问题：
1.就绪队列的数量
2.根据进程优先权确定进程应该进入那个就绪队列的算法
3.用以确定进程何时转移到较高优先权队列的算法
4.用以确定进程何时转移到较低优先权队列的算法
5.用以确定进程在需要服务时应该进入哪个队列的算法

第三节 实时系统中的调度
实现实时调度的基本条件有：提供必要的调度信息、系统处理能力强、采用抢占式调度机制和具有快速切换机制

实现实时调度，系统需要为调度程序提供的信息：
1.就绪时间，是一个实时任务成为就绪态的起始时间
2.开始截止时间和完成截止时间
3.处理时间，指一个实时任务执行所需要的资源信息
4.资源要求。关于任务执行所需要的资源信息
5.优先级。

快速切换机制应具有的能力包括对外部中断的快速响应能力、快速的进程切换能力

松弛度用来表示一个实时进程的紧迫程度

第四节 进程切换
进程切换的步骤：
1.保存包括程序计数器和其他寄存器在内的CPU上下文环境
2.更新被替换进程的进程控制块
3.修改进程状态，把执行态改为就绪态或阻塞态
4.将被替换进程的进程控制块移到就绪队列或阻塞队列
5.执行通过进程调度程序选择的新进程，并更新该进程的进程控制块
6.更新内存管理的数据结构
7.恢复被调度程序选中的进程的硬件上下文

第五节 多处理器调度
紧密耦合多处理器系统、松弛耦合多处理器系统
对称多处理器系统、非对称多处理器系统

紧密耦合的多处理器系统通常通过高速总线或高速交叉开关实现多个处理器之间的互连

对称多处理器系统中，静态分配方式的优点是进程调度的开销小，缺点是不能动态的平衡各处理器的负载，使系统存在各处理器忙闲不均的情况

动态分配的基本特征就是每个进程经过多次调度，每次获得的不一定是同一个处理器

自调度算法的优点是易移植和有利于提高CPU的利用率
自调度方式的缺点是瓶颈问题、低效性、切换频繁

专用处理器的优点是加速了应用程序的运行速度、避免了进程切换

第六节 死锁
产生死锁的原因是竞争共享资源且分配资源的顺序不当

产生死锁的必要条件：
1.互斥条件
2.请求和保持条件
3.不剥夺条件
4.环路等待条件

处理死锁的基本方法有预防死锁、避免死锁、检测并解除死锁和忽略死锁问题

预防死锁可以通过摒弃请求和保持条件、不剥夺条件、环路等待条件之一来实现

摒弃环路等待的方法是指进程必须按规定的顺序申请资源

解除死锁的途径有两个：终止处于死锁状态的进程、抢占死锁进程占有的资源

采用终止部分进程的方式是需要考虑的因素：
1.进程的优先级是什么？
2.进程已执行了多久？进程在完成其指定任务之前还需要多长时间？
3.进程使用了多少资源？分别是什么类型的资源？这些资源是否容易抢占？
4.进程需要多少资源才能完成
5.需要终止多少进程才能解除死锁
6.进程是交互的还是批处理的

第四章 内存管理
第一节 存储器的层次结构
CPU寄存器保存最常用的数据

如果程序需要的数据是存放在CPU寄存器中的，程序执行期间在0个周期内就可以访问到它们

程序的执行遵循局部性原理

关于程序执行局部性原理的几个论点：
1.程序在执行时，除了少部分的转移和过程调用指令以外，在大多数情况下是顺序执行的
2.过程调用将会使程序的执行轨迹由一部分内存区域转到另一部分内存区域
3.程序中存在很多循环结构，他们虽然由少数指令构成，但多次执行
4.程序中往往包括许多对数据结构的处理

局部性原理表现为时间和空间的局部性

第二节 程序的链接和装入
链接程序要解决的问题是将编译后的目标模块装配成一个可执行的程序

链接可分为：静态链接、动态链接

静态链接是程序运行前，用链接程序将目标模块链接成一个完整的装入模块；
任务一是对逻辑地址进行修改，二是变换外部调用符号

动态链接的优点是节省内存和外存空间，方便了程序开发

多数系统允许操作系统将用户进程放在物理内存的任意位置

就根据形成在内存中物理地址的时机不同，把程序的装入方式分为：绝对装入方式、可重定位装入方式（静态重定位）、动态运行时装入方式

在程序装入时对目标程序中的指令和数据地址的修改过程称为重定位

可重定位方式的两个特点：
1.编译程序使目标模块的起始地址从0开始
2.程序装入时，装入程序根据内存的使用情况将装入模块装入到内存的某个位置，并对模块进行重定位

动态运行时装入：一个进程在被换出之前所在的内存位置与后来被外存重新调入内存时所在的内存位置不同，在这种情况下，地址映射必须延迟到进程执行时再进行

第三节 连续分配存储管理方式
连续分配是指操作系统分配内存时，为每个进程分配一块物理地址连续的内存空间

连续分配方式有单一连续分区分配方式、固定分区分配方式、动态分区分配方式

在单用户、单任务操作系统中较常用的方法是设置一个基址寄存器和一个界限寄存器

基址寄存器中存放程序在物理内存中的最小地址，界限寄存器中存放装入用户区程序的地址范围

有些单用户、单任务的操作系统没有设置存储器保护机制的原因：
1.节省硬件
2.可能是用户自己造成的，后果不严重，不影响其他用户程序的执行，操作系统容易重装与重启

使用固定分区分配内存利用率低，难以提高系统的多道程序度
动态分区分配是根据进程的实际需要，为进程分配大小合适的内存区域
系统中用户分区的数量和大小都是动态变化的
动态分区分配算法包括：首次适应算法、循环首次适应算法、最佳适应算法
循环首次适应算法的优点是空闲区分布均匀、查找开销较小，缺点是容易使系统缺乏大空闲区
最佳适应算法的优点是避免了大材小用，能提高内存利用率，缺点是容易 留下难以利用的小空闲区

第四节 基本分页存储管理方式
把进程离散地存储在内存中物理地址不连续的区域中，这种内存管理方式称为离散内存管理方式

根据离散内存管理分配内存空间的基本单位的不同，将其分为三种不同的管理方式：分页存储管理、分段存储管理、段页式存储管理

将一个进程的逻辑地址空间分为若干个大小相等的片，称为页

将物理内存空间分成与页大小相同的若干个存储快，称为页框或页帧

在为进程分配内存时，以页框为单位的进程中的若干页分别装入多个可以不相邻接的页框中

在进程的最后一页一般装不满一个页框，而形成了不可利用碎片，称为页内碎片，是一种内部碎片

页表是系统为进程建立的数据结构，页表的作用是实现从页号到页框号的映射

影响页大小设计的因素：
1.管理内存的开销
2.内存的利用率

快表也称转换后援缓冲（TLB），是为了提高CPU访存速度而采用的专用缓存，用来存放最近被访问过的页表项

TLB是关联的快速内存。TLB的条目由两部分组成：键和值。键部分对应页号，值部分对应页所在的页框号

引入TLB之后的地址变换过程：
1.CPU产生分页的逻辑地址页号和页内偏移后，将该逻辑地址的页号提交给TLB
2.查找TLB，如果找到页号，则把该页所在的页框号用于形成物理地址。否则（TLB失效）查找内存页表，从内存页表中找到相应的页表项，读取页所在的页框号，以形成物理地址
3.如果所查找的页表项不在TLB中，在访问完页表后，要把找到的页表项中的页号和页框号写到TLB中。如果TLB中的条目已满，系统会根据某种策略（如最近最少使用替换）选择一个TLB中的条目，用刚访问的页表项信息替换选中的这个TLB条目

当系统支持的逻辑空间很大时，意味着系统允许每个进程的逻辑地址空间很大

使用两级页表的系统，当进程切换时，要运行的进程的页目录表起始地址被写入CPU寄存器，可以称之为页内寄存器

在两级页表的寻址中，地址映射的过程如下：
1.对于给定的逻辑地址A，由硬件从中分离出页目录号p1、页号p2和页内地址d。
2.由页表寄存器的值和页目录号p1，从存放页目录的页框中找到页表所在的页框号。
页表所在的页框号在内存中的地址 = 页目录起始地址 + p1 x 页表项长度，
从改地址指示的物理内存单元中读取页表所在的页框号
3.由页表所在的页框号和页号p2，从存放页表的页框中找到进程页所在的页框号，
进程页所在的页框号在内存中的地址 = 页表的起始地址 + p2 x 页表项长度
页表的起始地址 = 页表所在的页框号 x 页框的大小
4.A的物理地址 = 进程页所在的页框号 x 页框大小 + 页内地址d

地址空闲页框链表可以按递增的顺序排序，每个结点中包含页框的地址信息，指向后面结点的指针和指向前面结点的指针

第五节 基于分页的虚拟存储系统
虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统

虚拟存储技术实现的基本思想是只把进程的一部分装入内存

虚拟存储技术能带来的好处：
1.提高内存利用率
2.提高多道程序度
3.把逻辑地址空间和物理地址空间分开，使程序员不用关心屋里内存的容量对编程的限制

虚拟存储系统的主要特征：
1.离散性。是指进程可以分散地存储在物理内存中
2.多次性。是指不必把进程一次性全部装入内存，可以分多次装入内存
3.对换性。是指在内存中的进程可以换出，以腾出内存空间换入外存中的进程
4.虚拟性。是指虚拟存储系统为用户提供了比实际物理内存大的逻辑内存空间，是实现虚拟存储系统的最重要的目标

页表是支持请求分页系统最重要的数据结构，其作用是记录描述页的各种数据，包括在实现逻辑地址到物理地址映射时需要的页号与页框号的对应关系。除了页号和页框号之外，页表中增加了请求换入和页置换时需要的数据。

缺页异常机构的具体过程：
主要作用是：在访问内存的过程中发现缺页时产生缺页异常信号，使CPU中断当前控制流的执行，专去执行操作系统的缺页异常处理程序，完成请求调页。
1.分页硬件通过页表完成逻辑地址到物理地址的映射时，通过检查页表中的状态位P，判断当前被访问的页是否在内存中。如果不在，则产生缺页异常信号。
2.执行操作系统的缺页异常处理过程。现在内存中为请求调入的页找一个空闲页框，然后调度磁盘操作，把需要的页装入找到的空闲页框中
3.修改页表，更新已经调入页的存在位、在内存中的页框号，访问位和保护位等字段的值
4.重新开始执行因缺页而被中断的指令

采用平均分配算法为进程分配页框的缺点是算法不考虑进程规模，可能使大进程分配到的页框与小进程一样多

FIFO是最简单的页置换算法

计算机系统要提供足够的硬件来支持LRU算法是比较困难的，许多系统在实现时都采用LRU的近似算法，如附加引用位算法、简单Clock算法和改进型Clock算法等

引起系统抖动的主要原因是系统中的进程数量太多，每个进程能分配到的页框太少，以至于进程运行过程中频繁请求调页

抖动的预防：
1.采取局部置换策略
2.在CPU调度程序中引入工作集算法
3.挂起若干进程

第六节 分段存储管理
在使用分段存储管理的系统中，程序员使用二维的逻辑地址，一个数用来表示段，另一个数用来表示段内偏移

在分段的存储管理方式中，进程的地址空间被划分成若干个段。每个段定义了一组逻辑信息，每个段的大小由相应的逻辑信息组的长度确定，段的大小不一样，每个段的逻辑地址从0开始，采用一段连续的地址空间

若已知逻辑单元的地址为s:d，求相应物理地址的步骤如下：
1.以段号s作索引，从段表中找到段号为s的段表项
2.从找到的段表项中读出s段的基地址和段大小
3.如果d≤段大小，则将段基址与段内偏移d相加，得到与逻辑单元s:d相应的物理单元地址

分页和分段的主要区别：
1.页是按物理单位划分的，分页的引入是为了提高内存的利用率和支持虚拟存储。
段是按逻辑单位划分的，一个段含有一组意义相对完整的信息。引入分段的目的是为了方便程序员编程
2.页的大小是固定的。段的大小不固定
3.分页的地址空间是一维的，分段的地址空间是二维的
程序员在标识一个逻辑地址时需要给出两个数：段号、段内偏移

地址变换过程：
在段页式存储管理系统中，逻辑地址与分段系统的逻辑地址相同，由段号s和段内偏移地址d构成，地址变换过程：
1.以段号s做索引，找到段s的段表项，得到该段页表的起始地址
2.通过分页机制从段内偏移d中分理出页号P和页内偏移W

3. 以段内页号P做索引，从段s的页表中搜索页号P对应的页表项
   4.从页表项中得到页所在的页框号
   5.由页框号与页内偏移W得到某逻辑地址对应的物理地址

第七节 Linux的伙伴系统
Linux的伙伴系统算法把所有的空闲页框分组为11个块链表
对1024个页框嘴大请求对应着4MB大小的连续页框
每个块的第一个页框的物理地址是该块大小的整数倍

内核试图把大小为b的一对空闲伙伴块合并为一个大小为2b的单独块

两个块称为伙伴需满足的条件：
1.两个块具有相同的大小，记做b
2.它们的物理地址是连续的，起始地址是2b的整数倍

第五章 文件系统
第一节 文件
多数操作系统都支持文件名用圆点隔开分为两部分。圆点后面的部分称为文件扩展名

无结构字节序列文件也称为流式文件，Unix和Windows系统中都采用这种方式

在固定长度记录序列模型中，构成文件的基本单位是具有固定长度的记录，
把文件作为记录序列的中心思想：读操作返回一个记录，而写操作重写或追加一个记录

在树形文件结构中，基本操作是获取具有特定关键字的记录

常用的文件存取方式有两种：顺序存取和随机存取

随机存取又称直接存取，即可以以任意顺序读取文件中的字节或记录

常用的文件操作：
create、delete、open、close、read、writer、append、seek、getattributes、setattributes
seek：对于随机存取文件，要指定从何处开始取数据

第二节 目录
目录文件有两种常见的结构：属性放在目录项中和放在i结点中

文件目录的组织和管理是文件管理的一个重要方面，包括单层目录、两级目录和树形目录

使用两级目录的优点是解决了文件的重名问题和文件共享问题，查找时间降低。缺点是增加了系统的存储开销

把两级目录的层次关系加以推广，形成了多级目录又称树形目录

树形目录的优点是便于文件的分类，层次结构清晰，便于管理和保护，解决了重名问题，查找速度加快。
缺点是查找一个文件按路径名逐层检查，由于每个文件都放在外存中，多次访问磁盘会影响速度，结构相对复杂

用目录树组织文件系统时，需要有某种方法指明文件，如：绝对路径名、相对路径名

第三节 文件系统的实现
实现文件存储的常用方式：连续分配、使用磁盘链接表的分配、使用内存的链接表分配和i—结点

连续分配方式的优点：
1.实现简单
2.读操作性能好
连续分配方式的缺点：随着时间的推移，磁盘会变得零碎

磁盘链接表的分配方式的优点：可以充分利用每个簇，不会因为磁盘碎片（出来最后一块中的内部碎片）而浪费存储空间，管理简单
缺点：随机存取相当缓慢

相对路径的查找与绝对路径的查找方法相同，只不过是从当前工作目录开始查找而不是根目录开始

一般簇的大小是2的整数次幂个连续的扇区

第六章 I/O设备管理
第一节 I/O系统的组成
I/O系统的结构分为：微机I/O系统、主机I/O系统

I/O系统可采用四级结构，包括主机、通道、控制器、设备

I/O设备的分类
1.按传输速率分类
低速设备。如：键盘和鼠标
中速设备。如：打印机
高速设备。如：磁带机、磁盘机
2.按信息交换的单位分类
块设备。如：磁盘
字符设备。如：终端、打印机、鼠标
3.按设备的共享属性分类
独占设备。
共享设备。
虚拟设备。

设备控制器的功能：
1.接受和识别命令
2.数据交换
3.设备状态的了解和报告
4.地址识别
5.数据缓冲
6.差错控制

第二节 I/O控制方式
输入/输出方式有早期的程序轮询控制方式。在中断被引入计算机后广泛采用中断控制方式

采用轮询控制方式，主机试图发送I/O控制命令之前，先通过反复检测设备控制器状态寄存器的忙/闲标志位，若设备“忙“，主机继续检测该标志位，直到该位为“空闲”，主机发送I/O指令

采用中断控制方式的I/O工作模式是CPU执行进程中，发出输入/输出请求若此时I/O设备忙，则进程阻塞等待

中断控制的工作方式能使CPU与I/O设备在某些时间段上并行工作，提高CPU的利用率和吞吐量

DMA控制需要特殊结构的设备控制器，DMA控制器的逻辑组成包括三部分，主机与DMA的接口、DMA与设备的接口、I/O控制逻辑

第三节 缓冲管理
引入缓冲区的主要原因：
1.处理数据流的产生者与消费者之间的速度差异
2.协调传输数据大小不一致的设备

操作系统提供的最简单的缓冲类型是单缓冲区

双缓冲：当一个进程往一个缓冲区中传递数据（或从这个缓冲区中读取数据）时，操作系统正在清空（或填充）另一个缓冲区

循环缓冲的组成：
1.多个缓冲区
1.空缓冲区R：生产者进程下一个可用的空缓冲区
2.已装满数据的缓冲区G：用于指示消费者进程下一个可用的装有产品的缓冲区
3.线性工作缓冲区C：消费者进程正在使用的工作缓冲区
2.多个指针
1.Nextg：用于指示消费者进程下一个可用的装有数据的缓冲区
2.Nexti：用于指示生产者进程下一个可用的空缓冲区
3.Current：用于指示进程正在使用的工作缓冲区

缓冲池的4种工作缓冲区：收容输入数据的缓冲区、提取输入数据的缓冲区、收容输出数据的缓冲区和提取输出数据的缓冲区

第四节 设备分配
每张设备控制表包含的信息：
1.设备类型
2.设备标识符
3.设备状态：忙/闲
4.指向控制器表的指针
5.重复执行的次数或时间
6.设备队列的队首指针

为了使系统有条不紊的工作，系统在分配设备时应考虑以下3个因素：
1.设备的固有属性
2.设备分配算法
3.设备分配时的安全性

设备独立软件完成的主要功能：执行所有设备的共有操作和向用户层软件提供统一的接口

SPOOLing系统的组成包括输入井和输出井、输入缓冲区和输出缓缓从去、输入进程SP和输出进程SP、请求I/O队列

第五节 I/O软件原理
设备管理软件的功能：
1.实现I/O设备的独立性
2.错误处理
3.异步传输
4.缓冲管理
5.设备的分配和释放
6.实现I/O控制方式

I/O中断处理程序的作用是将发出I/O请求而被阻塞的进程唤醒

设备驱动程序是I/O进程与设备控制器之间的通信程序，其主要任务是接受上层软件发来的抽象的I/O请求，把它们转换为具体要求后，发送给设备控制器，启动设备去执行

设备无关I/O软件的功能：
1.设备命名，将设备名映射到相应的驱动程序
2.设备保护，为设备设置合理的访问权限
3.提供独立与设备的块大小
4.为块设备和字符设备提供必要的缓冲技术
5.块设备的存储分配
6.分配和释放独立设备
7.错误处理

第六节 磁盘管理
磁盘格式化完成后，一般要对磁盘分区

对磁盘可以从不同的角度进行分类，最常见的有：将磁盘分成硬盘和软盘、单片盘和多片盘、固定头磁盘和活动头磁盘

目前常用的磁盘调度算法：先来先服务、最短寻道时间优先、扫描算法

SSTF算法虽然能获得较好的寻道性能，但却可能导致某个进程发生“饥饿”现象

SCAN算法既能获得较好的寻道性能，又防止了“饥饿”现象，广泛用于大中小型机器和网络中的磁盘调度

提高磁盘I/O速度的方法：
1.提前读
2.延迟写
3.优化物理块的分布
4.虚拟盘
5.磁盘高速缓存