操作系统【清华慕课笔记】
操作系统计算机是由硬件构成的，如果我们直接去操作的话，需要使用汇编，众所周知十分的麻烦，windows，linux操作系统就是为了我们方便去操作硬件而提供的系统级别的软件Shellshell脚步其实也是代码，我们也可以编写shell，比如ls，makedir这样的但是这些能够控制操作系统。线程并行是需要多cpu支持的。即使在操作系统层面，也无法做到同时访问一个资源。特征并发操作系统肯定要支
操作系统
计算机是由硬件构成的，如果我们直接去操作的话，需要使用汇编，众所周知十分的麻烦，windows，linux操作系统就是为了我们方便去操作硬件而提供的系统级别的软件
Shell
shell脚步其实也是代码，我们也可以编写shell，比如ls，makedir这样的但是这些能够控制操作系统。
线程
并行是需要多cpu支持的。即使在操作系统层面，也无法做到同时访问一个资源。
特征
并发
操作系统肯定要支持多个应用程序同时执行的，但是系统肯定只能把资源分派给少部分，所以就需要看操作系统的管理和调度机制了，我以前了解过window是抢占式的，linux是时间分片，但是不得不说，还是jvm的牛逼，自带优化。
共享
同一个资源肯定是互斥的，但是不同的资源肯定要实现共享。
虚拟
把硬件虚拟化成程序容易理解的概念，比如把CPU虚拟化成进程，把磁盘虚拟化成文件，把内存虚拟化成地址空间，让每个用户感觉自己独占了一台计算机，计算机只为我而服务，想要内存你操作系统就能给我分配。
异步
异步你要确保一个事情，即使异步了，你也得确保程序的执行是正确的。
内部组件
CPU调度器，物理内存管理，虚拟内存管理(为上层应用提供一个尽可能大的而且独立的虚拟内存管理)，文件系统管理，中断处理与设备驱动(是实现功能最核心的部分)
难点
它的代码量很大，window xp就有4500w行的代码，它有很多容易出现错误的多线程操作，它还需要去操作硬件，它要求必须是高效的，而且必须是安全的，这么大的系统，需要做很多的权衡
系统接口
什么是接口？
连接了两个东西，好像还真是这样的，我们在使用接口的时候，肯定是为了给别人用的，我们在使用dubbo的时候，就是把接口单独抽离出现了，这个两个系统就可以联合起来开发了。而且最关键的一点是屏蔽了底层的细节，你只需要知道最终的实现就可以了。
图像界面怎么实现的？
有一个队列，鼠标和键盘的操作都会放到这个里面，然后应用程序从这个队列里面拉去内容，然后执行，就向回调函数一样，底层肯定是有一个switch-case的实现。
借助这个思考了消息队列的两种推送，这个是发布订阅类的推送，其他人订阅之后，消息队列接受到消息之后，主动推送。另一个是订阅者主动接受。最不好的肯定是订阅者定时查询，那样会做很多浪费。发布的好处在于消息量比较少的时候，所做的所有操作都是有用的，如果消息量比较大，订阅者可以采用自己拉取消息的方式，根据自己的承受能力合理的安排。另外，我突然想明白，其实如果我们定义一个简单的协议，基于jvm内存和socket做一个简单的消息队列，其性能也是要比tomcat好的，所以这个是消息队列可靠的原因之一。
操作系统的接口是什么？
由系统提供的函数，比如open()打开文件或目录，让代码去直接调用系统层面的接口。
为什么我们的程序不能直接操作内存？
因为不安全，如果我们的程序可以直接操作，那么其他的应用程序也可以直接操作，比如操作系统有保存用户名和密码的部分，如果其他程序可以随意访问，那么我们的安全肯定是受到巨大挑战的。就比如jvm实现了内存访问的安全，java是一个非常安全的语言。
怎么实现不让我操作呢？
大家如果都是软件的话，谁也限制不了谁，就向黑客攻防的无尽升级一样，但是如果我可以从另一个角度来看，我们完全脱离这个圈子，从更加深层次的角度来看，比如我们可以通过硬件来做实现，区分内核态和用户态的隔离。比如，我们可以采用内网，甚至自定义协议，让他们现有的破解工具和手段全部都失效，有的时候，加密肯定不是万能的，既然存在通信，那就必然存在被破解的可能性，我们唯一能够做的就是，增加破解的成本，让破解的成本高于他们想要获得的利益。
我们怎么去学习这个思路呢?从权限划分的角度思考一下吧，低级有的权限高级一定有，那么我们最好直接用一个数组来判断，当我们写权限枚举的时候，就应该考虑到，一个正常的枚举至少要扩充一个数字标号的字段，然后还要重写spring的一类转换器，当用户的权限发生变化了，我们可以随意的改写这些数字，然后在数据库里面改一下就行，如果你不想让数据改的话，你就得用维护一个角色表，然后用id来关联角色，这样两者就解耦了，我改了中间插入了一个角色，那我只需要在数据库里面插入在新的角色，然后调整一下他们的编号，这个其实对整个业务都是没有影响的。
操作系统在实现这个的时候，就是在执行代码的时候判断它属于哪个段，如果这些程序段是我系统内部的，但是由用户来操作的，那么直接就不行。
那我就是想实现这个功能怎么办呢？
用户程序中包含一段包含int指令的代码，中断则是进入系统内核的唯一方法，中断：CPU不再接着（刚执行完的指令）向下执行，而是转去处理中断信息。内中断：由CPU内部发生的事件而引起的中断。外中断：由外部设备发生的事件引起的中断
插一句，个人感觉面向对象比面向过程好的一点，当作为第三方包的时候，面向过程你需要了解这个库提供了哪些函数，需要记忆的比较多，但是面向对象，你只需要知道几个核心的类，就可以使用几乎整个系统功能了。
启动过程
和sping boot的对比，操作系统需要指令才能执行，但是这个时候，指令肯定不是在内存中的，我们就需要从硬盘中读取，这个点和spring boot很像，他指定了所有的启动配置类都放在一个共同的位置，如果在这个位置下的话，就加入自动配置阶段，spring boot就是用了这种约定，约定是一个很好的东西，可以减少我们的代码量。
操作系统把系统代码加载到了内存中，而spring把bean注册到了容器中，两者都是为了方便管理。
取指执行
取指：取出指令，从内存中取，这样可以保证计算机可以按照载入内存的代码，执行它可以执行的任何事情，而且不是只能执行特定的事情。
只能执行特定的事情，是因为你的代码是死的，数据是活的，但如果我们的代码可以在运行时不断的形成新的代码，然后执行，那么我们的程序也是活的，这就是jvm虚拟机，这就是反射，这就是动态字节码。
所以，想要了解操作系统，我们首先想要知道的就是，计算机执行的第一条指令是什么呢？CS:IP指向了哪里？
第一条指令
这个肯定是由硬件的设计者来决定的，因为在一开始，你的内存就必须有指令，不然连开始都没有，比如x86，CS=0xFFFF，IP=0x0000，根据寻址，得到的地址肯定就是0xFFFF0，这个就是ROM BIOS，B:base I:input O:output S:system 基本输入输出系统。
操作系统会首先检查RAM，键盘，显示器，软硬磁盘，如果这些过不去的话，后续肯定无法进行了。然后从磁盘的0磁道，0扇区读入0x7c00处，512字节(MySQL刷盘的字节数，就是为了刷盘不需要分开)，这个地方就是操作系统的引导扇区，这个时候，就可以执行操作系统的代码了，开机的时候狂按del就可以进入启动设置节目，可以设置为关盘启动，哦，那也可以从关盘读入内存，然后执行关盘里面的操作系统代码。然后cs就会指向0x07c0处，开始执行指令。
其中，启动设备的信息会被放到CMOS里面，用来存储时钟和硬件配置信息。
回到第一个扇区的代码bootsect.s，它是汇编代码，因为只有汇编代码才能实现对内存精准的控制，而c语言不可以，而且c语言编译之后会产生很多没有什么用的代码。
就是设置了基本指针位置，为指针设置好初始值，然后调用接下来的扇区，此外还为操作系统预留了一段空间，这段空间的是固定的，操作系统随时可以用非常快的方法，把这些内存中的信息读取出来。
setup.s
完成OS启动前的设置，下面的这些都被读入操作系统刚刚自己预留的从0地址处开始的内容，其他的内存就是给我们的应用软件分配的。你注意学习这个思路，我们可以通过特殊的约定，毕竟规则是我们制定的，我们可以把系统的和用户自己定义相互分开。
这些设置就比如读取内存的大小，因为操作系统要帮助我们管理内存等等。
这个程序最后做了一个非常关键的事情，它将我们的系统切换到了保护模式，为什么要切换到保护模式，因为通过cs和ip的寻址，我们访问的内存的能力只能达到1M，而且现在的计算机往往有好几个G，所以我们要解决这个问题，实际上改变的是计算机解释汇编指令的方式。那怎么改变到保护模式呢？cpu是通过一个寄存器cr0来实现的。之后，汇编程序进入了32位，然后调用了c语言的代码，开始了一大推的初始化。
gdt
以前是cs固定，然后通过ip来寻址，但是在保护模式下，setup.s初始化了gdt的内存，cs通过gdt直接获取一段内存，gdt是硬件层面的结构，速度很快，这时候结合ip就可以完成寻址了，同时，我们也发现，表示一段地址的cs:ip组合是固定的了，其实，本来就不应该出现以前的设计方式，为什么要可以用重复的组合表达相同的结果呢。
Makefile
idea帮助我们制定了先编译哪个类，后编译哪个类，而makefile就是让我们自己来制定这个过程的。源文件首先会生成中间目标文件，再由中间目标文件生成执行文件。在编译时，编译器只检测程序语法，和函数、变量是否被声明。如果函数未被声明，编译器会给出一个警告，但可以生成Object File。而在链接程序时，链接器会在所有的Object File中找寻函数的实现
中断
来源于外设，应该过程我们应用程序很难去模拟，因为我们没有这个概念。
异步，随时都有可能发生。
中断过程中，肯定是需要保护现在的现场，然后执行中断，最后还原现场继续执行，这个过程，操作系统已经帮助我们实现了。
在底层有一个中断表，不同的中断号代表不同的外界操作。
异常
是指程序产生了异常，但是呢，单个程序的异常如果影响到我们整个操作系统的其他软件肯定是不行的，这个就需要操作系统帮助它来处理，很想我们的全局异常处理器，不过那个全局是针对mvc的，毕竟它可以返回结果给前端，肯定是和mvc有关的异常。
肯定也是有一个异常的编号，就像MySQL定义的异常和java的异常类，在处理异常的时候，同样需要保护现场，处理异常，恢复现场
系统调用
就是调用系统提供的函数，它也屏蔽了一些底层的差异，方便了程序员的很多操作，很多函数都是功能简单，单一的，这样是为了方便程序去组合。而且这些可以操作的内容是不同的，比如内核态和用户态。
在调用操作系统接口的时候，会触发用户态到内核态的转换，所以为了安全，应用程序的互相调用和调用接口方法采用的堆栈都是不一样的，这个是为了系统安全，不得不牺牲的性能，就像我们总不能为了快放弃了权限校验，或者干脆直接让用户传递自己的id。
而且除了调用堆栈，用户态和内核态要保证内存的安全，所以还要发生内存拷贝，这个过程的开销肯定不少，因为不能通过指针直接访问内核态，所以必须要拷贝。
内存管理
代码肯定是在内存中的，代码就是指令，而且执行代码要求高速。最好梳理清楚一个学习的结构，知道改先学什么，后学什么。
首先，内存是硬件，但地址空间是操作系统抽象出来的软件，我们要学习的是，如何对用户屏蔽底层的差异，让用户很方便的去管理内存
抽象
把内存抽象成逻辑上地址连续的空间，那怎么抽象呢？只是概念上的抽象吗？
保护
多个程序之间不能互相访问内存，要做好这种保护，起到这种隔离的作用
共享
但是，程序之间又少不了数据的交互，所以操作系统要为我们提供一个安全的数据交互的方法，来使不同的程序可以完成数据的交互。
虚拟化
要是内存空间真的不够，我就先放到磁盘上，就比如一些很少用的内存，但是这个过程对用户来说是不知道的。在硬盘上的虚拟内存，真实内存中只有正在运行的程序，比如某个程序处于等待状态，而且这个过程比较长，操作系统就会展示把它的内存写到磁盘中，而内存中都是我们正在运行，而且操作系统自己的内存肯定是在首位的。
物理地址空间，比如内存和硬盘，它确实是有空间的，而且是由硬件来管理的。而且逻辑地址空间是一个程序自己看到的内存空间，它所看到的是一个一维的线性的地址空间。那逻辑地址空间必然会依赖物理地址空间，两者的关联是如何形成的。
函数的名字，变量的名字就是一种地址的指代。比如c程序编译完成后的.o他们都是以0地址开始的，然后把符号换成了具体的数字，但是肯定不止一个.c文件，所以通过link，计算出全局的相对地址空间，然后加载到内存中，Loader(不是操作系统)又一次完成真实运行时地址的分配，从头到尾都是相对，只不过相对的对象不同而已。但这仅仅是逻辑地址，如果对应到物理空间去呢。MMU(Memory Mangament Unit)利用逻辑地址查询物理地址，那这个映射关键其实就是操作系统帮助我们完成的。而且操作系统会帮助我们维护一个表，记录一个程序内存的起始和结束的地址(因为是连续的)，有了这个表，访问额外的肯定是要禁止的。但其实，只要我们提供给用户的指令没有相关的内存权限，比如jvm，它就没有给我们操作内存的权限，所以我们根本就没有办法对系统造成什么影响。
为什么需要虚拟内存，它为进程隐藏了物理内存这一概念，为进程提供了更加简洁和易用的接口以及更加复杂的功能。在顺序读取的时候，内存只比磁盘快一个数量级，所以我们在涉及磁盘的时候，尽量避免随机io。但是随机对内存来说是一样快的，差距就在于内存1ms响应，磁盘需要100s！而且操作系统是以页为管理单位的，就像MySQL的B+树一样，不然那么多内存如果以字节为单位的话，MMU哪得需要多大的空间呀。而且这个和MySQL也是一样的，当进程发现需要访问的数据不在内存时，操作系统可能会将数据以页的方式加载到内存中。它的作用有，虚拟内存可以利用磁盘起到缓存的作用，提高进程访问磁盘的速度；虚拟内存可以为进程提供独立的内存空间，简化程序的链接、加载过程并通过动态库共享内存(这个确实，如果没有虚拟内存的概念，估计很难实现上述要求)。虚拟内存可以控制进程对物理内存的访问，隔离不同进程的访问权限，提高系统的安全性；而且，虚拟空间处理可以使用真真的内存以为，还可以使用物理磁盘上的内容。
思考一个问题，为什么要虚拟这样一个地址空间呢？直接操作硬件可以吗？一开始确实是直接操作硬件的，但是内存分配的问题很大，而且程序运行的地址也不确定。
内存碎片的问题，如何用算法去分配内存空间。我自己想一个，维护一个数据结构，<start,tail>，分配的时候，用贪心算法找最小的，哎呀，不行，会有浪费，万一塞进去之后只剩下一小块，那就完全浪费了，那就先顺序，然后把空闲出来的记下了，如果是正好塞满空闲，或者是空虚的一半，就分配，还是有的麻烦，看看正经的算法吧。
内存分配算法
首次适配
遇到能满足需求的就分配，首先要排序，而且还要合并两个连续的内存空闲块，每次分配和释放完成之后，需要重新维护这个数据结构，我猜是堆。
这是算法的优点是很容易出现大块的内存空间，因为我一开始都逮着小的进行分配。
但是这个和我自己想的那个差不多，而且可以说是一模一样了，哈哈哈，就是容易产生那种小碎片，而且贪心的证据也没有，很想那种n-p完全问题中，用贪心获取了一种接近正确答案的简单实现。
最优适配
在多个空闲的空间中，找一个差值最小的。碎片可以多，但是保证了碎片尽可能的小，不过，差值最小，这明显需要遍历很多东西，或者我排序完成后一个二分，但是这个大小是不断变化的，难道我用要二叉树，那左和右我怎么选择。
最差适配
和上面的相反，在多个空闲的空间中，找一个差值最大的，这其实最大的缺点就是分配大内存很难。
有点失望吧，没有一个能打，还不如jvm呢
压缩试碎片整理
把内存空间整理到一个地方，类似gc的标记整理，但是操作系统肯定不是帮我们回收内存的。
交换试碎片整理
操作系统还有磁盘可以利用呢，如果内存不够话，操作系统甚至可以把暂时不需要内存的程序给放到磁盘中。但是这个开销也是很大的
内存管理
非连续分配
物理地址是非连续的，比连续更容易管理内存，支持共享数据和库(共享类加载)。
分段
段就是指，堆，运行栈，程序数据，代码段(用户代码和库，这样分应该是为了共享)，左边的逻辑地址是连续的，你可能会说，那这样一个溢出了怎么办。其实，他们的物理内存空间是分开的。寻找方式就和汇编的一样，用数组的变量名找到段的地址，这个map是由操作系统来维护的，找到这个实际的地址之后，根据偏移地址，就可以找到我们想要的数据了
分页
这个比分段要常用，但我感觉jvm主要是分段，带着这个问题思考一下，可以看成一个长的段而且是固定的段。
帧是物理页，页是逻辑页，两者就需要转换了！
物理内存被分割为大小相等的帧，(f,o)，f-帧号，F位，共有2F个帧，o是帧内偏移(S位，每帧有2S字节)，它的物理地址是2S*f+o，2S基本是固定的，这样就分成了一页一页的。注意，左边是f，右边是s，小写的是数字，大写的是位数，一开始有多少位，并不重要。9-bit（512 byte）大小的页帧，512=2^9，这个9就是S，大S。
逻辑内存(p,o)，通过一个页表，由p找到f，然后通过o定位到实际的空间
页表
是一个很大的数组，根据p能快速找到索引，然后有3个标志位，前三个是标志位，后面是对应的物理地址f，如果是这样的话，我设计标志位的时候，用一个数字就可以全部表示了，根本不需要那么多boolean，但是可读性很差。
这么多数据，根本无法存储！时间和空间就是我们最大的问题，解决思路有两种，一种是缓存
TLB(Translation Look-aside Buffer)
虚拟机好像没有这个概念，这个指的是我们在访问内存的时候，肯定有些内存的访问是十分频繁的，所以，我们才用这个CPU中的快表TLB来缓存这些常用的数据，这个是为了提速，实际上我们看，内存并没有减少多少，而且还增加了，此外，TLB也不是数组，更像Map，但是基于CPU硬件，所以速度很快
多级页表
和MySQL的b+树很像，属于以时间换空间，不然空间大的离谱。那为什么多级页表就更加省空间了呢？或者说，我在处理redis的时候，如果需要保存的内存真的很大，我是否可以借鉴这种办法。
不知道你是否记得，在以前的页表中，有一个标识位来代表是否存在，这显然是极大的空间浪费，但是索引就可以解决这个问题，如果让索引来决定指向哪个页，那么这些空页就不需要索引过来了。
我们思考一下，为什么会有不存在的项，这个就像是我们电脑的内存，一般占用率只有30%左右，很多地方都是空闲的，而且即使分配了那么多空间，比如jvm，它也不一定会全部占用，所以明显这个里面有太多的无效数据。所以，我们采用上述的方式可以减少很多内存占用，那，为什么需要多级呢？二级就能不去索引无效的页，其实是为了解决空间的问题，而且是为了解决索引页空间的问题，因为物理页的数目是不会改变的。假如有1000个实际的页，页索引，每页索引10个，那我需要100个二级索引，如果是三级索引呢？我需要10个三级索引，这样的空间效率真的高吗？应该是数据长度的宽度。
假如我们数字的范围是1-100，如果一层索引，那只能表示100个，如果二层索引那么就是100*100个。
反向页表
我们知道一个页对应多个物理内存，但其实有的时候，一个页里面的物理内存并没有全部用到，所以，如果我们用物理内存作为key，页号作为value，又会节省很多内存，但是，我们肯定是不知道，物理内存的，那这样的反向查找map操作怎么实现呢。
这其实不就是我们所说的hash表吗？hash首先要解决的就是冲突问题，其实我们这里要学的是一种减少hash冲突的方案，就是加上一些区分度比较大的编号，比如pid，来减少这种hash冲突。
覆盖技术
A调用3个函数，他们肯定是不能同时运行的，所以我们预留一个最大的空间，第一个函数执行完成后，第二函数覆盖第一个函数的空间。其实，当调用深度不止一个的话，我们也可以利用这个覆盖，但是，想想就觉得很麻烦。
交换技术
在空间不太足够的时候，把不太需要执行的程序内存放到硬盘里面。
虚拟技术
交换不要交换整个程序，只需要交换一小部分局部内存，分段分页放到硬盘里面。所以，如果我们的程序能把内存访问集中在一起(空间上的集中)，或者把对同一内存的访问集中在同一个时间(时间上的集中)。比如二维数组的行列遍历，比列行遍历好。
请求调页/页面置换
因为操作系统只会装载程序的部分页到内存中，一旦出现要访问的数据不在内存中，就需要请求调页，如果内存不够就置换到硬盘中。
驻留位：标识是否在内存中，还是在磁盘中。
保护位：可读，可写，可执行，权限够才能执行对应的操作
修改位：如果这个页被修改，就是被写过，这个时候，如果我们要同步磁盘的话，需要修改磁盘的内容，否则，我们直接释放这个就可了
访问位：包括读和写，用于页面置换算法
页置换算法
所以，把哪些内容放到硬盘，是非常关键的，因为两个操作时间差到了指数级别。
最优页面置换算法
很多问题难以解决的一个重要原因就是，我们难以预测未来会发生什么样的事情，但是，如果我们有一种已知未来的算法，那么我们可以利用这个算法衡量其他算法的好坏。我觉得这是一个很好的思路。
这个就是找出最晚出现的，把他换走，从总体的性能来考虑的话，肯定是最合理的。
先进先出算法
维护一个队列，不够的时候，把队首踢出，明显会有很多问题
最近最久未使用算法
实际上，频繁访问的代码，最近也是这样，但是有的代码，可能很长时间都不会再访问了。
记录，最近访问的时间，找出最早的哪个，说明它很久没有被使用了，盲猜是堆实现。
系统维护一个页面链表，最近刚刚使用过的页面作为首结点，最久未使用的页面作为尾结点。每一次访问内存时，找到相应的页面，把它从链表中摘下来，再移动到链表之首。每次缺页中断发生时，淘汰链表末尾的页面。
设置一个活动页面栈，当访问某页时，将此页号压入栈顶，然后，考察栈内是否有与此页面相同的页号，若有则抽出。当需要淘汰一个页面时，总是选择栈底的页面，'它就是最久未使用的。说句实话，这个和上面那不是一样吗？
时钟页面置换算法
我其实一直想保存这个时间的，但是保持时间的代价大的离谱，但是你还记得我们有一个访问位可以标识这个内存是否被访问过吗？
我们把空间连成一个时钟，指针不断的走，遇到被访问过的，把它设置为没有访问过的，要是碰到了没有被访问过的，那么就置换这个页。
明显，速度很快，但是肯定是不准确的，这个是操作系统第一次牺牲精确来提高速度，其实我们的应用系统也能借助这种思想，有的它确实只是需要高可用。
其中设置访问标识是硬件干的事情，但是读和写都是访问，但是操作系统如何判断读写，如果是写那么操作系统会把访问标识和dirty bit都设置为1
两次机会法
写过的页面在替换的时候，需要写入硬盘，代价非常大，最好不要抛弃，但是如果全都是写过的
| used | dirty | used | dirty | 备注 |
|---|---|---|---|---|
| 0 | 0 | / | / | 替换页 |
| 0 | 1 | 0 | 1 | 这种情况是不可能直接出现的，是由最后一个情况变换来的 |
| 1 | 0 | 0 | 0 | 没有写数据 |
| 1 | 1 | 0 | 1 | 当写入了数据，我们给两次机会 |
最不常用算法
选择访问次数最少，是从次数上来看的，而LRU是从时间上看的。
这种记数的，最怕的就是受到时间的影响，如果我们每个一段时间，把整体都减小一部分，比如右移动2位，那么就可以实现最近访问次数的问题了。
Belady现象
FIFO随着分配的增多，缺页的次数反而减少了，我从这个里面看到的就是，日志记录很重要！
全局页面置换算法
如果把同时支持的页面数量增多，那么页面置换的数量就会减少。
工作集
任意指定长度的时间段内，被访问的页面有哪些
常驻集
在内存中的页面，如果和工作集这个集合的重复度比较高，那么效率就会很好。
工作集页面置换算法
不同于局部置换算法，局部置换算法只有在页面不够的时候才会换页。
它很像滑动窗口，在滑出时间范围之后，就会被删掉，比如我访问了一次，给它设置一个时间，之后我再访问别人的过程中，发现这个时间差超出了窗口时间，所以就打断这个链路，即使页面空间足够，我也会把它放出。这样可以为程序预留更多的页面。
缺页率页面置换算法
上面的窗口大小是固定的，那如果我们可以根据缺页率在实时更新窗口大小，效果岂不是更好。缺页率越高，我们需要给它分配的就常驻集就应该越多。
每次缺页的时候，维护这个频率，动态的调整窗口的大小，这个大小就是解决缺页之后，现在这个页的数目，然后我们需要设置一个值，告诉操作系统什么时候调整最好。
抖动问题
就是缺页太多，操作系统要保持一个度，让运行的程序尽可能多，但是又不至于产生卡顿。
进程管理
进程
因为操作系统要支持多个程序同时在计算机上运行。程序是静态的代码，但是进程产生的基础，每次运行构成的程序都可以不同，同时，通过调用关系，一个进程也可以包含多个程序。
进程具有用户态和核心态的概念
组成
程序的代码
程序处理的数据
程序计数器，和jvm的一样，指向了下一条需要运行的指令
一组通用的寄存器，堆，栈
一组系统资源，比如文件和网络
特点
动态性：可以动态的创建和结束
并发性：可以被独立调度并占用处理机运行，并发，并行
独立性：不同进程工作互不影响，利用内存分配机制，不如进程访问不在自己空间内的内存
制约性：访问共享资源的时候，同步互斥
PCB 进程控制块
操作系统为每个进程都维护了一个PCB，用来保存与该进程有关的各种状态信息，相当于操作系统实现进程管理的数据结构。那这个数据结构应该包含哪些信息呢？
- 进程标识信息
- 本进程标识
- 父进程标识
- 用户标识
- 处理机状态信息保存区
- 用户可见的数据寄存器
- 控制寄存器和标志寄存器，比如程序计数器和程序状态字
- 栈指针，过程调用，系统调用，中断处理和返回时会用到这个
- 进程的控制信息
- 调度和状态信息，用于操作系统调度进程并占用处理机使用，比如Java线程的生命周期
- 进程间通信信息，为支持进程间的与通信相关的各种标识、信号、信件等，这些信息存在接收方的进程控制块中。
- 存储管理信息，包含有指向本进程映像存储空间的数据结构，比如内存的占用情况。
- 进程所用资源，说明由进程打开、使用的系统资源，如打开的文件等。
- 有关数据结构连接信息，进程可以连接到一个进程队列中，或连接到相关的其他进程的PCB。
组织方式
上面更像是单个对象的定义，但是我们的进程肯定是有多个的，所以，我们要想出一种组织方式。
链表
不同状态的放到不同的链表里面，比如就绪链表，阻塞链表，因为进程的动态性太强了。
索引表
和上面的一样，多个状态对应多个不同的index表
生命周期
进程创建
系统初始化时，用户请求创建一个新的进程，正在运行的进程执行了创建进程的系统调用。
系统创建，用户创建，进程创建
进程运行
创建好的进程不一定可以执行，还需要通过我们操作系统的调用。那么多进程，选择哪一个来执行，就需要我们使用算法来决定了。
进程等待
什么情况下会等待(阻塞)呢？
-
请求并等待系统服务，无法马上完成
-
启动某种操作，无法马上完成
-
需要的数据没有到达
进程只能自己阻塞自己，因为只有自己才知道什么时候才需要等待
进程唤醒
- 被阻塞进程需要的资源可被满足
- 被阻塞进程等待的事件到达
- 将该进程的PCB插入到就绪队列
进程只能被别的进程或操作系统唤醒。
进程结束
- 正常退出（自愿的)
- 错误退出（自愿的)
- 致命错误（强制性的)
- 被其他进程所杀（强制性的)
状态转换
总结一下，只有Ready态可以变成Running，也就是说，我们没有任何办法，让操作系统直接运行某个线程，即使是Blocked结束，也只是进入了Ready态，而且即使在Running中，也会因为分配给自己的结束而进入Ready态
进程挂起
挂起和阻塞不一样，挂起是运行程序的内存被放到硬盘中了。
分类
阻塞挂起状态(Blocked-suspend)：进程在外存并等待某事件的出现
就绪挂起状态(Ready-suspend) :进程在外存，但只要进入内存，即可运行
原因
阻塞到阻塞挂起:没有进程处于就绪状态或就绪进程要求更多内存资源时，会进行这种转换，以提交新进程或运行就绪进程。就是为了节省内存。
就绪到就绪挂起:当有高优先级阻塞进程和低优先就绪进程时，系统会选择挂起低优先级就绪进程;
运行到就绪挂起:对抢先式分时系统，当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时，系统可能会把运行进程转到就绪挂起状态，保证高优先级的会先运行，和挂起无关。
阻塞挂起到就绪挂起:当有阻塞挂起进程(注意这个对象，是咱们之前挂起的阻塞进程)因相关事件出现时，系统会把阻塞挂起进程转换为就绪挂起进程。
激活/解挂
就绪挂起到就绪:没有就绪进程或挂起就绪进程优先级高于就绪进程时，会进行这种转换(你发现了吗？它这样做的目的就是为了让挂起的和普通的对程序员来说，效果是一样的)
阻塞挂起到阻塞:当一个进程释放足够内存时，系统会把一个高优先级阻塞挂起（系统认为会很快出现所等待的事件）进程转换为阻塞进程;
进程管理
在内部，通过维护好多队列来实现相应的功能，有的时候，区分进程优先级，比如不同优先级的放到不同的队列中，维护的关系还是比较复杂的，不够毕竟进程是通过软件是维护的，并没有硬件去支持。
线程
Thread这个单词就很熟悉，这不是就java的Thread吗？我们重点关注一下区别，同时从底层看看，他们之间的原理。
为什么要又线程，因为进程共享空间难度和开销比较大，比较在各种的内存空间中。而且，这样也不太安全。
一个线程出现问题，其他的线程也会受到影响，所以，Chrome浏览器选择了一个网页一个进程，所以内存的开销会非常的大，几乎上就相当于开了好几个应用程序，而且内存直接肯定是毫无关系，互不干扰的。
他们的寄存器和栈都是有各自的分配。
比较
进程是资源分配单位，线程是CPU调度单位
进程拥有一个完整的资源平台，而线程只独享必不可少的资源，如寄存器和栈;
线程同样具有就绪、阻塞和执行三种基本状态，同样具有状态之间的转换关系;
线程能减少并发执行的时间和空间开销:
- 线程的创建时间比进程短;
- 线程的终止时间比进程短;
- 同一进程内的线程切换时间比进程短;
- 由于同一进程的各线程间共享内存和文件资源，可直接进行不通过内核的通信;
第一条和第二条肯定是因为线程需要创建和管理的东西少进程太多，而且由于内存管理机制，线程直接的切换页基本都在一起，第四点也是因为内存管理机制。
分类
用户线程
操作系统无法管理用户线程，用户线程对操作系统不可见。如果这些都是通过线程库来实现的，那么就说明，即使不支持线程操作的系统可以完成对应的功能，因为这个进程就是由操作系统通过队列实现的，咱们为什么不能实现这样的一个系统呢？
内核线程
window就自己在操作系统层面实现了对应的功能，但是这样的开销肯定更大，首先，需要内核来维护进程和线程的上下文信息，PCB和TCB，而且都是调用内核执行的。
但是，这样的消耗换来了什么呢？首先，用户线程对操作系统来说透明化了，一旦透明化之后，就不会出现，由于某个内核线程发起系统调用而且被阻塞，并不会影响其他内核线程的运行，而且CPU是知道你是多线程，所以会多给你分配一些时间，因为之前操作系统是不清楚你进程是如何运行的，所以当一个进程来给你分配时间了。
轻量级线程
内核支持的用户线程，一个进程可以有多个轻量级进程，而这些进程都是由一个单独的内核线程来支持的。和上面的区别应该是一个提供了函数，是全局的，这个是直接提供了管理者。
上下文切换
保存和复原寄存器内容，这个过程就是十分消耗资源的。
进程创建
fork
在创建一个进程时，子进程只是完全复制父进程的资源，复制出来的子进程有着自己的结构和ID，但却复制父进程的其他资源，例如父进程打开几个文件，那么子进程也有几个打开的文件，但是子进程的改变不会影响父进程。怎么说，深克隆？
fork调用的一个奇妙之处就是它仅仅被调用一次，却能够返回两次。
1）在父进程中，fork返回新创建子进程的进程ID；
2）在子进程中，fork返回0；
3）如果出现错误，fork返回一个负值；
这。。。说句实话，这编程难度有点大哈，而且我还没看见什么运行就直接执行了。
fpid的值为什么在父子进程中不同。其实就相当于链表，进程形成了链表，父进程的fpid(p 意味point)指向子进程的进程id, 因为子进程没有子进程，所以其fpid为0.
exec
根据参数不同，执行不同的内容，比如执行shell脚本
wait
主程序等子程序执行完成(退出)后再执行，退出指的是exit，这个用在子程序里面，不会退出整个进程。
僵尸进程
僵尸进程是当子进程比父进程先结束，而父进程又没有回收子进程，释放子进程占用的资源，此时子进程将成为一个僵尸进程。
调度
执行时机
CPU空闲的时候，操作系统从就绪状态的进程中选择一个执行，这个空间也可能是CPU有意制造的空闲，比如优先级，时间片等等。
内核运行调度程序的条件(满足一个就可以)
一个进程从运行状态切换到等待状态
一个进程被终结了
不可抢占
一旦执行之后，其他人就不容许抢占，这种容易因为一个人的延时影响到其他人
可抢占
当一个进程正在处理机上运行时，若有某个更为重要或紧迫的进程进入就绪队列，则立即暂停正在运行的进程，将处理机分配给更重要或紧迫的进程。
执行模型
一般情况下，CPU的执行是波动式的，在IO的过程中，CPU的负载其实并不高。
算法评价指标
CPU使用率
CPU处于忙状态所占时间的百分比
吞吐量
单位时间内完成某个任务的次数，比如MySQL1s内可以完成的事务次数
周转时间
一个进程从初始化到结束，包括所有等待时间所花费的时间，如果CPU只为我们服务，这个时间段肯定是最短的，否则，可能因为CPU的调度不合理，导致程序执行时间变长
等待时间
进程在就绪队列中的总时间，阻塞的不算，阻塞是程序自己阻塞的
响应时间
从一个请求被提交到产生第一次响应所花费的总时间
低延时
很快就能接受到响应，一打开水龙头，水就流了出来。
高宽带
流量大，能支持很多人同时使用，而且单个人使用的时候，文件传输的数量多
调度算法
FCFS
如果有多任务需要执行，他们执行的快慢不同，我们定义总执行时间，是系统开始，到任务执行完毕，那么我们越先处理速度快的，我们平均执行时间就越快，虽然总时间是一样的，但是每个人等待的时间变短了，这个很想排队，让快的先执行完，只有哪些被排到最后的执行的慢点会骂你，但是你先给慢的执行，那么骂你的人肯定更多。
队列，谁先到谁先跑
优点：
适合长作业，适合CPU繁忙型，不适合I/O繁忙型
缺点：
波动较大（其实我一直不认为这个是一个问题，只要总的时间变短就是好的），排序可以不合理，先来后到就是合理吗？我们在招聘的时候，后面有更好的，我们不要了吗？
最短作业优先调度算法
如果我们有办法能预测一个任务的执行时间，那么我们持续的选择最快的任务，比如有个任务比正在执行的，执行完的速度还要快，就换成新的任务执行。
但是这样会导致哪些时间长的任务，等待的时间更长。还记得我们怎么在内存算法中预测未来的吗？执行时间长的任务，你觉得是短任务，还是长任务呢？万一是一个快要结束的短任务，那不是血亏吗？怎么解决呢。
可以认为下一个 CPU 执行的长度与以前的相似，前提
τn+1 = αtn + (1-α)τn
值 tn 包括最近信息，而 τn 存储了过去历史。参数 α 控制最近和过去历史在预测中的权重：
- 如果 α = 0，那么 τn+1 = τn，最近历史没有影响（当前情形为瞬态）；
- 如果 α = 1，那么 τn+1 = tn，只有最近 CPU 执行才重要（过去历史被认为是陈旧的、无关的）。
- 更为常见的是 α = 1/2，这样最近历史和过去历史同样重要。初始值可作为常量或系统的总体平均值。
展开式：τn+1 = αtn + (1-α)αtn-1 + …+ (l-α)jαtn-j + …+ (1-α)n+1τ0
通常，由于 α 和（1-α）小于 1，所以后面项的权重比前面项的权重要小。
这，就是数学的魅力，如果我们需要一个算法，通过过去预测未来，而且越近的对未来的数字影响越大，我首先肯定要考虑这个算法。
最高响应比优先
在上面算法的基础上考虑了等待时间，(等待时间+执行时间)/执行时间，这个肯定是一个大于等于1的数，R太大的话，说明等待时间太长，我们就需要优先调度这个进程，其实我感觉这些都是可以通过日志观察出来的，如果你的日志记录的足够好，那么说不定也会发现更好的算法，毕竟这些算法都是为了解决具体问题而产生的
时间分片(量子分片)算法
这个是我之前看到过的算法，它最大的缺点就是上下文切换消耗太大，所以最难的就是确定时间量子的大小。
最高优先级调度算法
调度程序能从就绪队列中选择最高优先级的进程进行运行，因为有多个队列。
静态优先级：创建进程时候，就已经确定了优先级了，然后整个运行时间优先级都不会变化；
动态优先级：根据进程的动态变化调整优先级，比如如果进程运行时间增加，则降低其优先级，如果进程等待时间（就绪队列的等待时间）增加，则升高其优先级，也就是随着时间的推移增加等待进程的优先级。(随着进程执行时间的变化)
根据不同的形式还有不同的操作。
非抢占式：当就绪队列中出现优先级高的进程，运行完当前进程，再选择优先级高的进程。
抢占式：当就绪队列中出现优先级高的进程，当前进程挂起，调度优先级高的进程运行。
很多时候，另我们头疼的是，程序运行过程是不确定的，就是因为这个不确定，让我们的算法变得异常艰难，我们的一般思路是，针对特殊的情况开始思考算法，并且根据问题去优化算法，优化比较大的时候，就会出现新的算法，最后，我们通过分类的方式，来达到整体的最优，这是一个艰难而有趣的过程。
多级反馈队列调度算法
是时间片轮转算法和最高优先级算法的综合和发展
设置了多个队列，赋予每个队列不同的优先级，每个队列优先级从高到低，同时优先级越高时间片越短，根据运行时间而动态的改变所属队列，确实牛逼！
新的进程会被放入到第一级队列的末尾，按先来先服务的原则排队等待被调度，如果在第一级队列规定的时间片没运行完成，则将其转入到第二级队列的末尾，以此类推，直至完成；
当较高优先级的队列为空，才调度较低优先级的队列中的进程运行。如果进程运行时，有新进程进入较高优先级的队列，则停止当前运行的进程并将其移入到原队列末尾，接着让较高优先级的进程运行；
对于短作业可能可以在第一级队列很快被处理完。对于长作业，如果在第一级队列处理不完，可以移入下次队列等待被执行，虽然等待的时间变长了，但是运行时间也会更长了，所以该算法很好的兼顾了长短作业，同时有较好的响应时间。
其他调度
实时调度
针对实时系统，要求在deadline之前必须完成，我感觉这个需要动态规划，但是我们的服务器其实不需要考虑这些
强实时系统
需要在保证的时间内完成重要的任务，必须完成
弱实时系统
要求重要的进程的优先级更高，尽量完成，并非必须
多核调度
多个CPU完成调度，所以我们要考虑某个进程该让哪个程序运行
优先级反转问题
如果低优先级任务共享了高优先级任务的资源，那么高优先级任务就会被拖垮，导致最终的结果是可能不如低一级别但是不受低优先级任务的影响。这个前提肯定是我们希望优先级是死的。
怎么解决，如果我们发现了共享资源，那么我们就提升低优先级的地位，不让其他进程中间插入
并发编程
多线程应用意外为资源共享，意味着不确定性和难以重现性，bug间歇性发生，而且可能会在线上的时候，发生你意想不到的情况。
原子操作
即使是我们看上去的，只有短短一行代码的指令，比如i++在汇编层面也可能是几条，但是java可以让部分操作强制具有原子性！
临界区
临界区是指进程中的一段需要访问共享资源并且当另一个进程处于相应代码区域时便不会被执行的代码区域
是一个代码区域
互斥
当一个进程处于临界区并访问共享资源时，没有其他进程会处于临界区并且访问任何相同的共享资源，这就是锁
死锁
两个或以上的进程，在相互等待完成特定任务，而最终没法将自身任务进行下去
饥饿
一个可执行的进程，被调度器持续忽略，以至于虽然处于可执行状态却不被执行
锁
如果没有被锁，无需任何条件就可以锁，但是如果发现有锁了，就必须持有钥匙或者持有钥匙的人打开了锁，而且没有加锁之前的任意一个瞬间，都是有可能被其他线程介入的
实现方案
while 自旋也是一种方案，适合那种执行快的，不然一直自旋，消耗CPU时间。
禁用中断
线程切换是由中断来完成的，不过这个影响是全局性，明显不行，而且在CPU中，中断是分开的
软件解决
通过非加锁的代码来实现加锁的效果，个人感觉实现起来麻烦而且有耦合，忙等待比较多。
Test-and-Set
从内存中读取值，判断是否为1并且准备返回，内存设置为1，返回判断结果，这个操作是原子性的，是硬件提供的，毕竟硬件是不可能并发的。
怎么实现锁的？其实也是通过while循环，一开始的一个线程，执行操作，返回0，也就是false，这个时候它跳出来while循环，并且在这个过程中，它的值就已经是1了，所以当其他应用程序进去的时候，获取的值必然是1，只能无限的等待，这个1就相当于加锁，每个人都不断的加锁，即使自己没有进入也要疯狂的加锁，生怕在自己进去之后别人进来了。除非，有人执行完毕，主动把内存设置为0，这个时候，就会有新的进来。
但这也是一个忙等的操作，而且有个很搞笑的问题，为什么你没有进去，还不停的加锁，难道判断比读写的消耗还大吗？
一直while也不好，如果发现进不去，那么我们把它放到队列中，等获取锁的进程执行完了，我们把一个线程从队列中拉出，然后唤醒它，虽然是对列，但是谁先加进来是完全随机的。
Exchange
原子性的交换两个内存单元的值
这。。。怎么实现锁呢？
只能说牛逼！还是默认0可以执行，我们不断用1来和他交换，这个时候我们就发现了，当一个被加上锁，每次交换的结果都是1，因为两个都是1嘛，当获取锁的线程释放锁后，用1和0交换，锁就实现了！
优先级
但是我们不要忘记了，即使有锁，和我们前面的优先级中断出现了冲突，如果高优先级的要执行，发现锁在第优先级线程的里面，那么有永远不可能获取到锁，这样就产生了死锁。
信号量
读写锁，semaphore
依然是原子操作针对一个sem，这个值是自己设定的
P()
sem–，如果sem<0则等待
V()
sem++，如果sem<=0，唤醒一个等待的P
如果你不理解判断条件，你只需要记住，他们是先运算后判断的
说实话，这些原子操作还真不好想是干什么的。
加入我们的会场只容许10个人，每个人进来sem–，直到容量不够，这个时候，除非有人推出，执行了sem++，然后唤醒，这才能继续进入，而且这个也juc上也是可以模拟的。
sem=1
可以模拟锁的效果
sem=0
可能你觉得设置成这个谁也执行不了，不，你错了，这个只要大于1就可以执行，比如我们想实现这个的功能，当线程B执行完某个指令之后，才能执行线程A，你先不要嘲笑我，不是先调用B然后调用A实现的，我们的解决方案就是，B执行放出名额的操作，在这之前，A一直在等。
这么说吧！一个线程等待另一个线程处理事情，这样实现就比较优雅。
生产者消费者
需要三个信号量，一个设置为1，保证消费者和生产者，一个时候只能进来这个，我这边给出的更好的方案，是给这个队列对象加个锁！
一个full设置为0，另一个empty有几个设置为几
生产：
empty.acquire();//顺序不能换
lock.lock();
add(c);
lock.unlock();
full.release();
消费：
full.acquire();
lock.lock();
c=get();
lock.unlock();
empty.release();
没想到这样的实现也挺优雅的。
管程
包含了一系列的共享变量，针对这些变量的一系列操作函数的组合。来自java语言，就是wait和notifiy
为什么要使用它？
信号量机制的缺点：进程自备同步操作，P(S)和V(S)操作大量分散在各个进程中，不易管理，易发生死锁。
管程特点：管程封装了同步操作，对进程隐蔽了同步细节，简化了同步功能的调用界面。用户编写并发程序如同编写顺序(串行)程序
引入管程机制的目的：1、把分散在各进程中的临界区集中起来进行管理；2、防止进程有意或无意的违法同步操作；3、便于用高级语言来书写程序，也便于程序正确性验证。
notify和notifyAll
线程T2调用A.notify()来通知A等待队列中的一个线程，此时这个线程里面只有T1，所以notify唤醒的就是线程T1，如果当这个条件变量的等待队列不止T1一个线程，我们就需要使用notifyAll()
如果我们使用了ReentrantLock，那么通过lock.newCondition()可以创建任意条件，你可以把条件的名称起为你期待可以运行代码的条件，在加锁之后，首先判断的就是条件是否满足，如果不满足，那就使用条件.await()表示在等待这个条件，记住这里用while判断。
在处理完我们的任务之后，我们想想，我们可以破坏哪些条件，然后执行条件.signal
synchronized
这个本质上就是只有一个条件变量的管程
矛盾
如果说生产者和消费者都在我们的一个管程之内，那生产者执行完signal方法之后，唤醒了一个消费者，但是他们又占了同一把锁，之前我们执行完signal之后，程序就结束了，但是，这种情况应该怎么解决呢？
这个其实就强行指定的
分两种情况，如果是等我们释放锁之后，才唤醒其他线程(你会发现这个很好实现)，那么在这个情况下，如果唤醒了多个线程，他们就会共同来消费，加入我们是刚刚唤醒的，只有一个生产物，那么他们在抢的时候就会乱掉，所以要使用while去判断。但是！如果是急切的唤醒线程，等线程执行完毕后再继续执行我们下面的代码，那么这种情况就直接if就可以了，在java中，我们得采用while循环。
这么说吧，当只有一个消费者和生产者，写成if也是完全没有问题的，所以我们想解决这个问题，肯定是要思考在多线程的情况下怎么处理问题。
那么问题来了，一个线程执行了wait方法之后，它不会再继续执行了，直到被notify唤醒。那么唤醒之后从何处开始执行？
并不是从头开始执行！而是接着往下执行，这样就会导致！如果有多个都被唤醒了，但实际是只有一个消费品，那么就会出错，但是一个消费者却不会出现这种情况。但是，如果使用while的话，即使被唤醒了多个，也会再次判断，所以能保证消费是正确的！而且，这里的while是不会自旋消耗CPU的，这个基本上就是那些被幻想之后的条件包裹的while
这次，我终于彻底搞懂了！
经典多线程问题
生产者与消费者
这个问题我已经遇到过好多次了，是一个很经典的问题，后来我知道，jdk内部的队列也提供了这样的支持。
读者-写者问题
这个真的是经典到极致，因为它是我们web应用中，最最常见的问题，就是读写锁的实现，当有人在写的时候，不容许其他人来写，也不容许有人在读。但是可以支持多个人同时读。
究竟是怎么实现读写锁呢？其实关键在于读者，首先，维护一个读者数量，这个时候，我们需要利用一个必然性的因素，如果有了一个读者，那么肯定没有写者。
对于读者来说，如果读者的数量为0，那么自己是第一个读者，需要加锁，这样是为了防止写者写，然后readCount++，但是第二个读者发现readCount不为0，就不会要求锁了，也就是说，锁也可以是我们主动去加的，它本来就是对象独有的。每次退出之前，readCount–，如果发现自己是最后一个读者，那么就需要释放锁。这个就是逻辑，很好理解，但是自己真的想不出怎么实现。
此外，读者优先，因为查询操作更需要速度，但是这样也会出现，我先写，但你读到了之前的数据，不过呢，我这边响应的慢，显示的是我写的慢，你读完我才写成功，但是如果读的太多，我总不能不写吧，所以，这个问题待探讨，写者优先也是可以实现的，而且两个实现起来是一样的，所以我们的关键是选择哪个？比如要求高可用，我们就使用读者优先，对数据一致性要求比较高的，比如商品价格，我们肯定是写者优先的。
那这个实现的思路是什么呢？你会发现这个其实和算法很像的，这个也是需要我们不断去思考的，而且有的时候比算法更难考虑，需要更复杂的思想，尤其是那些可以解决实际问题的算法，简单又让人佩服。
其实，关于上面的问题，我们需要清楚一点，如果是读者可写，那么写者就需要判断，如果有读者正在读，或者准备读，都是不可以的，所以，需要把两者加起来，凡是大于0，就说明有这种情况出现。
等待数量是怎么统计，答案是在wait的前后操作，在wait之前增加等待者的数量，之后减少等待者的数量。
哲学家就餐
如果我们需要获取的资源不止一个，一旦出现了两个都拿到了一半的资源，他们都在等待对方的资源，这个时候，死锁就出现了。我现在感觉，我的交换网络图也可能出现死锁的问题的。
这个问题解决的演化还是很有意思的，一开，先拿左边的，然后再拿右边的，然后吃饭，死锁出现的原因就是占了对方的资源。那我们声临其境感受一下，如果我是哲学家，我肯定会要求，你把叉子放下，我先来吃，你想想，你会让谁放弃资源，总不能让正在吃的放弃资源吧，唉，那么怎么让它放弃呢，我一个一个判断吗？不如我们反转思路，让拿着叉子的人，发现自己没有另一把叉子，就主动放弃，把几乎让给别人，好，活锁来了！极端情况就是每个人轮流拿起，轮流放下，轮流拿起。。。。即使给他们加上时间，也只是减少这种概率而已。
还有什么解决方案呢？
限制可以锁资源的线程的数量，保证至少有一个线程可以获取完整资源并且执行，明显这个对我的监考系统是行不通的，因为我知道总共有多少人来交换，但是我可不敢保证，他们会同时交换，因为这个是这个数据不断流入的过程。
给一个全局id，自动增加，如果是奇数，则拿左边的一个，否则拿右边的一个，太局限于这个问题本事了，我们可以是数据结构中的图，这种环的问题怎么可能和我们来比较呢。我们怎么知道对于我来说是小的监考，对于别人来说是什么样的呢？
如果发现资源都可用，我就执行，然后放下资源，并且看看尝试唤醒其他需要这个锁的线程，否则，我就等待，那么，怎么保证这种原子性呢？
我们引入了状态判断，其实在java的环境中，我们可以尝试去获取锁，如果获取成功，就设置自己正在处于交换状态，然后利用同步的信号量(初始值为0)，让自己解除阻塞。为什么不直接在这个后面写呢？而且，自己通知自己是为何？
因为在尝试获取两个锁的时候，就代表自己需要进行操作了，那我就得上全局的锁，不然会影响其他人对我状态的判断。
死锁
本质
问题的本质就是线程和资源两个互相牵制。
可视化
我们可以借助图像来解决问题。
比如圆圈表示线程，它的特点是可以由箭头指向资源块，代表想要获取资源，或者是由资源块中的小黑点指向它，代表它获取了这个资源。
资源块有很多小黑点，比如有好几个停车场，每个停车场都有若干个停车位，如果一般情况下，比如枪支，每个人只能拿一份，我们也直接画成一个资源块也可。
一般什么时候不是死锁？答案是有的线程可以获取所有自己想要的资源，然后释放资源给别人用。
死锁预防
如果我拿不到全部资源就不再执行，这样的好处就在于快速失败，但是这样的坏处就是，本来可以利用的资源没有被利用到，导致发生了饥饿。
死锁避免
银行家算法
又被称为资源分配拒绝算法
银行就是资源的提供方，尽可能的提供给用户资源，用户就是线程，当用户获取了所有的资源后，必须归还资源，如果是分布式锁，设计一个超时时间，这个时候锁还可以随着时间失效。
在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若此次分配不会导致系统进入不安全状态，则将资源分配给线程，否则进程等待。
目前看来，这个算法可以持续不断的分配，是我想要的算法，这个算法考虑了一个资源有多份，我感觉变成一份之后，会出现跟简单的方案。也就是说，下面所有的数据结构都会被降低纬度。
比如第一个，就不需要了，只需要从数据库里面查询再不再，一般没有特殊的情况的话，肯定是在的。
最大请求矩阵，只需要标记哪个被分配了，但这两个好像是有关系的唉，是不是应该把这个改变成一个图的结构，那我是不是可以创造新的算法呢？
数据结构
1）可利用资源向量Available
是含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。
2）最大需求矩阵Max
这是一个n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
3）分配矩阵Allocation
这也是一个n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的数目为K。
4）需求矩阵Need
这也是一个n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。Need[i,j]=Max[i,j]-Allocation[i,j]
为什么不直接计算，非要再分配一个数组呢？
安全状态
安全序列是指一个进程序列{P1，…，Pn}是安全的，即对于每一个进程Pi(1≤i≤n），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j < i )当前占有资源量之和。
1）安全状态：如果存在一个由系统中所有进程构成的安全序列P1，…，Pn，则系统处于安全状态。安全状态一定是没有死锁发生。
2）不安全状态：不存在一个安全序列。不安全状态不一定导致死锁。
怎么说呢，我感觉有点废话，看还需要更加深入的逻辑。
实现
啥也别说了，咱直接debug它。
首先，这个算法是可以逐步分配的，而且这个算法其实决定的是一个借贷的顺序，也就说，这个时候，所有的需求量都知道了，那有没有那种以图为数据结构，而且支持连续数据的输入的算法呢，想想都感觉很难。
怎么决定顺序呢，就是当我把资源给某个人之后，可以收回全部资源，那这些资源可以让我把资源给跟多的人，如果逻辑上容许的话，那我要找出这样的一个算法，来实现。
其实就是找到可以分配的，分配给它，然后回收它的资源。但是这样不会出现错误吗？
死锁检测
容许系统进入死锁，进入死锁的可能性比较小，所以定时检测一下，能降低系统复杂度。
图算法来了！
依据我们上面的线程资源图，如果一个资源被一个线程所获取，且这个资源被另一个线程所占用。那我们就给这两个线程之间建立一条连线。那么这张图就只有线程了，如果发现图中有换，就说明产生了死锁。
但是！尽量不要这样做，这样做的开销太大，操作系统都不会帮助我们检测死锁的，而且一旦真的进入了死锁状态，我们也是无法解决的。杀死线程回滚吗？这个代价太大了，谁都支付不起。
进程通信
个人感觉，只是很想知道，感觉很有意思，但可能用处不大，因为我们都是通过分布式的网络通信的。
这个和操作系统对进程隔离的保护矛盾吗？
IPC
Inter Process Communication
其实，我也能想到，我一个进程把数据写到文件中，另一个进程去读，是也完全没有问题的，第一行数据是时间，如果另一个进程发现时间发生了变化，就读取，然后把时间设置为0时间，当我想要再写数据的时候，如果发现时间为0，就重置时间，否则，我就直接向末尾添加数据。目前看来，还是有点可以的哈，但io成本太高了。而操作系统的解决方案是抽离出了一块内存，帮助我们来完成。还有就是两个进程直接共享一块内存了。
也可以借助消息队列，消息队列我比较熟悉，不说了。
信号
借助中断的思想，效率很高，因为只是传递了一个bit，只是一种事件，不带有太多的参数。
首先，这种肯定是需要注册的，因为这个就像是内部的一个函数，突然被别人调用了，类似这样的，它既不是通过回调来实现的，那肯定就需要一个注册中心。
需要操作系统修改堆栈和程序计数器，那我来想想rpc是怎么实现的。
肯定需要对外暴露一个端口，咱们就加入是socket吧，然后会有参数传递进来，我们通过对url的判断，确定执行哪个函数，然后通过反射调用就可以了。
管道
Liunx的管道操作符，将一个程序运行的结果，作为另一个程序的输入。
文件系统
它是硬盘存储的抽象
功能
分配文件磁盘空间（和内存很类似）
管理文件块（哪一块属于哪一个文件)
管理空闲空间(哪一块是空闲的)
分配算法(策略)
管理文件集合
定位文件及其内容
命名:通过名字找到文件的接口
最常见:分层文件系统
文件系统类型(组织文件的不同方式)
提供的便利及特征
保护:分层来保护数据安全
可靠性/持久性:保持文件的持久即使发生崩溃、媒体错误、攻击等
文件属性
名称、类型、位置、大小、保护、创建者、创建时间、最近修改时间、…
所以，我们不需要存储什么最近修改时间在文件里面，不打开文件内容，我们也能获取到一定的信息
文件头
在存储元数据中保存了每个文件的信息
保存文件的属性
跟踪哪一块存储块属于逻辑上文件结构的哪个偏移
文件描述符号
当我们打开一个文件的时候，操作系统会把打开的文件维护在一个打开文件表里面，其中，文件描述符，就是这个表中的索引
元数据
文件指针，指向最近一次读写位置，每个打开了这个文件的进程都有这个指针
文件打开次数，记录多少个进程打开了它
文件磁盘位置，在磁盘中的实际位置
访问权限，linux做的很完善
原来一个文件可以被多个进程打开呀
块和扇区
块/页是逻辑，扇区/帧是物理，内存和磁盘，甚至MySQL，都和这是这样的，哪怕是访问和修改一点点数据，都和涉及到整个块
多用户系统
Linux系统，是支持多个用户同时操作一个文件的，此外，进程调度，也是可以根据用户所占有的资源合理分配的，比如阿里云服务，不能你系统需要的CPU多，我就把CPU分给你吧。
但是，USF是写入一个数据，对其他用户来说，是瞬间可见的，你说怎么实现的，腾讯文档不就是这样的吗？
还有就是会话级别的，写完的文件关闭后，别人才可以看到，这个我感觉是放到内存里面了。
当然，这些和MySQL比起来，还是太简单了。
硬链接和软链接
它们区别于删除的时候，硬链接有好几条命，但是软链接只能靠真身。
文件系统
日志文件系统，MySQL中先写日志再执行，利用磁盘空间，实现了速度(顺序io)和持续性
NFS，GFS分布式文件系统，需要网络支持
虚拟文件系统，比如Linux把所有的都抽象成了文件
虚拟文件系统
虚拟在这个就行是抽象，不管是抽象内存管理，还是文件系统管理，我们会发现，操作系统把普通的文件系统和网络文件系统等抽象成了一样的东西，接口不就是open，read，write，close吗？多么简单的接口，只有这样简单抽象的借口，才能适配各种的系统。
卷控制块(Unix: “superblock”)
每个文件系统一个
文件系统详细信息
块、块大小、空余块、计数/指针等
文件控制块(Unix: “vnode”or“inode”)
每个文件一个
文件详细信息
许可、拥有者、大小、数据库位置等
目录节点(Linux: “dentry”)
每个目录项一个(目录和文件)
将目录项数据结构及树型布局编码成树型数据结构
指向文件控制块、父节点、项目列表等
数据缓存
预先读
因为io是非常消耗时间的，但一般情况是，我们程序会读取整个io文件，在这个时候，操作系统就可以预读，这个好处是io在空闲的时候就已经执行好了，当执行好之后，我们在读的时候，就会省去很多时间
延迟写，直接在缓存操作
这样做就是为了减少io的次数，总不能写一个字节也要修改一下文件吧
桥接内存管理
最好文件系统的块和内存是有对应关系的，这样就很方便管理，此外，而且我们肯定不能缓存全部磁盘文件，所以，这里也有内存那样的换页算法。
文件分配
打开文件
read打开操作到底会发生什么？
打开就要找到文件在硬盘的什么地方，所谓打开就存文件控制块的内容，读入内存，比如文件打开表。
我们还可以设置锁，比如我们打开文件后，被人就不能打开了，但是我不知道java是怎么实现的
分配空间
当我们往一个文件里面写内容的时候，就需要考虑给文件分配数据块的功能，评价指标为，物理空间利用高效，访问速度很快。
连续分配
数组
需要一个起始块，和文件长度，这不是就是数组吗。很明显，这种在修改的时候，非常麻烦还需要牵扯到别人。如果是只读文件系统，那么这肯定是最好的，它非常的快。
链式分配
链表
尽管这个链表的扩展性很好，但是万一在磁盘中的某个链路断开，那么整个文件系统都会受到影响，而且这些链地址肯定是要占用额外空间的。
索引分配
哈希表
存储了逻辑位置和物理位置的索引关系，访问也比链表快。对于小文件的话，浪费比较严重，对于大文件，索引描述块又不够大。那怎么办，多级索引呗，唉，这个地方的多级索引可以解决问题吗？
空闲空间
bitmap，需要扫描这很小的一块bit位
但是，一致性怎么保证呢？就是说，如果写入了新的文件，在bitmap没有同步完成的时候，万一断电，怎么解决。你想想怎么解决这个问题，写日志再操作吗？
其实操作系统系统的解决是，先bitmap设置为1，然后再写文件，这个时候，如果断电了，唯一的坏处就是这个块空间被浪费了，但是绝对不会出数据丢失。唉，所以我就再想，为什么服务器不弄一个电池呢。
磁盘
扇区，磁盘通过分区来最大限度的减少寻道时间，因为探针的前后移动是最慢的，所以可以通过分区来减少，这是不是可以解释，为什么同一个盘内的复制速度很快，但是其他的不行。我对组成原理还没有任何了解。
分区
分区就是把一块硬盘的全部容量分成几部分来使用，每一部分就是一个分区，当然也可以把全部容量就当一个区使用。但即使把全部容量就当一个区来使用，这个分区的操作过程仍然是必须的，不经过分区的操作，硬盘无法使用。
卷
硬盘有好多种工作模式，其中在普通的模式下运行时，专业上将它称为“基本磁盘”，通常家庭计算机里的硬盘都是运行在“基本磁盘”模式，在这种模式下，卷与分区没有根本的区别，你尽可以认为一个卷就是一个分区，这种卷在专业上称之为简单卷。
分区和卷在Windows里通常互换使用，例如一个基本卷表面来看就是一个分区。但是分区只能被限制在一块磁盘中，也就是说一个分区最大也就是该分区所在磁盘的大小，不能跨磁盘建立分区。分区的记录存储在磁盘的第一个扇区中，它是一种较低层次的概念。
卷这个概念就比分区抽象许多了，而且卷能做的事情也比分区多。卷可以跨硬盘实用，可以将几个物理的分区（或磁盘）通过软件组合成为一块看起来是一个独立的大磁盘（VG卷组），然后再在VG之上建立逻辑卷，这样就不用再受制于一块硬盘的有限容量了，也可以实现不关机的扩容。
RAID
多个硬盘并行读，冗余存。并行读是想解决io速度的问题，冗余存可以提高磁盘的可靠性。
附加一个校验盘，如果有一个数据错了，还可以通过这个校验盘来纠正。但是，这个校验盘的开销太大了，每次读写都要涉及到它，所以我们可以每个硬盘抽出一部分做校验。
磁盘调度
寻道时间+旋转到目的地的时间
寻道时间是痛点，那我们的算法又来了
最短寻道时间
每次都找离自己最近的寻道时间，这样比较远的就会出现饥饿
更多推荐
2
0- 0
已为社区贡献1条内容
所有评论(0)