从宏观的鱼度看，可以计算机系统分成三个基本组成部分：底层的计算机硬件、中间层的操作系统以及上层的计算机应用程序，操作系统属于承上启下的中间层，所以它在计算机系统中的地位和作用尤为重要；
操作系统是计算机系统中最基本的系统软件；
操作系统的层次结构如下，可以认为对操作系统来说，用户和应用进程等价，都是其服务对象；
之后的课程将主要介绍操作系统中的六个基本模块，即CPU管理、内存管理、外设管理、磁盘管理与文件系统、用户接口和启动模块，以及这些模块之间的内在联系；
Q：处理机和CPU有什么关系，是等价的吗？
A：可以简单的认为处理机=CPU+存储器+I/O接口，所以对于单核CPU等价于只有一个处理机；
操作系统的理解从“走进操作系统开始”，系统启动无疑是操作系统的第一层面纱（本章最好参考王道视频，哈工大的教材有点过于偏向实操反而忽略了很多基础的知识点）；
操作系统就是安装在计算机硬件之上的一个实实在在的软件，人们通过这个软件可以方便而高效地使用计算机硬件。
（1）操作系统是安装在计算机硬件之上的一层软件；
（2）操作系统之上可以安装各种应用程序软件；
（3）用户可以通过应用程序软件来间接使用操作系统，也可以直接使用操作系统，但通常都是通过操作系统来最终使用计算机硬件的；
（4）直接使用操作系统的含义就是让用户通过编写程序来调用操作系统提供的系统接口从而进入操作系统，而图1.1中的应用程序软件就是为调用这些系统接口而编写的程序；
（5）用户通过系统接口进入操作系统后使用计算机硬件，即用户必须“穿过”操作系统才能使用计算机硬件；
（6）操作系统管理计算机硬件，目的是让用户对计算机硬件的使用更加简便，也更加高效；
总结：操作系统是硬件和用户/应用之间的桥梁，操作系统管理硬件，为应用和用户提供服务；
操作系统在管理CPU的时候，抽象出来一个基本的概念——进程，因此CPU管理就变成了进程管理；操作系统在管理磁盘等外部设备的时候，又抽象出来一个被称为文件的基本概念，这样磁盘管理又变成了文件系统；
一个基本操作系统包含如下四个基本管理模块：进程管理、内存管理、I/O管理以及文件系统，再加上提供给上层应用的系统接口，就形成了如图1.3所示的操作系统结构（这只是最基本的操作系统结构，各种操作系统都是在其基础上迭代演化）
我们可以认为操作系统在整个计算机系统中扮演如下角色：
操作系统是一种系统软件，操作系统的基本特征包括并发、共享、虚拟和异步；
Q：系统软件和应用软件的区别？
A：
操作系统的并发性是指计算机系统中“同时”存在多个运行的程序，它具有处理和调度多个程序“同时”执行的能力；
Q：并发和并行的区别？
共享也就是资源共享，是指系统中的资源可供内存中多个并发执行的进程共同使用，共享可分为以下两种资源共享方式：
虚拟是指将一个物理上的实体变为若干逻辑上的对应物；
操作系统利用了多种虚拟技术来实现虚拟处理器、虚拟内存和虚拟外部设备等：
简单来说，操作系统的虚拟技术可以归纳为：时分复用技术（处理器的分时共享）和空分复用技术（虚拟存储器）
操作系统系统了一系列接口为用户服务，主要分为两类：
简单的批处理系统
“批处理”工作模式即计算机逐个执行每个任务，每个任务只有在执行完毕或出错以后才会切换去执行下一个任务；
批处理操作系统的任务就是在当前程序执行完毕或出错时，将下一个程序读入内存，并将程序执行指针设置为放置下一个计算任务第一句代码所在的内存地址；
这样的操作系统实际上只能算是一个监控小程序，远不能算作是操作系统；
多道程序系统
假设有JOB1和JOB2，JOB1涉及外存的使用非常耗时，JOB2只进行科学计算；
多道程序的概念是指，可以同时启动JOB1和JOB2两个任务。首先执行J0B1，当其执行到外存读写操作时，CPU向外存发出操作指令后记住JOB1的当前执行状态，然后CPU切换到JOB2去执行，当J0B1的外存读写操作完成时，CPU保存JOB2当前的执行状态并切换回到JOB1，从那个保存下来的执行状态处继续执行；
多道程序是指计算机系统中有多个程序“同时”向前推进（这里的同时加引号是因为只有一个CPU，同时仅仅只是宏观上的感觉）
分时处理系统
总结
根据操作系统的发展历史，可以总结出操作系统的核心轮廓，即多进程视图和文件视图；
无论操作系统如何演进，操作系统的基本思想——多道程序一直没有改变过，这依赖于现代计算机都以“存储程序”思想作为基本结构；因为程序执行和未执行的状态差别非常大，所以针对执行中的程序定义了进程的概念，也因此CPU在多个程序之间来回切换就变成了在多个进程之间不断交替执行，也就是著名的多进程切换视图
文件视图简单来说就是将所有的计算机外部设备都统一抽象成文件（类似于Linux“一切皆文件”的思想）
多进程视图让CPU和内存高效运转，用户程序在文件视图下使用各种外部设备，因此在多进程视图和文件视图下，整个计算机硬件系统不断高效运转，操作系统也就完成了其对计算机硬件的管理。因此，多进程视图和文件视图构成了操作系统的完整轮廓；
计算机本质上是一个计算模型，最著名的计算模型是图灵机
简单图灵机
模拟大脑->笔->纸张的计算过程，图灵机由控制器、纸带以及连接两者的读写指针组成
通用图灵机
当然简单图灵机只能做非常简单的加法、减法等单一的操作，简单图灵机经过演化得到通用图灵机
类比厨师做菜，简单图灵机就只是一个只会做一道菜肴的普通厨师，一个能看懂菜谱的厨师对应可以修改的控制器，不同的菜谱（做菜的步骤）对应设置控制器动作（这也就是现代计算机中的程序），数据对象对应按照菜谱做出的菜肴；
通用图灵机已经非常接近现代“冯诺依曼”体系的计算机，我们可以得出结论，计算机的工作原理无非四个字——取值执行
操作系统启动的主要工作就三项：系统准备、系统初始化和系统运转进入shell；系统准备又包括读入内核、启动保护模式、启动段页等，图1.30给出了系统启动过程的基本轮廓；
BIOS是计算机启动以后第一个运行的软件，和普通软件和操作系统都不一样，通常放在不可改的存储器上面，被称为固件；
BIOS通常会执行以下操作：
BIOS实际上已经是历史，下面介绍BIOS的继承者UEFI
bootloader是OS的一部分，一般认为OS=bootloader+kernel，是第一个用户可以自定义的程序；
bootloader主要执行以下工作：
关于BIOS和Bootloader这里简单做一个区分，尽管这两个概念几乎不会混淆
Q：为什么BIOS不直接load整个OS的kernel？
A：因为BIOS只能load很小的一部分的数据（历史的包袱），并且BIOS需要保持最简化的功能（固件最简化），所以BIOS一般都是loadbootloader之后进而load整个OS的kernel；
X86架构是Intel较早出的CPU（8086、80286等16位以及之后的32位都属于这个架构），现在的64位CPU被称为X64（至于是AMD的还是Intel的就不要太纠结了），其他的ARM架构等不在我们的讨论范围中；
现在我们来介绍为什么会有实模式realmodel和保护模式protectedmodel这两个模式；
之所以会出现这两个模式是由于历史的包袱-因为硬件不断演化，操作系统需要兼容，甚至硬件之间也要相互兼容，因此诞生了这两个CPU运行模式，实模式下一般只能访问16bit的数据，保护模式能够兼容16bit并访问更高位数的数据，并且保护模式能够真正的保护进程的一些信息；
保护模式又被称为虚地址保护模式，是在80286系列之后出现的一种CPU操作模式，在此之前只有实模式，为了兼容，现代计算机上电后CPU首先会在实模式下再转换为保护模式；
下面的表格简单展示了实模式和保护模式的区别
CPU实模式的内存寻址方式为分段寻址（段地址*16+段内偏移）；
要注意寻址的概念不是操作系统专有（操作系统寻址最终还是对硬件进行操作），当数据存放在内存中的时候，我们称定位内存单元地址的方法为寻址，不管寻址方式如何，最终的内存中的物理地址都是一个整形的数值；
CPU保护模式脱胎于32位CPU，这意味着保护模式下CPU可以利用232的内存区域，而如今流行的64位CPU的内存空间几乎是无限大；
32位CPU除了能够寻址32位的地址以外（16位CPU可以寻址20位），还发展出了很多的功能，与现代操作系统相辅相成，例如内存保护，分页系统，以及硬件支援的虚拟内存，拥有这么多的功能，硬件自然要提供很多机制才能实现出来，这就叫做保护模式；且保护模式下可以防止程序之间互相访问带来的问题；
因为保护模式利用了更大的内存空间，所以其寻址方式相较于实模式更加复杂，其段寄存器不再是一个单纯的段基址而是一个指向数据结构的指针；保护模式下的寻址方式主要有分段模式和分页模式；
GDT是在保护模式下一个必不可少的数据结构，同时在系统中只能是唯一的；
实模式下对内存地址的访问通过段基址:段内偏移实现，保护模式下内存的管理模式分为段模式和页模式（页模式基于段模式，也被称为段页式）；
段模式下对一个段的描述包括3个因素[段基址，段最大长度，访问权限]，我们将该64bit长的数据结构称为段描述符，而寄存器始终是16bit的，因此只能将这些长度为64bit的数据结构放在一个数组中，该全局可见数组就是GDT（事实上GDT不仅存了段描述符，还有其他描述符）；
GDT可以存放在内存的任何位置，GDTR寄存器专门用于存放GDT的入口地址，之后CPU就可以根据该寄存器中的内容作为GDT的入口来访问GDT；
除了GDT，Intel32位体系架构还支持构建与GDT类似的数据结构LDT（每个进程的段表实际就是LDT）：
同样的，Intel32位架构提供了LDTR寄存器来保存LDT的入口地址（全局只需要一个）；
GDT表描述的是操作系统的代码段、数据段等（主要存放操作系统和各任务公用的描述符），LDT表用来描述每个进程的代码段、数据段等；
作为操作系统中奇葩的存在，电脑启动时CPU在实模式，启动过程中的某个阶段会切换成保护模式；
传统的16位处理器启动时就是在实模式，也就是纯裸的，没有任何支持。32位处理器为了兼容16处理器，把开机时的实模式也兼容了，所以即使是16位的操作系统，放到32位处理器上，仍然能运行。所以开机的时候CPU就是实模式，然后32位操作系统又将实模式切换成保护模式。如果发现是16位的操作系统，就直接运行在实模式好了。实模式的存在就能兼容之前的16位程序。
CPU通常会执行两种不同性质的程序：
对操作系统而言，前者是后者的管理者，因此“管理程序”会使用一些“应用软件”不允许执行的特权指令如I/O指令、置中断指令等；
具体实现就是将CPU的状态划分为用户态和核心态，使得用户自编程序运行在用户态，操作系统内核程序运行在核心态；
一些与硬件关联比较密切的模块如时钟管理、中断处理等；其次是运行频率较高的程序如进程管理、设备管理等，这两部分内容构成了操作系统的内核——这部分的指令操作工作在核心态，内核是计算机上配置的底层软件；
内核是不能直接使用的，如Linux内核，必须包装（添加C库、C编译器、绘图软件等应用软件）之后才能给用户使用；
不同的系统对内核的定义有区别，大多数操作系统内核包括：
Q：程序和软件的区别是什么？
A：简单来说，软件=程序+文档=数据结构+算法+文档
上面我们提到，操作系统引入了核心态和用户态两种工作状态，这里我们讨论这两种状态如何切换：
当用户程序需要使用一些核心态的功能时，就需要借助一些建立在核心态的“门”以便实现从用户态进入核心态，实际操作中唯一能够进入这些gate的途径就是通过中断或异常；
发生中断或异常时，运行用户态的CPU会立即进入核心态，这是通过硬件实现的（一位寄存器0表示核心态、1表示用户态）
中断（默认情况下所说的中断都是指外中断）处理流程大致如下：
操作系统在核心态应当为应用程序提供什么样的公共服务？主要有两种主要的体系结构解答：大内核和微内核；
操作系统是管理计算机硬件的一层软件系统，学习操作系统的核心就是学习操作系统如何使得用户对计算机的使用更加方便和高效，前提是我们知道用户是如何使用计算机系统的，这就是系统接口的基本概念；
系统接口是用户使用操作系统（计算机系统）的基本入口，系统接口也是通向操作系统内核的窗口，很多关乎内核模块的理解都需要通过系统接口进入；
计算机系统的使用方式主要可以分为如下三种：
无论哪种方式，最终真正能让计算机产生效果，即真正使用计算机硬件的那一部分实际上是一样的，即调用函数；
无论是命令行、应用程序或图形界面，在本质上都是一样的，即用户编写应用程序，在应用程序中会调用一些由操作系统提供的重要接口函数。然后这些应用程序相互配合，实现对计算机的使用；
接口函数就是应用程序在使用计算机时要调用的函数，由于这些函数是系统提供的，又是以函数调用的形式出现的，而且这些函数非常重要，所以这些函数对应一个非常重要的概念——系统调用；
Q：操作系统接口和系统调用等价吗？
A：等价，操作系统接口表现为函数调用，因为函数由系统提供，所以操作系统接口就是系统调用——“系统调用实际上就是操作系统提供给应用程序的接口函数”
操作系统提供的服务分为面向客户（命令接口）和面向软件/编程人员（系统调用）；
在用户程序中凡是与资源有关的操作都必须通过系统调用的方式向操作系统提出服务请求，由操作系统代替完成，系统调用按照功能可以大致分为如下几类：
系统调用的处理需要由操作系统内核程序负责完成，这需要运行在核心态；
fork、exec、wait和exit这四个系统调用是和进程有关的最为重要的四个系统调用：
fork
fork系统调用的函数原型定义为：
intfork();这个函数没有参数，调用该函数的进程会再创建一个进程，新创建的进程是原进程的子进程；两个进程都从fork（）这个地方继续往下执行，并且执行“同样”的代码。但是父进程执行fork（）会返回子进程的ID，而子进程调用fork（）会返回0，父子进程正是通过对这个返回值的判断（用if语句）来决定分别执行哪段代码；
exec
系统调用exec（）的功能是在当前进程中执行一段新程序，进程的PID保持不变。可以这样形象地理解，一个进程就像一个壳子，在这个壳子里可以装各种可执行代码。fork（）创建了这个壳子，并且将父进程的代码装在这个壳子中执行，而exec（）是用一个磁盘上的可执行程序（exec（）的参数告诉操作系统是哪个可执行程序）替换了这个壳子里原有的内容；
exec()函数分为两类，分别以execl和execv开头，其函数原型定义如下：
voidexecl(constchar*filepath,constchar*arg1,char*arg2,…);voidexeclp(constchar*filename,constchar*argl,char*arg2,…);voidexecv(constchar*filepath,char*argv[]);voidexecvp(constchar*filename,char*argv[]);这些函数基本上一样，只是execl中对应可执行程序入口函数的参数，即其中的arg1、arg2等，是一个一个列举出来的，而execv是将这些参数组织成一个数组告诉操作系统的；
可执行程序入口函数的参数就是可执行程序的main（intargc，char*argv[]）函数中的参数argv，我们都知道这些参数是通过命令行输入的，命令行中的参数实际上就是用系统调用execl/execv函数中的参数传进去的；
函数名中带p和不带p的差别在于：execv（）中filepath是绝对路径，而execvp（）中的filename是相对路径；
exit
系统调用exit用来终止一个进程，在进程中可以显式调用exit来终止自己，也可以隐式调用exit；
操作系统在编译main（）函数时，当遇到main（）函数的最后一个}时会“塞入”一个exit；
exit（）函数的原型定义为：
voidexit(intstatus);exit中的参数status是退出进程返回给其父进程的退出码。同时，退出的进程会向其父进程发送一个SIGCHILD信号，一个进程执行wait系统调用时就会暂停自己的执行来等待这个信号。所以wait和exit合在一起可以完成这样一种进程之间的同步合作：父进程启动了一个子进程，调用wait等待子进程执行完毕；子进程执行完毕以后调用exit给父进程发送一个信号SIGCHILD，父进程被唤醒继续执行；
wait
wait系统调用的函数原型定义为：
intwait(int*stat_addr);其返回值是exit子进程的PID，stat_addr是进程中定义的一个变量，用于存放子进程调用exit时的退出码，即exit系统调用的参数status；
open、read、write是典型的操纵文件的系统调用。同时，这三个系统调用也是用户编程时最为常用的系统调用，这是因为文件是用户操作计算机的基本单位；
三个系统调用的函数原型定义为
intopen(char*filename,intmode);intread(intfd,char*buf,intcount);intwrite(intfd,char*buf,intcount);open
open系统调用用来打开文件，其中第一个参数filename是要打开的文件名，mode是打开方式，返回值fd是打开文件后产生的句柄，以后就用这个句柄来操作打开的文件；
read
read和write是操作打开文件的系统调用，read用来将句柄fd对应的文件读入到内存缓存区buf中，并且要读入count个字节，而真正读入的字节数会由read返回；
write
write用来向句柄fd对应的文件写内容，即从内存缓存区buf中取出count个字节写出到文件中，当然真正写出的字节数由write返回；
printf和scanf是用来分别操纵显示器和键盘的函数，函数原型是：
voidprintf（格式化输出字符串，输出内容，…）；//如printf("ID:%d",3)voidscanf（格式化输入字符串，输入内存地址，…）；//如scanf("ID:%d",&id)注意，这两个函数不是系统调用，仅仅只是两个库函数，这两个库函数的实现依赖于write和read实现“写显示器”和“读键盘”
Q：库函数和系统调用的区别在哪里？
系统调用不仅是为了给上层用户提供“统一接口”供其使用，同时作为操作系统的大门，上层应用只能通过这个大门才能进入操作系统；
要实现系统调用的“大门”作用，首先要区分“门里”和“门外”，在操作系统中我们称其为内核态和用户态，一般情况下：
无论是操作系统内核代码还是应用程序代码都是装入内存后才执行的，而内核态代码和用户态代码在内存中放置的区域不同：
结论：一般来说kernel的代码都在高地址，方便用户态进程从低地址进行处理；
系统调用的“大门”作用体现在让执行在用户态区域的代码不能进入内核态区域（具体来说就是用户态代码不能通过jmp跳转到内核态内存区域中，用户态代码也不能通过mov访问存放在内核态内存中的数据）
Q：同样在内存中，如何区分是用户态内存还是内核态内存？
A：内存的使用由操作系统统一管理，操作系统在内存中划定一个区域并设置该区域的特权级，操作系统会及那个自己所在的内存区域的特权级别设置的非常高，将用户程序所在区域的特权级别设置的较低；
在用户程序执行时每访问一次内存都做一次审查。如果要访问的内存区域比自己的特权级高，CPU会拒绝执行，这就实现了操作系统的保护机制；
CPU提供了一种被称为特权环的机制来实现这个特权级检查；
由于很多指令在执行时都要进行这样的特权级检查，为了提高执行效率，应该用计算机硬件即CPU电路来实现这个权限检查，而不是用软件来完成这个检查；
特权级检查涉及两个重要的数值：
双模态是由操作系统和硬件一起实现的，硬件主要实现下面的功能：
特权指令是指只有在CPU处于内核态的时候才能执行的指令，一个不严谨的说法是，影响其他进程的指令就是特权指令
特权指令不能通过普通应用直接执行，必须让操作系统帮助执行，操作系统向用户态应用提供了接口用来执行这些特权指令，这些接口被称为系统调用
硬件会帮助操作系统检测程序的优先级（上面已经介绍过）；
内存保护可以保证物理地址和虚拟地址都是隔离的，当然这里硬件需要进行的地址的隔离是指物理地址；
分段法具有不容易实现共享、内存碎片化的问题，因此现代操作系统一般都采用分页的方法；
分页法涉及的一个很重要的概念是虚拟地址到物理地址的转换（实际上是虚拟页到物理页的映射，我们之后会详细介绍），这个映射过程是操作系统和硬件一起执行的-由硬件(CPU中的MMU)来执行虚拟地址到物理地址之间的映射，由软件OS来决定映射的策略，OS和CPU的中间体就是页表，页表存在内存中；
注意：计时器的设置只能在内核态进行
本质上就是进程/线程切换，我们将在后面详细介绍；
代码(静态存放在存储器中)：可以分为用户代码和操作系统代码；
进程(一段代码的上下文，不仅包括代码还有堆栈等)：可以分为用户进程和操作系统进程；
CPU的运行状态可以分为用户态和内核态；
前面已经介绍过，操作系统是管理计算机硬件的软件系统，本章开始将逐步讨论操作系统如何管理各种计算机硬件；
本章讨论的是操作系统如何管理CPU，从使用CPU开始，使用CPU最直观的方式就是——将一段程序的初始地址设置给PC指针，然后CPU就开始不断地“取指一执行”，CPU也就被使用起来了。但是这样的简单方式会导致CPU效率低下，我们给出了解决方法——并发；
在并发这一基本思想下，将分析给出程序执行起来的样子，并分析执行起来的程序和静态程序之间的本质差别。为了描述这种本质区别，进程的概念被提出来，多进程视图也随之出现了。由于CPU是计算机硬件的核心，多进程视图也就自然成为操作系统的核心视图；
CPU的工作原理就是不断地重复执行“取指-执行”，因此想要让CPU运转起来只需要将一段程序放入内存中，接着将PC指针设置为这段程序的起始地址，接着CPU便自动循环“取指-执行”开始工作；
这个直观方法也很容易实现：
当然这样使用CPU必然存在很大的问题，在实际场合中这样的管理会使得CPU的利用率变得非常低，解决办法就是利用——并发（在并发的思想下，分析程序执行起来的样子并对比执行起来的程序和静态程序之间的本质差别，为了描述这种本质区别提出了进程的概念，基于进程的概念提出多进程视图的概念）；
在采用了并发思想之后，操作系统高效管理CPU就具体实现为“在多段程序之间来回切换”，要实现这种切换，只修改PC指针（即修改寄存器CS:EIP）是不够的，不仅要修改PC指针，同时还要将曾经执行的信息保存起来，于是需要引入新的数据结构以保证程序的正确执行并实现多个执行的程序之间来回切换，这个数据结构保存了该程序当前执行位置、执行现场等重要信息；
介绍这种数据结构(PCB)之前，我们先介绍一个概念——进程，进程用来描述一个程序及其执行过程中的信息，即描述一个执行中的程序；
进程描述的是“程序以及反映程序执行信息的数据结构的总和”，该数据结构也就是常说的进程控制块（processcontrolblock，PCB）；
Q：进程与PCB之间的关系？进程实体和进程映像呢？
Q：PID和PCB之间的关系？
传统操作系统中的进程定义为：进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位；
简单来说，进程就是一个程序的运行时，包含了一些权限控制，进程之间不共享数据，每个进程有自己独立的地址空间，一个进程至少包含一个或多个线程；
进程的基本特征是对比单个程序的顺序执行提出的，也是对进程管理提出的基本要求：
（我们在下面还会涉及进程的状态，但是那个地方为了简化分析所以就只讨论最基本的三种情况，这里我们详细介绍五种状态的进程）
地址空间分为物理地址空间(内存、磁盘)和虚拟地址空间；
因为操作系统的缘故，对一个进程/程序来说似乎独占所有硬件资源，一般一个进程会分为如下几个段，其中堆向上生长，栈向下生长（注意这里的地址空间是虚拟地址空间，之后也会讲，分段常用于用户视图）
下面这段程序在load进入内存之后，变量将被分配到不同的段
结论：一个可执行程序已经指定好了段的大小等信息；
有了进程的概念后，可以应用进程的概念对CPU管理做描述：CPU管理的最终结构概括为操作系统启动多个进程，并能够在多个进程之间调度/切换，从而实现CPU高效管理；
（1）在操作系统中现在有三个进程，其PID分别是1、2、3；
（2）现在正在执行的是2号进程；
（4）进程1和进程3停下来的执行现场分别存放在各自的PCB中；
（5）操作系统通过这些PCB可以感知、了解并控制各个进程，操作系统对进程的管理关键在于对这些PCB的管理；
多进程视图是操作系统的核心视图.操作系统在从开机启动到最后关机的全部运行过程中都要围绕这个多进程视图工作；
一个进程执行完毕以后可以调用exit（）来退出自己，但shell不会调用exit（）退出自己，除非关机。因此shell进程会一直执行，不断创建新的进程，并用这些新进程完成各种各样的任务。在操作系统最终关机时，会将系统中所有进程杀死；
编写操作系统中的进程管理模块，需要做到以下两点：
在操作系统中，一般把进程控制用的程序段称为原语，原语的特点是执行期间不允许中断，它是一个不可分割的基本单位；
允许一个进程创建另一个进程，此时创建者称为父进程，被创建的进程称为子进程：
我们简单介绍操作系统创建一个新进程的过程（即给出一段创建原语）：
1.为新进程分配唯一的PID并申请一个空白的PCB，若PCB申请失败则创建失败；2.为新进程的程序和数据以及用户栈分配必要的内存空间，若资源不足不会导致创建失败，而是处于阻塞态等待内存资源；3.初始化PCB，主要包括初始化标志信息、初始化处理机状态信息以及初始化处理机控制信息、进程优先级等；4.若就绪队列能够接纳新进程则将新进程插入就绪队列等待被调度运行；3.2进程的终止引起进程终止的事件有：
撤销原语如下：
1.根据被终止进程的标识符检索PCB，从中读出该进程的状态；2.若被终止的进程处于执行状态则立即终止该进程的执行，将处理机的资源分配给其他进程；3.若该进程有子孙进程则将其所有子孙进程终止；4.将该进程拥有的全部资源归还给其父进程或操作系统；5.将该PCB从所在队列删除；3.3进程的阻塞和唤醒进程的阻塞是进程自身的一种主动行为，只有处于运行状态的进程才可能转换为阻塞态，阻塞原语的执行过程如下：
多进程视图工作的核心是多个进程之间的来回切换，这也是并发的基本含义，操作系统实现多进程视图需要解决如下两点：
//一个调度点的实例代码某个进程{ 启动磁盘写；pCur.state='W';//将进程状态修改为阻塞态将pCur放在DiskWaitQueue;//pCur就是用于保存“CPU中当前进程执行现场”的PCB结构，当然它就是当前进程的PCB，便于将来能够切换回当前进程schedule();//调用schedule函数完成进程切换}操作系统调用函数schedule()实现切换，其实现原理如下：
这其中如何选择pNew需要精心设计算法，如果只是简单的选择就绪队列首部的进程作为下一个进程，这样公平但是对于某些应当需要优先执行的进程来说非常致命；
简单给出schedule函数的基本代码结构
schedule(){pNew=getNext(ReadyQueue);switch_to(pCur,pNew);}switch_to(pCur,pNew){//保存当前进程的PCB结构pCur.ax=CPU.ax;pCur.bx=CPU.bx;...//用pNew中的执行现场替换CPU中的寄存器CPU.ax=pNew.ax;CPU.bx=pNew.bx;}4.进程组织要论述操作系统是如何实现多进程视图（前面已经给出过图示）的，第一步要解决的问题就是在计算机中如何组织多个进程；
操作系统管理进程的关键就是管理进程对应的PCB数据结构，所以很容易就能想到，组织多个进程就是用合适的数据结构来管理这些PCB；
PCB之间存在简单的线性关系，简单而高效的方式就是将这些PCB组织成队列，并且在管理进程时需要区分进程位于哪个队列，根据进程状态概念可以分类描述操作系统中的进程：
基于单CPU的背景，因此只有一个CPU意味着只会有一个处于运行态的进程，多个阻塞队列（多种等待事件），一个就绪队列（都在等待CPU），故形成下图所示多进程基本组织方式
上图类似于一张合照，是某一时刻下多个进程在操作系统中的样子，当然利用进程状态还可以描述一个进程在其执行过程中的演化过程（该过程常被称为进程的生存周期）
尽管多个进程同时在内存中交替执行可以提高CPU的使用效率，但是同时在内存中的多个进程也会相互影响（比如某个进程把另一个进程的内存地址给修改了）；
解决上述问题的办法就是使用地址隔离
进程操作的地址并不是真的物理内存地址，而是通过一个映射表对应到一个真实的物理地址，这也是需要用GDT表和页表来翻译CS:EIP的根本原因；
操作系统给每个进程分配的真实的内存区域是只属于该进程的、互相不重叠的，就算进程1和进程2同时访问的地址是100，但是通过映射表后访问的真实地址其实是2100和1100；
多进程之间不仅需要隔离，更需要合作，最基本的进程间合作模型是一个进程要往一个缓存区写数据，而另外一个进程要从缓存区里读数据。此时就需要一个合适的进程间通信机制与合作机制；
实现进程间通信的方法很多，可以读写同一个数据库、文件、共享内容以及一段内核态内存等；
真正困难的是提供合适的进程间合作机制，如果没有一个良好的机制可能导致一些问题（如一边写一边读，但是缓存已经满了，于是写不进去导致信息丢失）。我们将这种基本进程间合作模型（一个进程写共享空间，另一个进程读共享空间）称作“生产者-消费者”模型：
（上面说了那么多好像也不是很清楚，我们结合王道书再总结一下）
进程通信指的是进程之间的信息交换，PV操作是低级通信方式，高级通信方式（以较高的效率传输大量数据的通信方式）主要有以下三类：
注意：从管道读数据是一次性操作，数据一旦被读取，它就从管道中被抛弃，释放空间以便写更多的数据。管道只能采用半双工通信，即某一时刻只能单向传输。要实现父子进程双方互动通信，需要定义两个管道。
本章首先引出线程这个概念，并以线程为单位对CPU切换进行详细论述，这是因为线程切换是进程切换的核心内容；
进程切换由资源切换和指令流切换两部分构成，其中资源切换是将分配给进程的非CPU以外的资源进行切换，如对当前地址空间的切换（资源切换将在之后的内存管理、文件系统章节详细论述）；而指令流切换就是CPU切换，也就是线程切换（这是本章的重点）；
并发是CPU高效工作的基础，并发的基本含义就是多段程序交替执行，我们思考，是否可以将这种交替执行的思想应用于一个进程（同一个可执行文件）的不同函数之间呢？这样的交替执行就产生了线程的概念；
我们给出一个浏览器使用线程和不使用线程的例子：
肯定又有人问了，那我使用四个进程呗？和使用四个线程有什么区别？进程和线程的区别在于是否共享资源（线程之间不会共享栈！！！这在之后我们会介绍），此处因为这四个函数是可以不使用地址隔离策略将内存缓存区分离的（不存在安全性问题），况且使用四个进程会造成内存的浪费以及代码执行效率的降低，所以我们选择共享共同地址空间等进程资源的四个并发指令执行序列作为四个线程；
下面的表格给出了线程和进程的区别和联系
线程相较于进程的优点：
线程和进程的关系：
在一个地址空间下启动并交替执行的线程既可以由操作系统管理，也可以由用户程序管理：
想要实现多个用户级线程之间的切换，只需要在切换位置（调度点）调用一个普通的用户态切换函数（由用户自己编写）即可；
在设计用户态切换函数的时候需要注意：如果每个线程用自己的栈，那么在线程中执行函数调用和返回时就不会莫名其妙地跳转到其他线程中；
单个栈执行的两个用户级线程的切换实例
切换函数Yield是完成线程切换的核心，这里我们举例说明Yiled的工作过程：两个用户级线程，线程1执行A函数并在其中调用B函数；线程2执行C函数并在C函数中调用D函数；
首先线程1正常执行函数A，当需要调用函数B时需要通过一些栈来保存信息以便在函数B执行完毕后可以跳回A继续执行（这是函数调用的基本常识），因此我们将需要返回的地址104压栈；同理B中调用Yield的时候也会将204压栈，接着执行Yield函数（找到下一个线程以及下一个线程切换过去的时候的执行位置）
Yiled(){jmp300};切换到线程2执行，同理依次压入304和404，此时再次执行Yield函数跳转回线程1，因此此时的Yield函数应该为
Yiled(){jmp204};//跳转回204的地址，因为刚才线程1是从204之前切换出去的当我们从204继续执行的时候，遇到B的“}”会发生弹栈进行函数返回，我们期望的情况是能够弹回104即A函数中，但是很明显我们的栈会弹出线程2的404地址，因此我们需要做出改进
独立栈执行的用户级线程的切换实例
因为现在每个线程都拥有自己的栈，所以在Yiled函数切换的时候不仅要修改PC的值，还需要完成栈的切换，总结如下：
A：TCB是进程控制块，PCB是线程控制块（也称为任务控制块）：
与TCB相比，PCB额外存放地址空间、进程包含的线程Tid
一旦明白切换的具体实现，线程的创建就非常容易理解——线程的创建就是将线程做成第一次切换的样子（此处描述可能比较抽象，下面会详细描述）；
一个进程通常包含多个线程，多个线程中必须包含一个主线程，进程启动时会从主线程（程序运行时即使没有创建线程后台也会存在如主线程、gc线程等多个线程）开始执行，接着主线程调用其他子线程或其他子线程之间相互调用，主线程结束意味着整个进程都会结束，那么其他所有子线程也会结束（强制结束）；
我们假设线程1是主线程，线程1在执行过程中调用Yield()转换函数让出CPU切换到线程2中执行，如果线程2能够顺利执行则证明线程2创建成功（当然这里讨论的都是用户态线程的创建）
创建用户级线程的函数thread_create()大致如下
用户级线程这个概念刚提出的时候，操作系统的厂商为了避免直接将未验证过的东西加入内核于是编写了一个关于用户级线程的函数库，However，这个函数库位于用户空间，也就是说操作系统内核对这个函数库一无所知（也就意味着操作系统的眼中还是只有进程而没有线程这个概念，所以借助线程库写的多线程进程实质上还是只能在一个CPU核心上运行）
结论1：对操作系统来说，用户级线程具有不可见性（透明性）
结论2：用户级线程只能使用一个处理器，只能做到并发而无法做到并行加速
因为用户级线程的透明性，导致操作系统无法主动切换线程，也就意味着A、B两个进程同时存在时，A在运行的时候线程B想要运行只能等待A主动放弃CPU；
那么用户级线程就一无是处了？作为程序员，我们可以为自己编写的应用程序定制调度算法（自己决定什么时候退出线程），有关用户级线程的其他好处我们在之后会总结；
因为用户级线程在操作系统中是看不见的，那么当其中某一个线程阻塞（比如上面的A线程阻塞，那么B也会一直等待下去），在操作系统眼中是整个进程都阻塞了，对于这种情况也出现了相应的解决方法（如jacket），但如果我们使用内核级线程就不会存在这样的问题（线程A被阻塞，但与它同属一个进程的线程B不会被阻塞）；
为了实现内核级线程，内核中需要有一个能够记录系统中所有线程的线程表，每当需要新建一个内核级线程的时候都需要进行一个系统调用进行线程表的更新，得益于线程表，操作系统可以看见内核级线程，因此操作系统可以将这些多线程放在多个CPU核心上实现真正的并行，然而内核级线程并不是完全优秀，因为内核级的线程调度需要操作系统来实现，这意味着每次切换内核级线程都需要陷入内核态，而操作系统从用户态到内核态是有开销的，同时线程表存放在堆栈空间其数量受到限制，拓展性比不上用户级线程；
某些操作系统同时支持用户线程和内核线程，实现了用户级线程和内核级线程的连接方式：
1）多对一模型。将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。此模式中，用户级线程对操作系统不可见（即透明）。优点：线程管理是在用户空间进行的，因而效率比较高。缺点：一个线程在使用内核服务时被阻塞，整个进程都会被阻塞；多个线程不能并行地运行在多处理机上。2）一对一模型。将每个用户级线程映射到一个内核级线程。优点：当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强。缺点：每创建一个用户级线程都需要创建一个内核级线程与其对应，这样创建线程的开销比较大，会影响到应用程序的性能。3）多对多模型。将n个用户级线程映射到m个内核级线程上，要求m≤n。特点：多对多模型是多对一模型和一对一模型的折中，既克服了多对一模型并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程而开销太大的缺点。此外，还拥有多对一模型和一对一模型各自的优点，可谓集两者之所长。
Q：为什么要把用户线程和内核线程结合在一起啊？有什么意义呢？
A：用户线程就是用户自己创建的线程调度程序，但是这样的用户线程实际上不能单独运行，用户线程运行的唯一方法就是告诉内核线程，使其帮忙执行用户线程中包含的代码；
简单来说用户线程根本就不是线程，仅仅算得上是用户程序中的一堆数据，内核线程才是真正的线程，所以要使得用户线程能够运行只能是将其与内核线程映射关联；
回顾用户级线程的切换主要分为三个步骤：
补充知识点：
内核栈（栈是用来在函数跳转时保存返回地址等重要信息以备将来返回的）中记录了当前用户栈的位置和当前用户程序执行的位置，在内核级线程切换的时候利用这两个信息完成PC指针的切换以及用户栈的切换；
内核级线程的TCB存储在操作系统的内核中，因此完成TCB切换的程序应该执行在操作系统的内核中，因此内核级线程的切换应该从进入内核开始，那么我们就必须先介绍中断，因为中断会导致用户态到内核态的切换，那么首先我们就先来弄明白发生中断过后会有什么情况（几乎所有的外部中断都会引起下面的动作）：
中断指令执行时，会找到当前进程的内核栈，然后将用户态执行的一些重要信息压到内核栈中；
简单来说内核级线程切换仍然完成三个工作：切换TCB、切换栈和切换PC指针，但是这些切换动作要分散在中断入口、中断处理、线程调度、上下文切换以及中断返回等多个地方。不像用户级线程切换那样所有切换动作都在一个Yeild()函数中。因此内核级的切换过程就复杂得多，为清晰起见，将内核级线程的切换过程归纳整理为下图所示的五个阶段：
Q：很多人可能会疑惑不是说内核级线程之间的切换吗？怎么看图好像是用户线程1->内核线程1->内核线程2->用户线程2这样的一个切换顺序
A：这里因为书上有些概念没讲明白，所以我们额外讲一下
内核级线程由内核直接创建并管理
前面已经介绍过内核级线程的切换主要由四个具体的切换构成：切换TCB，切换内核栈，切换用户栈，用户程序PC指针切换；
相应地创建内核级线程的关键在于初始化TCB、内核栈以及用户栈：
前面已经介绍过，多进程视图是操作系统的核心视图，多进程视图的核心就是创建进程的系统调用fork；
fork的核心是通过复制父进程来创建子进程，操作系统中最基本的两个父进程是0号和1号进程（在操作系统初始化时由系统建立），系统中所有的进程都是从0号进程和1号进程继承而来；
fork是一个只能工作在用户态应用程序中的系统调用，创建0号进程不能使用fork，需要手动设置进程信息（PCB、内核栈、用户栈以及用户程序等）
调度的基本概念：当有一堆任务需要处理，但是由于资源有限，这些任务不能同时处理（此处是真正意义上的同时），于是就需要确定某种规则来决定处理这些任务的顺序，这就是调度研究的问题；
线程切换中我们并没有解决这样一个问题——如何在一系列可供选择的就绪线程中选择下一个线程（其目的是将CPU分配给这个线程）是良好的，这就引出本节的主题，CPU调度；
CPU调度简单来说就是在就绪线程/进程队列中选择一个合适的线程/进程，再通过切换机制将CPU资源分配给选择的线程/进程；（说一下，这里本质上应该是进程调度，只是哈工大教材根本没有提及三级调度的概念）
因为根据操作系统是否支持线程，CPU调度的基本单位分为线程和进程，所以这里我们将线程和进程统称为任务；
这里我们以PC机的通用操作系统作为基本对象分析（注意不同的对象其调度策略的目的和设计、实现原则等可能不同），需要考虑如下准则：
我们举个例子说明CPU调度的重要性，PC机上交互任务和非交互任务同时存在：
这两个目标之间存在矛盾，不可能同时优化，因此能够有效的折中任务调度策略成为CPU调度分析的核心问题；
一个作业从提交开始到完成，一般需要经历如下三级调度：
作业调度从外存的后备队列中选择一批作业进入内存，为它们建立进程，这些进程被送入就绪队列，进程调度从就绪队列中选出一个进程，并把其状态改为运行态，把CPU分配给它。中级调度是为了提高内存的利用率，系统将那些暂时不能运行的进程挂起来。当内存空间宽松时，通过中级调度选择具备运行条件的进程，将其唤醒；
这里我们再辨析两个概念：进程调度和进程切换
调度了新的就绪进程之后才会进行进程间的切换，理论上这两个事件顺序不能颠倒（事实上也确实不会颠倒），进程切换（也就是我们上面刚开始所说的切换机制）主要完成：
（有没有发现很类似之前介绍过的线程切换？因为线程切换是进程切换的核心，但是对于进程切换，王道和哈工大似乎都没怎么细讲）
进程调度方式简单来说就是当有优先级更高的进程进入就绪队列的时候应该如何分配处理机，通常有两种进程调度方式：
操作系统中有多种调度算法，有些调度算法适用于作业调度，有的适用于进程调度，有的两者都适用，下面我们介绍的都是能用于进程调度的一些调度算法；
根据FCFS的基本思想我们可以得到其算法实例如下
操作系统中既有交互任务，也有非交互任务，如何组合RR和SRTF来处理两种任务都存在的情况呢？
最简单的思想就是引入两个队列：
通常让前台队列具有更高的优先级，即假如前台队列中存在就绪任务则采用RR调度处理这个队列中的任务（此时就只能让后台队列中的队列慢慢等待）；
第二个问题是操作系统如何区分前台任务和后台任务——多级队列中的任务类型并不是在任务创建时确定，应该根据任务在执行过程的具体表现来动态调整（编译过程看起来是后台任务，但是Ctrl+C中断编译术语用户交互），而这个动态调整实际上就是“反馈”的含义；
因此动态调整就成为了多级反馈队列调度的核心：
多级反馈队列调度算法实现思想如下：
除了上面介绍的调度算法以外，我们这里额外补充一些有特点的调度算法；
下面我们直接给出一个例子理解
多个进程在并发执行的过程中并不一定完全独立，会相互依赖，本章就是解决在操作系统中如何实现这些依赖关系（比如多项式1+2*3，必须保证乘法先于加法执行才能得到正确结果）；
进程同步的基本结构：
上述流程我们称为睡眠和唤醒，据此可以给出进程同步的描述性定义：进程同步就是通过对进程睡眠和唤醒的控制使得多个进程步调一致，合理有序地向前推进；
进程互斥和进程同步不是类似的概念，进程互斥是指当一个进程访问某临界资源时另一个想要访问该临界资源的进程必须等待直到访问临界资源的进程释放；
系统中的资源主要有两种共享方式：
对临界资源的访问必须互斥地进行，可以在逻辑上分为如下四部分
do{entrysection; //进入区：负责检查是否可以进入临界区，如果可以进入则应上锁，以阻止其他进程同时进入临界区criticalsection; //临界区：访问临界资源的那段代码exitsection; //退出区：负责解除正在访问临界资源的标志“解锁”remaindersection; //剩余区：做其他处理}while(true)//临界区是进程中访问临界资源的代码段；//进入区和退出区是负责实现互斥的代码段；进程互斥需要遵循以下原则：
为什么要介绍进程互斥？因为进程互斥是实现进程同步的一种方式，进程同步是一种处理异步性的方式，基于互斥实现对资源的有序访问；
我们已经建立了基于睡眠和唤醒的进程同步轮廓，接下来就是实现这个轮廓，实现的核心在于进程间如何实现睡眠和唤醒（有些地方也称为等待和通知）——进程间通过信号实现等待和通知；
我们以前面提到过的“生产者-消费者”模型分析如何利用信号解决进程同步问题：
Q：信号量和条件变量(ConditionVariable)的关系是什么？
其实我们完全没必要将信号量和条件变量的区别分的很清，因为在某个角度来说互斥变量和条件变量属于信号量的特殊情况，即条件变量+互斥变量=信号量；
再换一个通俗易懂的说法，条件变量就是我们这里介绍的信号，因为语义信息较少所以不适用于多变的调度情况；
生产者-消费者模型是多个进程共享一个缓存区产生的相互依赖的问题，生产者进程往共享缓存区写入内存，消费者进程从共享缓存区取出内容：
要解决生产者-消费者问题，首先需要找到两个进程之间需要同步的地方：对于生产者进程，需要停下来等待的地方是在缓存区满的时候，在此处插入等待信号的动作；
接下来要找到发送信号的地方（让生产者进程继续前进的地方）：对于生产者进程，消费者进程制造出一个空闲缓存区时需要唤醒生产者进程，在此处发出生产者进程等待的信号；
消费者进程的睡眠和唤醒与之类似，此处不再赘述；
上述解决方案中，定义了两个信号：
通过if(counter==BUFFER_SIZE)来判断counter(当前缓存区中内容单元的个数)是否等于BUFFER_SIZE，如果相等说明缓存区已满生产者进程会令自己进入阻塞态并等待信号empty；
当消费者进程消耗掉一个内容单元后消费者发现counter变成BUFFER_SIZE-1，那么就会给生产者发送empty信号并唤醒生产者wake_up(empty)；（消费者进程与之类似不再赘述）
上述依赖变量counter进行判断是否需要同步存在一个问题，因为counter表达出来的语义不够因而无法应对多变的调度情况；
当缓存区满的时候，此时进来两个生产者进程P1和P2以及一个消费者进程C；此时的counter==BUFFER_SIZE，当C消耗掉一个内容单元会给P1发送empty唤醒P1，此时counter==BUFFER_SIZE-1;C再次消耗掉一个内容单元后此时counter==BUFFER_SIZE-2，现在P2就不能被唤醒了；引入信号量的概念：信号量就是在信号上关联一个表达“量”的整数（这个量可以自定义，如阻塞在empty上的进程个数）：
（1）信号量就是一个整型变量，用来记录和进程同步有关的重要信息；
（2）能让进程阻塞睡眠在这个信号量上；
（3）需要同步的进程通过操作（加1和减1）信号量实现进程的阻塞和唤醒，即进程间的同步；
因此，信号量就是一个数据对象以及操作这个数据对象的两个操作：
我们还是用前面的例子来讲解
如果P1阻塞，则需要等待的empty=1，如果P2阻塞，则需要等待的empty=1+1=2，C执行一次发现empty==1这意味着还有一个进程在阻塞，C再次执行一次发现empty==0；综上，对于empty这个信号来说，当它为正数或者0的时候，表示现在和该信号量对应的资源还有empty个；当它为负数的时候表示亏欠|empty|个资源（这个地方不要纠结，本质上就是简单的多余资源和少资源；总而言之信号量的定义是人为的，只要给出一个合理的定义就可以，不要太纠结书上的语法；综上，我们得出信号量的含义：
信号量的数值非常重要，只有信号量的数值与信号量对应的语义信息保持一致才能正确地使用信号量来决定进程的同步；
在多个进程“共同”修改信号量时需要对信号量进行保护，不能随意修改：每个进程对信号量的修改要么一点也不做，要么全部做完，中途不能被打断（每个进程对信号量的修改必须是一个原子操作）；
下图中P1和P2一次最多只能有一个进程进入执行某一段代码，这段代码就是进程的临界区；
临界区并非是信号量的专有概念，我们将一次仅允许一个进程使用的资源称为临界资源，对临界资源的访问必须互斥的进行，将临界资源的访问过程分为下面4部分：
do{entrysection; //进入区criticalsection; //临界区exitsection; //退出区remaindersection; //剩余区}while(true)有了临界区的概念以后，信号量的保护机制就是让进程中修改信号量的代码成为临界区代码（“进入区”->“临界区”修改信号量->“退出区”）；
（在王道课程中这里也被称为进程互斥的软件/硬件实现）
轮换法也称为单标志法，指的是两个进程在访问完临界区之后会把使用临界区的权限转交给另一个进程——即每个进程进入临界区的权限只能被另一个进程赋予；
任何时候只有一个进程有权利进入临界区，只有这个进程退出临界区后才能轮换到其他进程，保证了临界区的互斥性；
turn变量在任意时刻只能取值为0或1，对P0而言turn=0，对P1而言turn=1时表示允许进入临界区；
缺点：假如P1一直不访问临界区，则turn值永远都是1不变，抑或是P1进程直接退出，这些都会导致P0永远无法进入临界区执行；
实现临界区需要考虑如下（其实就是前面已经介绍过的进程互斥需要遵循的原则）：
标记法也被称为双标志检查法，算法思想是设置一个布尔型数组flag[]，数组中的各个元素用于标记各个进程想要进入临界区的意愿；每个进程在进入临界区之前先检查当前有没有别的进程想要进入临界区，如果没有则将自身对应的标志flag[i]修改为true之后访问临界区；
标记法在这里被分为双标志后检查法（哈工大教程介绍）和双标志前检查法（王道教程介绍）；
首先将整个flag[]数组初始化为全0，若进程P0想进入临界区就做一个标记flag[0]=ture，那么当进程P0在访问临界区的时候P1会一直在while循环等待，直到P0进程明确表示自己不再需要使用临界区；
我们分析标记法是否可以满足上述临界区的实现要求：
我们简单说一下双标志检查法的缺陷，假如我们将进入区的两行代码顺序交换，然后进行分析；
初始时flag[1]为0所以进程P0可以顺利跳出while循环，此时发生进程切换，进程P1此时因为flag[0]也是0所以也成功跳出while循环，接着这两个进程就修改标志并进入临界区...这就导致P0和P1同时访问临界区，不符合互斥进入的准则！
原因之一是因为P0进程和P1进程是可以并发执行的，进程并发执行很可能导致异步性；原因之二是因为在进入区的“检查”和“上锁”两个步骤并不是一气呵成的，即很可能在“检查”之后发生进程切换然后再“上锁”
标记法存在有空不能进的情况，是因为两个进程都要进入临界区而相互锁住；Peterson算法简单来说就是将两个相互竞争的进程化解为，主动让对方先使用临界区，类似“孔融让梨”
Peterson算法是一种综合性的算法：
Peterson算法满足上述三个原则，但是仍未遵循让权等待（即使进程P0不能进入临界区，但是会一直占用CPU使其一直执行while循环，这就是所谓的“忙等待”）
Peterson算法只能处理两个进程的临界区，涉及多进程时就需要Lamport面包店算法；
面包店（临界区）一次只能接待一个客户（进程），按照次序给每个客户分发一个号码，顾客按照其号码由小到大的次序进行购买，完成购买的顾客号码置零（这意味着如果该顾客需要再次购买需要重新取号排队）；
当软件实现变得复杂以后，可以使用硬件来简化操作、提高效率；
禁止中断是一种实现临界区保护的方法（禁止中断意味着禁止进入内核，那么就无法调用schedule函数进而无法实现进程切换，则CPU只会执行一个进程的临界区代码，那么就不可能发生两个进程同时访问临界区的情况）
However，这种关中断操作对于多CPU计算机的其他CPU没有任何影响（即中断屏蔽法不适用于多处理机），同时该方法只适用于操作系统内核进程而不适用于用户进程（开/关中断指令只能运行在内核态，用户随意使用会非常危险）；
TSL指令是用硬件实现的，执行过程中不允许被中断，只能一气呵成；
我们联想之前的消费者-生产者模型——这就引出了保护临界区的互斥信号量，该信号量只会取0、1两个值，通常被命名为lock：
我们可以看到，该信号量的P、V操作非常简单所以可以使用硬件实现，而实际上在计算机中的确存在这样一条指令，被称为TSL，这条指令有一个操作数lock，是存放一个布尔变量的内存地址，如果该内存中的变量为false，该指令会返回false，并且将内存中的变量置为true；如果在内存中的变量为true，则返回true；
假如我们使用代码模拟该硬件原子指令的实现，可以表示如下（时刻记住这只是一个模拟逻辑，实际上这一系列的语义都是由硬件来完成的且不可以被中断）
boolTestAndSet(bool*lock){//lock共享变量表示当前临界区是否被加锁，ture表示已加锁，flase表示未加锁boolold;old=*lock;//old用来存放lock原来的值*lock=true;//将lock设置为turereturnold;//返回lock原来的值}//进入区代码段while(TestAndSet(&lock));//上锁并检查//临界区代码段...lock=false;//解锁//剩余区代码段...TSL的优点是将“上锁”和“检查”两个操作用硬件的方式变成了一气呵成的原子操作；缺点是不满足“让权等待”的原则，即暂时无法进入临界区的进程会占用CPU并循环执行TSL指令导致“忙等”；
也称为Exchange指令或XCHG指令，swap指令是用硬件实现的，执行过程中不允许被中断；
逻辑上来看Swap和TSL并无太大区别，都是先记录下此时临界区是否已经被上锁（记录在old变量上），再将上锁标记lock设置为true，最后检查old，如果old为false则说明之前没有别的进程对临界区上锁，则可跳出循环，进入临界区；
因为这两个指令的逻辑类似，所以优缺点几乎也是一样的，这里就不再赘述；
前面我们讨论了临界区的四种软件实现方法以及三种硬件实现方法，但是它们或多都有一些缺陷（比如所有的方案都不能实现“让权等待”），一位科学家提出了一种卓有成效的实现进程互斥、同步的方法，这就是我们要介绍的信号量机制；
（前面小结中的信号量只是介绍了信号量最基本的使用，可以说就只是引出了信号量这个概念而已，本节我们将深入研究怎么实现信号量以及如何真正的使用信号量）
信号量机制：临界区保护了信号量P、V操作的原子性进而保证信号量数值的语义正确性（根据信号量数值表达的语义可以正确地控制进程的阻塞和唤醒，也就是实现进程同步），因此只要操作系统给上层用户提供了信号量定义接口以及P、V原语操作后，用户就可以直接调用这些接口方便地完成进程同步以及进程互斥；
举例来说，POSIX标准针对信号量定义了如下四个基本系统调用：
（简单理解信号量机制就是将前面的临界区和信号量概念整合在一起，共同实现进程同步和进程互斥）
关于P、V操作究竟是什么，怎么一来就抛出这样的概念不加解释？
信号量的P操作实质就是wait原语操作，而之前我们写的一系列wait函数实际上都是在模拟wait原语的动作（signal类似），所以其实我们是应当早就熟悉P、V操作；
wait用法：
wait(num)，num是目标参数，wait的作用是使其（信息量）减一。如果信息量>=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列；
signal用法：
signal(num)，num是目标参数，signal的作用是使其（信息量）加一。如果信息量>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程；
P操作
加锁对应的是P将信号量减1，并阻塞其他线程；(注意注意注意，P操作就是wait原语，它们两个的描述虽然不太一样但是并不矛盾！！！它俩就是同一个概念！！！)
V操作
解锁对应的是V将信号量加1，并唤醒某一个线程；
定义：用一个整数型的变量作为信号量，用来表示系统中某种资源的数量；
信号量与普通整数变量的区别在于对信号量的操作只有初始化、P操作以及V操作，我们这里用计算机系统中存在一台打印机举例说明整型信号量的简单使用；
intS=1；//初始化整型信号量s，表示当前系统中可用的打印机资源数voidwait（intS）{//wait原语，相当于"进入区" while（S<=0）；//如果资源数不够，就一直循环等待 S=S-1；//如果资源数够，则占用一个资源}voidsignal（intS）{//signal原语，相当于“退出区"S =S+1；//使用完资源后，在退出区释放资源}//进程P0：...wait（S）；//进入区，申请资源//使用打印机资源...//临界区，访问资源signal（S）；//退出区，释放资源...整型信号量存在的问题是不满足“让权等待”原则，会发生“忙等待”；
定义：使用记录型数据结构表示的信号量
本节将介绍如何利用信号量机制实现进程互斥、同步以及进程的前驱关系；
1.分析并发进程的关键活动，划定临界区（如：对临界资源打印机的访问就应放在临界区）；
2.设置互斥信号量mutex，初值为1；
3.在临界区之前执行P（mutex）；
4.在临界区之后执行V（mutex）；
/*信号量机制实现互斥*/semaphoremutex=1；//初始化信号量P1（）{... P（mutex）；//使用临界资源前需要加锁 临界区代码段... V（mutex）；//使用临界资源后需要解锁 ...}P2（）{... P（mutex）；//使用临界资源前需要加锁 临界区代码段... V（mutex）；//使用临界资源后需要解锁 ...}注意：对不同的临界资源需要设置不同的互斥信号量；
相信很多人或多或少在学习操作系统的时候听说过类似锁、条件变量等名词，但国内大部分教科书好像都对这些概念视而不见或仅仅只是浅谈几句（甚至有的教材默认我们已经了解这些概念），让人很是疑惑，所以这里我们将锁、条件变量以及信号量三者之间究竟有什么关系以及三者的详细概念做一个整理；
并发编程的最基本的问题：我们希望原子式执行一系列指令，但由于单处理器上的中断导致其难以实现；锁就是专门用于解决这一问题的，在源代码中加锁，放在临界区的周围以保证临界区代码能够像单条原子指令一样执行；
简单来说，锁就是一个变量，这个锁变量保存了锁在某一时刻的状态；它要么是可用的（available，或unlocked，或free），表示没有线程持有锁，要么是被占用的（acquired，或locked，或held），表示有一个线程持有锁，正处于临界区。我们也可以保存其他的信息，比如持有锁的线程，或请求获取锁的线程队列，但这些信息会隐藏起来，锁的使用者不会发现。
锁的操作主要有lock()和unlock()：
POSIX库将锁称为互斥量（mutex），因为它被用来提供线程之间的互斥。即当一个线程在临界区，它能够阻止其他线程进入直到本线程离开临界区。
当然我们可以选择使用不同的锁来保护不同的变量或数据结构，这样可以增加并发；
首先我们需要明确，如何评价一种锁的实现效果，我们设立了如下标准：
如何实现锁？实际上我们已经在临界区的软件实现和临界区的硬件实现介绍过了，这里就不再赘述，我们来介绍一些术语：
自旋锁
这是一种最简单的锁，一直自旋，利用CPU等待直到锁可用；
两阶段锁
但是，如果第一个自旋阶段没有获得锁，第二阶段调用者会睡眠，直到锁可用。Linux锁就是这种锁，不过只自旋一次；更常见的方式是在循环中自旋固定的次数，然后使用futex睡眠。
两阶段锁是一个杂合（hybrid）方案的例子，即结合两种好想法得到更好的想法。当然，硬件环境、线程数、其他负载等这些因素，都会影响锁的效果。
上文介绍的锁并不是并发程序设计所需要的唯一原语；在很多情况下线程需要检查某一条件满足之后才会继续运行，因此引出了条件变量的概念；
条件变量(conditionvariable)是利用线程间共享的全局变量进行同步的一种机制，主要包括两个动作：一个线程等待某个条件为真，而将自己挂起；另一个线程使的条件成立，并通知等待的线程继续。为了防止竞争，条件变量的使用总是和一个互斥锁结合在一起。
条件变量是一个显式队列，当某些执行条件不满足时，线程可以将自己加入队列等待该条件；而另外某些线程改变了执行条件之后就可以唤醒一个或多个等待线程；（实际上信号量机制中有非常类似条件变量的概念，这也体现出三者之间的关系）
提示：对条件变量使用while而不是if（原因在《操作系统导论》P260）
Q：为什么有了互斥锁和条件变量还需要提供信号量？
A：在Posix.1基本原理一文声称，有了互斥锁和条件变量还提供信号量的原因是：“本标准提供信号量的而主要目的是提供一种进程间同步的方式；这些进程可能共享也可能不共享内存区。互斥锁和条件变量是作为线程间的同步机制说明的；这些线程总是共享(某个)内存区。这两者都是已广泛使用了多年的同步方式。每组原语都特别适合于特定的问题”。尽管信号量的意图在于进程间同步，互斥锁和条件变量的意图在于线程间同步，但是信号量也可用于线程间，互斥锁和条件变量也可用于进程间。应当根据实际的情况进行决定。信号量最有用的场景是用以指明可用资源的数量。
信号量作为与同步有关的所有工作的唯一原语，可以使用信号量代替锁和条件变量；
使用信号量实现锁非常简单，因为锁只有两个状态（持有和未持有），所以信号量的这种用法也被称为二值信号量；
当然我们完全可以自己实现一个信号量，这只需要一把锁、一个条件变量和一个状态变量来记录信号的值；
而使用信号量实现条件变量可能不是一件容易的事，这里我们不再赘述；
结论：信号量是编写并发程序的强大而灵活的原语，因为其简单实用，所以很多时候可以只用信号量而不需要使用锁和条件变量；
前面我们介绍线程同步的时候简单介绍过一些同步问题，这里我们对经典的同步问题及其规范的解答方法做一个总结和整理；
问题描述：
问题分析：
1.关系分析
互斥关系：
同步关系：
2.整理思路
一共需要三对P、V操作以对应三个不同的信号量：
3.设置信号量
semaphoremutex=1；//互斥信号量，实现对缓冲区的互斥访问semaphoreempty=n；//同步信号量，表示空闲缓冲区的数量semaphorefull=0；//同步信号量，表示产品的数量，也即非空缓冲区的数量具体代码实现：(while表示生产者进程不断的生产产品，消费者不断的消费产品)
注意：实现互斥的P操作一定要在实现同步的P操作之后，但是因为V操作不会导致进程阻塞，所以V操作的顺序可以交换
注意这里的“多”并不是指多个生产者、消费者，而是指生产者生产的产品的类别不同；
具体代码实现：
本质上这题也属于“生产者-消费者”问题，更详细的说应该是“可生产多种产品的单生产者-多消费者”；
代码实现：
潜在的问题：只要有读进程还在读，写进程就要一直阻塞等待，可能“饿死”，因此，这种算法中，读进程是优先的；
解决方法很简单，只需要额外加一个互斥信号量w即可
我们很容易想到使用如下的代码解决方案，但这将导致死锁的发生
如何防止死锁的发生呢？主要有如下解决方案：
在管程引入之前，实现同步机制和互斥机制一般都是使用信号量机制，但是信号量机制存在的问题就是编写程序困难、易出错；
管程是一种特殊的软件模块，由这些部分组成：1.局部于管程的共享数据结构说明；2.对该数据结构进行操作的一组过程(函数)；3.对局部于管程的共享数据设置初始值的语句；4.管程有一个名字(其实这里可以看出管程类似于面向对象语言中的类)；
管程的基本特征：1.局部于管程的数据只能被局部于管程的过程所访问；2.一个进程只有通过调用管程内的过程才能进入管程访问共享数据；3.每次仅充许一个进程在管程内执行某个内部过程；
死锁现象简单来说就是进程P0在等待P1的时候，P1也在等待P0；
死锁现象在多进程并发和同步的计算机系统中是必然会产生且不可预见的，故必须依靠操作系统提供的处理机制保证进程的有序推进；
死锁的定义：在并发环境下，各进程因竞争资源而造成的一种互相等待对方手里的资源，导致各进程都阻塞，都无法向前推进的现象，就是“死锁”。发生死锁后若无外力干涉，这些进程都将无法向前推进；
接下来我们辨析三个比较容易让人混淆的三个概念：
主要总结了如下三种情况会导致发生死锁：
1.对系统资源的竞争。各进程对不可剥夺的资源（如打印机）的竞争可能引起死锁，对可剥夺的资源（CPU）的竞争是不会引起死锁的；2.进程推进顺序非法。请求和释放资源的顺序不当，也同样会导致死锁。例如，并发执行的进程P1、P2分别申请并占有了资源R1、R2，之后进程P1又紧接着申请资源R2，而进程P2又申请资源R1，两者会因为申请的资源被对方占有而阻塞，从而发生死锁；
3.信号量的使用不当也会造成死锁。如生产者-消费者问题中，如果实现互斥的P操作在实现同步的P操作之前，就有可能导致死锁。（可以把互斥信号量、同步信号量也看做是一种抽象的系统资源）
结论：总而言之，对不可剥夺资源的不合理分配，可能导致死锁；
死锁的处理策略主要有如下三种：
1.预防死锁。破坏死锁产生的四个必要条件中的一个或几个；2.避免死锁。用某种方法防止系统进入不安全状态，从而避免死锁（银行家算法）；3.死锁的检测和解除。允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁；
这也是我们之后会详细介绍的内容；
死锁发生的四个基本条件（必要条件）如下，只要其中任意一个条件不成立，死锁就不会发生：
注意！发生死锁时一定有循环等待，但是发生循环等待时未必死锁（循环等待是死锁的必要不充分条件）
只需要破坏这四个必要条件中的某个条件，就不会形成死锁，这就是死锁预防的基本思想；
但是“互斥”和“不可剥夺”这两个条件在通常条件下是资源自身特性或程序本身决定，无法直接破坏，所以死锁预防主要是破坏“请求与保持”和“循环等待”两个条件：
这里简单补充一下为什么在实际应用中我们不会选择破坏互斥条件和不可剥夺这两个条件实现死锁预防；
关于破坏互斥条件
基本思想：如果把只能互斥使用的资源改造为允许共享使用，则系统不会进入死锁状态；
实际上是可以有这样的技术的，比如：SPOOLing技术。操作系统可以采用SPOOLing技术把独占设备在逻辑上改造成共享设备。比如，用SPOOLing技术将打印机改造为共享设备；
该策略的缺点：并不是所有的资源都可以改造成可共享使用的资源。并且为了系统安全，很多地方还必须保护这种互斥性。因此，很多时候都无法破坏互斥条件。
关于破坏不可剥夺条件
方案一：当某个进程请求新的资源得不到满足时，它必须立即释放保持的所有资源，待以后需要时再重新申请。也就是说，即使某些资源尚未使用完，也需要主动释放，从而破坏了不可剥夺条件。
方案二：当某个进程需要的资源被其他进程所占有的时候，可以由操作系统协助，将想要的资源强行剥夺。这种方式一般需要考虑各进程的优先级（比如：剥夺调度方式，就是将处理机资源强行剥夺给优先级更高的进程使用）
该策略的缺点：1.实现起来比较复杂。2.释放已获得的资源可能造成前一阶段工作的失效。因此这种方法一般只适用于易保存和恢复状态的资源，如CPU。
3.反复地申请和释放资源会增加系统开销，降低系统吞吐量。
4.若采用方案一，意味着只要暂时得不到某个资源，之前获得的那些资源就都需要放弃，以后再重新申请。如果一直发生这样的情况，就会导致进程饥饿。
死锁预防固然是一种解决死锁的方式，但是它需要预先计算资源且预留资源，这样的设计是及其不合理的，所以我们需要想出新的解决办法，这就是我们接下来会介绍的死锁避免；
死锁避免的基本思想：每次资源申请都要判断是否有出现死锁的危险，如果有危险就拒绝此次申请；
（1）银行是操作系统，资金就是资源，客户相当于要申请资源的进程；
（2）客户能最终偿还贷款需要银行满足客户的全部贷款请求，相当于操作系统满足进程的所有资源请求，即让进程执行完成，不造成死锁；
（3）银行判断贷款请求是否应该被批准相当于操作系统判断进程资源请求是否可以被允许，银行没有损失相当于操作系统没有死锁；
（4）操作系统判断这个资源请求是否安全的算法就是银行判断此次贷款是否安全的算法，因此被称为银行家算法；
银行家算法的核心在于确保“系统安全”，也就是找到一个安全序列，使得对所有进程的资源请求都存在一种调度方案令其满足，从而能顺利执行完成；
当然银行家算法一开始只是为了解决银行系统的放贷问题，之后才被用于操作系统避免死锁，而银行系统只有一种类型的资源--money，但是在计算机系统中会存在多种多样的资源，所以思考如何将算法拓展为多种资源的情况；
最简单思想就是将单维的数字拓展为多维的向量，比如：系统中有5个进程P0-P4，3种资源R0-R2，初始数量为（10，5，7），则某一时刻的情况可表示如下：
我们下面直接给出一个例子帮助理解(考题就是这种形式)
当然上述都只是理论上的分析，我们下面简单介绍一下如何编程实现银行家算法
本节最核心的思想：系统处于不安全状态未必死锁，但死锁时一定处于不安全状态，系统处于安全状态一定不会死锁(这个点一定理解，不要觉得说不按照路线来就会导致死锁什么的，只要是安全状态不管怎么作都不可能死锁！！！)；
前面介绍的两种方式都是通过资源使用的限制保证不出现死锁，这样的限制会造成资源使用效率的降低；那么我们就直接放开资源的使用，这意味着一定会造成死锁（因为相当于预防和避免直接跳过），此时我们的死锁检测/恢复就派上用场了；
死锁的检测
为了能对系统是否已发生了死锁进行检测，必须：
针对第一点，我们使用一种被称为资源分配图的数据结构
针对第二点，我们考虑如何基于上述数据结构来分析系统是否处于死锁状态：
如果按上述过程分析，最终能消除所有边，就称这个资源分配图是可完全简化的，此时一定没有发生死锁（相当于能找到一个安全序列）；
如果最终不能消除所有边，那么此时就是发生了死锁；最终还连着边的那些进程就是处于死锁状态的进程；
总结死锁检测算法：依次消除与不阻塞进程相连的边，直到无边可消(注：所谓不阻塞进程是指其申请的资源数还足够的进程)
死锁的解除
注意这里的死锁并不是指的系统中所有的进程都是死锁状态才进行处理，而是指使用死锁检测算法化简资源分配图之后仍然还连接有边的进程就是死锁进程，需要对这些进程进行处理；
接下来就需要考虑对哪个死锁进程“动手”使其做出一定牺牲，可以从如下角度考虑
“进程管理和内存管理两部分构成操作系统的真正内核”
内存管理相对复杂，涉及到硬件和软件，从微机原理到应用程序到内核。
比如，硬件上的cache，CPU如何去寻址内存，页表，DMA，IOMMU；软件上，要知道底层怎么分配内存，怎么管理内存，应用程序怎么申请内存。
本章的主线就是程序正确载入内存和指令正确读写内存：
重定位保证了指令正确读写内存，以致读写指令能够正确执行；重定位是由操作系统安排执行的；
我们知道，计算机工作的基本过程是：CPU不断重复“取指-执行”的过程，而取指和执行指令这两个过程都涉及内存；
源文件编译形成可执行文件的时候（准确来说应该是链接后形成可执行文件），使用的地址都是从0开始的相对地址，而当程序真正被载入物理内存的时候可能使用任意一段空闲物理地址，此时如果想要保证程序的正确执行就需要做重定位（也就是将程序中的逻辑地址对应到实际使用的物理内存地址）
重定位主要分为如下几种：
(1)编译时重定位：这样产生的可执行文件的地址就是实际地址而不是相对地址，显然这种方法不能用于任务不断“启动-退出”的通用计算机系统中；
(2)载入时重定位：在程序载入的过程中根据载入的物理内存地址区域来修改程序中的逻辑地址；
因此诞生了另一种重定位的方法
(3)运行时重定位：在内存中存放的指令一直都是“call40”，只有在指令执行的时候才将指令的逻辑地址转换为物理地址；
具体实现：程序在载入内存的时候，记录下这段内存区域的基址（将其放在某个约定的寄存器中），执行每一条指令都会将指令中的逻辑地址加上基址以后才会放在地址总线上，计算机中有这样专门的硬件MMU，每条指令运行时进行的从逻辑地址到物理地址换算的过程被称为地址转换；
现在回到多进程的视图下，MMU进行重定位的CPU寄存器只能有一个，所以每个进程的重定位基址都需要放在PCB中供需要时使用；
进程切换的两个部分：指令执行序列的切换（实际就是PC指针的切换）和地址空间的切换（实际上就是重定位基址寄存器的切换）到此阐述完毕；
2022/9/2619:01分段给我的感觉不像是操作系统做的事，而是CPU自己完成了分段，操作系统不得不接受这个事实，也就是与硬件上的内存分段机制对应（毕竟操作系统是运行在硬件之上的，这就类似于在操作系统之下写的汇编程序也得遵守CPU的寻址方式）；
2022/9/2620:17跟你说了看太多书不消化是会出问题的（你上面那个理解是有错误的），实际上在硬件层面根本就没有分段这个概念，这个概念是将程序载入内存区域的一种方式，分段是程序层面的概念；（虽然这门课叫做操作系统，但这并不意味着书中所有的概念都是操作系统的子集）
上面我们已经清楚了指令如何正确读写内存，现在我们来介绍程序载入内存的方式；
实际上段这个概念源自于CPU管理内存（分段是CPU管理内存的一种方式），这也是我们接下来会介绍的；
既然程序已经被分段，那么在载入内存的时候也不应该作为一个整体载入——程序中多个段分别载入内存，前面我们提高如果程序整体载入内存需要记录基址，那么这里需要记录每个段的基址，多个基址形成段表
使用了分段机制以后的，程序中的逻辑地址会变成“段号：段内偏移”这种基本格式(注意是逻辑地址不是物理地址！！物理地址还是一个整型数值)；
分段机制下的地址转换核心就是查找段表，我们给出下面一个地址转换过程图
在介绍分页之前先介绍一下内存分区，前面介绍了程序以分段的方式载入内存，但能够载入的前提是内存中拥有这样一段空闲内存，因此我们需要分割内存；
从空闲内存区域中分割出一个分区来满足段请求，关键是记录和维护“内存空闲区域”信息，具体的内存分区的算法我们这里就不介绍，感兴趣自行Google；
因为不合理的内存分区，将会导致尽管总空闲的内存很大，但是无法满足某个大小的内存请求，这就是内存碎片导致的，解决内存碎片的方法主要有：
这就是分页机制的基本思想，上述片就是内存页；
Q：有些人可能乐了，你刚才讲的分段机制难道不算内存分区？
A：额，严格意义上来说分段机制甚至都算不上内存分区，它只是方便程序员编程使用而提出的概念（这么说吧，分页是系统管理的需要，对用户透明，分段是为了满足用户编程需要）；
分段和分页根本就不是一个层面上的概念，一个是内存硬件的层面，一个是程序员编程的层面，不要将两者混为一谈；
Q：分页机制和分段机制有什么不同？为什么虚拟内存中又把页式虚拟存储器和段式虚拟存储器以及段页式虚拟存储器相提并论？
A：分段和分页相似之处在于两者都不要求作业连续存放，但两者在概念上是完全不同的：
分页能有效提高内存的利用率，分段能反映程序的逻辑结构，便于段的共享和保护，因此诞生了一种新的思想——将分页和分段存储方式结合，形成段页式存储管理方式；
至于第二个问题，虚拟存储器为什么将分页和分段放在一个高度谈，这就是我们之后才讨论的问题了；
分页机制首先将物理内存分割成大小相等的页框，然后再将请求放入物理内存的数据（比如代码段）也分割成同样大小的页，最后将所有页都映射到页框上，完成物理内存页框的使用；
上述过程是内存使用的第一步——程序载入，接下来解决重定位的问题；
分页机制下的地址转换过程如下所示
因为页是信息的最小的物理单位，所以为了避免内存空间的浪费，通常需要将页的尺寸设置的合理，而页的尺寸越小，页表就越大，这将引出多级页表和快表；
页表由页表项组成，每个页表项记录逻辑页放在了哪个物理页框；
总结一下现在的问题：设计页表，使其既不存储无效页表项，又能保证页表中的逻辑页号连续；
多级页表的思想与书本的主目录非常相似
上图中的节目录对应页表（每一小节对应一个页表项），多级页表是在页表的基础上建立一个高层结构，通常称为页目录（多级页表的基本思想就是构造一个页表的页表，每一章对应一个页表）；
两级页表结构及其地址转换过程如下所示
Q：多级页表究竟怎么减小进程对内存的占用？
A：单级页表存在的最大问题就是操作系统为每个进程分配了固定大小的空间作为页表，并且这个页表必须包括所有的页表项（因为OS不知道进程到底会访问哪些页表项），这就意味着操作系统不能实现按需分配页表空间；而多级页表可以在使用时根据内存的占用为进程分配页表空间，实现动态按需分配而不是预先全部分配；
计组中已经介绍过Cache，现在我们再次复习一遍；
Cache出现的前提是因为CPU和内存之间的速度差异，在Cache之前有诸如双端口RAM、多模块存储器这些特殊结构的存储器，但是采用存储体结构上的优化速度仍然匹配不上CPU，所以考虑直接优化存储元，引入了局部性原理的Cache层次化设计；
CPU与Cache/主存之间交换数据以字为单位，Cache与主存之间交换数据以块（多个字）为单位（一定程度上我们可以把内存的基本单位“页”也称为“块”，之后的文件系统章节我们直接认为无论是物理还是逻辑，内存都以“块”为单位），Cache基于局部性原理：
下面我们介绍几个重要的知识点：
命中率：设一个程序执行期间Cache的总命中次数为Nc，访问主存的次数为Nm，则命中率H为
缺失率=1-命中率
地址映射规则：将主存分区，每个区域内的主存块数与Cache内的块数相同；
地址映射规则：主存的任意一块可以映射到Cache中的任意一块
地址映射规则：将主存分区，将Cache分组，要求主存的每个区的块数与Cache的组数相同（主存中一个区分为4块所以Cache中需要4组）
为了在Cache中记住自己存储的数据块来自主存中的哪一个区，Cache额外增加了标记字段；
假设每组有r个Cache块，则称为r路组相联；
组间直接映射规则：
2.使用组相联映射，CPU的内存地址结构为：
标记：主存区号的标记组号：Cache组的地址块内地址：Cache中的字块内的地址
3.地址变换过程：首先使用组号找到Cache中的组，然后将标记与该组所有Cache块中的区号比较，如果相同则命中，使用块内地址取出需要的数据；
采用全相联或组相联映射方式的时候，从主存向Cache映射一个块，当Cache或Cache组中的空间被占满时候，需要使用替换算法（直接映射没有选择直接替换，故不考虑替换算法）；
Cache中的内容是主存的副本，当Cache中的内容更新的时候，需要选择写策略使得Cache与主存内容保持一致；
也称为写直通法、write-throught：
优点是简单，随时保持主存数据的正确性；
缺点是增加了访存次数，降低了Cache效率，我们可以适当在Cache和主存之间增加一个写缓冲——CPU同时将数据写入写缓冲和Cache，写缓冲再将内容写入主存，由此解决速度不匹配的问题；
write-back：
这种方法减少了访存次数，但是增加了不一致的风险——采用这种策略时每个Cache块必须设置一个标志位脏位以标志此块是否被CPU修改过；
上述两种方法都应对的是Cache写命中（也就是要修改的单元在Cache中），对于Cache不命中也有两种处理方法：
加载主存中的块到Cache中，接着再更新这个块（这个方法需要搭配写回法，在该Cache块被替换的时候更新主存对应块）；
优点是利用了程序的空间局部性，缺点是每次不命中都需要从主存中读取一块，效率过低；
这种方法只写入主存，不进行调块，通常与全写法合用；
上面我们介绍了Cache，但是实际上常用的逻辑页不会是连续的，且常用的逻辑页不会很少（这意味着Cache中往往缓存了几百个映射关系），使用基于Cache的传统比较查找方法效率将会很低，无法起到提高效率的作用，因此我们引出了借助硬件电路设计来实现对Cache的查找，我们将这种硬件电路称为快表（简单理解的话就是快表是专门针对页表的Cache，所以其效率比普通Cache要高（具体原因我这里猜测是因为不同的组织方式有关系））；
注意虽然快表和页表都是表，但是两个根本不是一个层次的概念（快表是个硬件！）；快表是一种特殊的Cache，内容是页表中的一部分或全部内容，在OS中引入快表是为了加快地址映射的速度；快表就是将页表存在Cache中，慢表表示将页表存在内存上；
快表会缓存常用的逻辑页映射（虚拟地址<->逻辑地址），引入快表的地址转换过程为：先查快表，若命中hit则能够快速的获得物理页框号；如果未命中则查找页目录表、页表、找到物理页框号并更新快表；
快表、CPU以及Cache的速度比较大致如下
TLB表项映射
TLB中存放的基本单位是页表条目（虚拟页表项），对应RAM中存放的页表条目（物理页框）；页表条目大小不变，但是RAM不可能与TLB一一对应（因为TLB始终容量有限）；
CPU收到一个线性地址需要做如下判断：
TLB表项更新
TLB表项更新可以由TLB硬件自动发起，也可以由软件主动更新
TLBShootdown
TLB条目需要始终与其各自的页表条目同步，现在，TLB是每核缓存，即每个核心都有自己的TLB，每当页表条目被任何内核修改时，该特定TLB条目在所有内核中都会失效，此过程称为TLB击落；
简单来说，一个处理器导致TLB在其他处理器上刷新（当处理器更改地址的虚拟到物理映射时，它需要告诉其他处理器在其缓存中使该映射失效）的操作就是所谓的TLB击落；
TLB刷新可以由各种虚拟内存操作触发，这些操作会更改页表条目，如页面迁移，释放页面等；
不知道在学习分页和分段的时候大家脑子里有没有这样一个问题“这两概念看起来和操作系统没啥关系啊？”，而事实的确是这样，程序用户想要分段，物理内存想要分页；那么能不能将分段和分页结合在一起？这就是操作系统大显身手的时候了——操作系统通过在用户和硬件之间加一个中间结构（中间层这个概念真的是计算机界的万精油），我们将这个数据结构称为虚拟内存，正是虚拟内存这个抽象将分段机制和分页机制有机地结合；
现在结合虚拟内存来回答之前的两个问题：
接着我们来聊聊虚拟内存真正厉害的地方，假设虚拟内存大小为4GB而实际物理内存只有1GB，是否意味着我们4GB的程序无法运行了呢？
换入/换出行为使得可以使用一个小的物理内存来制造一个大且规整的虚拟内存用户视图——实际上就算物理内存是4GB也需要换入/换出，因为每个进程都需要有一个4GB的虚拟内存
当然想要在系统中实现换入/换出只是一个概念，真正要实现需要从段页式内存管理机制入手分析，下图给出了段页式内存机制下地址转换过程遇到的问题：
地址转换的第一步能够正确得到虚拟地址，但是根据虚拟地址和页表获得物理地址时发现页表中没有该虚拟页对应的物理页——这是因为这一页的虚拟内存还没有和物理内存建立关联；
在具体实现时，MMU检查页表项的有效位，如果为0表示该虚拟页还没有映射到物理页框，此时就需要内存换入——操作系统实现请求调页：
常识：一个程序在被加载进入内存的时候只会加载很少一部分进入内存（这部分标识为“驻留”），另一部分会在需要的时候才调入内存（这部分标识为未驻留），也就对应了有效位为1和0的情况；
页面换出要解决的基本问题就是选择哪个页面进行淘汰，我们定义一个指标来评价页面换出算法的优劣：缺页次数；
我们要介绍的页面换出算法曾经在计算机组成原理课程中也有介绍——LRU最近最少使用算法，LRU也有多种选择，这里我们选择使用基于页面栈的LRU算法
然而直接在计算机中实现精准的LRU算法代价过大，所以出现了类LRU的算法——clock算法：
当然还可以引入一个扫描指针，该指针定期扫描所有页面，并将所有页面为1的清零；当出现缺页时调用换出指针来扫描页面判断页面的R位
只有当分配给进程的所有物理页框都被用完之后，发生缺页才会调用clock算法进行淘汰，所以操作系统应该决定给进程分配多少个物理页框：
当Cache使用的是虚拟地址的时候会存在别名问题，原因是操作系统和用户程序可能对同一个物理地址使用两种以上不同形式的虚拟地址来访问，这些地址被称作别名，他们会导致同一个数据在使用虚拟地址的cache中存在两个副本，如果其中一个数据被修改，那么另外一个就是错误的；
解决别名问题的方法之一就是使用页着色：
Cache中存储同一个颜色的连续多个set(组，直接映射的Cache只有一个set)被称为bin，上图中两个黄色的页因为具有相同的colorbits，于是被映射到L2Cache中的bin中；
总结：
（这章不难，但是把我搞得很崩溃，因为王道和哈工大的书立足点完全不一样，然后这部分和计算机组成原理也疯狂重合，不断冲击我的认知，哭了WW...哈工大的教材对于I/O管理这部分描述的不是很清楚，所以我们将结合王道的教材额外补充未涉及的知识点；）
之所以不一来就讲解文件系统，是因为本质上文件系统是基于硬件系统的，有必要具备一些硬件知识，硬件的一些特性能帮助开发者开发更好的软件系统；
本章将讨论操作系统对于设备的管理以及它为用户程序提供服务的作用；
I/O设备按照使用特性可分为以下类型：
1）人机交互类外部设备。用于与计算机用户之间交互的设备，如打印机、显示器、鼠标、键盘等。这类设备的数据交换速度相对较慢，通常是以字节为单位进行数据交换的。2）存储设备。用于存储程序和数据的设备，如磁盘、磁带、光盘等。这类设备用于数据交换，速度较快，通常以多字节组成的块为单位进行数据交换。3）网络通信设备。用于与远程设备通信的设备，如各种网络接口、调制解调器等。其速度介于前两类设备之间。网络通信设备在使用和管理上与前两类设备也有很大不同。
I/O设备按照传输速率可分为以下类型：
1）低速设备。传输速率仅为每秒几字节到数百字节的一类设备，如键盘、鼠标等。2）中速设备。传输速率为每秒数千字节至数万字节的一类设备，如行式打印机、激光打印机等。3）高速设备。传输速率在数百千字节至千兆字节的一类设备，如磁带机、磁盘机、光盘机等。
I/O设备按照信息交换的单位可分为以下类型：
1）块设备。由于信息的存取总是以数据块为单位的，所以存储信息的设备称为块设备。它属于有结构设备，如磁盘等。磁盘设备的基本特征是传输速率较高、可寻址，即对它可随机地读/写任一块。2）字符设备。用于数据输入/输出的设备为字符设备，因为其传输的基本单位是字符。它属于无结构类型，如交互式终端机、打印机等。它们的基本特征是传输速率低、不可寻址，并且在输入/输出时常采用中断驱动方式。
整个I/O系统可以视为具有如下层次的系统结构，各层次及其功能如下：
I/O子系统不同于I/O系统，I/O子系统是操作系统中负责和I/O设备打交道的子系统（也就是说操作系统中负责I/O管理部分的就是I/O子系统），而I/O系统是由输入输出控制系统和外围设备两部分组成的一个系统；
下面我们介绍I/O子系统提供的主要服务：
I/O子系统还可使用主存或磁盘上的存储空间的技术，如缓冲、高速缓存、假脱机等来改善计算机效率；
磁盘高速缓存技术不同于常规意义下的介于CPU与内存之间的小容量高速存储器(Cache，注意这里的Cache是一种硬件，由SRAM组成)，磁盘高速缓存逻辑上属于磁盘，物理上是驻留在内存中的盘块；
磁盘高速缓存在内存中分为两种形式：
Q：是不是觉得很神奇，这和我们计组学的Cache不一样啊，我不能接受！
A：现在Cache的概念已经被扩充了：不仅在CPU和主内存之间有Cache，而且在内存和硬盘之间也有Cache（磁盘高速缓存），乃至在硬盘与网络之间也有某种意义上的“Cache”（Inter临时文件夹），因此Cache现在的定义为：凡是位于速度相差较大的两种硬件之间的，用于协调两者数据传输速度差异的结构，均可称之为Cache；
其实现方法如下：1）采用硬件缓冲器，但由于成本太高，除一些关键部位外，一般不采用硬件缓冲器。2）采用缓冲区（位于内存区域）。
缓冲区有一个特点，即当缓冲区的数据非空时，不能往缓冲区冲入数据，只能从缓冲区把数据传出；当缓冲区为空时，可以往缓冲区冲入数据，但必须把缓冲区充满后，才能从缓冲区把数据传出；
学习了磁盘高速缓存和缓冲区之后，我们会产生疑问，这两东西真的好像，下面我们给出表格区分：
设备分配是指根据用户的I/O请求分配所需的设备。分配的总原则是充分发挥设备的使用效率，尽可能地让设备忙碌，又要避免由于不合理的分配方法造成进程死锁。从设备的特性来看，采用下述三种使用方式的设备分别称为独占设备、共享设备和虚拟设备：
上面我们只是在理论层面介绍了I/O子系统提供的一些服务，现在我们真正用实例来体验一下操作系统如何参与控制I/O设备工作（这一小节在哈工大的教材是单独作为一个章节罗列出来的，本质上这个小节的内容是为了下一章的文件系统做铺垫）；
完成CPU和内存这两个计算机核心设备的管理以后，操作系统的最后一项重要任务就是管理计算机外部设备，外部设备也称为输入输出(I/O)设备，通过总线和CPU、内存连接在一起；
外设的工作模式非常直观：
上述两个步骤是操作系统使用外设的核心主线，但外设管理不只包括外设的使用，还包括外设使用效率的提高；
操作系统引入文件视图的概念，使得所有外设的使用都被统一为对文件视图的使用，文件视图给上层用户提供了一个统一的接口，屏蔽了细节；文件视图背后根据外设各自的特点实现缓冲机制、排队调度等来提高外设的工作效率；
CPU对外设的使用主要由以下两条主线构成（有点啰嗦，但是这两条主线就是外设管理的整个核心）：
如果按照8.1的方式来使用外设，需要知道外设的端口地址、设备操控指令的详细格式和指令流程等信息，这对一个普通程序员来说是很困难的，让应用程序员通过命令直接操作计算机外设的想法几乎不可行；
文件视图应运而生，不管是什么样的外设，操作系统都将其抽象为一个文件，程序员只需要通过文件接口open、read、write来使用这些外设；
有了文件视图之后，上层用户操作外设和对文件的操作完全一样（外设端口号、设备指令格式等细节交给操作系统完成），操作系统负责将上层接口展开形成对设备的具体操作，形成一系列out语句；
操作系统进行外设管理的核心就是构建两条路线：
printf是一个库函数，该库函数会调用系统调用write，write的内核实现是sys_write；
sys_write首先需要找到所写文件的属性，以区分它究竟是普通文件还是设备文件：
设备属性被存放在一个数据结构中（该数据结构描述了文件），这个数据结构就是FCB文件控制块，因此sys_write的第一步就是找到要写的目标文件（当然这里的文件就是设备文件）的FCB；为了找到FCB，需要从当前进程的PCB中找到文件的句柄标识fd，根据fd就可以找到文件的FCB；
intsys_write(unsignedintfd,char*buf,intcount){structfile*file;file=current->filp[fd];//current是当前进程，current->filp存放了当前进程打开的文件，根据fd可以在文件FCB数组中找到我们需要的目标文件的FCBinode=file->f_inode;//inode变量就是文件的FCB，file中的属性信息被存储在inode变量中...}我们已经获得inode变量，首先根据inode中的信息来判断该文件对应的设备是否是一个字符设备（显示器就是一个字符设备）：
接下来的函数根据是设备读操作还是设备写操作继续分支（显示器只写，键盘只读）：
tty_write函数向显示器进行输出，之后的过程我们就不再细讲，感兴趣可以见书P205自学；
Q：为什么显示器是写操作，不是显示给用户吗？
A：我们将显示器理解为一个设备文件，要让显示器显示东西那么这个设备文件中一定要有东西才行，所以显示器对应写操作；
整个文件视图路线总结如下：
按下键盘会产生0x21号中断，所以先来看0x21号中断的中断处理函数；
CPU向设备写的最终命令是"out"，相应的，读设备的第一步是"in"即从设备上取出内容交给CPU；
（本节直接从课堂上的PPT总结，主要目的就是为了承上启下引出文件系统）
I/O栈非常复杂，利用计算机系统中常规的分层思想我们大致可以将其分为如下（I/O栈本质上就是用户从应用的层次对磁盘进行读写如何影响到最终磁盘的读写）
我们仅介绍其中最核心的文件系统，文件系统的主要功能（也是设计一个文件系统需要具备的最基本的功能）如下
结论：
其中Naming是文件系统最基本的功能，课堂上老师讲解文件系统的流程也是按照Naming的两个阶段进行
操作系统打开(open)一个文件的时候会对文件名做一个解析，将文件名转换为文件号，操作系统赋予该文件一个文件描述符并返回一个句柄，之后所有的操作(read、write)都是基于句柄操作，将操作映射到文件描述符和磁盘块上；
该过程主要分为两个阶段，目录承担了文件名到文件号的映射阶段的任务，文件承担了文件号到磁盘块的映射阶段的任务；
目录对任何文件数据都认为是<文件名：文件号>的对，目录对文件名的映射过程如下（实际上就是根据目录结构对文件进行查找）
通过对目录结构的改进可以得到更高效的查找效率（如B+树的结构）
这部分的考点是计算将文件名映射为文件号需要做多少次的磁盘访问（文件号也是保存在磁盘中的）
第二阶段，从文件号到磁盘块的映射，我们将在下面章节10.常见文件系统一节进行介绍，分文件系统对这部分知识点讲解（因为常见文件系统的区别也主要就体现在从文件号到磁盘块的映射）
CPU管理和内存管理构成了操作系统的核心kernal，通过外设管理用户可以用键盘和显示器进行输入和输出（可以将文件视图理解为文件系统的一个子集），本章将讨论构成一个完整的操作系统的最后一部分——文件系统，用户对操作系统的使用都是以文件为基础的，无论是用户编辑的文档、执行的指令还是使用的外部设备在OS中都是文件，因此文件系统是构成操作系统的必要组成部分；
文件系统归根结底是对磁盘的驱动，因为在磁盘驱动的过程中发现直接使用磁盘非常繁琐，所以引入如下五层抽象：
操作系统通过上述五层抽象讲整个磁盘变成一系列文件，并将这些文件组织成树状结构，形成操作系统第二个基本的视图——文件视图；
本章从磁盘驱动出发逐层揭开上述抽象过程；
磁盘是一类较为特殊的I/O设备，也就是持久性存储设备，学习磁盘是接触文件系统的基础（因为文件系统的底层就是存储设备，且一般考虑块设备而不是字符设备），在本章的后面章节我们将基于磁盘讨论读写速度的优化和文件系统的设计
磁盘作为一种外部设备，其工作原理和一般外设工作原理完全一样：
磁盘的构成：磁盘是由多个圆形盘面形成的盘面组，每个盘面上又有多个同心圆环，每个同心圆环被称为一个磁道，多个磁盘的同一磁道合在一起形成一个圆柱面，简称柱面。每个磁道再被分割为多个扇区，扇区是磁盘读写的基本单位。由于有多个盘面，所以在每个盘面上都有一个读写磁头，进行磁盘读写时，只有一个磁头是上电的，会读写该上电磁头对应的那个磁道上的那个扇区。
总结：一块磁盘有多个记录面，每个记录面有多条磁道，每条磁道被划分为多个扇区（也被称为块，块是磁盘最小的读写单位）
CPU使用磁盘的方法非常直观：让CPU给磁盘控制器发出读写命令，具体就是告诉磁盘控制器读写哪个柱面C、哪个磁头H、哪个扇区S以及要读写的内存缓存区的位置和读写长度即可。当然需要查阅硬件手册，找到这些信息对应的端口地址，一旦找到以后，CPU用out指令将这些信息写出去即可，磁盘控制器一旦看到了这些信息就会执行磁头滑动、磁盘旋转以及读写扇区等动作了。
磁盘读写的具体过程是：
（1）磁头移动，找到要读的那个柱面（cylinder，以下简称C），由于多个磁头是绑在一起移动的，所以每个磁头下面的磁道在各自的盘面中具有同样的位置，所有磁头下面的磁道从上到下组合在一起就形成了一个“柱面”；
（2）从柱面中选择要具体读写哪个磁道，实际上就是选择哪个磁头（magnetichead，以下简称H）上电；
（3）旋转磁盘，将对应磁道中要读写的那个扇区（sector，以下简称S）转到磁头的下方；
（4）开始读写，将扇区中的内容读到内存缓存区中，或者是将内存缓存区中的内容写出到该扇区中；
参考链接：
符合程序员使用习惯的磁盘读写是抹去C、H、S等具体细节，让程序员感觉是一堆扇区排成一排等待用户使用；
实现这种访问的核心是建立从C、H、S扇区地址到扇区号的一个映射，即建立一个在C、H、S基础之上的编址方案，该编址方案是文件系统第一层抽象的中心任务；
完成了从C、H、S到扇区号的完整映射后，操作系统用户可以通过一个一维扇区编号来访问磁盘扇区而不需要再使用繁琐的C、H、S地址，也不需要记住磁头个数等硬件参数；
经过第一层抽象之后，我们可以处理磁盘块的读写请求了；
操作系统中有多个进程，每个进程都会提出磁盘块访问请求，所以在实际操作系统中是多个进程产生多个磁盘块读写请求的情形。多个磁盘读写请求，需要用队列来组织这些请求，这就是操作系统对磁盘管理的第二层抽象；
经过第二层抽象以后，磁盘读写会变成这个样子：想进行磁盘读写的进程首先建立一个磁盘请求数据结构，并在这个数据结构中填上要读写的磁盘块号（简称盘块号），然后将这个数据结构放入磁盘请求队列中就完成了“磁盘读写”。剩下的工作交给操作系统来完成，对用户进程完全透明，操作系统要处理的工作如下：
（1）从队列中选择一个磁盘请求——第二层抽象的核心，磁盘调度算法；
（2）取出请求读写的；
（3）根据盘块号计算出C、H、S；
（4）用out语句向磁盘控制器发出具体指令；
整理一下到目前为止的磁盘处理过程：操作系统处理各个进程提出的磁盘请求，根据请求中的磁盘块号在磁盘上找到相应的扇区位置，将这些扇区读入到内核态内存中，然后再由系统调用（如sys_read）将存放于内核态内存中的磁盘数据复制到用户态内存中，用户态程序操作用户态内存中的数据。
磁盘高速缓存能大幅度减少磁盘读写次数，是磁盘管理的又一层抽象，简单来说就是操作系统将磁盘数据“变成一系列位于内核态内存中的缓存区内容”；
简单分析一下磁盘高速缓存的工作原理：当用户发出一个磁盘块读写请求时，操作系统会在高速缓存中查找这个磁盘块是否已经在高速缓存中
所以高速缓存的关键是要提供一种机制来快速查找一个磁盘块数据是否在高速缓存中，根据关键字（盘块号）来快速查找其是否在一个表中，最常使用的数据结构就是散列表，因此以盘块号为关键字形成一个散列表来组织已经载入的磁盘块数据——缓存块；
而当在物理磁盘中读写的情况下，这要求在高速缓存中取出一个空闲缓存块，用来缓存从磁盘块中读出的数据，组织空闲缓存块通常使用的数据结构就是空闲链表；
因此设计磁盘高速缓存的核心就是要建立两个数据结构：用一个散列表组织有内容的缓存块，再用一个空闲链接组织那些空闲的缓存块；
抽象到现在，用户通过盘块号来调用bread函数，就可以读写磁盘了，看起来已经比较方便了。但是对于那些连磁盘是什么都不知道的大多数计算机用户而言，用磁盘块号来读写磁盘仍然不可行，因为这要求用户除了知道磁盘块的概念外，还需知道磁盘块大小这样一些“高级参数”。
为了让磁盘上的数据访问更符合人们的习惯，操作系统引出了磁盘使用的第四层抽象文件，文件是一个连续的字符流。为什么是字符流？因为不管是什么数据，也不管这个数据内容有多大，我们都将其看成是一个字符流。在这个字符流上读取、改写、插入、删除某个或某些字符，这才是符合人类习惯的数据访问方式。
操作系统的这一层抽象就是要将磁盘块抽象为一个字符流，经过抽象以后：
（1）用户看到并访问的是一个文件，是一个字符流，和磁盘块没有任何关系；
（2）从磁盘物理设备出发，磁盘中只有磁盘块，所以字符流最终还是要存放在磁盘块上；
（3）操作系统将字符流读写映射为对磁盘块的读写；
经过抽象之后，用户可以在这个字符流上随意滑动，随意处理，操作系统会根据一个映射表找到和字符流位置对应的磁盘块号，操作系统完成了从磁盘块到字符流的映射。显然，实现文件抽象的关键就在于能根据字符流位置找到对应的盘块号，即建立字符流和盘块号之间的映射关系。
顺序存储结构
链式存储结构
文件字符流存放的磁盘块不需要连续，只要每个磁盘块中存放下一个字符流片段所在的盘块号即可。这样就会形成一个“链”式结构；
索引存储结构
文件字符流被分割成多个逻辑块，在物理磁盘上寻找一些空闲物理盘块（无须连续），将这些逻辑块的内容存放进去，再找一个磁盘块作为索引块，其中按序存放各个逻辑块对应的物理磁盘块号
多阶索引存储结构
引入了文件抽象以后，对磁盘的使用已经变成对文件的访问。抽象到现在，磁盘的使用更符合人们的直观感觉，并且在整个抽象过程中操作系统引入了高速缓存等提高磁盘读写效率的处理技术，磁盘使用的效率也有了大幅提升。
但是，现在还没有完成对整个磁盘的全部抽象。因为一个文件可以将磁盘上的一些磁盘块抽象成一个字符流，但是磁盘是很大的，不可能用一个文件完成对磁盘上所有物理盘块的抽象。另外，从给用户提供文件视图的角度出发，整个磁盘上也绝不可能只有一个文件，显示器对应一个文件，打印机也对应另一个文件。
本节的核心就是讲述操作系统如何组织多个文件（这里是多个文件，不是多个进程，注意和第二层抽象区分），磁盘中的文件按照树形结构组织，形成目录树；
实现磁盘的抽象就是实现目录树，那么实现目录树的关键又是什么呢？目录树由文件和目录两部分组成，实现目录树的关键就是实现目录；
本节主要参考王道，因为哈工大的教材是根据抽象构成来描绘文件系统的，但是知识点/考点的总结并不是很清晰，所以这里使用王道视频做一个对上面知识点的总结和拓展；
文件：一组有意义的信息/数据集合；
文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件；
标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称；
类型：指明文件的类型；
位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）；
保护信息：对文件进行保护的访问控制信息；
文件可以分为如下两类：
所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的（下一节将介绍文件之间是如何组织的）；而“物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的（可以类比数据结构的逻辑结构和物理结构）；
因为无结构文件内部的数据就是一系列字符流，不存在明显的结构特性，故不需要讨论无结构文件的“逻辑结构”；
有结构文件指的是由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成，如数据库表文件，一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）。根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种；
根据有结构文件中的各条记录在逻辑上如何组织，可以将有结构文件分为三类：
顺序文件：文件中的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上可以顺序存储或链式存储。
根据文件的特性，有如下结论：
目的：解决可变长文件访问慢的问题，实现可变长文件随机访问的功能；
索引文件：每一个文件会建立一张索引表，每一张索引表的表项会对应该文件的一条记录，文件中的这些记录可以在物理上离散地存放，但是索引表的表项（一条记录）在物理上是需要连续存放的（另外需要注意的是每一个索引表的表项大小是相同的）；
索引表本身是定长记录的顺序文件，因此可以快速找到第i个记录对应的索引项；
可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找；
每当要增加/删除一个记录时，需要对索引表进行修改；由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合；
目的：解决索引表对存储空间的利用率很低的问题——假如文件的每个记录平均只占8B，而每个索引表的表项占32B，这就导致索引表比文件本身还大；
索引顺序文件是索引文件和顺序文件思想的结合：索引顺序文件中，同样会为文件建立一张索引表，但不同的是，并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项；
多级索引顺序文件：为了进一步提高检索效率，可以为顺序文件建立多级索引表；
我们知道从用户的角度看文件之间的组织方式是按照文件目录（树结构）进行的，本节将详细讨论从操作系统的角度来看如何实现文件目录结构（很多地方将文件目录和目录文件混用，因此我们不需要做过多区分）；
本节的知识图谱如下
目录（也称为文件夹、文件目录、目录文件）中的一条记录就是一个文件控制块FCB，FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项；
FCB最核心的功能是实现了文件名和文件之间的映射，使得用户/用户程序可以实现“按名存取”；
文件目录主要实现以下功能：
在操作系统的发展过程中出现了各种各样的目录结构
早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项；
早期的多用户操作系统，采用两级目录结构，分为主文件目录（MFD，MasterFileDirectory）和用户文件目录（UFD，UserFlieDirectory）；
又称为树形目录结构，是现代操作系统中很常见的一种目录结构
很多时候，用户会连续访问同一目录内的多个文件（比如：接连查看“2015-08"目录内的多个照片文件），显然，每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”，从当前目录的路径称为“相对路径”，引入“当前目录”和“相对路径”之后明显减少了磁盘的I/O次数，提升了访问文件的效率；
树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护，但是，树形结构不便于实现文件的共享，为此，提出了“无环图目录结构”；
可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）；
删除目录：需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点；只有共享计数器减为0时，才删除结点；
注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。
本质上是对FCB数据结构的改进
当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据“存放位置”即可找到文件；
存放在外存中的索引结点称为“磁盘索引结点”，当索引结点放入内存后称为“内存索引结点”；相比之下内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等；
本节解决的问题：从上往下看，文件数据应该怎么存放在外存（磁盘）上，文件的物理结构也称为文件的分配方式；
操作系统对磁盘进行的管理主要分为：
文件的物理结构主要探讨的就是文件数据应当怎样存放在外存中，在开始本节知识点之前需要介绍几个前置知识点
文件块/磁盘块
物理地址空间：类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、内存页的大小相同（外存的物理地址表示为(物理块号，块内地址)）；
逻辑地址空间：在内存管理中，进程的逻辑地址空间被分为段地址:段内偏移（分段，但是如果我们引入“块”的概念（Cache块，分页和分块的中间层），那么就可以将进程的逻辑地址表示为(逻辑块号，块内地址)）；同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间被分为了一个一个的文件“块”，于是文件的逻辑地址也可以表示为(逻辑块号，块内地址)的形式；
操作系统负责实现将文件的逻辑地址空间与物理地址空间进行映射（这也是本小节的核心问题）；
概念
FCB
连续分配方式下文件目录需要记录的关键文件属性如下，这是为了实现之后地址映射
地址映射
采用连续分配方式的地址转换方式（逻辑块号，块内地址）->（物理块号，块内地址）：只需转换块号就行，块内地址保持不变；
用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB），利用公式物理块号=起始块号+逻辑块号进行计算；
小结
优点：
缺点：
链接分配采取离散分配的方式，可以为文件分配离散的磁盘块，分为隐式链接和显式链接两种；
考试中出现的“链接分配”默认是隐式链接分配；
隐式链接分配方式下文件目录需要记录的关键文件属性如下
用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB）；
从目录项中找到起始块号（即0号块），将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，再找到2号逻辑块的存放位置以此类推；
因此，读入i号逻辑块，总共需要i+1次磁盘I/O；
优点：很方便文件拓展，不会有碎片问题，外存利用率高；
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间；
把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，FileAllocaticnTable）
概述
从目录项中找到起始块号，若i>0，则查询内存中的文件分配表FAT，往后找到i号逻辑块对应的物理块号，逻辑块号转换成物理块号的过程不需要读磁盘操作（FAT常驻内存）；
优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高；
缺点：文件分配表的需要占用一定的存储空间；
索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）；
磁盘中用于存放索引表的磁盘块被称为索引块，磁盘中用于存放文件实际数据的磁盘块被称为数据块；
从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只i号逻辑块在外存中的存放位置；
拓展
一个磁盘块的大小是有限的，相应的能够存储的索引项也是有限的，在某些情况下仅使用一个磁盘块是不能装下整个文件的索引表的（即索引块不只一个磁盘块的大小），主要有以下解决方案；
缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘1/0次数过多，查找效率低下；
关于为什么每个索引表的大小不能超过一个磁盘块，因为255指向的是二级索引表而不是下一个一级索引表（至于为什么不单独把最后一个二级索引表当作一级索引表以拓展索引表大小，应该是二级索引表仍然能够起到拓展大小的作用，无需复杂化，因为多层索引表本来就是为了解决单层索引表的缺点诞生，是优化关系而不是并列关系）
采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作；
缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘；
注意：各索引表最大不能超过一个块的大小；
优点：对于小文件，只需较少的读磁盘次数就可以访问目标数据块（一般计算机中小文件更多）；
对存储空间的管理实际上就是对空闲磁盘块的管理；
可以将将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘，如C、D、E盘），文件卷可以划分为目录区和文件区，目录区主要用于存放文件目录信息FCB以及用于进行磁盘存储空间管理的信息，文件区主要用于存放文件数据；
在学习这几个经典的存储空间管理方法的时候我们时刻提出并解决以下问题：
空闲表法适用于文件的物理结构是连续分配的情况；
以盘块为单位组成一条空闲链
以盘区（连续的盘块）为单位组成一条空闲链，对离散分配、连续分配都适用，与空闲盘块链相比为一个文件分配多个盘块时效率更高；
用二进制位对应盘块是否已分配的信息，对连续分配和离散分配都适用；
空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大，UNIX系统中采用了成组链接法对磁盘空闲块进行管理；
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存，并且要保证内存与外存中的“超级块”数据一致；
需要注意的是，每个分组被分配之前需要将该分组的链接信息复制到超级块中，超级块充当了一个链头的作用，在该链头中永远要保持指向下一个分组的信息；
操作系统为用户提供文件共享功能，可以让多个用户共享地使用同个文件；
主要有两种实现方式：
注意：多个用户共享同一个文件，意味着系统中只有“一份”文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化；
索引结点，是一种文件目录瘦身策略。由于检索文件时只需用到文件名，因此可以将除了文件名之外的其他信息放到索引结点中。这样目录项就只需要包含文件名、索引结点指针；
索引结点中设置一个链接计数变量count，用于表示链接到本索引结点上的用户目录项数。若count=2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件；
若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1；
若count=0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空；
Link类型的文件记录了对应文件的存放路径，类似于Windows操作系统中的快捷方式；
为文件设置一个“口令”（如：abc112233），用户请求访问该文件时必须提供“口令”；口令一般存放在文件对应的FCB或索引结点中。用户访问文件前需要先输入“口令”操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件；
使用某个“密码”对文件进行加密，在访问文件时需要提供正确的“密码”才能对文件进行正确的解密；
在每个文件的FCB（或索引结点）中增加一个访问控制列表（Access-ControlList，ACL），该表中记录了各个用户可以对该文件执行哪些操作；
精简的访问列表：以“组”为单位，标记各“组”用户可以对文件执行哪些操作。如：分为系统管理员、文件主、文件主的伙伴、其他用户几个分组；当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限；
本节介绍的内容是集成了之前介绍的文件系统的所有的知识点，可能会有重复的内容，但是这些重复的内容恰好就是重要的点；
文件系统实际就是操作系统管理持久性存储数据的方法，它的基础是文件的抽象、存储设备管理和存储区域分配算法(内存分配)；
FAT的全称是FileAllocationTable，即文件配置表；
顾名思义，这种文件系统的核心是一个文件配置表，表中的每一项都对应着磁盘中一个实际的数据块；这个数据块可能包含了多个扇区，其大小由操作系统决定，因此它被成为逻辑数据块，以便于与物理扇区做出区分；
每个文件至少拥有一个数据块，因此我们可以通过文件在系统中的“编号”寻找表中对应的项，每一项都以链表的形式存储了同一个文件下一个数据块对应项的位置，如果其存储值为-1则代表这是这个文件的最后一个数据块；在寻找一个文件时，我们先进入这个配置表的第一项，也就是代表了根目录的数据块，从中找到根目录中存储的子目录或文件对应的项的编号；
FAT中所有的空闲分区也被以链表的形式存储在配置表中，因此当我们需要延长一个文件时，我们就可以从链表中选取第一项；当一个文件被删除时，我们将它所占有的所有数据块都接入这个空闲分区链表中；
FAT文件系统的缺点：
如果我们选择较小的逻辑数据块大小，那么一个大型文件就会包含很多个小分区，由于FAT文件系统给文件分配的物理数据块不一定是连续的，这样的结构会导致读写效率很低；然而，如果我们转而选择较大的逻辑数据块，那么针对一些小文件的存储就会产生很多内部碎片；
FAT文件系统下大文件和小文件的读写效率都不高，且它没有利用磁盘连续读写时速度快的优势，因此连续读写和随机读写的表现都较为糟糕；
特点：
FAT是一个效率不高的文件系统，且它不包括控制使用权限等对于系统安全来讲至关重要的功能；
由于磁盘中数据的最小存储单位是一个扇区，我们可以自然地想象到，一个文件需要记录其数据对应着哪些磁盘扇区，但如果我们在同一个扇区里记录所有数据扇区的序号，那么一个文件的大小就被一个扇区能够存储的序号数量乘以单个扇区的大小限制了。这种大小限制会限制文件系统的实用性——研究表明，虽然大多数文件都是较小的文件，但文件系统中占据较大部分空间的都是较大的文件，因此我们需要能够处理大文件的情况。然而，如果我们单纯使用两到三个扇区来存储所有数据扇区的序号，在存储小文件时这种结构又会浪费很多空间。为了防止这种问题的出现，我们需要一个“伸缩自如”的结构；
FFS就发明了这样一种结构。在FFS中，每个文件都被一个inode(即之前介绍的索引节点)代表。这个inode中存储的是文件的元数据和数据扇区的指针，但是与一般指针不同的是，inode中不只包含直接指向数据扇区的指针，还包含二层指针和三层指针。二层指针指向的扇区中包含的不是数据、而是指向数据扇区的指针；以此类推，三层指针指向的扇区包含的是指向二层指针扇区的指针。这样假如我们的一个扇区原本可以存储n个指针，现在我们就可以通过二层指针存储n2个指针。不过，由于大多数文件都是小文件，FFS对于inode中二层指针和三层指针的数量作出了限制，大多数指针仍然是直接指针；
NTFS文件系统在Windows系统中取代了FAT成为了新一代文件系统；
日常生活中使用的存储设备如U盘、移动硬盘等都有自己的文件系统，但我们在将这些设备接入到计算机中时、它们仍然可以作为我们计算机中文件系统的一部分被浏览。用于实现这一功能的过程集叫做挂载（mount）；在一台设备上可能存在多个文件系统，每个可以独立存在的文件系统就被称为“卷”（Volume）；当一个设备被插入到计算机中时，操作系统会先识别设备上存在的文件系统，然后将这些文件系统挂载到操作系统自带的文件系统下；
如果操作系统自带的文件系统与设备上的文件系统版本不同（当然也不一定是版本不同，反正可能就是出现各种问题），那么操作系统如何才能兼容这个设备上的系统呢？
一种简单的方法是针对每个不同的文件系统写一段用于兼容的代码，但这种解决方法的效率显然不高，而且很难维护——每当一种新的文件系统出现时，我们都需要更新操作系统的代码；
在计算机这一领域中，解决这类问题有一个常见的方法，那就是增加一个新的抽象层，因为一个新的抽象层可以使我们在不考虑更底层的抽象层的细节的前提下实现我们需要的功能；
在文件系统中，这个新的抽象层就是虚拟文件系统（VirtualFileSystem，VFS）；虚拟文件系统基于一个类似于inode的概念，vnode，定义了一个使用文件的界面，所有实现这一界面的文件系统无论实现方式多么不同都能够被支持VFS的系统方便地读写、使用；不仅如此，vnode不同于inode，它的编号在整个网络上都是唯一的，因此它可以被用来支持远程文件系统；
操作系统的作用：
OS与CPU之间频繁的进行交互，因此了解CPU的组成非常必要
BIOS是一种固件，固件是一种软件，和普通软件和操作系统都不一样，通常放在不可改的存储器上面；
BIOS是第一个机器启动以后会运行的软件，BIOS主要执行以下的操作：
bootloader是OS的一部分，一般认为OS=bootloader+kernel；
bootloader主要完成下面的操作
关于bootloader和BIOS的区别
Q：为什么BIOS不直接load整个OS？
A：因为BIOS只能load很小的一部分的数据（历史的包袱），并且BIOS需要保持最简化的功能（固件最简化）；
实模式和保护模式的区别-历史的包袱，因为硬件不断演化，操作系统需要兼容，甚至硬件之间也要相互兼容；
保护模式能够真正的保护进程的一些信息；
实模式和保护模式实际上是CPU运行的两种状态，实模式下一般只能访问16bit的数据，为了访问更高位数的数据并兼容16bit出现了保护模式；
进程的定义：一个程序的运行时，包含一些权限限制
Q：进程和普通程序的区别？
对一个进程/程序来说似乎独占所有硬件资源，一般进程会分为几个段，其中堆向上生长，栈向下生长
注：这里讨论的地址都是虚拟地址，一个可执行的程序已经指定好了段的大小等信息；
操作系统设计了双模态的概念，即CPU在执行的时候可选择两种状态，其中内核态拥有更高的权限，能够做更多的事情；
双模态由OS和硬件共同实现，其中硬件主要完成以下四部分的功能
特权指令：只有CPU在内核态的时候才能执行
一个不严谨的说法是，影响其他进程的指令就是特权指令
如何执行特权指令呢？让操作系统帮进程执行特权指令，其中系统调用是操作系统暴露给用户态程序的一些接口
如果程序执行了特权指令会被检测到并kill
硬件需要提供的第二部分是内存保护，使得地址是隔离的
分段法是最简单的方法，每个程序使用bounds大小的内存空间，缺点是共享、碎片化问题
因为分段存在很大的问题，所以现代操作系统一般都使用分页的方法；
由硬件(CPU)来执行虚拟地址到物理地址之间的映射，由软件OS来决定映射的策略；
OS和CPU的中间体就是页表，页表存在内存中；
一般多个进程的kernel代码都是相同的，映射到同一块区域
Q：为什么内核代码存放在高地址空间？
A：历史的包袱--方便进程用户态从低地址处理
上下文切换，主要讲解用户空间和内核空间的上下文切换（这个话是老师的原话，但是我感觉和上下文切换完全没有关系）
有三种可能CPU会从用户态切换到内核态
中断处理对用户来说是不可见的，对进程的状态不会影响；
中断向量表
中断向量表是在实模式下使用的，中断向量表一般保存在一个固定的位置
中断描述符表
中断描述符表IDT是在保护模式下使用的，有更多专有名词，其中的每个元素称为一个门，一共有256个门，中断描述符表不是在固定的位置，通常其位置存放在一个寄存器IDTR中，该寄存器的值可以动态加载
Q：具体如何从中断发生定位到中断处理程序？
A：首先IDTR会指向中断描述符表的开始位置，接着根据中断号找到中断描述符表中对应的项，在项中提取出offset，因为分段的原因可能还需要加上一个基地址，就可以找到相应的中断处理程序
Q：如何知道中断号呢？如何知道现在发生的是第几号中断呢？
A：只有硬件知道，硬件层面会通知这个中断是第几号；
中断向量表和中断描述符表的区别，首先它们的共性是可以实现隔离，所有用户态的代码要进入内核态只有这几道门，这两个表决定了门的数量和种类，因此在写内核的时候只需要保证这几个门的安全性即可
中断屏蔽
不是所有的中断都必须要发生，操作系统可以mask一些中断，有些中断可以屏蔽有些不可以；
中断屏蔽只是推迟了中断的发生，并不是直接忽略的中断的发生；
中断栈
在内核的中断处理程序在处理中断的时候需要栈，这个栈放在内核态（因为用户态的栈会被修改）；
如果没有中断产生的时候中断栈是空的，因为不需要处理任何事情；
操作系统中的中断栈的计算公式
数字1的原因是第一次中断就是我们常见的中断，将用户态转换为内核态，一般情况下可以在一层中断的基础上嵌套实现第二层中断，这个中断可以共享第一次的中断栈，二第三层中断一般不被允许直接导致OS重启；
每一个线程或者进程都会有一个自己的中断栈，是为了使得操作系统能够更好的处理不同进程/线程的中断（多个进程可能同时产生中断）
如下情况（或者方式）会导致CPU从内核态切换到用户态
X86使用的是分段
其中CS寄存器的值只能使用以下指令改变
当中断/异常/系统调用发生的时候，硬件会进行如下操作
Q：为什么需要临时寄存器？
A：因为第三步切换栈是修改SS:ESP的地址，如果没有临时寄存器就根本不能保护现场即回不去之前的状态了
硬件处理之前的栈状态
硬件处理之后的栈状态
中断发生的时候硬件会做上面的事，OS会做什么操作呢？
Q：专门的寄存器指向当前栈，但是为什么没有专门指向堆的寄存器？
A：因为不需要，指向栈是因为OS需要用到栈，但是堆是用户自己操控的；
操作系统给应用/用户提供了非常多的功能
在Windows下通常使用CreateProcess这个API来创建进程
在Linux中会使用fork()和exec()函数创建一个新的进程；
fork没有任何参数，会完全拷贝一个当前进程，返回值为0则是子进程，父进程会得到子进程的进程ID，是一个大于0的值，父进程和子进程之间唯一的区别就是返回值不同，父进程和子进程不共享地址空间，但是它们的地址空间的值完全相同；
Q：为什么父进程和子进程的环境相同还需要拷贝再赋值？
A：实际上这涉及Linux的优化问题，并不会是简单的值拷贝；
exec将会从磁盘下载并执行一个程序，需要注意的是exec不会创建任何新的进程；
并不是每个fork后面都需要紧跟一个exec，例如浏览器中打开新的tag实际就是打开一个新的进程，但是这个进程实际上是和原来的进程使用的同一套代码，就不需要再load一个新的程序
Linux中除了fork()和exec()以外，还有其他辅助函数
OS除了提供进程管理功能，还提供I/O功能；
计算机有很多I/O设备，最简单的管理方法就是给每一个设备一个系统调用，但是Unix将所有的设备抽象为文件，好处是接口简洁、统一；
有文件就有相应的结构体来描述，Unix中使用文件描述符来描述，文件描述符本质上就是一个int类型的值；
怎么使用int值来描述文件？操作系统有一个文件描述符表，每一个文件描述符可以在里面寻址到相应的文件的信息；
需要注意的是每个进程都有自己的文件描述符表，只有打开的文件才有文件描述符（文件描述符是open函数的返回值，一个文件可以被open多次）；
注意点：
open
close
对应用来说操作系统看起来就是提供了很多的函数（系统调用）而已，设计系统调用难点是如何保证内核态的安全性，Unix中的系统调用基本都是如下流程实现
Q：如果不拷贝，内核可以直接访问用户态的参数吗？
A：当然可以，内核的权限高于用户；
Q：为什么参数一定要拷贝到内核的内存中？
A：直接使用会出现一些问题，本质上就是用户态的代码随时可能被改变不安全，所以一般不建议；
Q：可不可以先检查再拷贝？
A：如果在检查以后再拷贝进来就没办法修改了（内核态的代码不能修改），容易导致系统漏洞；
Q：为什么需要线程？
线程定义：一个可以被单独调度的顺序执行序列，即线程可以随便被挂起、恢复
线程就是同一个进程中不同的函数，可以交替执行，线程是操作系统最小的调度单位；
线程之间不会共享栈，因为栈是执行的上下文，线程是被单独调用的，不能共享上下文；
线程共享地址空间但是不共享栈、寄存器（上下文）；
线程的执行速度是不可预测的，因为它随时可能被挂起（同步问题）
和进程控制块类似，线程也有控制块
Q：一个进程可以有很多线程，那么线程的栈的大小有限制吗？
A：栈的大小实际上和递归的深度有关，在内核中，因为要处理中断所以需要中断栈，但是因为比较简洁所以中断栈不需要很大；
同一个进程中的线程共享代码和地址空间、全局变量，因为线程共享地址空间，所以可能会导致一些危险；
线程如何实现呢？这里循序渐进，先讲内核中如何实现线程，再讲用户态如何实现线程，需要注意的是内核线程永远运行在内核态，其数据也存放在内核空间中，由内核态线程可以扩展到用户态线程；
下面这段代码是一个简单的在内核中创建线程的例子
怎么删除一个线程？只需要把这个线程从List中删除即可，再将相应的空间释放掉
综上，一个线程不能销毁自己！！！解决办法是使用其他线程来帮助自己free掉finished的list中的线程；
主要分为两种切换方式，一种是主动切换，另一种是被动切换（中断、异常）；
注意这里的线程切换不是指CPU状态的切换，因为内核线程只能运行在内核态，这里指的是将一个正在运行的内核线程挂起，运行另一个内核线程；
主动切换的流程如下
实例代码如下
被动切换的流程相对简单
实现用户态的多线程主要有如下几种方法：
假如要实现一个用户态的create_thread函数
第二种方式就是完全使用用户态下的库函数，整个过程没有内核的参与，库维护了用户空间所需的一切状态；
Q：如何使得在用户态下实现并发的多线程？
Q：用户态线程如何切换程序指针或栈指针呢？
A：用户态线程改变PC下一条指令使用jump指令实现，改变栈指针很简单，直接修改寄存器的值即可；
下面总结用户线程和内核线程的异同
用户看到的所有地址都是虚拟地址，从虚拟地址到物理地址有一个转换的过程，被称为地址翻译，地址翻译并不仅仅做翻译的事
地址翻译的目标如下
地址翻译需要硬件和操作系统同时协作实现；
地址翻译主要有两种实现方式，分别是分段和分页，一般分段都使用16为操作系统，分页一般使用32位操作系统进行讲解；
在分段和分页同时存在的情况下，虚拟地址经过分段后称为线性地址，线性地址经过分页过后才是物理地址；
在实模式下不存在分段表
X86规定程序只能有6个段，并且规定了每个段怎么使用，默认会添加段前缀
最多能访问220的物理地址，并且同一个物理地址可能有多种组合情况；
保护模式下，分段表被称为GDT全局描述符表和LDT局部描述符表
分段很强大，主要有以下功能
分段最大的问题就是很容易产生碎片化
分页和分段最大的区别就是分页将物理地址分为一个个固定大小的页，以页位单位进行内存的映射；
页表用于实现虚拟页和内存页之间的映射，记录了每一个虚拟页对应的物理页；使用页不再需要bound这个限制，因为页的大小已经固定；使用分页后，在虚拟地址看起来连续的页在物理地址上几乎是完全随机的；
分页的好处：
下图是一个最基本的分页的地址翻译的过程，使用的是一级页表
当我们限定地址的大小为32bit的时候，需要会计算页表和物理页的大小
可以看到一个页表大小为4MB，很多进程甚至都用不到4MB，而且每一个进程都需要这么大的页表，无疑会造成浪费，所以现代操作系统出现了多级页表
Q：本质上二级页表并没有增大逻辑地址或者物理地址，二级页表是怎么节省空间的呢？
A：这是因为借助了稀疏性，只调用需要的页表即可；
Q：在上下文切换的时候（指的是进程），什么也需要切换？
A：CR3寄存器的值，也就是页目录的起始地址；
每个进程和内核都有自己的页表，因为地址隔离，但是线程是共享地址空间的所以线程共享页表（页目录同理）；
整个翻译的过程是由一个被称为MMU的硬件完成，不是操作系统实现的（因为操作系统实现地址翻译非常缓慢）；
PS：页的大小非常重要，页太小会导致页表非常大（页变多了），页表太大会浪费空间；
简单理解缺页中断就是CPU/MMU在进行映射的时候发现内存中并不存在与逻辑页对应的物理页；
出现缺页中断的情况：页表项不存在（最后一个比特为0）、权限不足、页表不存在（最后一个比特为0）；
这个概念的全称是Copy-on-Write，是Linux中节省空间的做法
下面给出几道练习题
4K是指一个物理页的大小是212bit，一共有多少个物理页呢？一共有210*210的物理页框，故计算得到最大寻址空间为4GB
Q：操作系统只能使用虚拟地址，那么操作系统如何知道一个虚拟地址的物理地址？
A：使用自映射，需要页表项的物理地址就映射一次，需要页目录项的物理地址就映射两次；
实际上分段和分页是可以合并使用的，逻辑/虚拟地址经过分段称为线性地址，线性地址经过分页之后变成物理地址
缓存是一个非常广泛的概念（有各种各样的缓存），本质上是一段存储，访问速度非常快
为什么需要缓存？存储器的提升并没有CPU的迭代速度快，缓存就是用于填补这部分的gap的
缓存可以构成如下架构
常见的缓存如下
地址翻译最大的缺点就是使得内存的访问变慢；
TLB是在MMU内部的一个加速地址翻译的缓存，为什么地址翻译可以被缓存？因为局部性原理：
TLB中的翻译实际上是以页为单位，换句话来说，地址翻译都是以页为单位；
TLB能够很好的工作的原因就是因为其命中率很高；
TLB的工作过程非常简单：可以将TLB理解为具有如下三项的列表，分别是虚拟页号（之所以不是虚拟地址是因为地址翻译是以页对齐，因此只需要操作页）、物理页号和访问权限
TLB不命中的原因：页没有被访问过、TLB内存有限等其他原因
如何解决TLB的Miss呢？当我们按照完整的地址翻译过程找到虚拟地址对应的物理地址之后，需要将其更新到TLB中，现在基本上都让硬件来完成更新的操作（因为硬件速度快）；
TLB最重要的一点就是需要保持一个非常高的命中率，如何进一步提高TLB的命中率呢？页大一点还是小一点更加容易命中？因为大一点可以导致页更少，因此只需要缓存更少的页即可，那么缓存命中的概率就更大；
超页：向操作系统申请多个连续的极其大的页（物理地址上连续），这在一定程度上能够提高局部性原理，但是页变大了不够灵活浪费空间，并且物理页需要连续增加开销；
一个超页在TLB中是对应了一个TLB项（如果对应多个TLB超页就没有存在的意义了，超页可以看作是多个页的集合体）；
无论是什么缓存（包括TLB），都需要具备一个非常重要的概念，即一致性，原因就是避免缓存和内存的值不同；
主要在一下情况需要保持一致性：进程上下文切换、权限变换、TLB击落（多处理器访问）；
进程上下文切换
权限变换
当改变了页表的权限（权限降低，从可写改变成只读），解决办法是直接将整个TLB或者单个的TLB项丢弃；
权限增大的时候是不需要做什么事情的，miss之后重新去页表中更新TLB即可；
TLBShutdown
在多处理器系统中，如果多个处理器在跑同一个进程的多个线程（内核线程），它们的页表是相同的（因为是同一个进程），但是它们的TLB不同，因为TLB在CPU的MMU中，多处理器意味着多个CPU当然TLB也就不同，那么当一个处理器将页表改变过后，它不仅需要修改自己的TLB，还需要告知其它处理器对TLB进行修改；
此处的Cache就是CPU和内存之间的告诉缓存，块是Cache中的单位，块的大小取决于硬件的设计；
主要分为全相联映射、直接映射和N路组相联映射，理解这几种映射需要做题；
上述两种方法都应对的是Cache写命中（也就是要修改的单元在Cache中）；
Q：Cache中的地址是虚拟地址还是物理地址？
A：从图中可以知道是物理地址（从MMU中出来的都是物理地址）
如果Cache的命中率高但是TLB的命中率低则还是不能很好的协同工作，所以需要考虑如何使得TLB和Cache能够协同工作
一个进程需要工作，一般需要一块内存，该内存的大小就是该进程常驻在内存中的大小，过大浪费，过小需要不停的换入换出；
本节课主要讲解的是内存实际上也可以作为磁盘的缓存；
这种做法有一个好处就是仿佛内存是无限大的（因为磁盘一般是足够大的），如何实现呢？借助页表以及Pagefault（缺页中断是很广泛的概念）完成这种缓存的设计；
TLB是虚拟地址和物理地址的缓存，Cache是CPU和内存之间的缓存，内存是CPU和磁盘之间的缓存，后两者都是基于前者工作的，Cache的单位是块，内存的单位是页
内存映射文件本质上是和需求分页的思想是相同的（甚至可以说是一回事）
一个程序要使用磁盘的一个文件，最朴素的方法就是直接将文件读进来，第二种方法就是内存映射文件，就是操作一块内存等价于操作该文件
内存映射文件的好处是不需要read文件所有的bit，可以访问文件的任何位置
实际上这一节的页的置换策略和前面的Cache置换策略很相似，分别是FIFO、MIN(LRU的理想版本)和Random；
时钟算法-最适合需求分页的替换算法，本质上是在最大可能上逼近LRU算法
关于Usebit，1->0是操作系统完成，0->1是硬件完成
具体工作流程可以看视频理解，需要注意的是指针不会随着当前访问的页移动（即访问页的时候不调用指针旋转），只会在置换算法实施（即发生PageFault的时候）的时候才转动
时钟的如果快速过快即一直在转，这是一个坏现象，表明一直在置换说明系统过载；
可以对时钟算法进行改进，也就是将页面的访问的机会从1改成n次，n越大理论上越逼近LRU，但是n过大就一直找不到一个合适的页导致一直旋转，一种解决方法是针对性的设置，比如替换脏页的开销大（因为要写回），所以对于脏页和干净的页的n可以不同；
调度的评价指标主要是：
假如对任务的先后次序进行调整
短任务优先的缺点是导致饥饿，进而影响公平性，并且在实现的时候实际上并不知道一个任务需要执行多久；
不是所有的任务都是平等的，前台应用优先级高于后台应用，同级之间可以使用RR等调度算法；
优先级导致的问题：低优先级可能会被饥饿，或者高优先级被翻转（场景：一个高优先级的任务依赖一个锁，当前锁正在被低优先级的任务使用，但是因为优先级不能调用低优先级所以高优先级的任务和低优先级的任务都会被卡住）；
解决严格优先级调度的问题一种方式是动态优先级调度算法，我们将在后面反馈队列中介绍；
前面的调度算法一般都只优化了一个方面（最多DDL、最公平...），MFQ几乎是兼顾了所有的优点，但是都不是很优秀；
基本思想：有多个队列，每个队列有不同的优先级，同级队列使用同一的调度算法，与严格优先级队列的区别就是CPUBound的任务会从高优先级队列一直降到低优先级队列，而I/OBound的任务会一直维持在一个高优先级的队列中；
MFQ另一个显著的特点是高优先级队列使用RR，低优先级队列使用FCFS，之所以这样设计是因为前台应用需要尽可能让短任务快速完成；
彩票调度，不同之处是有了一些随机性（有时候随机可能是一件好事，实现比较简单）；
基本思想：给每个任务一个彩票，在调度的时候刮奖，刮到谁（或者定制一个规则）就调度哪个任务；短任务会有多一些的彩票，长任务少一些的彩票，为了确保不会饥饿，每个任务至少都会有一个彩票；
需要注意的是彩票刮完之后不能丢掉，不然彩票少的就不会再执行了（一次没执行完还需要执行第二次）；
调度算法-实时调度，针对实时操作系统，传统操作系统考虑的调度指标是效率，实时操作系统需要保证实时性，也就是可预见性
前面讨论的问题都是基于单处理器，多处理器调度会遇见诸如锁、Cache等问题
这是整个操作系统在线程层面的框架，存在多个进程，每个进程中又有多个线程，线程之间有自己的CPU状态，但是线程之间共享地址空间和I/O；线程之间会有一个CPU调度器来对它们进行调度
为什么需要线程同步？从开发者的角度来看似乎每个线程都在一个单独处理机上，也就是似乎有无限多个处理机，从开发者的角度来看线程是不会发生中断的，实际上应该是右边的情况：少数线程在run，其他线程在等待，这意味着线程的执行速度是不可预测的，这就可能出现一些同步的问题
既然线程合作会产生同步问题，为什么还需要线程合作？线程合作有如下好处：
独立的线程不会出现问题（实际上并不存在完全独立的线程），但是合作的线程会出现不确定性和不可复现性，不确定性错误是非常难被找到并且不可被复现（两台机器几乎不可能出现同样的同步错误状态），因此我们很有必要使用锁这些方法来保证线程之间的状态的同步，下面是一些线程同步问题的具体例子
除了上面出现的问题以外，因为编译器会进行一定程度的优化，修改顺序以最大化并行性，但是编译器只能保证在一个线程里面的依赖是正确的，不能保证多个线程的依赖顺序（编译的时候当然不知道有什么程序会和该程序一起运行，但是这不属于线程同步的问题了）
关于线程同步，有三个概念非常重要
有些操作可以在最基本的层面上解决一定程度的同步问题，比如原子操作，对于大部分机器来说，内存的访问是原子的（load和store指令）；
但是并不是所有的汇编指令都是原子的，本质上由硬件决定（只有硬件能够支持原子操作，所以不能随心所欲的认为哪条指令就应当是原子操作）；
下面我们再展示一幅图，表明了为什么一定要在中间加锁这些API而不是直接使用原子操作，因为开发者直接使用底层的原子操作来实现线程安全的话是非常复杂的
锁：阻止某人做某事，上锁的资源只能被等待才能使用，所有的同步问题一定会引入等待；
问题：如何在硬件提供的有限的原子操作的基础之上来实现我们需要的锁，进而实现互斥；
锁最基本的两个操作（这两个操作都是原子操作，因为我们在实现的时候就是按照原子操作的目标来实现的，基于硬件提供的最基本的原子操作实现）
使用加锁解决牛奶问题
原理：通过加锁和解锁保证了中间代码的原子性-没有两个线程可以同时执行这段中间代码，这段代码被称为临界区
锁的特性如下
锁的实现：在单处理机上最简单的实现就是加锁的时候将中断关闭，释放锁的时候将中断打开；这个方法的问题是中断不能随便开关，不能让用户线程来控制中断的开关；
关中断和开中断之间运行的代码都是操作系统的可信任的代码，而不能是未知的用户代码
之所以需要关闭中断是为了避免两个线程同时进入临界区；
另一个重点是中断什么时候应该被打开，一般来说中断总是在代码的最后打开，中断在中途打开很可能出现问题
使用开关中断实现锁在多处理器的情况也可以实现，即使得所有的处理器一起中断，但是开销太大了（多处理器每个处理器都有L1缓存，需要注意缓存一致性），所以实现了更多的基础的原子操作，这些原子操作的集合被称为RMW；
使用RMW既可以在单核也可以在多核的情况下实现锁；
这里只介绍使用t&s实现自旋锁，基于test&set实现的自旋锁的缺点是存在忙等待或者优先级翻转的问题，这也是自旋锁的名字的由来
对于用户来说自旋锁的开销太大，所以可以进一步的优化（尽管前面我们说最好不要对锁进行优化），这里的优化主要是解决了busywaiting的问题，并且会主动放弃锁的持有权
事实证明条件变量优于信号量以实现锁，锁在某些情况下会出现拿着锁空等（死锁）这种问题，在等待期间我们应当将锁释放掉，条件变量就是用来做这个事情的；
条件变量有三个函数
wait函数的传入参数是一个锁，调用wait函数会释放掉这个锁，同时将这个线程放在一个等待队列中，直到接收到一些特定的信号才会唤醒这些等待线程，当这些线程被唤醒之后会重新尝试获取这些锁，注意获取锁的操作是在该函数返回返回值之前，这意味着wait函数可以理解为在实现过程中将锁丢掉再将锁拿回来，效果就是再wait前持有锁，wait之后仍然持有锁
下面使用条件变量解决生产者-消费者问题
假设这里持有锁但是需要等待生产者队列产生产品才能工作，所以我们再等待的过程中调用wait释放掉锁，当生产者进程生产出产品后会发出signal进而唤醒并归还锁，执行之后的操作
如何实现删除操作？此处需要注意一定会考试
使用条件变量需要注意以下两个原则
信号量可以理解为锁的一个更加强大的实现，但是信号量被认为是一种不太好的同步机制，反之只需要锁和条件变量就能够实现所有的同步
可以认为信号量是一个整数值，这个整数值不会是负数，信号量整数有且仅有两种操作-P、V
信号量和锁很像，但是更强的功能在于锁只有两种状态，但是信号量可以使用多个值表示多种状态；
信号量的特点：
使用信号量解决生产者-消费者问题，需要设置如下三个信号量
对于上述Producer中的第一条和第二条代码如果交换顺序会导致死锁，这也是为什么信号量不太好的原因-太容易死锁
Q：在锁的各种实现过程中，加锁和释放锁操作是否都需要陷入内核态？
A：首先开关中断一定需要陷入内核态，但是使用test&set不是特权指令所以不需要陷入内核；
Q：队列锁是什么？
A：队列锁实际上就是对自旋锁的改进，在等待的时候会进入等待队列；
Q：中断处理程序可以使用自旋锁吗？
明天再重新听一下这部分的实现，一定要会写代码；
主要实现RWLock类以及四个函数
Q：饥饿和死锁的区别？
关于银行家算法和哲学家进餐问题看王道和blog，银行家算法一定会考；
内存是非持久性存储设备，外存是持久性存储设备；
下面主要介绍两类二级存储器（注意除了主存储器以外的其他外存储器都是二级存储器）：
关于磁盘的构造一定要搞清楚，磁盘的计算等是考点；
磁盘容量计算公式
关于磁盘的计算题主要如下
Q：read和write系统调用的区别是什么呢？
A：read和write在形式几乎相同，对文件系统来说，写和读的区别在于写可能会有一个buffer在kernel中，写的时候先写入缓存再写入内存；
对上面的I/O系统做一个细致的划分就可以得到I/O栈（注意其组成）
什么是MMI/O呢？实际上是操作系统管理I/O设备的一种方式，需要注意的是MMI/O和PortI/O是对应的，前者只需要使用常规的读写内存的操作就可以操作I/O设备，但是后者只能使用单独的特殊命令来读写I/O设备；
文件系统主要有以下的功能
分角度看待文件系统：
注意：一切文件系统的操作都是以block为单位，一个文件就是一个block集合；
文件和目录是文件系统管理磁盘的两个手段：
将磁盘组织成线性扇区队列的方式有两种：
文件系统的底层是存储设备（一般考虑块设备而不是字符设备）
文件系统的工作流程如下
打开一个文件实际上就是做了一个文件名的解析，主要流程如下
之后的所有操作都是在句柄上进行
目录的作用如下-将文件名转换为文件号
目录一般是树状结构，根目录一般都是操作系统预先设定好的值
将文件名映射到磁盘号需要做多少次磁盘的访问？
文件的主要功能就是讲述如何从文件号映射到真正的数据块；
这里直接拿常见的三种文件系统举例说明
FAT表的长度和block的数量相同，每一个文件号会指向其中一个block
访问其中的datablock的方式类似于指针解引用
Q：FAT存在哪里？
A：FAT既可以理解为一个文件系统，也可以理解为一个表，FAT存放在磁盘中固定的特殊位置上；
Q：FAT中哪些磁盘块是空的？
A：FAT值等于0就是空的；
Q：如何在FAT中尽量保证局部性呢？
A：FAT使用NextFit算法，在Append一个文件的时候寻找现在文件末尾最近的空闲block，相应的，FAT会产生零碎化的问题，尽管有整理碎片的方法，但是效率太低了
Q:如何读/写一个文件？
A：直接按照FAT表blockbyblock依次读取即可；写数据就是先append之后再修改FAT表；
Q：如何格式化一个磁盘
A：格式化磁盘，本质上就是清理磁盘然后清零FAT表，当然快速格式化就是直接清空FAT表
关于FAT文件系统，存在很多问题
FFS文件系统的特点：
理解FFS只需要理解下面的图即可
FileMetadata是文件的元数据和基本属性；
DP表示直接索引，表示其中每一项直接指向其中一个datablock，和FAT相同-inode中有12个直接索引，因此可以寻址的范围是48kB，如果文件小于等于48kB，则直接使用直接索引就足够；
IndirectPointer一级间接索引指向的datablock不存储文件的数据，只存储索引，每个索引指向的datablock存储文件数据，二级索引和三级索引类似，要会计算其容量；
一个一级间接索引：假设一个datablock是4kB，地址都是32bit，则一个datablock可以存储1024个索引，每个索引指向一个datablock，则寻址范围为4kB*1024=4MB
FFS文件系统的特性
FFS对于稀疏文件可以良好的存储，少占用空间；
FFS还是使用bitmap管理空闲空间，0/1表示是否空闲，bitmap存放在固定的位置
Q：inode究竟存放在哪里？
A：最早的时候存放在磁道的最外面，问题就是距离datablock可能会有点远，现在存储inode会根据目录的具体结构进行存储；
Q：FFS文件系统如何保证局部性？
具体设计：同一个目录/文件下的所有文件尽量放在同一个块组中，因为同一个目录中的文件被打开的概率更大；当创建一个新文件的时候，在文件所属文件夹的块组中寻找一个inode，除非块组中已经没有空闲的inode了；需要注意的是不能将所有的目录放在一起，不然所有的文件都是在一个块组中没有意义，还是适当做一定的区分；
Q：如何在一个块组内部分配datablock？
A：思路是在块组中寻找第一个空闲块，这个方法能很好的规避碎片化，被称为FirstFit算法，需要注意的是FFS中永远不会将磁盘占满；
FirstFit算法的好处，因为前面的文件将空隙填满了，所以后面的文件几乎都会是连续的
最后做一个关于FFS中文件号转化的题型
之所以上面默认直接取inode中第一个项，实际上也是因为一般只需要一个对应的block就能存储所有文件/目录
其实还有一种可能是你这个地方没理解对，实际上应该是inode中存储了信息，是可以直接找到912号block存储了foo的，反正不可能是直接在block中寻找
关于FFS的优点和缺点的整合
NTFS中最重要的数据结构是主文件表MFT，主文件表中的每一项都是1KB大小，有时候可以直接存储数据而不仅仅只是存储索引；
MFT中条目的属性分为常驻和非常驻，常驻的意思就是直接存储在MFT表中，非常驻表示其属性的值存储在MFT指向的空间中
NTFS主要分小文件结构、中文件结构和大文件结构
对于大文件，假如文件的碎片化实在是太多了，就需要加入间接的索引；
NTFS中文件的元数据并不是存在文件的本身，而是存储在一些固定的文件中，即这些文件是专门存储MFT这些结构的；
前面的文件系统都是把重要的结构简单的存放在固定的位置，但是在NTFS中将这些结构本身也作为文件来管理，好处是统一管理；
Q：假如MFT本身是一个文件我们如何读它？
A：因为读文件本身就需要MFT，但是MFT本身又是一个文件，无限循环，一般会直接约定NTFS的卷的第一个扇区指向MFT的第一个条目；
Q：NTFS如何保证局部性？
A：因为是变长的，所以使用bestfit，找到最小的合适的datablock即可
虚拟文件系统VFS用于给用户提供统一的接口，VFS并不是只提供统一的API接口，实际上还进行其他工作，比如协调Cache、路径查找等；
前面一直在讲文件系统功能和效率如何优化，本章讲解如何使得文件系统更加可靠；
为什么需要可靠性？因为存储设备本身可能并不可靠（断电等行为），所以文件系统需要保证可靠性
Q：可靠的文件系统的可靠，指的是什么？
A：要么操作全部完成，要么一个操作都没有执行-即保证在各种错误情况下都能可靠，这与同步问题的原子性操作其实很类似；
主要有两类技术保证文件系统的可靠性：事务和RAID冗余阵列
并不是所有的文件系统都使用事务，但是基本所有的数据库都使用事务；
一个事务本质上就是一系列原子的行为，核心概念就是将两个consistent状态转换，不会出现中间状态
一个事务的行为主要分为三个步骤，beginupdatescommit
事务保证了四个非常重要的属性
怎么实现一个事务？一个非常重要的手段就是logging，日志的思想非常简单，先将所有需要做的update写入log，写完log再写存储器；
注意：log中是append-only，不能修改
下面这个流程是事务的具体实现，被称为Redologgiong
其中添加commitrecord的操作可以理解为一个原子操作
性能方面，log中记录了几乎所有的操作和数据的修改，本身就要写磁盘，现在还要写log，这将导致速度慢；
这也是为什么有些文件系统不采用事务的方式（实际上因为log是顺序的所以其实对性能影响也不会很大）
事务中的顺序非常重要
现在主要有两种实现事务的方法-Journaling和Logging，其中Journaling只会对metadata的数据进行事务操作，而Logging会对所有的数据进行事务操作，这是为了在效率和可靠性之间做一个权衡；
RAID的整体思想非常简单，即将数据存储在多个Disk中，即使一个磁盘坏了也可以通过另一个磁盘恢复，恢复方法有多种，恢复方法既可以在硬件层面也可以在软件层面；