1

操作系统概述

什么是操作系统

1. 操作系统本质上是一个运行在计算机上的软件程序 ，用于管理计算机硬
   件和软件资源
2. 操作系统的内核是操作系统的核心部分，它负责系统的内存管理，硬件设
   备的管理，文件系统的管理以及应用程序的管理

用户接口

1. 命令接口：用户可以直接使用的，利用这些操作命令来组织和控制作业的执行
2. 程序接口：用户通过程序间接使用的，可以使用它们来请求操作系统服务
3. 图形接口：用户利用鼠标或通过菜单和对话框，调用OS完成相应功能

操作系统的功能

1. 处理机管理：处理机分配都是以进程为单位，所以处理机管理也被看
   做是进程管理。包括进程控制，进程同步，进程通信和进程调度
2. 存储器管理：内存分配，内存保护，地址映射，内存扩充
3. 设备管理：管理所有外围设备，包括完成用户的IO请求，为用户进程
   分配IO设备，提高IO设备利用率，提高IO速度，方便IO的使用
4. 文件管理：管理用户文件和系统文件，方便使用同时保证安全性。包括
   ：磁盘存储空间管理，目录管理，文件读写管理以及文件共享和保护
5. 提供用户接口：程序接口（如API）和用户接口（如GUI）

操作系统的特征

1. 两个或多个事件在同一时间间隔内发生，这些事件在宏观上是同时发生的，在
   微观上是交替发生的，操作系统的并发性指系统中同时存在着多个运行的程序
2. 并行：两个或多个事件在同一时刻发生
3. 资源共享即共享，是指系统中的资源可以供内存中多个并发执行的进程共同使用

• 互斥共享 某个资源在一段时间内只能允许一个进程访问，资源称为临界资源，需
  要用同步机制来实现对临界资源的访问
• 同时共享 在一段时间内可以同时允许多个进程访问

4. 虚拟 虚拟是把一个物理上的实体变为若干逻辑上的对应物

• 时分复用技术：如处理器的分时共享，分时来使用一个CPU
• 空间复用技术：如虚拟存储器，从逻辑上扩充存储器容量

5. 异步 多道程序环境允许多个程序并发执行，但由于资源有限，如cpu只有一个，
   进程的执行并不是一贯到底的，而是走走停停的，它以不可预知的速度向前推进，
   每个进程占用资源的时间不固定，所以进程的执行以不可预知的速度前进

用户态和内核态

根据进程访问资源的特点，我们可以把进程在系统上的运行分为两个级别

1. 用户态: 用户态运行的进程可以直接读取用户程序的数据
2. 内核态:可以简单的理解系统态运行的进程或程序几乎可以访问计算机的
   任何资源，不受限制
3. 用程序状态寄存器PWS中的某标志位来表示处理器处于什么状态如：0是
   用户态，1是内核态。也就是特权指令比如IO指令、置中断指令和非特权指令
   比如加减乘除指令的切换

用户态切换到内核态的方式

3种方式本质都是通过中断机制实现的，中断是用户态进入内核态的唯一方法
，系统调用和异常也称为内中断，外围设备的中断称为外中断

1. 系统调用
   这是用户进程主动要求切换到内核态的一种方式，用户进程通过系统调用
   申请操作系统提供的服务程序完成工作。而系统调用的机制其核心还是使
   用了操作系统为用户特别开放的一个中断来实现，用户态执行trap陷入
   指令进入内核态，这个指令是唯一不能在内核态执行的指令
2. 异常
   当CPU在执行运行在用户态的程序时，发现了某些事件不可知的异常，这是
   会触发由当前运行进程切换到处理此异常的内核相关程序中，也就到了内
   核态，比如缺页异常
3. 外围设备的中断
   当外围设备完成用户请求的操作之后，会向CPU发出相应的中断信号，这时
   CPU 会暂停执行下一条将要执行的指令转而去执行中断信号的处理程序，
   如果先执行的指令是用户态下的程序，那么这个转换的过程自然也就发生
   了有用户态到内核态的切换。比如硬盘读写操作完成，系统会切换到硬盘
   读写的中断处理程序中执行后续操作等。如I/O完成中断，表示设备输入
   输出处理已经完成，处理器能够发送下一个输入输出请求

系统调用

我们运行的程序基本都是运行在用户态，如果调用操作系统提供的内核态级别
的功能那就需要系统调用，也就是说在我们运行的用户程序中，凡是与系统态
级别的资源有关的操作（如文件管理、进程控制、内存管理等），都必须通过
系统调用方式向操作系统提出服务请求，并由操作系统代为完成，系统调用
按功能可分为如下

1. 设备管理。完成设备的请求或释放，以及设备启动等功能
2. 文件管理。完成文件的读、写、创建及删除等功能
3. 进程控制。完成进程的创建、撤销、阻塞及唤醒等功能
4. 进程通信。完成进程之间的消息传递或信号传递等功能
5. 内存管理。完成内存的分配、回收以及获取作业占用内存区大小及地址等功能

Linux 的系统调用函数

1. 进程控制 fork(); exit(); wait();
2. 进程通信 pipe(); shmget(); mmap();
3. 文件操作 open(); read(); write();
4. 设备操作 ioctl(); read(); write();
5. 信息维护 getpid(); alarm(); sleep();
6. 安全 chmod(); umask(); chown();

用户空间与内核空间

操作系统的核心是内核，独立于普通的应用程序，可以访问受保护的内存空间
，也有访问底层硬件设备的所有权限。为了保证用户进程不能直接操作内核，
保证内核的安全，操心系统将虚拟空间划分为两部分，一部分为内核空间，
一部分为用户空间。针对linux操作系统而言，将最高的1G字节（从虚拟地
址0xC0000000到0xFFFFFFFF），供内核使用，称为内核空间，而将较低
的3G字节（从虚拟地址0x00000000到0xBFFFFFFF），供各个进程使用，
称为用户空间

宏内核和微内核

1. 宏内核是将操作系统功能作为一个紧密结合的整体放到内核，不管是用户
   服务还是内核服务事实上都是内核在统一管理，它们是运行在同一地址空间
   中的。由于各模块共享信息，因此有很高的性能，但是很难定位bug，拓展
   性比较差，每次需要增加新的功能，都要将新的代码和原来的内核代码重
   新编译
2. 在微内核中用户服务和内核服务在不同的地址空间中实现。在内核架构中，
   用户服务是独立于内核服务的，因此任何用户服务崩溃都不会影响到内核服务
   ，这就加强了操作系统的健壮性，这是微内核的优势所在。另一点，微内核的
   扩展性强，添加一个功能，只需要建立一个新的服务到用户空间当中，而内
   核空间不需要任何的修改。因此，微内核可移植性强、安全并且易于扩展。
3. 微内核就是内核的最基本功能时钟管理、中断机制和CPU切换等功能依然
   保留在内核，而对资源进行管理的功能比如进程管理、存储器管理和设备管
   理等功能转移到用户态，需要在用户态和内核态频繁切换

进程和线程

进程

进程是对正在运行程序的一个抽象，一个进程就是一个正在执行程序的实例。
由三部分组成：程序、数据及进程控制块(PCB)，进程控制块描述进程的基本
信息和运行状态，所谓的创建进程和撤销进程，都是指对PCB的操作，PCB中
保存程序运行的现场（进程标识、处理机状态、进程调度、进程控制等信息）

• 优点 内存隔离，单个进程的崩溃不会导致这个系统的崩溃。而且进程方便
  测试以及编程简单
• 缺点 创建销毁比较麻烦，进程间数据的共享麻烦，并且消耗的资源比较多

PCB

系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志。
进程与PCB是一一对应的，PCB中记录了操作系统所需的，用于描述进程的
当前情况以及控制进程运行的全部信息。
当OS要调度某进程执行时，要从该进程的PCB中查处其现行状态及优先级；在
调度到某进程后，要根据其PCB中所保存的处理机状态信息，设置该进程恢复
运行的现场，并根据其PCB中的程序和数据的内存始址，找到其程序和数据

1. 进程标识符 每个进程都必须有一个唯一的标识符，可以是字符串，也可
   以是一个数字
2. 进程当前状态 说明进程当前所处的状态。为了管理的方便，系统设计时
   会将相同的状态的 进程组成一个队列，如就绪进程队列，等待进程则要根
   据等待的事件组成多个等待队列，如等待打印机队列
3. 进程优先级 表示获得CPU控制权的优先级大小
4. 特征信息 一般分系统进程、用户进程、或者内核进程等
5. 程序开始地址 程序开始地址规定该进程的程序以此地址开始执行
6. CPU现场保护结构 寄存器值（通用、程序计数器PC、状态PSW，地址包括
   栈指针）
7. 描述虚拟地址空间的信息（如虚拟地址与物理地址之间的映射关系）

进程的状态

进程有三种基本状态：运行态，就绪态，阻塞态

1. 运行态 该时刻进程实际占用CPU
2. 就绪态 可运行，当因为其他进程正在运行而暂时停止，这是系统技术上的
   原因引起的，比如没有足够CPU
3. 阻塞态 除非某种外部事件发生，否则进程不能运行，这是程序自身固有
   原因（请求IO、键入用户命令之前无法执行命令）

还有两种状态

1. 创建状态：进程正在被创建，尚未到就绪状态
2. 结束状态：进程正在从系统中消失。可能是进程正常结束或其他原因中断退
   出运行

状态切换情况，不能由阻塞态直接切换到运行态或就绪态切换为阻塞态，因为
进入阻塞态是进程主动请求的，必须在运行态才能发出请求

1. 运行 -> 阻塞 等待I/O或事件完成
2. 运行 -> 就绪 进程的CPU时间片用完或被更高优先级的进程抢占
3. 就绪 -> 运行 获得了CPU的时间片
4. 阻塞 -> 就绪 I/O或事件完成

临界区和临界资源

1. 临界区
   通过对多线程串行化访问公共资源或一段代码，适合控制数据的访问。在任意
   时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资
   源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并
   一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占
2. 临界资源
   临界资源是一个时刻只能由一个进程使用的资源，比如硬件资源：许多都属于
   临界资源，如打印机，磁带机等和软件资源：如变量、表格、队列等

进程和线程的区别

1. 调度方面：进程是资源分配的基本单位，线程是CPU调度的基本单位
2. 并发性：引入了线程的OS中，进程间可以并发，而且一个进程内部的
   多个线程之间也是可以并发的，这就使OS具有更好的并发性，有效的提
   高了系统资源利用率和吞吐量
3. 拥有资源：无论OS是否支持线程，进程都是基本的资源拥有单位，线
   程只拥有很少的基本的资源，但是线程可以访问所隶属的进程的资源（
   进程的代码段，数据段和所拥有的系统资源如fd）
4. 内存空间：系统运行时，不同的进程的占有独立的地址空间，而一个
   进程内的多个线程可以共享进程的地址空间
5. 系统开销：创建或者撤销进程的时候，系统要为之创建或回收PCB，
   系统资源等，切换时也需要保存和恢复CPU环境。而线程的切换只需要保
   存和恢复少量的寄存器，不涉及存储器管理方面的工作
6. 通信：同一个进程中的多个线程共享地址空间，所以通信同步等都比
   进程要更为方便

用户级线程和内核级线程

1. 用户级线程 线程的处理不通过内核实现，线程的状态信息等全部存放在
   用户空间中，内核不能感知用户级线程

• 优点 线程的调度不需要内核直接参与，控制简单
• 缺点 一个用户级线程的阻塞将会引起整个进程的阻塞

2. 内核级线程 线程的处理均由内核实现，内核为线程保留TCB，并通过TCB
   感知线程

• 优点 当有多个处理机时，一个进程的多个线程可以同时执行
• 缺点 线程在用户态的运行，而线程的调度和管理在内核实现

进程同步、互斥和通信的区别

进程之间存在两种基本关系：竞争关系和协作关系。进程的互斥、同步、通信都
是基于这两种基本关系而存在的

1. 为了解决进程间竞争关系（间接制约关系）而引入进程互斥
2. 不同进程之间存在着不同的相互制约关系。为了协调进程之间的相互制约关、
   系，如等待、传递信息等，引入了进程同步的概念
3. 为了解决进程间紧密的协作关系而引入进程通信

进程同步的实现方式

进程同步：信号量、管程、消息传递

信号量

信号量是一种特殊的调度变量，由一个初始值为1的整数mutex，和一个任务
队列queue 组成，并且提供两个原子操作，wait 和signal，用于管理。
互斥问题信号量初值为1，临界区之前对信号量执行P操作，临界区之后对初
始量执行V操作。同步问题信号量初值为0，比如进程A生成数据，进程B消费
数据，那么进程A生成数据后进行V操作，进程B先进行P操作然后读取数据，
可以保证进程A 应在进程B 之前执行

1. wait 操作，也称为P 操作。首先将mutex 减1，如果mutex 小于0那么
   将进程放入指定阻塞队列，意味着请求一个资源，请求不到就block进程
2. signal 操作又名V 操作。A 任务结束，首先给mutex 加1，如果mutex
   小于等于0说明还有别的进程等待资源那么把阻塞队列的第一个进程唤醒，
   意味着释放一个资源，wakeup一个进程

管程

管程是由一个或多个过程、一个初始化序列和局部数据组成的软件模块。局部
数据变量只能被管程的过程访问，任何外部过程都不能访问。一个进程通过
调用管程的一个过程进入管程。在任何时候，只能有一个进程在管程中执行
，调用管程的任何其他进程都被阻塞，以等待管程可用。管程通过使用条件
变量提供对同步的支持，这些条件变量包含在管程中，并且只有在管程中
才能被访问。有两个函数可以操作条件变量

• cwait(c) 调用进程的执行在条件c上阻塞，管程现在可被另一个进程使用
• csignal(c) 恢复执行在cwait之后因为某些条件而阻塞的进程。如果有多
  个这样的进程，选择其中一个，如果没有这样的进程，什么也不做

消息传递

消息传递的实际功能以一对原语的形式提供：

• send(destination,message)
• receive(source,message)

这是进程间进程消息传递所需要的最小操作集，一个进程以消息的形式给另一
个指定的目标进程发送消息，进程通过执行receive原语接收消息，receive
原语中指明发送消息的源进程和消息

线程同步的方式

1. 信号量的用法和互斥量的用法很相似，不同的是它可以同一时刻允许多个线
   程访问同一个资源，PV操作
2. 事件(信号)，Wait/Notify：通过通知操作的方式来保持多线程同步，还可
   以方便的实现多线程优先级的比较操作
3. 互斥量 互斥对象只有一个，只有拥有互斥对象的线程才具有访问资源的权
   限。互斥与临界区很相似，但是使用时相对复杂一些（互斥量为内核对象），
   不仅可以在同一应用程序的线程间实现同步，还可以在不同的进程间实现同
   步，从而实现资源的安全共享
4. 临界区 通过对多线程的串行化来访问公共资源或一段代码，速度快，适合
   控制数据访问

生产者消费者问题

系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放
入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。消费者与消费者
，生产者与生产者，消费者与生产者之间，同一时间能且仅能有一者使用缓
冲区，否则阻塞。
于是需要三个信号量。生产者私有信号量empty 保证时刻有空位，消费者私有
信号量full 保证时刻有数据，公共信号量mutex 用于保证任意n个任务有且
仅有一个在访问缓冲区。

//生产者
wait(empty)
wait(mutex)
写缓冲
signal(mutex)
signal(full)
//消费者
wait(full)
wait(mutex)
读缓冲
signal(mutex)
signal(empty)

线程间的同步方式

1. 互斥量：采用互斥对象机制，只有拥有互斥对象的线程才有访问公共
   资源的权限。因为互斥对象只有一个，所以可以保证公共资源不会被多个
   线程同时访问。比如Java 中的synchronized 关键词和各种Lock 都是
   这种机制
2. 信号量：它允许同一时刻多个线程访问同一资源，但是需要控制同一
   时刻访问此资源的最大线程数量
3. 事件:Wait/Notify：通过通知操作的方式来保持多线程同步，还可以
   方便的实现多线程优先级的比较
4. 事件
   通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优
   先级比较的操作

进程间通信的方式

进程通信是指进程之间的信息交换。进程是分配系统资源的单位，因此各个进程
拥有的内存地址相互独立，为了保证安全，一个进程不能直接访问另一个进程
的地址空间，但内核空间是每个进程都共享的，所以进程之间要通信必须通过
内核。为了实现进程通信，操作系统提供了以下方法

信号量

用了共享内存通信方式，带来新的问题，那就是如果多个进程同时修改同一个共
享内存，很有可能就冲突了。信号量是一个计数器，用于多进程对共享数据的访
问，信号量的意图在于进程间同步。这种通信方式主要用于解决与同步相关的问
题并避免竞争条件。

管道通信

管道传输数据是单向的，如果想相互通信，我们需要创建两个管道才行。管道
这种通信方式效率低，不适合进程间频繁地交换数据，所谓的管道，就是内
核里面的一串缓存。从管道的一端写入的数据，实际上是缓存在内核中的，
另一端读取，也就是从内核中读取这段数据。另外，管道传输的数据是无格
式的流且大小受限。管道通信可以分为两种：匿名管道和有名管道

1. 匿名管道：用于具有亲缘关系的父子进程间或者兄弟进程之间的通信。
   通过调用pipe 函数创建，fd[0] 用于读，fd[1] 用于写。没有名字标识
   ，匿名管道是特殊文件只存在于内存，没有存在于文件系统中，shell命
   令中的「|」竖线就是匿名管道。可以使用 fork 创建子进程，创建的子进
   程会复制父进程的文件描述符，这样就做到了两个进程各有两个 fd[0]
   与fd[1]，两个进程就可以通过各自的fd 写入和读取同一个管道文件实
   现跨进程通信了。在shell 里面执行A | B 命令的时候，A 进程和B 进
   程都是shell 创建出来的子进程，A 和B 之间不存在父子关系，它俩的
   父进程都是shell
2. 有名管道：突破了匿名管道只能在亲缘关系进程间的通信限制，因为使
   用命名管道的前提，需要在文件系统创建一个类型为管道的设备文件，可
   以实现任意两个进程通信，有名管道的名字存在于文件系统，内容存放在
   内存中。在使用命名管道前，先需要通过mkfifo 命令来创建，并且指定
   管道名字。只有当管道里的数据被读完后，命令才可以正常退出，通过
   echo “hello”> myPipe 将数据写进管道，通过cat < myPipe 读取
   管道里的数据。不管是匿名管道还是命名管道，进程写入的数据都是缓
   存在内核中，另一个进程读取数据时候自然也是从内核中获取，同时
   通信数据都遵循先进先出原则，不支持lseek 之类的文件定位操作

消息队列

A 进程要给B 进程发送消息，A 进程把数据放在对应的消息队列后就可以
正常返回了，B进程需要的时候再去读取数据就可以了。消息队列是保存在
内核中的消息链表，在发送数据时，会分成一个一个独立的数据单元，也
就是消息体（数据块），消息体是用户自定义的数据类型，消息的发送方
和接收方要约定好消息体的数据类型，所以每个消息体都是固定大小的存
储块，不像管道是无格式的字节流数据。如果进程从消息队列中读取了消
息体，内核就会把这个消息体删除。消息队列生命周期随内核，如果没有
释放消息队列或者没有关闭操作系统，消息队列会一直存在，而前面提
到的匿名管道的生命周期，是随进程的创建而建立，随进程的结束而销
毁。通过msgsnd发送消息和msgrcv接收消息
消息队列不适合比较大数据的传输，因为在内核中每个消息体都有一个最
大长度的限制，同时所有队列所包含的全部消息体的总长度也是有上限。
在Linux 内核中，会有两个宏定义MSGMAX 和MSGMNB，它们以字节为单
位，分别定义了一条消息的最大长度和一个队列的最大长度。
消息队列通信过程中，存在用户态与内核态之间的数据拷贝开销，因为进
程写入数据到内核中的消息队列时，会发生从用户态拷贝数据到内核态的
过程，同理另一进程读取内核中的消息数据时，会发生从内核态拷贝数据
到用户态的过程

共享内存

现代操作系统对于内存管理采用的是虚拟内存技术，也就是每个进程都有
自己独立的虚拟内存空间，不同进程的虚拟内存映射到不同的物理内存中
。所以即使进程A 和 进程B 的虚拟地址是一样的，其实访问的是不同的
物理内存地址，对于数据的增删查改互不影响。
共享内存的机制，就是拿出一块虚拟地址空间来，映射到相同的物理内存
中。这样这个进程写入的东西，另外一个进程马上就能看到了，都不需要
拷贝来拷贝去，传来传去，大大提高了进程间通信的速度。
共享内存可以解决消息队列通信中用户态与内核态之间数据拷贝过程带来
的开销，它直接分配一个共享空间，每个进程都可以直接访问，就像访问
进程自己的空间一样快捷方便，不需要陷入内核态或者系统调用，大大提
高了通信的速度，享有最快的进程间通信方式之名。但是便捷高效的共享
内存通信，这种方式需要依靠某种同步操作，如互斥锁和信号量等

信号

信号是进程间通信机制中唯一的异步通信机制，信号可以在任何时候发给某
一进程，信号可以在应用进程和内核之间直接交互，内核也可以利用信号来
通知用户空间的进程发生了哪些系统事件，信号事件主要有两个来源：

• 硬件来源：用户按键输入Ctrl+C退出、硬件异常如无效的存储访问等
• 软件终止：终止进程信号、其他进程调用kill函数、软件异常产生信号

一旦有信号发生，进程有三种方式响应信号1. 执行默认操作、2. 捕捉信号
、3. 忽略信号。有两个信号是应用进程无法捕捉和忽略的，即 SIGKILL 和
SEGSTOP，这是为了方便我们能在任何时候结束或停止某个进程

Socket

用于在客户端和服务器之间通过网络进行通信。套接字是支持TCP/IP 的网
络通信的基本操作单元，可以看做是不同主机之间的进程进行双向通信的
端点，用套接字中的相关函数来完成通信过程。可根据创建Socket 的类
型不同，分为三种常见的通信方式，一个是基于 TCP 协议的通信方式，
一个是基于UDP 协议的通信方式，一个是本地进程间通信方式

线程通信方式

1. 使用全局变量
   主要由于多个线程可能更改全局变量，因此全局变量最好声明为volatile
2. 使用消息实现通信
   在Windows程序设计中，每一个线程都可以拥有自己的消息队列（UI线程默认
   自带消息队列和消息循环，工作线程需要手动实现消息循环），因此可以采用
   消息进行线程间通信sendMessage,postMessage

进程通信哪种方式开销最小

1. 进程间的通信手段大体可以分为两类：通信类和同步类
2. 本质来讲管道也是一片内存区域，默认大小是65536字节
3. 相比于管道来讲，消息队列机制中，双方是通过消息来通信的，无需花
   费精力从字节流中解析出完整的消息
4. 消息队列的作用是进程之间传递消息。而信号量的作用是为了同步多个
   进程的操作
5. 共享内存是所有IPC手段中最快的一种。它之所以快是因为共享内存一旦
   映射到进程的地址空间，进程之间数据的传递就不须要涉及内核了
6. 共享内存是开销最小的通信方式，源于它和内核的交流比较少，从而降
   低了开销

进程的调度算法

批处理系统没有太多的用户操作，在该系统中，调度算法目标是保证吞吐量
和周转时间（从提交到终止的时间）

1. 先到先服务(FCFS)调度算法 :
   从就绪队列中选择一个最先进入该队列的进程为之分配资源，使它立即执行并
   一直执行到完成或发生某事件而被阻塞放弃占用CPU 时再重新调度。有利于长
   作业，但不利于短作业，因为短作业必须一直等待前面的长作业执行完毕才能
   执行，而长作业又需要执行很长时间，造成了短作业等待时间过长
2. 短作业优先(SJF)的调度算法 :
   从就绪队列中选出一个估计运行时间最短的进程为之分配资源，使它立即执行
   并一直执行到完成或发生某事件而被阻塞放弃占用 CPU 时再重新调度。可能
   导致长作业或进程长时间不被调度
3. 最短剩余时间优先(SRTN)：
   最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作
   业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要
   的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待

交互式系统有大量的用户交互操作，在该系统中调度算法的目标是快速地进行
响应

1. 时间片轮转算法
   将所有就绪进程按先来先服务排成队列，每次调度时，把 CPU 时间分配给队
   首进程，该进程可以执行一个时间片。当时间片用完时，由计时器发出时钟中
   断，调度程序便停止该进程的执行，并将它送往就绪队列的末尾，同时继续
   把CPU 时间分配给队首的进程
2. 优先级调度算法
   为每个进程分配一个优先级，按优先级进行调度。为了防止低优先级的进程永
   远等不到调度，可以随着时间的推移增加等待进程的优先级
3. 多级反馈队列算法
   一个进程需要执行100 个时间片，如果采用时间片轮转调度算法，那么需要交
   换100 次。多级队列是为这种需要连续执行多个时间片的进程考虑，它设置了
   多个队列，每个队列时间片大小都不同，例如 1,2,4,8,..。进程在第一个队
   列没执行完，就会被移到下一个队列。每个队列优先权也不同，最上面的优先
   权最高。因此只有上一个队列没有进程在排队，才能调度当前队列上的进程。
   可以将这种调度算法看成是时间片轮转调度算法和优先级调度算法的结合。
   UNIX 操作系统采取的便是这种调度算法

进程切换

为了控制进程的执行，内核必须有能力挂起正在CPU上运行的进程，并恢复以前
挂起的某个进程的执行。这种行为被称为进程切换。因此可以说，任何进程都是
在操作系统内核的支持下运行的，是与内核紧密相关的。
从一个进程的运行转到另一个进程上运行，这个过程中经过下面这些变化：

1. 保存处理机上下文，包括程序计数器和其他寄存器
2. 更新PCB信息
3. 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列
4. 选择另一个进程执行，并更新其PCB
5. 更新内存管理的数据结构
6. 恢复处理机上下文

线程上下文切换

1. 当进程拥有多个线程时，线程会共享虚拟内存和全局变量等资源，这些资
   源在上下文切换中不需要修改
2. 线程的上下文切换也需要保存自己的一些数据，比如栈，寄存器。这些在上
   下文切换时是需要保存的
3. 线程的调度是在内核态运行的，而线程中的代码是在用户态运行

进程阻塞

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某
种操作的完成、新数据尚未到达或无新工作做等，则由系统自动执行阻塞原语
(Block)，使自己由运行状态变为阻塞状态。可见，进程的阻塞是进程自身的
一种主动行为，也因此只有处于运行态的进程(获得CPU)，才可能将其转为
阻塞状态。当进程进入阻塞状态，是不占用CPU资源的

文件描述符

文件描述符是内核为了高效管理已被打开的文件所创建的索引，用于指代被打
开的文件，对文件所有I/O 操作相关的系统调用都需要通过文件描述符

1. 进程级别的文件描述符表：内核为每个进程维护一个文件描述符表，该表
   记录了文件描述符的相关信息，包括文件描述符、指向打开文件表中记录的
   指针
2. 系统级别的打开文件表：内核对所有打开文件维护了一个进程共享的打开
   文件描述表，表中存储了处于打开状态文件的相关信息，包括文件类型、访
   问权限、文件操作函数等
3. 系统级别的i-node 表：i-node 结构体记录了文件相关的信息，包括文
   件长度，文件所在设备，文件物理位置，创建、修改和更新时间等，”ls -i”
   命令可以查看文件i-node 节点

死锁

什么是死锁

多个进程可以竞争有限数量的资源。当一个进程申请资源时，如果这时没
有可用资源，那么这个进程进入等待状态。有时，如果所申请的资源被其
他等待进程占有，那么该等待进程有可能再也无法改变状态。这种情况成
为死锁

什么是饥饿

长期获取不到想要的资源，某进程无法向前推进

产生死锁的四个必要条件

必须同时满足这四个条件要不然死锁就不会发生

1. 互斥：资源必须处于非共享模式，即一次只有一个进程可以使用。如果
   另一进程申请该资源，那么必须等待直到该资源被释放为止
2. 占有和等待：一个进程至少应该占有一个资源，并等待另一资源，而该
   资源被其他进程所占有
3. 不可抢占：资源不能被抢占。只能在持有资源的进程完成任务后，该资
   源才会被释放
4. 循环等待：有两个或者两个以上的进程组成一条环路，该环路中的每个
   进程都在等待下一个进程所占有的资源

什么时候会发生死锁

1. 对系统资源的竞争。各进程对不可抢占资源的竞争可能引起死锁
2. 进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁
3. 信号量的使用不当也会造成死锁。在生产者消费者问题中如果实现互
   斥的P操作在实现同步的P操作之前就可能导致死锁

如何解决死锁

对于死锁，主要有4种解决策略

1. 鸵鸟策略
2. 死锁预防
3. 死锁避免
4. 死锁检测和恢复

什么是鸵鸟策略？

不采取任务措施，当发生死锁时不会对用户造成多大影响，或发生死锁的概
率很低

如何预防死锁

死锁预防是指通过破坏死锁产生的四个必要条件中的一个或多个，以避免发生死锁

1. 破坏互斥条件 把互斥的资源改为共享使用
2. 破坏占有和等待条件 已拥有资源的进程不能再去请求其他资源，要求进程在
   开始执行前请求需要的所有资源或先暂时释放其当前拥有的所有资源，再尝试
3. 破坏不可抢占条件 当某个进程请求的资源得不到满足时，必须立即释放所
   保持的所有资源，待以后需要时再申请
4. 破坏环路等待 每个进程在任何时刻只能占用一个资源，如果要请求另一个
   资源，必须先释放第一个资源或要求进程必须按照顺序请求资源
5. 锁排序法 指定获取锁的顺序，比如某个线程只有获得A锁和B锁，才能对某资
   源进行操作，通过指定锁的获取顺序，比如规定，只有获得A锁的线程才有资格
   获取B锁，按顺序获取锁就可以避免死锁。这通常被认为是解决死锁很好的一种
   方法
6. 使用显式锁中的ReentrantLock.try(long,TimeUnit)来申请锁

如何避免死锁

为了避免因为预防死锁而导致所有线程变慢，死锁避免采用了与死锁预防相反
的措施，通过算法判断资源请求是否可能导致循环等待的形成并相应决策，来
避免死锁点的产生，其前提是知道当前资源使用的整体情况，以及申请资源线
程本身所占有的资源细节

1. 线程启动拒绝：如果一个线程的请求会引发死锁，则不允许其启动
2. 资源分配拒绝：如果一个线程增加的资源请求会导致死锁，则不允许此申请

如何死锁检测与恢复

1. 死锁检测 维护一个系统的资源分配图，找到不会阻塞又不独立的进程结点
   ，使该进程获得其所需资源并运行，运行完毕后，再释放其所占有的全部资源
2. 死锁恢复

• 取消所有死锁相关线程
• 把每个死锁线程回滚到某些检查点，然后重启
• 连续取消死锁线程直到死锁解除，顺序基于特定最小代价原则
• 连续抢占资源直到死锁解除