操作系统目的是：为了填补人与机器之间的鸿沟，即建立用户与计算机之间的接口，而为裸机配置的一种系统软件。

系统软件：编辑程序、汇编程序、编译程序、数据库管理系统等

操作系统在计算机系统中的地位：

程序与进程

程序顺序执行时的主要特征包括：顺序性、封闭性（程序在封闭的环境下运行，即程序运行时独占全机资源，程序一旦开始执行其执行结果不受外界因素影响）和可再现性。

前趋图：有向无循环图

PV操作

信号量s：为0或1，一个前趋关系对应一个信号量

程序并发执行时的主要特征包括：

失去了程序的封闭性

程序和机器的执行程序的活动不再一一对应

并发程序之间的相互制约性

前驱图

进程的状态和状态间的转换

三态模型

在多道程序系统中，进程在处理器上交替运行，状态也不断地发生变化，因此进程一般有3种基本状态：运行、就绪和阻塞。

运行：当一个进程在处理机上运行时。

就绪：一个进程获得了除处理机外的一切所需资源，一旦得到处理机（CPU）即可运行（还未得到）。

阻塞（等待或睡眠）：进程一开始是运行的，中途因为正在等待某一事件发生而暂时停止运行，这时即使把处理机分配给进程也无法运行（撤销CPU）。

进程间的通信

在多道程序环境的系统中存在多个可以并发执行的进程，故进程间必然存在资源共享和相互合作的问题。进程通信是指各个进程交换信息的过程。

同步和互斥

同步：合作进程间的直接制约问题。

  进程间的同步：是指在系统中一些需要相互合作，协同工作的进程，这样的相互联系称为进程的同步。

  例如，进程A向缓冲区送数据，进程B从缓冲区取数据加工，当进程B要取数据加工时，必须是进程A完成了向缓冲区送数据的操作，否则进程B必须停下来等待进程A的操作结束。

互斥：申请临界资源进程间的间接制约问题。

  进程间的互斥：是指系统中多个进程因争用临界资源而互斥执行。

 临界资源：在多道程序系统环境中，那些一次只能供一个进程使用的资源。如打印机、共享变量和表格等。

临界区管理的原则（吃饭）：

临界区：是进程中对临界资源实施操作的那段程序。

对互斥临界区管理的4条原则如下：

有空即进：当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间。

无空则等：当有一个进程在临界区时，其他欲进入临界区的进程必须等待，以保证进程互斥地访问临界资源。

有限等待：对于要求访问临界资源的进程，应保证进程能在有限的时间进入临界区，以免陷入饥饿状态。

让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入忙等状态

信号量机制

信号量机制是一种有效的进程同步与互斥工具。

信号量机制主要有：

- 整型信号量

- 记录型信号量

- 信号量集机制

整型信号量：

信号量是一个整型变量，根据控制对象的不同被赋予不同的值。信号量分为如下两类：

- 公用信号量：实现进程间的互斥，初值为1或资源的数目。

- 私用信号量：实现进程间的同步，初值为0或某个正整数。

信号量 S 的物理意义：

- S ≥ 0：表示某资源的可用数，此时有可用资源；

- S＜0：则其绝对值表示阻塞队列中等待该资源的进程数，此时无可用资源，并且有进程被阻塞。

PV操作

PV操作：实现进程同步与互斥的常用方法。

P操作和V操作是低级通信原语，在执行期间不可分割。其中：

P操作（减）：表示申请一个资源；

  定义：S := S−1（S表示信号量）

  - S ≥ 0：执行P操作的进程继续执行；

  - S＜0：无可用资源，置该进程为阻塞状态，并将其插入阻塞队列。

V操作（加）：表示释放一个资源。

  定义：S := S+1

  - S > 0：执行V操作的进程继续执行；

  - S<=0：表示释放前有程序被阻塞，从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。

利用PV操作实现进程的互斥：

1. 令信号量的初始值为1；

2. 进入临界区：执行P操作；

3. 退出临界区：执行V操作。

利用PV操作实现进程的同步(生产者和消费者)：

实现进程的同步可用一个信号量与消息联系起来。

Isempty初值为1，isfull初值为0

生产者：

p(isempty)和v(isfull)

消费者：

p(isfull)和v(isempty)

信号量的值：

- 为0：表示希望的消息未产生；

- 非0：表示希望的消息已经存在。

死锁

当有 n 个进程，m个资源，且每个进程所需要的资源数为k，并且系统采用的分配策略是轮流地为每个进程分配资源时，判断是否发生死锁的公式如下：

m >= n *(k-1)+1

进程资源图

先分配，再申请

不存在死锁就可以化简。

死锁的处理策略主要有4种：鸵鸟策略（即不理睬策略）、预防策略、避免策略和检测与解除死锁。

死锁避免：银行家算法：当一个进程申请使用资源的时候，如果发现分配给该进程资源后的系统处于不安全状态，则不予分配，让该进程继续等待。

线程

传统进程有两个基本属性：

可拥有资源的独立单位；

可独立调度和分配的基本单位。

引入线程的原因是：系统要为进程付出较大的时空开销。引入线程后，将传统进程的两个基本属性分开：

- 线程：作为调度和分配的基本单位；

- 进程：作为独立分配资源的单位。

线程的特点：

- 线程基本上不拥有资源，只拥有一点运行中必不可少的资源（如程序计数器、一组寄存器和栈），它可与同属一个进程的其他线程共享进程所拥有的全部资源。

- 线程也具有就绪、运行和阻塞3种基本状态。

- 线程可创建另一个线程。

- 同一个进程中的多个线程可并发执行。

存储管理

程序局部性原理

程序的局限性表现在以下两个方面：

- 时间局限性：

  - 如果程序中的某条指令一旦执行，则不久的将来该指令可能再次被执行；

  - 如果某个存储单元被访问，则不久以后该存储单元可能再次被访问。

  产生时间局限性的典型原因是在程序中存在着大量的循环操作。

- 空间局限性：指一旦程序访问了某个存储单元，则在不久的将来，其附近的存储单元也最有可能被访问。

  即程序在一段时间内所访问的地址可能集中在一定的范围内，其典型原因为程序是顺序执行。

页面变换表：（先淘汰在内存中为0的）

分页存储管理

16位，4位页号（逻辑页地址），12位（4K）页内地址（物理页地址）

段页式存储管理

最多有多少个段，每段最大允许有多少个页，页的大小为多少

缓冲技术

单缓冲工作过程图：

双缓冲工作过程图：

N个作业，输入时间T，传送时间M，处理时间C

单缓冲计算公式为：(T+ M)*n + C  (C<T)

双缓冲计算公式为：T*n+M+C  (M+C<T)

磁盘调度算法（移臂调度算法）

- 先来先服务（FCFS）：根据进程请求访问磁盘的先后次序进行调度。

- 最短寻道时间优先（SSTF，最短移臂算法）：该算法选择与当前磁头（移动臂）所在的磁道距离最近的进程，使得每次的寻道时间最短。

- 扫描算法（SCAN，电梯调度算法）：总是从磁头当前位置开始，沿磁头的移动方向去选择离当前磁头最近的那个柱面的请求。如果沿磁头的方向无请求访问时，就改变磁头的移动方向。

- 单向扫描算法（CSCAN，循环扫描算法）：扫描算法的改进，算法规定磁头只做单向移动。

旋转调度算法（可优化）

多级索引结构

文件目录

- 文件控制块（FCB）：用于文件的描述和控制的数据结构，实现了文件的“按名存取”。

  文件控制块至少要包括文件名和存放文件的物理地址。

  文件控制块也称为文件的说明或文件目录项（简称目录项）。

- 文件目录：文件控制块的有序集合。

  即文件目录是由文件控制块组成的，专门用于文件的检索。

文件控制块中包含以下信息：

- 基本信息类：例如文件名、文件的物理地址、文件长度和文件块数等。

- 存取控制信息类：文件的存取权限。

- 使用信息类：文件建立日期、最后一次修改日期、最后一次访问的日期、当前使用的信息（如打开文件的进程数、在文件上的等待队列）等。

目录结构

组织好文件的目录是设计文件系统的重要环节，文件目录结构的组织方式直接影响到文件的存取速度，关系到文件的共享性和安全性。

常见的目录结构有：

- 一级目录结构

- 二级目录结构

- 多级目录结构：在多道程序设计系统中常采用多级目录结构。

  多级目录结构是树型目录结构。从根结点向下，每一个结点是一个目录，叶结点是文件。

  在采用多级目录结构的文件系统中，用户要访问一个文件，必须指出文件所在的路径名：

  路径名

  - 绝对路径名：指从根目录开始的完整路径。

  - 相对路径名：从当前所在目录开始（也可以不要当前目录）到其他目录或文件的路径。

全文件名：指绝对路径名加上该文件的文件名。

位示图

位示图用二进制的一位来表示一个物理块的使用情况：

位示图是一种空闲空间管理方法。通过在外存上建立一张位示图，记录文件存储器的使用情况。

0表示空闲；

1表示占用。

左边是逻辑编号（字号），右边是物理块编号（一位对应一个物理块）。

位示图的大小由磁盘空间的大小（物理块总数）决定。位示图的描述能力强，适合各种物理结构。

补充：

I/O设备管理软件层次（自上向下）：用户进程，与设备无关的系统软件、设备驱动程序、中断处理程序、硬件

嵌入式os的特点：微型化、可定制、易移植性、实时性、可靠性

中断和进程无关（和i/o有关）

FAT文件系统用基于文件的簇状链式结构文件管理结构。

磁盘清理和碎片处理不会清除有用数据，磁盘分区会。

相对路径名前没有‘/’，绝对路径前有‘/’。（后面‘/’可有可无）