《现代操作系统》第十章——实例研究（读后笔记）

10.1 UNIX 与 Linux 的历史

就当看看历史，不记笔记了这节。

10.2 Linux 简介

10.2.2 Linux 接口

POSIX：可移植操作系统接口

POSIX 规定库函数的接口，而不是系统调用接口。

Linux 具有三种不同接口：系统调用接口、库函数接口、标准应用程序构成的接口

10.2.3 shell

一个程序的标准输入，标准输出，标准错误，正常情况默认指向终端。

< 文件名：重定向标准输入

> 文件名：重定向标准输出

| 管道符将左边输出当作右边输入

命令后加上 & 后台运行程序

shell 脚本：存放一系列 shell 命令，而且有一些语法规则

10.2.4 Linux 应用程序

Linux 的命令行用户界面包含大量标准应用程序，大致分六类：

• 文件和目录操作命令
• 过滤器
• 程序设计工具，如编译器和编辑器
• 文档处理
• 系统管理
• 其他

POSIX 规定了上述分类中主要是前三类的程序的语法和语义

10.2.5 内核结构

Linux 内核还有三个重要部件，各个部件之间相互依赖

• I/O 部件
• 内存管理部件
• 进程管理部件

I/O 部件包含所有负责设备交互以及实现联网和存储功能的I/O的内核部件。

这些 I/O 功能整合在虚拟文件系统层中。顶层来看，对一个文件进行读写，不论是磁盘还是内存都是一样的。

下面有句话没读懂，需要每一个键盘输入 …算了不求甚解

内存管理部件包含：虚拟内存、页面置换、页面缓存

进程管理部件包含：信号处理、进程/线程创建终止、CPU调度

10.3 Linux 中的进程

10.3.1 基本概念

守护进程：后台运行的特殊进程，系统启动时守护进程就已经被 shell 脚本开启

一个典型的守护进程『计划任务』，每分钟运行一次检查是否有工作需要它完成。

fork 系统调用，创建一个与原始进程完全相同的进程副本，fork 系统调用给子进程返回零值，父进程返回子进程的进程标识符。父子进程都有自己的私有内存映像。但父进程和子进程共享已经打开的文件。

子进程想要知道自己的 PID，可以调用 getpid

进程间通信方式：管道、软中断

管道：两个进程之间建立一个通道，一个进程向通道写入字节流，另个进程从通道中读取字节流。

管道是同步的，一个进程试图从空的管道读取数据，该进程会被挂起直到管道中有数据。

shell 中的管线就是用管道技术实现的。

软中断：一个进程给另一个进程发送信号。需要一个信号处理函数，信号到达时控制立即切换到信号处理函数。一个进程只可以给它所在『进程组』中其他进程发送信号。一个进程可以利用系统调用给它所在进程组中所有成员发送信号。

10.3.2 Linux 进程管理相关的系统调用

感觉这部分可以大致了解，后面再深入学习。

fork：创建子进程，子进程中返回 0，父进程返回子进程 PID

waitpid：三个参数，第一个指定等待进程，如果时 -1 任何一个子进程结束都可以；第二个参数存储子进程退出状态的变量地址；第三个参数没有子进程结束，调用者是阻塞还是返回。

exec：

在 fork 后的子进程中使用 exec 函数，可以装入和运行其它程序（子进程替换原有进程，和父进程做不同的事）。

exec 函数可以根据指定的文件名或目录名找到可执行文件，并用它来取代原调用进程的数据段、代码段和堆栈段。在执行完后，原调用进程的内容除了进程号外，其它全部被新程序的内容替换了。

三个参数，第一个参数待执行文件名；第二个参数指向数组指针用来传递参数；第三个参数指向环境变量的指针

exit：进程退出时调用这个函数，传入的参数会传提给父进程调用 waitpid 函数的第二个参数。

如果一个进程退出但父进程没有等待它，这个进程进入『僵死状态』，直到父进程等待它，进程才会结束

sigaction：可以用来查询或设置信号处理方式

alarm：一个定时器，过一段时间发送信号

pause：将本进程挂起直到下个信号到来

10.3.3 Linux 中进程与线程的实现

每个进程一个 task_struct 的进程描述符始终存在内存中，包含内核管理全部进程所需的信息，如调度参数、已打开的文件描述符列表等。进程描述符从进程创建就一直存在内核堆栈中，Linux 还通过进程标识符（PID）区分进程。

进程描述符的信息大致分以下几类：

• 调度参数。进程优先级、最近消耗 CPU 时间、最近睡眠时间。
• 内存映射。指向代码、数据、堆栈段等的指针
• 信号。忽略的、需要被捕捉的、暂时阻塞的、在传递中的。
• 机器寄存器。内核陷阱发生时，机器寄存器的内容都会被保存
• 系统调用状态。当前系统调用的信息，参数，返回值
• 文件描述符表
• 统计数据
• 内核堆栈
• 其他。PID、父进程的 PID 等

进程创建过程大致理解，为子进程创建一个新的进程描述符和用户空间，然后从父进程复制大量内容。再赋予子进程 PID，并建立内存映射，赋予文件访问权限，然后寄存器内容初始化准备运行。

写时复制：创建子进程时，复制内存慢，并不直接复制，只有当进程（父子都可）进行写入操作才复制。

Linux 线程

多进程多线程，fork 会有一堆需要解决的问题，信号量，文件等。

引入一个新的系统调用 clone。略复杂不做笔记，之后深入。

10.3.4 Linux 中的调度

Linux 线程是内核线程，Linux 系统的调度是基于线程，而不是进程的。

Linux 将线程区分为三类：

• 实时先入先出：最高优先级
• 实时轮转：有一个时间量，时间到后可以被抢占
• 分时

前两类线程不是真正的实时线程，只是比分时优先级高。

实时线程优先级从 0 到 99，0 是最高优先级。非实时优先级分 100 到 139。非实时线程根据优先级分配 CPU 时间片。

每个线程被分配一个 nice 值，即『优先级调节值』。默认是 0，可以通过系统调用 nice 来修改。

接下来讨论两个 Linux 系统的调度算法。

Linux O(1) 调度器

能够常数时间内执行任务调度。

调度队列分成两个数组：正在活动数组、过期失效数组

每个数组包含 140 个链表头每个链表有不同优先级。链表头指向给定优先级的双向进程链表。

先对活动数组内的任务进行调度，任务时间片到期放入过期失效数组。当活动数组内没有任务，过期失效数组变为活动数组。

这样保证优先级低的任务不会被饿死。不同优先级被赋予不同的时间片长度。

CPU 密集型应该优先级高，但是 Linux 事先无法确定任务类型，所以优先级需要动态的不断被计算。根据被抢占时间长度更改优先级。

完全公平调度器『CFS』

非实时任务的默认调度器。

思想：使用一颗红黑树作为调度队列的数据结构。根据任务在 CPU 上运行时间长度有序排列到树中，这种时间称为『虚拟运行时间』。树中每个节点对应一个任务，左侧的子节点对应 CPU 上运行时间少的任务，因此左侧任务更早调用。周期性的根据任务已运行时间增加虚拟运行时间值，并重新插入合适位置。

优先级低的任务虚拟运行时间值增加得更快。选择一个节点运行 O(1)，插入任务 O(logN)

Linux 调度器还包含对多处理器多核平台有益的特性。

多处理器，每个运行队列数据结构与一个处理器相对应，在满足性能和亲和的前提下调度器能够加载平衡。

调度器只考虑可运行任务，可运行任务在调度队列，其他任务在等待队列。

每种任务可能需要等待的事件对应一个队列，队列头包含指向任务链表的指针以及一枚自旋锁。

Linux 系统中的同步

内存屏障：保证读写操作在任何后续访问发生前已经完成。

自旋锁、信号量、互斥量等

10.3.5 启动 Linux 系统

启动计算机 -> BIOS加电自检 -> 对硬件检测和初始化 -> 启动磁盘第一个扇区『主引导记录』 -> 读入到一个固定内存区域并执行……看看就好

10.4 Linux 中的内存管理

10.4.1 基本概念

每个 Linux 进程都有一个地址空间，逻辑上由三段组成：代码、数据、堆栈段。

代码段包含形参可执行代码的机器指令，通常只读。

数据段包含程序变量、字符串、数字和其他数据的存储。分初始化数据和未初始化数据。

栈段，从虚拟地址空间顶部或附近开始，并向低地址空间延伸。程序启动时栈不为空，包含了所有环境变量以及为了调用它而向 shell 输入的命令行。

大多 Linux 系统支持共享代码段。

数据段和栈段不共享，除非是没有修改页面的父进程下的子进程。

Linux 的进程支持 『内存映射文件』来访问文件，类似读取内存中的数据。

下面部分草草读过

10.4.2 Linux 中的内存管理系统调用

10.4.3 Linux 中内存管理的实现

Linux 内存由三部分组成。前两部分是内核和内存映射，固定在内存中（页面从不换出）。

1. 物理内存管理

四级页表

2. 内存分配机制

第一个内存分配器

页面分配器，分配物理内存页框的主要机制，使用『伙伴算法』

大概意思，将页框分为连续的二的幂次个数个页面块。这样能快速找到合适的内存块。但是会导致碎片太多。

第二个内存分配器

为了缓解碎片太多，另个内存分配器『slab 分配器』，使用伙伴算法得到的内存块，切除 slab（更小的单元）进行管理。

对象缓存：因为内核频繁创建撤销一定类型的对象，使用对象缓存。缓存由指向一个或多个 slab 的指针组成，slab 可以指向大量相同类型的对象。

第三个内存分配器

vmalloc：用于仅仅需要连续虚拟地址空间的请求，用于分配大量连续地虚拟地址空间。

3. 虚拟地址空间表示

10.4.4 Linux 中的分页

分页一部分由内核实现，一部分由『页面守护进程』实现。

交换区：长度固定的分页文件（应该是指这句话）

页面置换算法

PFRA（页框回收算法），页面区分为四种：

• 不可回收：包括保留或锁定页面、内核态栈等，不会被换出
• 可交换：必须在回收前写回交换区或分页磁盘分区
• 可同步：如果被标记为脏的必须写回磁盘
• 可丢弃：可以立即回收的

每次先回收容易回收的页面，可丢弃和未被引用的可以立即加入空闲链表从而回收。接着找有备份未修改的页面……

10.5 Linux 中的 I/O 系统

10.5.2 网络

套接字，常用套接字类型：

• 可靠的面向连接的字节流
• 可靠的面向连接的数据包流
• 不可靠的数据包传输

第一种，允许不同机器上两个进程之间建立一个等同管道的连接。系统保证所有被传送的字节都能够到达，并按发送顺序到达。

第二种，和第一种类似，不过是发送一次接收一次。第一种如果发送五次，会一次接收到所有。

第三种，高性能

10.6 Linux 文件系统

10.6.1 基本概念

独占锁：指该锁一次只能被一个线程所持有

共享锁：指该锁可以被多个线程锁持有（应该是只能一人写，读者不限的意思）

这块竟然看得还挺轻松，文件系统很多都讲了，笔记先略过大部分。

10.6.2 Linux 种的文件系统调用

creat

open

close

read

write

lseek 改变读写位置

stat 查看文件信息

pipe

fcntl 锁

10.6.3 Linux 文件系统的实现

1. Linux 虚拟文件系统

虚拟文件系统『VFS』，隐藏 Linux 支持的所有文件系统之间的区别。

VFS 支持的四个主要的文件系统结构

• Superblock，包含文件系统布局的重要信息
• i 节点，表示某个确切的文件，目录和设备也被当作文件
• Dentry，目录项
• File，打开文件在内存中的表示

2. Linux ext2 文件系统

磁盘被分为许多块组，0 号块组通常存储启动计算机的代码。

实现太复杂，草草看看过，告辞。

3. Linux ext4 文件系统

最主要相比 ext2 多了日志文件系统，其他方面也有加强。

4. /proc 文件系统

10.6.4 NFS 网络文件系统

网络文件系统，就知道干啥的，不看了。。

10.9 小结

关键概念，进程、内存模型、I/O 和文件系统。

我就这？太菜了，好多没怎么看懂就草草看过。