cs保研经验贴|操作系统

保研资料：操作系统

OS实现什么？

有效地管理系统中软件硬件资源（处理器、存储、设备、文件）；提供计算机用户与计算机硬件之间的接口，使计算机系统更易于使用。
操作系统特性：并发性、共享性、异步性、虚拟性（虚拟存储管理技术扩充内存空间；虚拟设备管理把独占型设备改造成共享的设备。）。
PSW：CPU运算器的一部分，存放两类信息：一类是体现当前指令执行结果的各类状态信息，如有无进位、有无溢出、结果正负、结果是否为0等；一类是存放控制信息，如允许中断、屏蔽字、中断码等。
并发进程：间断性、非封闭性、不可再现性。并发执行的条件：Bernstein条件。
软件互斥算法一般适用于单处理机系统，多机环境下可并行执行的指令的效果可能是重排序执行的结果，会不满足互斥性。
硬件互斥：存储障碍、原子变量、测试并设置、交换、关中断（仅在单CPU有效）。多CPU下, 指令周期间交叉, test_and_set, swap指令不是原子的。
同步机制：信号量与PV操作、管程、会合（被调用者代调用者执行调用代码，适合分布式环境）、事件。

进程

特征：并发性、动态性、独立性（可以调度）、交互性、异步性（进程各自独立的速度向前推进）、结构性（拥有PCB）。
执行中的程序。当进程发生进程切换时，需要将现场信息（PSW、PC）弹出，保存于PCB中。
多道程序：考虑设备、内存、处理器资源的管理问题。
进程：由进程映像（代码+数据）、进程控制块组成。
上下文：PCB、程序、系统环境（系统栈、打开文件表）。
中断嵌套时，栈内压入PSW、PC、中断处理程序用到的寄存器、中断处理程序的返回点、参数、返回值等。
进程间互斥、同步、信息交换统称为进程通信。
进程创建、撤销过程：向系统申请一个空闲PCB、为新进程分配资源、初始化新进程的PCB、加载程序、将PCB入就绪队列。
一个进程包含多个线程；线程通信容易、系统开销小。
Fork：复制地址空间、复制控制结构。

进程和线程

①进程是程序在其自身地址空间中的一次执行活动，是资源分配的基本单位；
②线程是进程中一个相对独立的执行流，一个进程包含多个线程，是调度的基本单位；
③进程是拥有资源的一个独立单位，有自己独立的地址空间；线程不拥有系统资源，但可以访问隶属于进程的资源，共享进程的地址空间（通讯容易）；
④在系统开销上，进程的系统开销大于线程；线程切换速度快；线程通讯容易。
⑤线程出错时，属于一个进程的其他线程也无法正常运行。
⑥相同：都是实现多任务并发的技术手段、都可以独立调度，父子进/线程调度时平等竞争
线程的应用：内在的多控制流，具有合作性质,需要共享数据；如每个http请求，对应一个线程。

交互式作业，不需要像批处理作业那样把作业控制意图预先写成一份作业控制说明书。Unix下，对于非内部命令，会建立子进程。

内核线程、系统进程

内核线程没有用户栈，只在系统态运行；
用户线程无法进入内核态，需要一个内核线程帮其实现调用；
系统进程：假脱机输入进程、假脱机输出进程；
系统进程包含核心线程，只运行在核心态。

进程的调度性能指标有哪些？

CPU利用率、系统吞吐量、周转时间、平均周转时间、等待时间、带权周转时间=作业周转时间/作业实际运行的时间（带权周转时间越大，说明相对等待得越久）、平均带权周转时间。
调度算法：先来先服务、短作业优先、最短剩余时间优先、最高响应比优先、最高优先数（动态静态）、循环轮转、多级队列、反馈排队；
实时：最早截止期调度（可剥夺）、速率单调调度（优先调度频率最高的实时任务）
多处理器：自调度、组调度（将相关线程同时分配到多处理机，避免相互等待）

通信

管道（也称作共享文件，简单、界面统一、延迟写策略）、消息队列（也称作消息传递，分为有缓冲和无缓冲）、共享内存（也称作共享存储）、信号量和 PV 操作、信号（进程收到信号后执行signal函数，是用户处理的中断）、套接字（Socket）。

死锁

一组进程中的每一个进程，均无限期地等待此组进程中其它进程所占有的，因而永远无法得到的资源，这种现象称为进程死锁。
调度时机不合适，竞争，进程通讯，可能造成死锁。
必要条件：资源独占、不可剥夺、保持申请、循环等待。当每类资源只有一个实例时， Coffman条件为充要条件。
死锁检测时刻：只检测占有资源的进程，他是所有进程的子集。针对request数组而非need数组。检测时间：等待时检测、定时检测、资源利用率下降时检测。
死锁恢复：重启、剥夺资源、进程回退、终止进程。
忙式等待条件下发生的饥饿,称为活锁(live lock). 死锁进程等待永远不会释放的资源, 饿死进程等待可能被释放,但却不会分给自己的资源,其等待时间没有上界。死锁至少涉及两个进程, 饿死进程可能只有一个。死锁一定发生了循环等待,饿死不然。
发生死锁等价于资源分配图约减后仍然存在环。对于资源分配序列来说，即便出现环，也需要进一步判断进程能否同时推进到成环时刻。

存储管理

存储分配（分配表、空闲表）、存储共享、存储保护（检查越界和越权）、存储扩充（内存、外存结合）、地址映射、（程序段的动态连接）
内存页框分配：平均分配、按长度分配、按优先级分配。同时有交换技术、覆写技术来缓解空间。
解决颠簸：工作集模型、页故障率反馈模型。
外存页框分配：静态分配（调入后不在外存删除）、动态分配。
二维地址：因为段号所占的位数不确定，只给出一个逻辑地址，无法得到其段号。
静态等长：字位映象图、空闲页面表、空闲页面链（对于外存页面的分配和去配均需执行一次数据传输，速度较慢）。
动态异长：空闲区域表（最先适应、下次适应、最佳适应、最坏适应）
置换算法：最佳淘汰法、先进先出、最近最少使用（LRU）、最不经常使用的先淘汰（LFU）、最频繁使用的淘汰、最近不用的先淘汰（引用位、修改位。定时清零引用位）、时钟算法、带修改标志的时钟算法
影响缺页的因素：淘汰算法、页框数、页大小、程序本身。

磁盘存储管理有哪些方法？

主要有三种方法，分别是连续分配、链接分配和索引分配。
连续分配：要求每一个文件分配一组相邻接的盘块，访问速度快，但是必须事先知道文件的大小；
链接分配：分为隐式链接和显示链接，隐式链接是指在每个目录项中都含有指向链接文件第一盘块和最后一个盘块的指针，每个盘块都有指向下一个盘块的指针，显示链接是指把用于链接文件各物理块的指针都存放在内存中的一张链接表中。它不支持随机访问，但是利于文件的动态增长；
索引分配：分为单级索引分配以及多级索引分配。它为每个文件分配一个索引表，把分配给该文件的所有盘号都记录在该索引块中。它不能支持高效的直接存取。

虚拟内存的定义

虚拟内存是一种计算机系统内存管理技术，使得应用程序认为它拥有连续的可用内存（一个连续完整的地址空间），而实际上，这些内存通常被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。虚拟存储系统是忽略了主存与辅存的差异，将其都看作是主存。

虚拟内存的工作原理

当进程开始运行时，系统会将一部分程序装入内存，另一部分暂时留在外存。当需要执行的指令不在内存时，系统会自动将它们调入内存；当内存不足时，系统会选择部分内存空间，将其中的内容交换到磁盘上，并释放这些内存空间供其他进程使用

虚拟内存有什么好处？

使得大的程序能在较小的内存中运行、使得多个程序能在较小的内存中运行、局部装入内存利用了局部性，且进程与进程是相互隔离的，提高了系统的安全性。

分页的好处是什么，分页和分段有什么区别？

分页的好处：

（1）实现了虚拟内存：分页将进程的逻辑地址空间划分为固定大小的页，并将物理内存也划分为相同大小的页框。这样，每个进程只需要将所需的页加载到物理内存中，而不需要一次性加载整个进程。

（2）内存利用率高：分页可以更灵活地分配内存，当进程的大小不是固定的且不规则时，分页可以更好地利用内存空间，减少内存碎片的产生。

（3）页表简单：由于页的大小是固定的，页表可以更加简单有效地实现。

分页和分段的区别：

（1）分页以固定大小的页作为单位进行管理，而分段以逻辑段作为单位进行管理。分页的大小是固定的，由操作系统指定；而分段的大小是可变的，由程序员决定。

（2）由于分页使用固定大小的页，会产生内部碎片，而分段可以更好地适应变长的逻辑段，避免内部碎片，但会产生外部碎片。

文件系统

文件和管理信息资源的程序集合称为文件系统，提供按名存取的手段。
文件共享方式：公共目录、连接。
分为主部次部：提高查找速度、实现文件连接。
分为普通文件、目录文件（文件名，文件号序列）、特殊文件。
记录式文件：信息项是记录，记录的序列。文件头保存记录长度和数量等说明信息。物理组织形式：考量空间开销、访问速度、长度变化：顺序、链接、索引、散列、倒排（以键值和记录地址构成的索引结构）。
多级目录：便于文件分类、查找速度快、可以实现文件连接（节省空间+通讯）。

Unix内存映射文件：以访问内存的方式访问文件。解决文件IO慢、访问前打开、访问经过表的问题。通过局部映射实现对大文件的访问；将不必再对文件执行I/O操作。

设备管理

分配去配、设备驱动、缓冲管理。
分为存储型设备、IO型设备、网络设备。
接口（设备控制器）：识别命令、数据交换、地址识别、数据缓冲。
IO端口：接口中的可被CPU访问的寄存器，主要有数据寄存器、状态寄存器、控制寄存器。
通道类型：字节多路通道（时间片轮转，低速IO）、数组选择通道、数组多路通道（时间片轮转）。通道包含通道程序、CAW、CCW、CDW、CSW。一个通道能控制多种设备。
系统调用处理程序:进行设备保护，禁止用户直接访问设备；将逻辑设备名映射为物理设备名
设备驱动程序：实现物理I/O操作的启动和执行

磁头引臂调度：先到先服务、最短时间优先、电梯算法（存在地域差别）、循环扫描（地位相同；磁头粘性）、N-扫描、冻结扫描
缓冲：处理数据到达与离开速度不一致所采用的技术。通过增加缓冲区的个数，可使并行程度得到明显提高。
缓存：将慢速存储器上活动信息缓冲到快速存储设备上的技术。
虚拟设备：在一类物理设备上模拟另一类物理设备的技术。利用共享型设备实现的数量较多、速度较快的独占型设备，将独占型设备转化为共享设备。用户都感到独占了一台设备。
在进程与独占型设备之间增加共享设备缓冲。提高了设备的利用率，且能够立即满足进程的需求。

UNIX

Unix采用可抢占的动态优先调度算法，优先数越大，优先级越低（系统进程优先级高）。
进程互斥使用关中断；
采用事件同步；
采用双对界管理；
分配算法为最先适应算法；
采用工作集模型；
页面置换算法为二次机会法；
普通文件：512B为一块的顺序存取的流式文件，物理结构为链接+索引，分为零级索引和一级、二级、三级索引：即节省空间，又提高速度
空闲磁盘空间管理：成组连接，空闲块链+空闲块表
管理内存中的空闲页框：伙伴堆算法，针对内存碎片问题而提出的一种稳定高效的分配策略；按前后顺序以2i个页面作为一个块组，与其相邻的2i个页面作为另一个块组，那么这两个块组合为一对Buddy.
特殊文件：1.与文件界面统一；2.可以采用相同的保护机制；
采用u_file：进程在共享文件时可采用相同的读写指针；
B链：指向高速缓存块
D链：实际的输入输出队列（同时属于B链）
Bfreelist链：指向系统可用缓冲区，整个系统只有一个（一个缓冲区也能同时属于B链：缓冲区可用的前提下提高缓存效果）
VFS(Virtual File System)文件系统
并不是一个实际文件系统，而是多种实际文件系统的一个统一界面
为多种文件系统（Ext2fs, FAT）提供统一接口，也为各种外部设备提供统一接口