简单介绍操作系统。
概述
操作系统是人造学科
- 没有对错，只有好坏
- 是对人类活动的观察
- 人有主观能动性，不同的人理解各不相同，多数人认同的抽象就称为了标准，即少数服从多数。
- 符合人的直觉
程序是如何运行的
- OS只认识机器语言，高级语言到机器语言需要编译器、汇编器的帮助
- 机器语言需要加载到内存中才能成为运动中的程序：进程，这需要OS的帮助
- 进程需要被调度到cpu上执行，需要OS的帮助
- cpu执行时，需要指令集和硬件的支持
OS = Operating System，其中Operating是掌控的意思
- 最开始计算机是没有Operating System的，是由人来operate，随着计算机越来越复杂，人不能胜任了，
于是有人编写了这个叫做Operating System的软件，来把人解放出来。
- 既然Operating System是专门掌控计算机的，所以任何未经Operating System同意的事情都是非法的，
OS是魔术师和管理者
根据OS管理的资源不同，分为：
- cpu管理，即进程管理： 如何分配cpu给不同用户
- 公平：每个用户程序都有机会
- 非阻塞：一个用户程序不能霸占着cpu不放
- 优先级：用户程序和人类一样，也有优先级
- 内存管理： 如何分配内存给不同用户
- 目的是让大家共用一个物理内存，这就需要对内存进行分割和保护，即不能越界。
- 存储管理： 如何分配磁盘给不同用户
- 将磁盘变成一个很容易使用的设备，无需让用户知道磁道，磁柱，扇区等。
- I/O设备管理： 如何分配输入输出设备给不同用户
OS在管理好硬件资源的同时，为用户提供各种服务，用户程序不断的使用OS提供的服务来完成自己的任务，
例如用户要读写磁盘、用户要发数据包。从这个角度看，用户程序是主程序，OS是子程序。
既然是OS为用户提供服务，那么启动机器时，应首先启动OS，而不是用户程序，在此之后，OS每调用一次用户程序，
就将控制权交给用户，用户执行完成后，控制又回到OS。这时OS是主程序，它在一生中不断的调用各种应用程序，
而每个应用程序执行完成后，控制又回到OS手上。从这个角度看，OS是主程序，用户程序是子程序。
为什么要学OS？
- OS的技巧在很多领域被使用，例如抽象，缓存，并发。
- OS就是在实现抽象：进程抽象，文件抽象，虚拟内存抽象。
OS不断演进的驱动力
- 硬件越来越便宜
- 计算机的功能和复杂性的不断变化
- 不断遭到黑客的攻击
OS的历史阶段
- 1940年以前，自动机，代表：英国人巴贝斯，不支持交互命令输入，不支持自动程序设计，还没有存储程序的概念，人本身就是操作系统，自动机都是由人来操作。
- 20世纪40年代，单一操作员，单一终端是刚出现计算机时人们能想到的最直观的方式。代表是：ENIAC，是第一台 电子 计算机，这种计算机，任何时候只能做一件事情，不支持并发，操作系统本身只是一组库函数，操作系统等待人的输入，人输入一个命令就是直接调用库函数名即可，这种OS的资源利用率很低，机器等人。在那个时代，机器很贵，提高机器的利用率成了头等大事。
- 20世纪50年代，出现了批处理系统。单一操作员单一终端之所以效率低，就是因为机器等人，如果事先将人的操作变成清单，统一由一个人送入机器，就成了批处理系统。批处理的过程是：用户将自己的程序写在卡片上，交给管理员，管理员批量的送入机器，然后将结果写到磁带上，所有用户程序运行结束后，将磁带取下来，送到机器上打印，然后打印结果交给用户。这时的操作系统仍然是同一时间只能执行一个程序，但是有了文件的概念，为什么到了批处理时代才出现文件的概念呢？因为多个用户需要用某种方式隔离开来，文件是最直接的方式。除了文件管理之外，这时的操作系统还能够管理读卡机，磁带，打印机等。
- 20世纪60年代，多道批处理。虽然批处理一定程度上提高了机器的利用率，但仍然在等待输入和输出，即在等待IO，IO设备相对于cpu来说实在太慢，让昂贵的cpu在等待人工的输入输出，有点让人受不了。人们想，能不能在等待IO的空隙时间里，让cpu计算其他程序呢？答案是可以，但需要加载多个程序到内存里，就成了多道批处理系统。这对操作系统提出了更高的要求，操作系统需要在多个程序间切换，并且能够管理IO设备，同时还要能够保护一个程序不被另一个程序干扰。既要管cpu调度，又要管内存，还要管IO设备。这个时代的驱动力仍然是机器昂贵，人们不能容忍机器闲下来。
- 20世纪70年代，多道批处理系统虽然提高了效率，但是用户只能将程序交给管理员去运行，太麻烦，能不能回到单一操作员的时代，自己坐在电脑前，有个显示器，自己能够管理自己的程序？这就是分时系统，操作系统可以运行多个程序，不用等人，如果人执行命令，操作系统就过来执行。由于是多个人共用一个操作系统，那么公平的管理用户的cpu时间就显得很重要。分时操作系统中最出名的就是Multics和unix。当时IBM给密歇根大学和MIT捐了机器，但很傲慢，MIT请来了密歇根的人，召集了DEC，贝尔实验室的人，一起针对IBM，开始了Multics的研发，不过团队内部出现了分歧，贝尔实验室的人看不惯MIT和DEC的人，就自立门户，搞了unix。这个时代的驱动力是不让人等待。由于分时，引入了多道程序设计，造成操作系统更复杂了，我们需要应对竞争，通讯，死锁，保护的一系列的功能
- 实时操作系统。对于一些实时性要求高的程序，人们又开发了实时操作系统，其中最重要的就是进程和工作调度，只有合理的进程调度，才能保证响应时间。代表作是VxWorks
- 1980年后，现代操作系统。硬件越来越便宜，个人可以拥有计算机了，无需和别人分享了，也就不需要分时操作系统了，因此，个人电脑又回到了标准库函数的系统，最有名的就是DOS，MacOS。但是过了一段时间后，人们想用一台电脑同时做几件事情，没有分时功能是不行的，于是又把分时功能加进去，例如windowsNT。贝尔实验室UNIX，UCB在国防部的支持下开发了BSD，IBM开发了AIX，斯坦福开发了SUN OS。90年代中期，美国国防部停止了对BSD的支持，贝尔实验室在官司中放弃了System系列，linux发展了起来，卡内基梅隆慌忙做了个MACH微内核系统
- 个人操作系统是从dos说起，微软1980年100美元的成本买断了dos，看到苹果的图形界面后，为dos做了层界面，称为windows，
但并不支持多道程序，bill亲自请来了DEC的David Culter，设计出了windowsNT，引入了多道程序。
OS基本概念
软件不像数学，软件存在一种“差不多”精神。
体系结构
计算机的结构非常简单：一个总线，通过各种控制器，将各种设备连接起来，所有设备之间的通信都要经过总线。为了提高效率，人们又设计出流水线结构，仿照工业流水线，将计算机的功能部件分为多个，例如：指令读取，指令译码，读操作数，指令执行，写结果。
中断
中断是OS中最重要的机制，它是OS获得计算机控制权的根本保证。中断的原理是：设备完成自己的任务后向cpu发出中断，cpu判断优先级，确定是否响应，如果响应，则执行中断服务程序，并在执行完中断程序后继续原来的程序。
内核态、用户态
不是所有的程序都是平等的，OS作为管理者，自然享有特权，所有人们发明了内核态和用户态
在内核态下的程序可以访问计算机所有资源，而用户态的程序访问资源则会受到限制。例如要访问内核中的进程表，需要在内核态下才能访问。
什么样的程序需要在内核态下呢？
- cpu管理和内存管理必须要在内核态下
- 诊断和测试程序也需要在内核态下，访问所有设备，才能判断计算机是否正常。
- 输入输出需要访问各种底层设备，也需要在内核态下
- 文件系统需要放在内核态下，不能让用户去破坏文件系统的结构
计算机是如何知道正在运行的程序是内核态还是用户态？是使用cpu的一个标志位，内核态和用户态不是指程序的状态，而是指cpu的一种状态，cpu处于什么态，程序就运行在什么态。
如何限制用户程序对资源的访问？要限制的话，需要对每一条指令进行检查才行，这种检查就是地址翻译，
程序发出的每条指令都要经过地址翻译，控制了地址翻译，就等同于控制了程序对资源的访问。
系统处于内核态时，内核程序可以绕过地址翻译，直接执行特权指令，例如关机。
OS演进
操作系统的结构演进：
- 刚开始，只有库函数，还没有称为操作系统，是杂乱的
- 慢慢的，各种功能划分成了模块，组成一个大的单体
- 参照人类社会的层次关系，将功能模块划分了层次，低层次的为高层次的提供功能。
进程
进程是运行中的程序，OS是通过进程表来管理所有进程的，任何时，一个进程所占有的所有资源，包括分配给他的内存，
数据结构，和其他资源形成一个core。
系统调用
OS是通过什么形式为应用程序提供服务呢？是通过系统调用（API）。系统调用的过程是
以用户程序调用read为例，系统调用的过程如下：
将需要的参数，压入stack，然后调用库函数read，库函数read将系统调用的read代码放在约定好的寄存器里，然后通过trap的方式将控制权给OS，进入了第二阶段。OS得到控制权后，将系统调用的代码从寄存器中取出，与OS维护的一张系统调用表进行比对，获得系统调用read程序体所在的内存地址，之后跳到该地址，进入到第三阶段，开始调用，系统调用执行完毕后返回用户程序。
压入stack的方式并不是最快的方式，最高效的是将参数放在指定的寄存器里面，在x86里，前8个参数是放在寄存器里的，
超过8后的参数，才用stack来传递。
shell
对于不编程的用户来说，怎么使用OS的系统调用呢？可以用shell，用户输入的是很多utilities，这些相当于c库函数
进程
什么是进程？
程序一加载进内存，就变成了进程。进程在Multics出现前叫job，job是IBM批处理系统中的概念，Multics
的研发人员不愿意和IBM叫的一样，改了个名字，叫做process，即进程。
进程为什么会出现？
由于资源宝贵，为了提高cpu的利用率，人们把多个程序同时放到了内存中，让他们共享cpu，让用户觉得自己在独占cpu，进程就是为了在
cpu上实现多道编程而出现的概念。
程序到底是什么？
从物理内存分配的角度看，每个进程都占有一片内存空间，从这点上说，进程就是内存的某片空间。
程序计数器
任意时刻，cpu只能执行一条指令，也就是说某个时刻，在cpu上执行的进程只有一个，而到底执行哪条指令，是由计数器决定的，
也就说所有程序共享一个计数器。
程序切换时，需要记录下当前程序执行到哪了，以便后面切换回来时知道从哪继续执行，所以每个程序都有一个自己的计数器。
什么事件会造成进程的产生和消失？
产生
- 系统初始化（神造人）
- 执行程序创建子进程（人生子）
- 用户请求创立新进程（试管婴儿）
消亡
- 寿终：进程运行完成而退出
- 自杀：因运行错误自己退出
- 他杀：进程被其他进程杀死
- 处决：进程因异常而被强行终止
进程有哪些状态？
- 正在cpu上运行的，当然是执行态。
- 进程还可以被挂起，导致挂起的有哪些原因？
- 一个进程在运行过程中主动执行了某种阻塞操作，比如读写磁盘，那么cpu就把这个进程挂起，让其他进程使用。
- 这种挂起属于程序的自身原因，就算cpu分给它，也不能运行
- 另一种情况是一个进程占据cpu太长时间，为了公平起见，挂起该进程，让其他进程也分享一下cpu
- 这种挂起是操作系统的原因，只要cpu分给它，它就能运行，它属于就绪态。这样的话，操作系统只需要查看这种类型的挂起，而无需看上一种
其实不同的OS有不同个数的进程状态，windows有7个，solaris有6个，不管是几个，都是为了方便管理进程，只要细分对管理有利，我们就细分
进程创立的步骤
- 分配进程控制块
- 初始化机器寄存器
- 初始化页表
- 将程序从磁盘读进内存
- 将cpu设置为用户态
- 跳转到程序的起始地址（设置程序计数器）
跳转指令是内核态的，第五步已经将cpu设置成用户态了，问题是怎么解决的？答案是由硬件将第5，6步一次性完成。
进程创立在不同的操作系统的方法也不同
- unix将进程创立分为两个步骤：
- fork，创建一个和自己一模一样的新进程
- exec，将新进程的地址用另一个程序的内容覆盖，然后跳转到新程序的起始地址
- windows使用一个系统调用（CreateProcess）就完成了一个进程的创建，将新程序名称作为参数传过来，创建新页表，无需复制别的进程。
两种方法各有优缺点：
- unix的方法灵活，既可以自我复制，也可以启动新程序。自我复制有时很有用，比如apache创建的进程都一样
- windows的自我复制要复杂一些，而且共享数据只能通过参数传递来实现。
进程管理
进程是谁来管？是操作系统.那么操作系统怎么管？必须要有手段和资源，就像国家要管理人一样，必须先要给人建立档案。
当创建一个新进程时，进程的信息就存在PCB（进程控制块）中。
那么进程有哪些资料呢？主要有：
- 寄存器
- 程序计数器
- 状态字
- 栈指针
- 优先级
- 进程id
- 信号
- 创立时间
- 所耗cpu时间
- 当前持有的fd
采用的数据结构主要就是线性表，链表，struct，树，图等。
进程管理要解决什么问题？公平和效率是进程管理中永恒的话题，是公平重要还是效率重要？不同的倾斜程序引出了不同的进程管理模式。
进程是个好东西，但是有哪些缺点？
- 一个cpu一个时间只能执行一条指令，也就是只能执行一个进程
- 进程在执行过程中如果阻塞了，整个进程就被挂起了，无法继续执行，这样，即使进程里有部分不依赖IO的事情，也无法推进。
为了解决上面两个问题，人们就发明了 线程
线程
线程是进程的分身术。
进程在一个时间只能干一件事，线程可以让进程一个时间可以干多件事。
线程既然是进程的分身，那么每个线程自然在本质上一样的，即拥有一样的程序文本。但每个线程又有不一样的地方，那就是线程的执行上下文，
或者说是执行序列，显然一个进程可以拥有多个执行序列。
如果一个舞台是一个进程，那么舞台上演员就是线程。
线程的好处
将进程分解为线程还可以有效的利用多核cpu。在没有线程的情况下，增加核数并不能提高一个进程的执行速度，但如果分解为多个线程，
则可以让多个线程运转在不同的cpu上，提高整个进程的执行速度。
线程的管理
有了进程后要管理，有了线程同样要管理。存放线程的地方就是线程控制块。
线程是共享一个进程空间的，所以这些共享的资源肯定是不需要放在线程控制块中的，放在进程中即可。但总会有一些东西不是共享的，
这些非共享的内容就要存在线程控制块中了。如果评判哪些资源是独享的呢？一般的标准是：如果某资源不独享会导致线程运行错误，
那么就应该独享，其他的都共享。
按这个标准，共享的内容有：
- 地址空间
- 全局变量
- 文件
- 子进程
- 定时器
- 信号，信号处理程序。
独享的有：
- 程序计数器（因为每个线程的执行序列不同）
- 寄存器（是执行的上下文环境）
- 栈（是执行的上下文环境）
线程的实现方式
既然线程是进程的分身，那么由谁来管就有了两种选择：
- 进程自己来管线程，即用户态线程
- 让操作系统来管线程，即内核态线程
内核态线程实现
线程是进程的分身，是进程的不同执行序列，既然是不同的执行序列，说明线程应该是cpu调度的基本单位，而cpu又是操作系统来管理的，所以看起来线程由操作系统管理是天经地义的。
那么操作系统如何管理线程？与管理进程一样，操作系统需要保存线程的各种资料，即将线程控制块存放在内核空间。这样操作系统就有了进程控制块和线程控制块，根据这些信息，操作系统就可以对线程进行类似进程的管理，例如线程调度，线程的资源分配等。
由操作系统管理线程的好处就是用户编程变的简单，因为线程的复杂性由操作系统承担，用户编程时无需管理线程的调度，即无需关心线程什么时候执行，什么时候挂起；另一个好处是线程执行阻塞操作时，操作系统可以从容的调用另一个线程执行，因为操作系统管理着所有的线程。
但是操作系统管理线程也有缺点：
- 首先是效率低，因为线程在内核态实现，每次线程切换都要从用户态trap到内核态，而trap是需要花时间的
- 另外，内核态的线程实现的方式占用了宝贵的内存资源，因为操作系统需要维护线程表，操作系统的内存空间一旦装在结束就已经固定，无法动态改变。由于线程的数量通常大于进程的数量，那么随着线程数量的增加，内核空间将很快被耗尽。如果要建立线程，但内核空间不够了，会怎么样？操作系统会宁愿终止进程，也不会选择错误的运行。
- 最要命的是内核态线程的实现需要修改操作系统，这在线程概念提出之初是很难办到的事情，操作系统厂商不会为了一个新概念而动大手术。这样就催生了用户态线程的先行实现。
用户态线程实现
线程概念提出之初只能自己在用户态实现，即所谓的谁提出谁举证。用户态实现意味着自己要做线程的切换，自己管理线程的信息，而操作系统无需知道线程的存在。
那么用户态如何进行线程调度？就是用户自己写一个调度器，除了正常的执行任务的线程外，还有一个专门负责线程调度的线程。由于大家都在用户态下工作，所以谁也不比谁占优势，要想取得cpu控制权，只能靠大家的自愿合作。一个线程在执行完一段时间后主动把资源释放给别人用，而在内核态下就无需如此，因为操作系统可以通过周期性的时钟中断把控制权夺过来，用户态的调度器也是线程，没有能力强行夺走控制权，所以必须合作。
用户态线程优点？
- 灵活，因为操作系统不知道线程的存在，在任何操作系统上都能应用
- 线程切换快，因为不需要用户态trap到内核态
- 不用修改操作系统，容易实现
缺点？
- 编程变得很诡异，因为用户态线程需要互相合作才能运转，所以写程序时需要斟酌什么时候应该让出cpu给别的线程，而让出的时机选择很重要
- 另一个严重的问题是，用户态线程无法达到类似进程的多道编程，如果一个线程受阻，它将无法交出控制权，整个进程就无法推进，操作系统就把cpu控制权交给另一个进程，这样一个受阻的线程就导致了整个进程受阻，当初计划的进程分身的原始目的就没有达到。这是致命缺点。
那么怎么破呢？想两个办法，其实都行不通。
- 不让线程阻塞，而这个是行不通的。
- 阻塞后想办法激活另一个线程。
- 这种方法必须依赖操作系统，因为阻塞后，cpu控制权回到了操作系统手中，这时需要修改操作系统，让它不要立即分配给其他进程，而是再给个第二次机会，询问一下有没有线程要切换的？这种做法叫调度器激活，看似可行，但这违反了设计原则，即下层不能调用上层，否则会给黑客留了系统缺口。这种做法也没有达到操作系统厂商的认可。
内核态和用户态的结合
由于内核态和用户态都有缺点，现代操作系统是将二者结合，用户态负责进程内部线程在非阻塞时的切换，内核态的操作系统负责阻塞线程的切换。
多线程引发的问题
人们发明多线程是为了进程级的并发，一个进程中会存在多个线程，这些线程共享进程的空间。那么
这两个问题对于进程来说同样存在，只不过多个进程共享的是整个物理内存。
什么情况会造成一个线程从用户态转为内核态？
- 如果程序运行过程中发生中断或异常，系统将自动转为内核态，进程中断处理。
- 进程进行系统调用，比如read，当处理器处理到read步骤时，发现是系统指令，就会将处理器设置为内核态
线程的不确定性
线程的机制和像硬件的流水线机制，流水线也提供并发，只不过是指令级的，而不是程序级的。
线程通信
通信是人的基本需求。
如果进程间不能进行通信的话，进程所能完成的任务就大打折扣。例如父进程创建子进程后，需要对子进程进行监督。
而线程间的通信则需要更多。一个进程包括多个线程，这多个线程由于共享一个进程空间，天然就有一种合作关系。
舞台上的演员们通过对白进行合作，共同完成一出戏。
想想人和人的通信方式有哪些？
- 两人之间挖个地道 - 管道
- 一个主动拨号，建立连接，打电话 - socket
- 发电报 - 信号
- 旗语 - 信号量
- 两人约定地方，一个人将大包裹放入，另一个取走 - 共享内存，大数据传递。
- 信件 - 消息队列
线程间通信都有哪些方式？
- 管道
- 管道就是一个线性的字节数组，使用文件读写的方式进行访问，但却不是文件，因为文件系统中看不到管道。管道可以设在内存里。
- 管道在shell中和程序中创建时不同的，在shell中使用竖线，而程序中需要系统调用pipe()，pipe调动将返回两个fd，一个用于读，
一个用于写，
- socket
- 始于bsd
- 使用socket的双方都需要创建一个socket，一个是server端，一个是client端。类似虫洞
- 信号（线程电报）
- 由于管道和socket虽然强大，但是使用麻烦，需要建立连接后方可使用。信号被用来解决如下通信需求：
- 迫使另一方立即做出回应
- 不愿意先建立连接，而是临时突然需要发个东西
- 传输量非常小，使用管道和socket不划算。
- 信号就是个内核对象，或者说一个内核数据结构。发送方填好该数据结构，并指明该信号的目标进程后，发出特定的软中断，操作系统收到中断请求后，知道是有进程发出信号，于是到特定的内核数据结构中查找信号接受方，并进行通知。接收方进程进行信号处理。特别像生活中的电报，发电报的人将报文和收报人一起交给电报公司，电报公司将电报送到所在地邮局（中断），并通知收报人来取电报。
- 信号量semaphore（旗语）
- 60年代，由Dijkstra提出的，原型来源于铁路。在一条单轨铁路上，任何时候只有一辆列车在上行驶，而管理这条铁路的系统就是信号量，任何一列火车必须等到信号后才可以驶入，当进入轨道行驶后，需要将信号修改为禁止进入，防止别人火车进入，当驶出时，要将信号修改为允许进入。在计算机里，信号量其实就是一个简单的整数，通过0和1来控制禁止或允许
- 共享内存
- 管道，socket，信号，信号量，虽然满足了多种通信需求，但还是解决不了一种需求，就是两个进程需要交换大量的数据
- 共享内存和管道有点像，但有区别，区别是：
- 共享内存的两个进程必须在同一台物理机器上
- 共享内存的方式是随机的，不像管道只能是一端读，一端写。
- 消息队列
- 和管道的区别是：
- 没有固定的读写进程，任何进程都可以读写
- 可以同时支持多个进程读写，即多对多，不像管道那样点对点
线程同步
引入线程后，就引入了一个巨大的问题，就是多线程程序的执行结果有可能是不确定的。线程之间是合作关系，既然是合作，就要有约定，否则合作就会出问题。
线程同步的目的就是不管线程如何穿插运行，运行结果都是正确的。
典型的例子就是两个人喂金鱼，不喂就饿死，多喂就胀死。要想避免胀死，就要避免竞争，要想避免竞争，就要防止多个线程同时进入临界区。
同一时间，只能有一个人在临界区，这称为互斥。
可以用锁将临界区锁住，但缺点是其他线程只能等待锁释放，效率不高。
sleep和wakeup是操作系统的原语。就是为了避免锁效率不高而发明的。
信号量可以说是所有原语中最强大的，不光是一个同步原语，还是一个通信原语，还可以当锁用。
信号量说白了就是个计数器，有两个操作就是加操作和减操作。历史上把加操作称为P操作，减操作称为V操作。p和v是荷兰语中的单词首字母，分别代表加和减。
减就是获得锁，加就是释放锁。信号量比锁灵活，因为等在信号量上的线程不是等待，而是sleep，等另一个线程执行加操作后被叫醒。所以说二元信号量可以看做是锁、sleep&wakeup的合成。有了信号量，可以轻而易举的解决生产者和消费者的同步问题。
锁解决了同步问题，但带来了循环等待，我们不满意，于是发明了sleep&wakeup，但又带来了死锁，因此又发明了信号量，但信号量的PV操作的顺序至关重要，稍有不慎，就会死锁，如果一个程序有10个信号量，程序员很难搞清楚正确的顺序是什么。
进程调度
cpu调度的总体目标是要达到极小化平均响应时间，极大化系统吞吐率，保持各个功能部件都处于繁忙状态，提供某种貌似公平的机制。
算法：
- 先来先服务（FIFS）： 简单，但不能抢占，有时效率很低
- 时间片轮转是对FIFS的改进，但增加了系统切换开销，时间片间隔越短，cpu被浪费在切换上的时间就越多。时间片轮转同样没有做到绝对公平
- 短任务优先（STCF）： 时间片轮转其实就是大锅饭！STCF就像年轻人遇到老人就让座一样。STCF分为抢占式和非抢占式。缺点是造成长任务饥饿。
- 优先级调度：解决STCF的方法就是设置优先级，STCF本身就是一种优先级，只不过是优先级高的是短任务。不过如果大家都将自己的优先级设置为最高，等同于没用
- 混合调度算法： 既然所有算法都有缺点，那么就摒弃缺点，将他们混合起来，该算法原理是将所有进程按优先级分成几个大类，大类中的进程采用时间片轮转
- 彩票调度算法：调度器给所有进程发一定数量的彩票，调度器随机抽取，抽到谁，cpu就分配给他。解决了饥饿问题。通过给进程分配的彩票数量的设置，可以增加/减少几率
- 实时调度算法： 实时系统要求在规定时间内完成即可，早完成也没有什么好处，例如导弹轨道计算，电视的帧输出。主要的实时调度算法有：
- 最早截止任务优先（EDF）：谁的deadline最早，就给谁，缺点是切换开销大。
- 最短周期优先（RMS）：调度前先计算出所有任务的优先级，然后按结果进行调度，执行中间不接受新的进程，也不调整优先级，和不抢占cpu。优点是效率高，缺点是不灵活
优先级倒挂
是指一个低优先级的任务持有了高优先级任务需要的共享资源，导致高优先级的任务被阻塞。由于低优先级的进程抢不到cpu，而又不释放共享资源，于是导致高优先级的任务无法推进。美国火星探测器就是因为优先级倒挂引起的。解决倒挂的方法有：
- 使用中断禁止： //TODO
- 优先级上限：//TODO
- 优先级继承：当高优先级占了低优先级的资源，低优先级将暂时获得高优先级，执行结束后，再恢复成低优先级
锁的实现
多进程/线程的同步机制虽然各不相同，但都有一个特点，即同步原语都是原子操作。
闭锁的两个步骤：
- 等待锁变成闲置状态
- 获得锁
很显然，锁的闭合之间是有可能被别人插入的，但操作系统为什么能实现原子性呢？其实在微指令级别，不止这两个步骤，甚至有十几步。
硬件帮我们提供了一些原子操作，例如中断禁止，中断启用等等，在这些硬件原子操作之上，我们便可以构建软件的原子操作：锁，sleep，wake等等。
最初硬件提供原子操作只不过是为了方便自己测试，操作系统利用这些原子操作来构建原语只是副产品而已。
内存管理
在OS出现之前，程序并不需要加载到内存里才能运行，在很久以前，程序是直接放在卡片上，计算机每读一张卡片，就运行一条指令，因此程序是直接从卡片到执行。由于卡片的方式效率极低，人们发明了内存，将程序先放入，然后批量运行，提升效率。理想状态下，大家对内存的要求是容量大、速度快、持久化，但物理现实却是缓存+主存+磁盘的这种组合式内存结构，这种架构就需要一个管理机制，就是内存管理。内存管理就是要达到一种效果：让用户不用关心是怎么存的，而只需要关心输入和输出就行了。内存管理实现这种透明的手段就是 虚拟内存 ，虚拟内存是OS历史上革命性的突破。
内存管理的目标是什么？
- 地址保护：一个进程不能随便访问其他进程的内存空间
- 地址独立：使用的不是物理地址，而是虚拟地址，因为物理地址无法提前确定。
计算机中运行的程序可以归为两类：管理计算机的程序（OS）和使用计算机的程序。而OS本身的运行也需要资源，所以OS和应用程序在内存中的位置分配成为内存管理首先需要考虑的问题。
单道编程的内存管理
单道编程环境下，整个内存中只有两个程序，一个是OS，一个是用户程序，由于只有一个用户程序，所以OS的所占内存空间是恒定的。我们将用户程序总是加载在同一个内存地址，OS永远跳转到同一个物理地址上开始执行，这样用户程序里面的地址都可以事先计算出来。这样方式下，内存管理不需要做地址翻译，但同时有问题：
- 如果程序比物理内存大，就无法放入
- 只运行一个程序造成浪费。
- 无法在不同的操作系统上运行，因为不同OS所占的内存大小不一样，使得用户程序的起始地址不一样，编译出来的程序拿到另外一处就无法运行
多道编程的内存管理
在多道编程的情况下，虽然提高的cpu和内存的利用率，但要付出代价：就是OS变复杂了，因为程序无法固定在某个地址上，需要动态地址翻译。
非固定分区的内存管理
一个程序加载进内存后，在运行过程中产生的数据和函数调用分别需要用到数据空间和栈空间，unix采用的方法是：数据和栈在两端，向对方挤占内存，这样能充分利用合占的内存空间
swap
swap是将一个进程dump到磁盘上，再将其从磁盘上加载回内存的过程。swap的目的是为程序寻找一片更大的内存空间，避免程序应该自己的内存不足而崩溃。
空闲内存管理
OS将空闲的内存空间通过链表链接起来，当程序申请时，从链表中查找合适大小的内存
分页内存管理
分页很厉害，解决了内存碎片问题。分页系统的核心是页面的翻译，即从虚拟页面到物理页面的映射，是由内存管理单元（MMU）完成的。MMU为每个程序保存了一个页表，MMU就是通过查表的方式进行完成翻译动作。
文件系统
磁盘
- 一个磁盘有多个盘片，每个盘片正反面都可以存数据，每个盘面都有一个读写磁头，所有磁头连在一根磁臂上，磁臂移动时，所有磁头跟着动
- 盘片匀速转动，转速有7200转/分钟，10000转/分钟等，转一圈大概需要6毫秒到8毫秒
- 每个盘面只有一个磁头，磁头悬浮在盘面上方几微米的高度
- 任何时候，只有一个磁头处于活动状态，从盘面输出的数据流都是串行的
- 为了方便存储，每块盘面又分为磁道和扇区，扇区是IO的最小单位，一个扇区 = 标题10字节 + 512字节数据区 + ECC纠错12-16字节
- 寻道时间 = 磁头移动到磁道的时间（8ms-20ms左右）
- 旋转延迟时间 = 磁头到达磁道后，等待扇区转到下方时等待的时间（通常是1/2的旋转时间，即3ms左右）
从磁盘读取扇面的过程：
- OS将LBA（logic block address）传给磁盘驱动器
- 磁盘驱动器指示磁头去寻找磁道，并等待扇区转到磁头下面
- 磁盘驱动器将数据存在缓冲区
- 磁盘驱动器向OS发出数据就绪的信号
- OS可以从缓冲区中一个字节一个字节的读出（也可以用DMA）
影响磁盘读写的因素：
- 寻道时间（机械）（时间最长）
- 旋转延迟（机械）
- 数据读取（电）
为了减少寻道时间，需要磁盘调度算法（各种算法都有缺点）
文件系统
文件系统就是OS提供给用户的抽象，让磁盘变得更容易使用，用户只需要给出文件名，路径即可，不需要知道磁道，扇区。