操作系统

什么是操作系统？

操作系统是管理硬件和软件的一种应用程序，它为计算机硬件和软件提供了一种中间层，使应用软件和硬件进行分离，让我们无需关注硬件的实现，把关注点更多放在软件应用上。

操作系统是干什么的？

管理计算机资源，这些资源包括 CPU、内存、磁盘驱动器、打印机等。
提供一种图形界面，就像我们前面描述的那样，它提供了用户和计算机之间的桥梁。
为其他软件提供服务，操作系统与软件进行交互，以便为其分配运行所需的任何必要资源。

用户态和核心态

用户态和内核态是操作系统的两种运行状态。

内核态

处于内核态的 CPU 可以访问任意的数据，包括外围设备，比如网卡、硬盘等，处于内核态的 CPU 可以从一个程序切换到另外一个程序，并且占用 CPU 不会发生抢占情况，一般处于特权级 0 的状态我们称之为内核态。

用户态

处于用户态的 CPU 只能受限的访问内存，并且不允许访问外围设备，用户态下的 CPU 不允许独占，也就是说 CPU 能够被其他程序获取。

为什么要有用户态和内核态？

这个主要是访问能力的限制的考量，计算机中有一些比较危险的操作，比如设置时钟、内存清理，这些都需要在内核态下完成，如果随意进行这些操作，那你的系统得崩溃多少次。

用户态和内核态是如何切换的？

只能系统调用才能操作用户态与内核态的切换，而只有操作系统才能操作系统调用。

用户态 -> 内核态 的工作流程：

1. 首先用户程序会调用 glibc 库，glibc 是一个标准库，同时也是一套核心库，库中定义了很多关键 API。
2. glibc 库知道针对不同体系结构调用系统调用的正确方法，它会根据体系结构应用程序的二进制接口设置用户进程传递的参数，来准备系统调用。
3. 然后，glibc 库调用软件中断指令(SWI) ，这个指令通过更新 CPSR 寄存器将模式改为超级用户模式，然后跳转到地址 0x08 处。
4. 到目前为止，整个过程仍处于用户态下，在执行 SWI 指令后，允许进程执行内核代码，MMU 现在允许内核虚拟内存访问
5. 从地址 0x08 开始，进程执行加载并跳转到中断处理程序，这个程序就是 ARM 中的 vector_swi()。
6. 在 vector_swi() 处，从 SWI 指令中提取系统调用号 SCNO，然后使用 SCNO 作为系统调用表 sys_call_table 的索引，调转到系统调用函数。
7. 执行系统调用完成后，将还原用户模式寄存器，然后再以用户模式执行。

内核

内核是一个计算机程序，它是操作系统的核心，可以控制操作系统中所有的内容。内核通常是在 boot loader装载程序之前加载的第一个程序。

boot loader又被称为引导加载程序，能够将计算机的操作系统放入内存中。在电源通电或者计算机重启时，BIOS会执行一些初始测试，然后将控制权转移到引导加载程序所在的主引导记录(MBR) 。

操作系统启动过程

进程

进程和线程

进程

进程

进程就是正在执行程序的实例，比如说 Web 程序就是一个进程，shell 也是一个进程，文章编辑器 typora 也是一个进程。

进程表

操作系统为了跟踪每个进程的活动状态，维护了一个进程表。在进程表的内部，列出了每个进程的状态以及每个进程使用的资源等。

进程控制块（PCB）

PCB是进程的唯一标识，系统通过PCB来控制和管理进程的状态。

PCB主要包含的信息：进程描述信息、进程控制和管理信息、资源分配清单、处理机相关信息。

PCB里含有进程的标识信息、状态信息、资源的占有情况等。

线程

线程的实现方式

1. 用户级线程：线程的控制和管理发生在应用程序，内核不感知。而且一般从单线程开始，运行过程中派生出其他线程。
2. 内核级线程：线程的控制和管理发生在内核，应用程序不感知。
3. 组合方式：线程的创建、调度、同步都发生在用户空间，一个内核线程映射多个用户线程。

线程模型

1. 多对一：所有用户线程都对应一个内核线程。线程管理在用户空间。优点是效率高，缺点是内核线程阻塞，所有用户线程都受到影响。
2. 一对一：一个用户线程对应一个内核线程。线程管理在内核空间。有点是并发能力强，缺点是开销大，程序性能低。
3. 多对多：少量内核线程映射多量的用户线程。取二者所长，弥补二者所短。

进程和线程的区别

进程和线程的区别

资源和调度：进程是资源分配的最小单位；线程是cpu调度的最小单位。

并发：进程是用来实现各应用程序并发的，线程是为了提高并发性能的。（因为进程切换需要虚拟内存空间的切换，而线程可以共享进程资源，因此上下文切换的开销小。）

系统开销：进程的上下文切换开销大，而线程的上下文切换开销小。

地址空间：进程间相互独立，进程内的线程共享资源，并且对其他进程的线程不可见。

通信：进程间通信通过同步和互斥保证数据的一致性，线程可以直接读写数据。

并发和并行的区别

并发：一个cpu处理多个线程；
并行：多个cpu，每个cpu处理一个线程。

进程间的通信方式

IPC(Inter Process Communication)：进程间通信。

• 共享内存

  多个进程可以直接在内核专门预留一块内存空间读写，是最快的IPC形式。

  需要同步机制（信号量）达到进程间的同步及互斥。

  • 信号量
    • 信号量是一个计数器，用于多进程对共享数据的访问，信号量的意图在于进程间同步。
    • 进程获得共享资源需要进行的操作：1、创建一个信号量，初始值为0或1；2、等待一个信号量：该操作测试信号量的值，如果小于0，就阻塞，也称为P操作；3、挂出一个信号量：该操作将信号量的值加1，也称为V操作。
    • 信号量的操作都是原子的（PV原语，或wait、signal），是在内核中实现的。
    • 信号量和互斥量之间的区别：互斥量用于线程的互斥，信号量用于线程的同步。

• 管道

  半双工通信方式，双方通信需要建立两个管道；

  是一个独立的文件系统，只存在在内存中；

  本质是一个内核缓冲区，可以认为是一个循环队列。进程以先进先出的方式从缓冲区存取数据，一端进程顺序写到队尾，一端进程从队头开始读数据，且每个数据只能被读一次；

  只能用于亲缘进程之间的通信。（非亲缘进程可以通过有名管道通信）

• 消息队列

  消息队列是以消息（每个消息都被认为是一个管道，接收进程可以独立地接收含有不同管道的数据结构）为单位的链表，存放在内存中并由消息队列标识符标识，能提供不同进程间的全双工通信。

  • 消息队列 & 管道 对比：
    • 管道是跟随进程的，进程结束之后，管道随之销毁；消息队列是跟随内核的，进程结束之后，消息队列还会存在，只有在操作系统关机之后才会销毁；
    • 管道是文件，存储在磁盘上，消息队列是数据结构，存储在内存上，因此消息队列的性能比管道更高；
    • 管道是流式存储，消息队列是数据块式存储。

• 信号

  信号可以在任何时候发给某一进程，而无需知道该进程的状态。

  SIGINT：程序终止信号。程序运行过程中，按Ctrl+C键将产生该信号。

• socket

  这种通信方式可以实现跨机器的进程通信。

  socket是对TCP/IP协议簇的接口抽象。

  • socket通信的建立过程：
    • 服务端：
      1. 服务器系统调用socket创建一个套接字；
      2. 服务器进程调用bind方法给套接字命名，并等待客户端连接到这个套接字；
      3. 系统调用listen来创建一个队列并将其用于存放来自客户的进入连接；
      4. 服务器通过系统调用accept来接受客户的连接，并创建新的套接字用于特定客户端的连接。
    • 客户端：
      1. 客户端系统调用socket创建一个未命名套接字;
      2. 然后将服务器创建的命名套接字作为地址，调用connect与服务器进行连接；
      3. 建立连接后，就可以用套接字进行数据双向通信。

进程同步

同步 & 互斥

临界资源

一次仅允许一个进程使用的资源称为临界资源。

临界区

访问临界资源的代码块称为临界区。

互斥

互斥是指某一资源同时只允许一个访问者对其进行访问，具有唯一性和排它性。但互斥无法限制访问者对资源的访问顺序，即访问是无序的。

同步

同步是指在互斥的基础上（大多数情况），通过其它机制实现访问者对资源的有序访问。

同步机制的四个原则

同步机制的四个原则：空闲让进、忙则等待、有限等待、让权等待。

实现临界区互斥的方法

软件方法：peterson算法

硬件方法：中断屏蔽、硬件指令

经典同步问题

生产者-消费者问题

semaphore mutex = 1; // 临界区互斥信号量
semaphore empty = n; // 空闲缓冲区
semaphore full = 0; // 缓冲区初始化为空
Producer() {
    while (true) {
        data = produce(); // 生产数据
        P(empty); // 要用一个empty，p一下
        P(mutex); // 进入临界区，互斥夹紧
        buffer.add(data); // 将数据放到缓冲区
        V(mutex); // 离开临界区，释放信号量，互斥夹紧
        V(full); // 提供了一个full，v一下
    }
}
Consumer() {
    while (true) {
        P(full); // 用full，p一下
        P(mutex); // 进入临界区
        data = buffer.remove(); // 消费一个data
        V(mutex); // 离开临界区，释放信号量
        V(empty); // 提供了一个empty，v一下
        consume(data); // 消费数据
    }
}

管程

管程是共享资源抽象出的一组数据结构及在该数据结构是那个实施操作的一组过程所组成的资源管理程序。

管程包含的要素：

1. 管程的名称
2. 内部的数据结构
3. 对数据结构进行操作的一组过程（函数）
4. 对内部共享数据的初始化操作

monitor Demo {
    struct S {
        ... // 共享数据结构
    }
    conditon x; // 定义一个条件变量x
    init_code() {
        ... // 对共享数据进行初始化
    }
    take_away() {
        if (S <= 0) x.wait(); // 资源不够，在条件变量x上进行阻塞
        ... // 资源充足，分配资源，做一系列相应处理
    }
    give_back() {
        ... // 归还资源，做一系列相应处理
        if (有进程在等待) x.signal; //唤醒一个阻塞进程
    }
}

死锁

死锁产生的原因

资源竞争和程序执行顺序不当

死锁产生的必要条件

1. 互斥条件：每个资源都被分配给了一个进程或者资源是可用的
2. 保持和等待条件：已经获取资源的进程被认为能够获取新的资源
3. 不可抢占条件：分配给一个进程的资源不能强制的从其他进程抢占资源，它只能由占有它的进程显示释放
4. 循环等待条件：死锁发生时，系统中一定有两个或者两个以上的进程组成一个循环，循环中的每个进程都在等待下一个进程释放的资源。

死锁的处理策略

1. 死锁预防
   1. 破坏互斥条件：一般不会破坏互斥的条件，但可以尽量做到尽可能少的进程可以请求资源。
   2. 破坏保持和等待条件：让进程在运行前一次申请完它需要的全部资源，会造成“饥饿”。
   3. 破坏不可抢占条件：cpu的中断等，
   4. 破坏循环等待条件：顺序资源分配法，给资源分配编号，每次申请比之前编号大的资源。
2. 死锁避免
   1. 银行家算法
3. 死锁检测和解除
   1. 检测方法：根据死锁定理，如果资源分配图可以被完全简化，说明不存在死锁，反之，则会死锁。
   2. 死锁解除的方法：资源剥夺；撤销进程；进程回退。

银行家算法

// 进程集合
static HashSet<Integer> processSet;
// 当前可用资源，m代表资源总类，available[j] 代表第j类资源可用的数量
static int[] available;
// 已分配资源, allocation[i][j] 代表进程i已经分配到的j资源的数量
static int[][] allocation;
// 资源最大请求数，need[i][j]代表进程i对j资源的最大请求数
static int[][] need;
// 资源总类
static int m;

/**
 * 银行家算法
 * @param i 进程
 * @param j 资源类别
 * @param k 进程申请资源数
 */
public static void Banker(int i, int j, int k) {
    try {
        if (k >= need[i][j]) {
            // 抛出异常
            throw new Exception();
        } else if (k > available[j]) {
            // 阻塞进程i
            wait(i);
        } else {
            available[j] -= k;
            allocation[i][j] += k;
            need[i][j] -= k;
            if (!isSafe()) {
                available[j] += k;
                allocation[i][j] -= k;
                need[i][j] -= k;
            } else {
                // 为进程i分配资源
            }
        }
    } catch (Exception e) {
        // 处理异常
        log.error(e);
    }
}

/**
 * @return true: 存在安全序列 false: 不存在安全序列
 */
private static boolean isSafe() {
    boolean found = false;
    while (processSet.size() > 0) {
        for (Integer i: processSet) {
            for (int j = 0; j < m; j++) {
                if (available[j] >= need[i][j] - allocation[i][j]) {
                    available[j] += allocation[i][j];
                    processSet.remove(i);
                    found = true;
                }
            }
        }
        if (! found) 
            return false;
    }
    return true;
}

进程的状态模型

进程的五种状态

进程的五种状态：运行态、就绪态、阻塞态、创建态、结束态。

1. 运行态：进程在处理机上运行；
2. 就绪态：进程除了处理机外获取了其他一切资源，等待处理机被调度执行；
3. 阻塞态：进程正在等待某一事件而释放处理机资源；
4. 创建态：进程正在被创建；
5. 结束态：进程正从系统中消失。

进程的创建

操作系统创建一个进程的过程

1. 为新进程分配一个唯一标识号，并申请一个空白的PCB；
2. 为进程分配内存空间等资源（体现在PCB），资源不足，则进入阻塞状态；
3. 初始化PCB，主要包括初始化标志信息、处理机状态信息、处理机控制信息、进程优先级等；
4. 将进程加入到就绪队列里，等待执行。

进程的终止

进程终止的原因

1. 正常结束
2. 异常结束：存储区越界、非法指令、运行超时、IO故障等；
3. 外界干扰，如操作系统干预、父进程终止等。

进程终止的过程

1. 根据标示号，检索PCB，读出进程状态；
2. 如果进程处于运行态，终止运行，释放处理机资源；
3. 若进程有子进程，终止子进程；
4. 将进程拥有的全部资源归还给父进程或操作系统；
5. 将该PCB从所在队列中清除。

进程的阻塞和唤醒

阻塞的执行过程

1. 找到进程标识对应的PCB；
2. 如果进程状态为运行态，保护现场，转换状态为阻塞态，停止运行；
3. 将PCB插入事件的等待队列，释放处理机资源。

唤醒的执行过程

1. 在事件的等待队列中找到相应进程的PCB；
2. 将其从等待队列中移除，并置进程状态为就绪态；
3. 把PCB插入就绪队列，等待调度程序调度。

进程的切换

进程切换的执行过程

1. 保存处理机上下文，包括程序计数器及一些寄存器；
2. 更新PCB信息；
3. 把PCB移到相应的队列（就绪队列、阻塞队列）
4. 选择另一个进程执行，并更新其PCB；
5. 更新内存管理的数据结构
6. 恢复处理机的上下文。

调度算法

影响调度程序性能的指标

• cpu使用率
• 等待时间
• 吞吐量：单位时间内完成进程的数量
• 响应时间：从提交作业到开始执行作业的时间
• 周转时间：从提交作业到完成作业的时间

先来先服务

算法简单，效率低，非抢占，长作业有利，有利于cpu繁忙型作业，不利于IO繁忙型作业。

短作业优先

对长作业不利（饥饿），不能保证紧迫性作业及时处理。

优先级调度

优先级用于描述作业的紧迫程度。

分为抢占式和非抢占式。

IO型 > CPU型；系统进程 > 用户进程

高响应比调度

是先来先服务和短作业优先的平衡算法。

响应比 = （等待时间 + 要求服务时间）/ 要求服务时间

时间片轮转调度

多级反馈队列调度

是对优先级和时间轮转的发展。

1. 设置多个就绪队列，赋予不同的优先级；
2. 为就绪队列赋予时间片，优先级越高的就绪队列时间片越短；
3. 新进程进入内存后，放到最高优先级的队列，按先来先服务等待调度，执行时间为分配的时间片时间；如果没有执行完就放到第二优先级的队列的队尾；
4. 仅当第一优先级为空的时候，再来调度第二优先级队列里的进程。

内存管理

内存管理的概念

程序装入内存要经过哪几步？

1. 编译：由编译器将用户源代码编译成若干目标块；
2. 链接：由链接程序将编译后的形成的一组目标块及所需的库函数链接在一起，形成一个完整的装入模块；
3. 装入：由装入程序将装入模块装入内存运行。

程序的链接有哪几种方式？

1. 静态链接：程序在运行之前，先将各目标模块及它们所需的库函数链接成一个完整的可执行程序，以后不再拆开。
2. 装入时动态链接：装入内存时，边装入边链接。
3. 运行时动态链接：程序执行中需要该模块时才进行链接。

程序的装入有哪几种方式？

1. 绝对装入：逻辑地址和实际内存地址相同，直接把程序装入内存某个位置，只适用于单道程序环境。
2. 静态重定位装入：将作业一次性装入内存，装入时对程序的指令和数据的修改，相对于起始位置进行重定位。
3. 动态重定位装入：程序执行时，再把相对地址转为绝对地址。

覆盖 & 交换

覆盖和交换是多道程序下扩充内存的两种方法。

覆盖用在同一程序和进程中，交换技术用在不同进程之间。

覆盖

把用户空间分成一个固定区和若干个覆盖区，将经常活跃的部分放到固定区，将即将要访问的段放到覆盖区，其他段放在外存，在需要调用前，系统将其从外存调到覆盖区，替换覆盖区原有的段。

交换

把等待状态的程序从内存移到辅存，即唤出；把准备好竞争cpu资源的程序从辅存移到内存，即唤入。

区别于换页，交换是针对等待资源的程序而言的。

虚拟内存管理

按需分页

在操作系统中，进程是以页为单位加载到内存中的，按需分页是一种虚拟内存的管理方式。

当操作系统需要访问的页未在内存中，会出现缺页异常。操作系统才会将磁盘页面复制到内存中。

内存分配策略

连续的分配管理方式

1. 单一连续分配
2. 固定分区分配
3. 动态分区分配

非连续的分配管理方式

1. 基于分页存储管理方式
2. 基于分段存储管理方式
3. 段页式管理方式

空闲内存管理方式

操作系统在动态分配内存时，需要对空闲内存进行管理。一般采用了两种方式：位图和空闲链表。

位图

用1位（0/1）来表示一块内存区域的使用情况，以此来跟踪内存的使用情况。

位图的缺点是，很难通过位图来找到一块连续的确定大小的内存空间。

空闲链表

虚拟内存

虚拟内存是一种基于非连续分配管理方式的内存分配的机制。

虚拟内存的实现方式

虚拟内存在软件层面使用的是非连续的分配管理方式。

需要的硬件方面的支持：

1. 一定容量的内存和外存；
2. 页表机制（或段表机制），作为主要的数据结构；
3. 中断机构，当用户程序要访问的部分尚未调入内存，则产生中断；
4. 地址变换机构，逻辑地址到物理地址的变换。

页面置换算法

1. 最佳置换（OPT）算法

   当调入新的一页而必须预先置换某个老页时，所选择的老页应是将来不再被使用，或者是在最远的将来才被访问。

2. 先进先出（FIFO）算法：

   优先淘汰最早进入内存的页。

   但是会出现Belady异常（分配的物理块增大但页故障数不减反增）。

   效率不高，在按线性顺序访问地址空间时才是理想的。

3. 最近最久未使用（LRU）算法

   该算法认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。

   LRU算法需要为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰时选择页面字段最大的值进行淘汰。

   LRU性能较好，但是需要寄存器和栈的硬件支持。

   LRU是堆栈类的算法，而FIFO是基于队列实现的。

4. 时钟（CLOCK）置换算法

页面分配策略

1. 固定分配局部置换：为每个进程分配一定数目的物理块，整个运行期不改变。缺页时候，从内存中唤出一页，唤进一页。
2. 可变分配全局置换：为每个进程分配一定数目的物理块，操作系统维护一个空闲物理块的队列，缺页时，从队列中出队空闲的物理块，并进行换页。
3. 可变分配局部置换：为每个进程分配一定数目的物理块，缺页时，从该进程的内存中换页，不会影响其他进程的运行。

抖动

刚刚唤出的页马上又要唤入内存，刚刚唤入的页马上又要唤出，这种频繁的页面调度就称为抖动。

其原因在于频繁访问的页面数目多于可用的物理页数目。

文件系统

文件在磁盘，访问磁盘的速度远小于内存。

文件系统性能

提高文件系统性能的方法：

1. 高速缓存

   最常见的减少访问磁盘次数的技术：缓冲区高速缓存(buffer cache)。

   高速缓存指的是一系列的块，它们在逻辑上属于磁盘，但实际上基于性能的考虑被保存在内存中。

2. 块提前读：直接将接下来可能用到的块先写到高速缓存中。

3. 减少磁盘臂运动：把有可能顺序访问的块放在一起，当然最好是在同一个柱面上，从而减少磁盘臂的移动次数。

4. 磁盘碎片整理

磁盘臂调度算法

影响磁盘快速读写的因素

1. 寻道时间：活动头磁盘在读写信息前，将磁头移动到指定磁道所需要的时间。
2. 延迟时间：磁头定位到某一磁道的扇区（块号）所需要的时间。
3. 传输时间：从磁盘读写数据所需要的时间。

调度算法

1. 先来先服务（FCFS）算法
2. 最短寻找时间优先算法
3. 扫描（电梯调度）算法
4. 循环扫描算法

IO

IO控制方式

1. 程序直接控制方式：cpu要不断检测外设状态，直到确定已经把数据读到寄存器中。cpu使用率低。
2. 中断驱动方式：解决cpu等待io的问题，但数据从存储器到IO都要走cpu。
3. DMA方式：数据开始和结束传输的时候走cpu，其他时间都是dma芯片来管理控制数据的传输的。
4. 通道控制方式：在dma技术之上发展的，把对一个数据块的读写单位扩展为对一个组数据块的读写，同时实现cpu、通道、io的并行操作，进一步提高系统的资源利用率。

DMA(直接内存访问)

CPU授权IO模块权限跳过CPU直接读写内存，整个过程由DMA的芯片管理，这样可以缓解总线上的拥塞。

DMA的特点：

1. 数据传送以数据块为基本单位
2. 数据从设备直接送入主存，或者从主存直接输出到设备上
3. 仅在传输数据的开始和结束的时候需要cpu的介入，而整个传输的过程只需要dma的芯片参与。

中断处理的过程

1. 关中断。CPU关闭中断，即不再接受其他外部中断请求。
2. 保存断点。将发生中断处的指令地址压入堆栈，以使中断处理完后能正确的返回（注意，有可能保存中断处的指令地址，也有可能是中断处的指令的下一条指令的地址，具体情况视中断的类型）。
3. 识别中断源。CPU识别中断的来源，确定中断类型号，从而找到相应的中断处理程序的入口地址
4. 保存现场（以上三步一般由处理中断的硬件电路完成）。将发生中断处的有关寄存器（中断服务程序要使用的寄存器）以及标志寄存器的内容压入堆栈。
5. 执行中断服务程序。转到中断服务程序入口开始执行，可在适时时刻重新开放中断，以便允许响应较高优先级的外部中断。
6. 恢复现场并返回（后三步一般软件，即中断处理程序完成）。把“保护现场”时压入堆栈的信息弹回寄存器，然后执行中断返回指令，从而返回主程序继续运行。（IRET指令，无操作数，从栈顶弹出3个字，分别送入IP、CS和FLAGS寄存器）

设备驱动程序

计算机程序，用来控制和操作连接到计算机的设备。

驱动程序提供了与硬件交互的软件接口，使操作系统或计算机程序可以直接访问硬件，而不需要了解硬件的具体构造。