现代操作系统读书笔记

第一章：引论操作系统是运行在内核态的软件，为程序猿提供资源集抽象以及管理硬件1.1.2主要任务：记录那个程序在用什么资源，管理资源分配，评估使用代价，调节冲突1.3.11.操作系统必须知道所有的寄存器，以便中断时保存进度2.用户程序在用户态运行时，仅允许执行至灵级的一个子集，一般不能调用IO和内存保护指令3.陷阱：a.用于执行系统调用b.多数由硬件引起，用于警告异常4.超线程：无并行处理，线程切换纳秒级1.3.2存储器1.寄存器（和CPU一样快）-》高速缓存（多级缓存）-》主存（RAMROMEEROM闪存）1.3.3上下文切换：多道程序系统中从一个程序切换到另一个程序1.3.51.设备驱动程序：控制IO设备，与控制器对话并收发命令2.设备存储器：映射到操作空间A．优点：不需要特定IO指令B．缺点：占地址空间（8088）3.实现输入输出的方法：A．忙等待：设备驱动循环检查IOB．操作完成时中断C．使用特殊的直接存储器访问芯片DMA1.3.61.USB：通用串行总线，键盘鼠标等慢速设备1.3.7启动1.加电-》BIOS检查硬件-》BIOS查询启动设备（设备第一扇区用启动签名才可以作为启动设备）-》硬盘第一区（MBR），分区表，超级块等1.5.1进程1.本质：正在执行的程序的实例，地址空间（coreimage进程可读写，有数据和堆栈）。2.相关：资源集（寄存器，报警，文件清单等）3.容许运行一个程序所需要所有信息的容器4.UID与GID1.5.31.IO设备的分类：A．块设备：硬盘，可随机读取B．字符特殊文件：键盘鼠标2．管道：虚文件，连接进程1.6系统调用1.用户程序与操作系统交互：处理抽象2.能进入内核的过程调用用户态切换到核心态三种方法：中断，异常，系统调用3.TRAP指令：副作用切换到内核态1.7.3微内核1.高可靠性，把操作系统划分成小的，定义良好的模块，只有微内核运行在内核，其他是普通用户程序2.设备驱动：崩溃不会导致系统死机3.机制与策略分离第二章：进程与线程2.1进程模型1.多道程序设计：CPU在多个程序之间快速切换2.UNIX:开始是相同，之后不同。Windows：一直不同。3.进程退出的原因：1.正常退出；2.出错退出；（异常处理）3.严重错误；（非法指令，引用错误内存，除零错误）4.被杀死4.进程层次Windows:没有层次的概念，所有进程地位相同Linux：进程及进程的子女们组成进程组5.进程的三种状态：1.运行态（实际占用CPU）2.就绪态（可运行）3.阻塞态（等待外部事件）6.进程表：储存进程状态（程序计数器，堆栈指针，内存分配状况，打开的文件状态。账号等）7.中断向量：与每一个IO类关联1.中断发生时，中断硬件程序将进程表中的重要数据压入堆栈，计算机跳到中断向量的地址2.汇编语言设置新的堆栈（无法用C语言这类高级语言来描述）8.多道程序设计1.假设一个进程等待IO与停留在CPU的时间比为p，n个进程时，CPU使用率为使用率=1–p^n2.2线程（进程与线程）1.定义：传统操作系统中，每个进程有一个地址空间和一个控制线程2.线程将应用程序分解成可以并行运行的多个顺序线程3.使用多线程的原因：1.并行实体共享同一个地址空间和所有可用数据的能力2.线程更轻量级，所以他们比进程更快创建和撤销3.同时需要大量IO和CPU计算时，多线程允许多个活动彼此重叠进行，从而加快执行速度4.多核系统中，多线程可以真正实现并行5.例子：多线程/单线程web服务器1.第三种设计（有限状态机：并行，非阻塞系统调用，【中断】）：唯一的线程对请求进行考察，如果需要IO，则启动一个非阻塞IO，服务器在表格里记录当前请求，然后处理下一个事项。6.线程模型1.进程：集中程序运行的相关资源（地址空间，全局变量等）2.线程：程序计数器，寄存器，堆栈，共享的地址空间，多个线程的执行能力。7.线程之间没有保护：1.不可能2.不需要（线程之间是合作关系）8.每个线程都有自己的堆栈9.thread_yield：不同于进程，线程无法使用时钟中断强制线程让出CPU10.线程引入的问题1.fork系统调用是否应该复制子线程2.共享文件冲突4线程实现1.用户空间实现1．每个进程需要有其专门的线程表，由运行时系统管理2.优点1.可以在不支持线程的操作系统上实现多线程2.线程切换速度快（调用运行时系统的过程，不需要刷新和上下文切换）3.允许每个进程有自己定制的调度算法4.有较好的拓展性（内核县城需要固定的表格空间和堆栈空间）3.缺点1.某个线程进行阻塞调用会引起所有其他线程阻塞1.使用非阻塞系统调用2.阻塞提前通知（select系统调用）2.页面故障阻塞其他线程3.除非线程放弃CPU，否则其他线程（包括调度线程）无法运行（没有时钟中断）1.运行时系统也给与时钟中断：不好，不可能而且开销大2.内核线程1.内核有记录所有线程的线程表2.使用环保方法回收线程3.在线程级别使用调度算法：如果线程的操作比较多，会带来很大的开销4.信号：是发给进程的。当多个线程注册时，会出问题3.混合实现1.使用内核级线程，将用户级线程与某些或者全部内核线程多路复用（很灵活）4.调度机制1.内核给每个进程安排一定数量的虚拟处理器并且让运行时系统分到线程上2.进程被阻塞后，内核通知运行时系统（upcall）3.根据中断决定是否继续5.弹出式线程1.一个消息的到达导致系统创造新的线程处理消息-》弹出式线程2.优点：没有历史，创建迅速6.重写单线程代码1.私有的全局变量2.可重入的库1.重写整个库2.为每个过程提供wrapper，标志该库正在被使用中3.信号：内核不知道用户级线程，因此不容易将信号发给正确的线程4.堆栈管理：内核不了解线程，无法自动增长，可能会造成线程堆栈出错。2.3进程间通信1.三个基础问题1.进程如何把信息传递给另一个·2.确保两个或多个进程在关键活动中不会交叉3.进程执行的正确顺序2.竞争条件：两个或多个进程读写共享数据，最后结果取决于进程执行的精确时序。3.临界区：多个进程中访问共享区域的程序段1.互斥：不能同时多个进程使用共享变量或者文件2.临界区解决方案四个条件1.任何两个进程不能同时处于临界区2.不应对CPU的数量和速度有任何的假设3.临界区外的程序不应阻塞其他程序4.不能使程序无限期等待进入临界区3.解决方案（基于忙等待：进程如不能进入互斥区，则会一直原地等待）缺点：1.可能导致优先级反转问题2.浪费CPU3.用户级线程会一直忙等待，从而没用办法让拥有锁的线程运行1.屏蔽中断：进程进入临界区之后屏蔽所有中断（CPU不会切换）评价：不好的方案1.不能把屏蔽中断的权力交给用户进程（不打开中断则系统会终止）2.多处理器时不能解决互斥2.锁变量：共享锁，程序在进入临界区之前检查锁的值评价：无法解决临界区问题3.严格轮换法评价：1.可以解决，但为忙等待。只有有理由认为等待时间很短的情况下才使用忙等待（锁被称为自旋锁）2．在一个进程比另一个进程慢很多的情况下，不好（违反条件三）4.Peterson解法评价：可以解决，满足四大条件5.TSL指令（硬件解法）TSLRXLOCK：测试并加锁，把LOCK值读到RX并在LOCK上存入1。原子操作可以阻止所有处理器访问LOCK（屏蔽中断只能屏蔽本地处理器）4．睡眠——唤醒方案（进程无法进入临界区时会阻塞）‘1.原语：生产者——消费者问题：一个发给未睡眠进程的信号丢失了2.解决方案1.唤醒等待位：唤醒时生产者置1，消费者睡眠前检查该位，若为1，则清除该位并继续保持清醒（不好，多进程时需多个等待位）2.信号量（semaphore）：检查数值，修改变量等应为原子操作1.在进入一个关键代码段之前，线程必须获取一个信号量；一旦该关键代码段完成了，那么该线程必须释放信号量。其它想进入该关键代码段的线程必须等待直到第一个线程释放信号量。2．实现方法：操作系统在执行以上事务时屏蔽中断3.另一种用途：互斥锁3.互斥锁：只需要一个二进制位与忙等待差异：在未获得锁时，调用另外的线程4.如何共享锁？a)共享数据结构可以存放在内核并且只能用系统调用访问b)让进程与其他的进程共享部分地址空间5.条件变量1.允许线程因为某些未达到的原因而阻塞2.允许被阻塞而等待的线程原子性进行3.经常与互斥量一起使用：让一个线程锁住一个互斥量，当他不能获得期待结果时等待一个条件变量。有另外一个线程发信号唤醒。4.条件变量不会存在于内存（发出后丢失）5.管程：一个数据结构和能为并发进程所执行（在该数据结构上）的一组操作，这组操作能同步进程和改变管程中的数据1.任何一个时刻管程里只能有一个活动的进程2.第二个进程将被挂起直到活跃进程离开3.如果一个条件变量上有若干程序在等待，则执行signal操作以后，系统只能从中任选一个恢复4.实现：JAVAsynchronized关键字5.劣势1．操作系统是C写的，没有管程的概念2.分布式系统无法避免6．消息传递1.使用系统调用send和receive2.潜在问题：消息丢失，消息认证，消息传递速率低3.编址方法1.为每个进程分配一个唯一的地址2.引入新的数据结构：信箱。消息发往信箱。（解决消费者生产者问题）7.屏障：在每个阶段结尾安放屏障，当一个进程达到屏障时，它被屏障阻拦，直到所有进程都达到屏障2．4调度1.定义：多个进程就绪是，CPU选择下一个将要执行的进程的方法。2.进程行为：IO密集型（web服务器）和CPU密集型（象棋软件）。越来越多的软件倾向于IO密集型，应该多运行这类进程以保持CPU使用率3.何时调度：1.创建新进程时，应该先调度父进程还是子进程2.进程退出时3.进程阻塞时（IO，信号量等）4.IO中断发生时4．调度算法定义:1.抢占式：挑选一个进程，并且让进程运行某个固定时段的最大值，之后挂起2.非抢占式：挑选一个进程，让进程运行直到其阻塞或者自动释放CPU5.调度算法目标（所有系统）：1.公平：每个进程公平的CPU份额2.策略强制执行：所宣布的策略执行3.平衡：系统所有部分都忙碌6.调度算法分类：1．批处理：处理周期性作业，广泛的商业应用1.调度算法目标：1.吞吐量throughout：系统每小时完成的作业数量2.周转时间turnaroundtime:从一个批处理作业提交时刻开始直到作业完成时刻位置的平均时间3.CPU利用率2.具体调度算法：1.先来先服务（first-come）优点：易于理解，便于实现缺点：同时运行IO密集型和CPU密集型程序时效率低下2.最短作业优先（不可抢占）1.计算公式：T=na+(n−1)b+(n−2)c+⋯+zn其中abc….z2.只有所有作业都可同时运行且运行时间可以预知的情况下才能使用3.最短剩余时间优先：最短作业优先的抢占版1.新作业到达时，整个时间与当前进程的时间做比较，运行剩余时间较少的作业2.交互式系统1.调度算法目标：1.响应时间：发出指令到相应的时间2.均衡性：满足用户的期望2.具体调度算法1.轮转调度：最古老，最简单，最公平，使用最广1．每个进程被分配时间片，时间片结束时切换进程2.时间片1．过长：对短命令的交互请求时间变长2.过短：过多进程切换，降低CPU效率2.优先级调度：每个进程赋予优先级，优先级高的进程先执行1.使IO进程良好运行的算法：进程优先级为1/f，其中f是进程在上一时间片中实际运行的比例（IO进程会得到较高优先级）2.多优先级队列：低优先级可能出现饥饿现象3.多级队列1.实现方法：最高优先级的进程获得1个时间片，之后优先级下降并在下次运行时获得两倍的时间片4.最短进程优先1.根据过去进程运行时间预测并执行估计运行时间2．老化算法：当前测量值和先前估计值进行加权平均（1/2比较好，右移一位即可）5.保证调度：每个进程获得1/n的时间6．彩票调度：向进程提供各种系统资源的彩票，某些进程可以协作获得更多彩票。不错的方法7．