OS理论

王道刷题重点

1. 进程切换时，需进行上下文切换，完成:1).将当前CPU中各寄存器的内容存到当前进程的PCB中；2).将新进程的现场信息装入CPU各个寄存器；3).将控制转至新进程，即更新程序计数器、用来指明系统内核栈位置的寄存器——栈基址寄存器和指明当前进程顶级页表基地址(这里指的是物理地址)的寄存器——页表基址寄存器。
2. 死锁产生的四个必要条件:互斥条件、请求并保持条件、不可剥夺条件和循环等待条件。
3. 死锁处理策略：死锁预防(破坏必要条件，可以确保不发生死锁现象)、死锁避免(资源动态分配，防止进入死锁状态，银行家算法不能判断系统当前是否处于死锁状态)、死锁检测(允许发生死锁，采取措施解除)
4. 在具有对换功能的OS中，通常将外存分为文件区和对换区，前者存放文件，后者存放从内存换出的进程。抖动现象指刚被换出的页很快又要被访问，而又要被换出其他页，而该页又很快又要被访问，如此频繁地置换页面导致大部分时间花在页面置换上，使系统性能下降。撤销部分进程可减少要用到的页面数，防止抖动。
5. 采用连续分配方式，使很大的一部分内存处于暂时或“永久”的空闲状态，造成内存资源浪费，无法从逻辑上扩大内存容量，因此虚存管理只能建立在离散分配的内存管理上。虚存实际容量受外存和内存之和限制，最大容量由计算机地址位数决定。虚地址空间大小由底层的虚存管理机制和OS决定，不同的OS有所不同，与内存和硬盘大小无关，这二者只决定了虚拟存储器实际可用容量的最大值。
6. 只有可变全局、可变局部和固定局部三种置换方式。
7. 页缓冲队列是将被淘汰的页面缓存下来，暂时不写回磁盘，队列长度会影响页面置换速度，但不影响缺页率。
8. 管道机制中的数据只存在于内存中。
9. 操作系统在执行系统调用时可以被中断。
10. 互斥同步设计上应遵循的准则：空闲让进、忙则等待、有限等待和让权等待。实现的硬件方案有中断屏蔽、使用Test and Set指令和使用swap指令(原理与TS类似)。
11. 管程是一种高级同步机制，由名称、局部于其内的共享数据结构说明、对该数据结构进行操作的一组互斥执行过程和对局部于其内的共享数据设置初始值的语句组成。为了区别不同等待原因，引入条件变量，对应不同原因的进程阻塞等待队列。
12. 条件变量与信号量区别：前者值不可增减，后者可；前者wait操作一定阻塞当前进程，没有等待进程，signal将丢失。访问条件变量必须有管程的锁。
13. 一个进入管程的进程执行等待操作时，其应释放管程的互斥权，当后进入管程的进程执行唤醒操作时(如P唤醒Q)，管程中便存在两个同时处于活动状态的进程，有三种处理方式:P等待Q执行(Hoare管程)、Q等待P执行(MESA管程)和规定唤醒操作为管程中最后一个可执行操作(Hansen管程)。
14. 对于Hoare管程，有两个等待队列，一个是正常的由于管程的互斥性而产生的入口等待队列，另一个则是因为Hoare的管程唤醒机制，由于唤醒的进程将接替当前进程运行，当时当前进程实际上并未运行结束，因此仍需要在唤醒的进程运行完后继续运行，因此诞生了紧急等待队列，有着比前者更高的优先级。
15. 进程间的通信有两种低级和高级。前者只能传递状态和整数值，包括信号量和管程机制，有传送信息量小和编程复杂的缺点；后者包括管道、共享内存和信息系统。
16. 管道是半双工，即数据只能单向流动。无名管道只能用于父子或兄弟进程间。有名管道(FIFO)可使不相关进程间也能交换数据。
17. 消息传递通过两个**通信原语(send和receive)**来实现。
18. 共享内存是最有用的IPC，也是最快的，效率很高，但是需要同步机制约束不同进程对内存的读写，安全性不如消息传递。
19. 套接字不仅可用于不同机器间进程通讯，也可用于本机的两进程通讯。
20. 虚存技术特征：离散性(物理内存分配不连续)、多次性(作业分成多次调入内存)、交换性(允许作业运行过程中换进换出)和虚拟性。虚存内存量的扩大是以牺牲CPU处理时间及内外存交换时间为代价。
21. cache的管理完全由硬件完成，对系统和应用程序员都透明。而虚存管理由软件和硬件共同完成，其对实现内存管理的系统程序员不透明，对应用程序员透明。
22. Belady现象只出现在使用FIFO的替换算法的时候。
23. 进程的工作集:当前正在使用的页面集合；驻留集：虚存中，每个进程驻留在内存的页面集合，或分到的物理页框集合。
24. 驻留内存的进程数增加，或进程并发水平的上升，CPU利用率先上升后下降，下降的原因就是”抖动”。抖动的消除与预防：局部置换策略(将抖动局限在小范围内，并未消除抖动的发生)、引入工作集算法、预留部分页面和挂起若干进程(腾出内存空间供抖动进程使用，消除抖动现象，宏观层面)。
25. 负载控制主要解决系统应当保持多少个活动进程驻留在内存的问题，即控制多道程序系统的度，若内存中活动进程数太少，其将增加新进程或激活一些挂起进程；相反暂时挂起一些进程。
26. 可挂起进程：优先级最低、缺页、最后一个被激活、驻留集最小和最大的进程。
27. 多级页表破除页表连续性假设。
28. 内存映射文件：进程通过一个系统调用将一个文件映射到其虚拟地址空间的一部分，访问这个文件就像访问内存中的一个大数组，而非对文件进行读写。多数实现中，在映射共享的页面时不会实际读入页面内容，访问页面时才会被每次一页的读入，磁盘文件当作后备存储。进程退出或显式解除文件映射时，所有被修改页面回写回文件。
29. 一个作业的完成要经过作业提交、作业收容、作业执行和作业完成4个阶段。作业是用户向计算机提交任务的任务实体。一个作业可由多个进程组成，且必须至少由一个进程组成，反之不成立。一个作业常有程序、数据和操作说明。每个进程由PCB、程序和数据集合组成。
30. 页表存放在内存中，属于进程的现场信息。用于记录进程的内存分配情况，实现进程运行时的动态重定向。
31. 不具备页面对换功能，不支持虚拟存储器功能的内存管理方式称为纯分页或基本分页内存管理方式。
32. 哈希页表的每一条目都包括一个链表元素，有如下3个域:虚拟页码、所映射的帧号和指向链表中下一个元素的指针。就是哈希链表的存储方式。
33. 使用反向页表可以使占用内存空间小，依据进程在内存中的物理页面号组织(按物理页面号排列)，表项内容是逻辑页号P及所属进程id。大小只与物理内存大小相关，与逻辑空间大小和进程数无关，使用方式如下图：
    ，地址转换的流程，就是拿进程id和页号去检索反向页表，若检索整个页表未找到匹配的页表项，表明该页未调入内存，对有请求调页功能存储器产生缺页中断，否则表示地址出错。若检索到匹配表项，则表项序号i即为页的物理块号，将块号与页内偏移构成物理地址。可能需要查找整个表来寻找匹配的页表项，可以使用哈希页表限制页表条目或加入TLB改善查找性能。由于每个物理帧只对应一个虚拟页条目，所以很难共享内存。
34. 实现数据共享的最好方法是分段内存管理。
35. 共享以信息的逻辑单位为基础，页是存储信息的物理单位，段是信息的逻辑单位。
36. 页式管理中地址空间是一维的。
37. 相较于页式管理，段式管理更加安全，其以信息的逻辑单位进行保护，而页式则在一个页面中可能装有2个不同的子程序段的指令代码，不便于保护。
38. 一个段可定义为一组逻辑信息，是两维地址结构。
39. 可重入代码，又称”纯代码”，一种允许多个进程同时访问的代码，不允许其在执行过程中有任何改变。
40. 为满足分段的动态增长和减少外部碎片，要采用拼接手段。页式管理无外碎片。
41. 硬盘实际扇区数比硬盘标签上标定的大，其中一部分用于存储硬盘的固件(硬盘控制器使用)；一部分是用户存储数据区域，(工作区)，即硬盘标定容量的扇区；剩下的为保留区，超过在固件里定义的硬盘容量的扇区就为保留扇区。用于记录硬盘生产过程中产生的缺陷的是P表，永久缺陷列表；用于记录硬盘使用过程中由于磁介质性能变弱引起的缺陷的是G表，增长缺陷列表。
42. 硬盘的0柱面、0磁头、1扇区构成主引导扇区(MBR)，占512B，用于硬盘启动时将系统控制权转给用户指定的、在分区表中登记了某个操作系统分区，其内容在硬盘分区时由分区软件写入，不属于任何一个OS，不夹带OS性质，具有公共引导特性。其由两部分组成，前446B是启动代码及数据，此后是由4个有16B的记录启动时的分区参数的分区项组成的分区表(DPT)和2B的魔数组成。
43. 由于MBR限制，硬盘只能有4个主分区，系统必须装在主分区上，硬盘分区有三种：主磁盘分区、扩展磁盘分区和逻辑分区。一个磁盘主分区至少有1个、最多4个，扩展分区可以没有，最多一个。主分区+扩展分区总共不能超过4个，逻辑分区可有若干个。主分区只能有一个是处于激活状态。分出主分区的部分可分成扩展分区，可全分也可不全分。扩展分区不能直接使用，一定要分成若干逻辑分区。
44. Flash Disk有两种技术NOR和NAND，前者在随机读取和连续传输速度上都比后者快，但连续大数据传输速度基本一致，且前者平均成本比后者高。
45. 现代OS基本特征:并发执行、资源共享、虚拟化和异步性。OS的内核态又称管态，用户态又称目态。
46. 杂凑页表就是哈希页表。
47. CPU的三种调度，高级调度、宏观调度、作业调度：对每个作业进行调度；中级调度、内外存调度：进行存储资源在内外存间的调度；低级调度、微观调度、进程或线程调度。
48. 死锁解除的两种方法：资源剥夺法和撤销进程法。
49. I/O设备分类：按数据组织：字符设备、块设备；按用途：存储、传输和人机交互设备；资源分配：独占设备、共享设备和虚设备。
50. 内存映射I/O(控制器内存/寄存器作为物理内存空间一部分)，不用特殊的保护机制组织用户进程进行相应I/O操作，可引用的内存每一条指令都可适用于引用控制寄存器。不允许对一个控制寄存器内容进行高速缓存。
51. I/O独立编址：外设不占内存地址空间，编程时易于区分是在对谁进行操作。但这样设计指令类型少，操作不灵活。
52. I/O的软件组成自顶向下为：用户层(使用I/O系统调用、格式化I/O、SPOOLing)、设备无关软件层(命名、保护、阻塞、缓冲、分配设备)、设备驱动程序层(设置设备寄存器、检测状态)、中断处理程序层(进行进程上下文切换，对处理中断信号源进行测试，读取设备状态和修改进程状态并在设备工作结束后向CPU发中断信号等)、硬件层(执行I/O操作)。
53. 设备独立性的好处：设备分配时的灵活性和易于实现I/O重定向。
54. 与设备密切相关代码在设备驱动程序中，每一个设备驱动程序处理一种设备类型。接收来自与设备无关的上层软件的抽象请求并执行，是I/O进程与设备控制器间的通信程序，与I/O设备特性和I/O控制方式紧密相关。由自动配置和初始化子程序(检测驱动的硬件设备是否存在正常)、I/O操作子程序(调用此为系统调用结果，执行时用户态变为管态)和中断服务子程序(接收硬件中断，再调用中断服务子程序)三者组成。以模块初始化函数为入口，完成初始化后不再运行，等待系统调用，不使用标准C库。
55. SPOOLing技术，利用假脱机技术将独享设备变成有共享特征的虚拟设备来提高设备利用率。由输入输出井(前者用于暂存I/O设备输入数据、后者暂存用户程序和输出数据)、输入输出缓冲区(前者暂存由输入设备送来数据此后再传给输入井，后者暂存输出井来的数据，再传给输出设备)和输入输出进程(前者模拟脱机输入的外围控制机将用户要求数据从输入机通过输入缓冲区再送到输入井，CPU需要时直接从输入井读入内存；后者将用户要求输出数据从内存送到输出井，待设备空闲时，再将输出井中数据经输出缓冲区到输出设备上)组成。
56. RAID——廉价冗余磁盘阵列。主要利用数据条带、镜像和数据校验获得高性能、可靠性、容错能力和扩展性
    RAID0：条带化存储、连续以位或字节为单位分割数据并行读/写于多个磁盘上，有高数据传输率，无数据冗余；
    RAID1：镜像，成对独立磁盘互相备份，成本最高。
    RAID2：海明码校验条带存储，数据条块化分布在不同硬盘上，单位为位或字节，需多个磁盘存放检查及恢复信息，冗余磁盘数与数据盘数的对数成正比。
    RAID3：奇偶校验条带存储，数据条带存储单位为字节，将数据条块化分布不同磁盘上，用单块磁盘存放奇偶校验信息，对大量连续数据可提供好的传输率，对随机数据，奇偶盘会成为写操作瓶颈。读写要访问组中所有盘，每组中有一个盘作为校验盘。出差错后恢复时间较长。
    RAID4：奇偶校验条带存储，共享校验盘，数据条带存储单位为块，条块单位为块或记录，每次写操作要访问奇偶盘。与RAID3很相似，但是访问数据方法不同，RAID3的一次磁盘访问将对磁盘阵列中所有磁盘进行操作。
    RAID5：奇偶校验条带存储，校验数据分布式存储，数据条带存储单位为块，不单独指定奇偶盘，在所有磁盘上交叉地存取数据与奇偶校验信息，读/写指针可同时对阵列设备进行操作，提供更高的数据流量。更适合小数据块和随机读写的数据。与RAID3相比，3每进行一次数据传输就涉及所有阵列盘，但5大部分数据传输只对一块磁盘操作，可并行操作.5有写损失，即每一次写操作将产生四个实际的读/写操作，其中两次读旧数据及奇偶信息，两次写新的。当有两块盘损失时，整个RAID数据失效。
    RAID6：奇偶校验条带存储，两个分布式存储校验数据，存储单位为块。与5相比增加了第二个独立的奇偶检验信息块，两个独立奇偶系统使用不同算法，可靠性高，即使两块盘同时失效也无影响。相对于5有更大“写损失”，写性能差，存储开销是5的两倍。

理论易考点(可能的)

1.gcc调用包含几个工具:cc1(预处理器和编译器)、as(汇编器)、collect2(链接器)。

2.链接过程是将.o文件链接起来形成可执行文件，重定位是将之前未填写地址填写的过程。

3.内存管理的基石：地址独立和地址保护。

4.存储分配的三种方式：直接指定(编程或编译时使用实际地址)、静态(装配程序时确定地址)和动态(装入时确定在存储空间位置，执行过程中可多申请或归还)。

5.整个内存里只有用户程序和操作系统两个程序的环境下是单道程序内存管理。采用分区式分配(将内存分成一些大小相等或不等的分区)的环境为多道程序内存管理，根据大小是否可变分为固定式和可变式。前者根据分区获取作业方式分为单队列和多队列。

6.空闲空间表示方式：位图和链表

7.可变分区采用已分配和未分配两张分区表，每张表表项为内存控制块MCB包括AMCB(Allocated)和FMCB(free)

8.基于顺序搜索的分配算法:FirstFit(较大空闲分区保留在内存高端、容易产生外碎片)、NextFit(剩下空闲块大小均衡，但缺乏大空闲分区)、BestFit(容易留下很多难以利用的外碎片)、WorstFit(大作业难以被满足)

9.基于索引搜索的分配算法(大中型采用较多)：快速适应算法、分类搜索法，空闲分区按大小分类，常用到长度空闲区设立单独的空闲区链表，系统设立一张管理索引表；伙伴系统(介于固定和可变间的动态分区技术)。

10.移动作业将多个分散小分区拼接成大分区称为紧凑。

11.将相对独立的程序段和数据段分别装入内存中不同区域。

12.采用界限寄存器或内存保护键法来进行分区的内存保护。后者实现是内存块和进入系统作业都分配保护键，进行匹配，成功才能运行，否则停止。前者通过值的比较。

13.多道程序下扩充内存方法：覆盖(早期，要求作业模块间有明确调用结构，程序员需指明覆盖结构)与交换(现代，利用辅存在主存满时进行交换达到扩充的效果)。

14.进程需要连续的空间。

15.页的保护：地址越界保护和保护位的设置。分段内存管理是实现数据共享的最好方式。

16.段式内存管理：方便编程、信息共享、信息保护(以信息的逻辑单位进行保护)、动态增长、动态链接

17.虚拟内存量的扩大以牺牲CPU处理时间及内外存交换时间为代价

18.虚存的调入问题，预调入与按需调入。前者在刚开始所有页都在磁盘上，页需通过页错误调入，此时会将所需要所有页调入，阻止大量页错误，有时效好。后者则是只在有需求时调入，需使用备份存储，来保存不在内存的页，即快速磁盘。

19.页面替换算法：OPT、FIFO、Second Chance(就是在FIFO基础上多给了一次判断是否被访问过，优先替换靠后的未再次被访问过的，若都被访问过仍按照FIFO原则)、Clock(最近未使用，将FIFO队列形成一个环形队列，若无缺页错误，则访问的页面访问位置1，指针不动；产生缺页错误，且当前指向C，环形队列下一个为D，则若C被访问过，即访问位为1，置0，指针指向D；若C访问位为0，则替换掉C，指向指向D)、LRU、Aging(老化算法)

20.换出更新问题，若换出页面为file backed类型，且未修改，则丢弃；但已修改，则需要写回。若为anonymous类型，若为第一次换出，写入Swap区；若不为第一次且未修改丢弃；若已修改，写入Swap区。

21.

22.由若干指令组成的连续不可分割的指令序列来在内核态下执行且常驻内存来实现某个特定操作功能。

23.fork函数执行后一个进程变为两个，一个子进程，一个原来的父进程。前者返回0，后者返回子进程进程号(用来区别父子进程)，若出现错误，fork将返回负值。

24.进程上下文切换与陷入内核是不同的，前者由调度器执行、保存进程执行断点、切换内存映射；而后者则是模态切换，CPU状态改变、需保存执行现场，通常由中断、异常、自陷指令引起。

25.引入线程来减小进程切换开销、提高进程内并发程度和共享资源，线程是进程中的一个实体，一个CPU调度和分派单位，只拥有必不可少的少量资源、可与其他同进程的线程共享进程的资源。

26.进程有：虚空间、进程映像、处理机保护、文件和I/O空间；线程有:运行状态、保存上下文(程序计数器)、栈和资源共享机制。

27.进程是资源分配的基本单位，线程是处理机调度的基本单位，所有进程共享其所属进程所有资源与代码。进程需要通过消息通信同步，线程协作同步较容易。线程不能单独执行，每个线程都有程序的入口、执行序列及出口，须组成进程才能被执行。

28.线程的三种实现方式：用户级、内核级和混合式。用户级通过library模拟的thread，不需或仅需较少kernel支持，切换线程与内核无关，易于优化，可在任何OS上运行，但是过多的系统调用会引起阻塞，相关线程将都被阻塞；内核级即为kernel的多个分身，任一分身处理一件事，这处理非同步事件极有用，支持此类线程的称为多线程内核(Windows、linux、mac OS X等)内核级实现多个处理器上调度一个进程多个线程实现同步并行执行，阻塞只发生在线程级别，但是进程中线程切换需要内核参与，而又涉及进程进程和线程线程两种模式，降低了效率。前者创建、撤销和调度不需OS支持、后者需要且与进程大体相同。前者执行系统调用时导致所属进程中断，后者则只导致该线程中断。

29.只有用户级线程系统中，CPU调度以进程为单位，由用户程序控制线程的轮换运行，程序实体为用户态下运行的程序；在有内核支持线程系统中，CPU调度以线程为单位，由OS线程调度程序负责调度，任何状态下运行程序。

30.混合型，线程在用户空间创建和管理，要实现从用户空间的线程到内核空间线程的映射。

31.根据实现用户级和内核级线程连接方式的不同，分为many-to-one(效率较高，但一个线程阻塞时整个进程都阻塞，多个线程不能并行运行在多处理机上)、one-to-one(并发能力强，每个用户级都要有一个内核级，开销大)和many-to-many(折中前两种方式)三种(前用户后内核)。

32.linux不区分进程线程，将后者定义为执行上下文。

33.fork和clone系统调用，两者都建立新进程，前者创建普通进程，后者创建线程。前者不指定克隆标志使用SIGCHLD标志，后者可由用户指定克隆标志(CLONE_VM(父子进程共享同一mm_struct结构，用于创建一个线程)、CLONE_FS(共享同一文件系统)、CLONE_FIFES(共享打开文件)等)。

34.仅允许一个进程访问的资源是临界资源，每个进程中访问临界资源的那段代码称为临界区。

35.机制设计上遵循的准则：空闲让进、忙则等待、有限等待(应保证要求访问临界区的进程在保证在有限时间内进入临界区，避免死等)和让权等待(长时间不能进入临界区要释放处理机，避免忙等)。

36.进程互斥软件实现有两种算法：Lamport面包店算法(排队取号的方式，若号码相同则按进程编号依次进入，会造成忙式等待，空耗CPU资源)和Eisenberg算法。

37.硬件实现方案：中断屏蔽(进临界区前关中断，退出前开中断，但不适用多CPU系统，性能损失大)、使用Test and Set指令(TSL指令，一种不可中断的基本原语，若一个进程在执行该指令，其他进程不能执行，可用于提供互斥支持)和使用swap指令(同TSL，是不会被选中断的原子指令，功能是交换两个字内容，同TSL指令类似，也会由于循环对换两个变量，导致忙等)。

38.MIPS中的spinlock，MIPS提供了LL和SC两个汇编指令实现，前者是从内存中读一个字来实现接下来的RMW(Read Modify Write，先从Mem中读data，然后对其进行修改，再写回)，后者是向内存中写入一个字来完成RMW操作。

39.为了解决某个进程等待某个条件发生而产生忙等浪费CPU时间的情况，可使用两条进程间的通信原语Sleep和Wakeup，将其变为阻塞。

40.为了统计唤醒次数，引入信号量，这种只允许对其进行P和V操作的原子操作的特殊变量，同时还设定了两种操作P(S)(test\semWait)和V(S)(increment\semSignal)，PV操作是进程的低级通信。

41.信号量：一个确定二元组(s，q)，s初始化为非负整型数，s>0，则值为发P操作后可立即执行进程数；s==0，则发出P操作后进程被继续执行完;s<0，则发出P操作后进程阻塞，-s为被阻塞进程数。q是一个初始化为空的队列，被阻塞的进程进入此处。

42.单处理器系统中，并不是任意时刻都只有一个进程处于执行态，也有可能由于系统死锁，导致全部进程阻塞。

43.一个进程可以顺序执行一个或多个程序，但不能同时执行多个程序，一个程序的一次执行可以产生多个进程。

44.进程间可能无关，但也可能有交互性。

45.并不是所有信号都可以由用户自定义处理函数，有的只能按照默认处理程序来。

46.信号的处理时机只会在内核态转为用户态时，反之不会检查。OS对某些信号的默认处理可能就是忽略。

47.线程是CPU调度的基本单位，可以独立执行程序。

48.线程的优点有提高系统并发性、节约系统资源、便于进程通信，但不能增强进程安全性。

49.用户级线程调度以进程为单位，各个进程轮流执行一个时间片。内核级线程调度以线程为单位，各线程轮流执行一个时间片，

50.用户级线程在用户空间中实现，不能直接利用系统调用获得内核的服务，只能借助OS的帮助来获得，其只能在用户态运行。

51.用户级线程的切换由应用程序自行控制，不由OS干扰，OS感受不到其存在，而系统调用、I/O请求和异常处理等涉及内核态的事件不会导致用户级线程切换，会导致内核级线程切换。线程同步作为多线程间协调执行顺序的机制(互斥锁、信号量、条件变量等)，是会有可能进行线程的切换。

52.有了线程后，进程是资源分配单位，内核级线程是处理器调度和分派单位。

53.在同步问题中，有多少资源就将信号量的初值设置为多少，申请资源时执行P操作，释放资源时执行V操作，前者保证对于该临界资源的互斥访问，后者保证临界资源可被释放。

54.在同步问题中，若某个行为会提供某种资源，则在该行为后加上V操作，唤醒需要该资源的行为。若某个行为要用到该资源，则在其之前加上P操作去尝试获取这个资源。

55.每对前驱关系都是一个同步问题，因此每对都要设置一个同步信号量，初值为0.在“前驱操作”后加上V操作，在“后继操作”之前加上P操作确保前驱关系的正常运行。

56.不同线程对同一个进程内的共享变量的访问才有可能要进行互斥，不同进程的线程、代码段或变量不存在互斥访问的问题，同一线程内的局部变量也不存在。

57.硬件方法实现进程同步时不能实现让权等待，Peterson算法实现满足有限等待但不满足让权等待。

58.一组互斥关系需要指出是哪些进程对哪个变量的互斥，考虑两种情况：1.两个进程1、2对共享变量C互斥访问，进程1、3也对C互斥访问，这是两组不同的互斥关系，不能简单理解为对C的互斥，这时若2、3进程间不互斥，就可以不设置信号量来管理，可提高并发性；2.进程1、2、3两两间都对C互斥访问。

操作系统的基本类型

批处理系统

分时系统

实时系统

混用系统

操作系统的特征

操作系统的功能

处理机管理

进程：将学校比作操作系统，每个学生比作程序，那么进程大致是学校赋予每个学生的学籍，是用来管理每个程序的标识。

存储器管理

设备管理

文件系统(持久化接口)

作业控制

操作系统结构

模块式接口

宏内核(Linux)

有序分层法

虚拟机结构

微内核结构(Windows类微内核)

将部分服务处理和用户管理放在用户态。

系统引导

BootLoader

指引导加载程序是系统加电后运行的第一段软件代码，一般独立于操作系统，不让可以由OS代替。

嵌入式一般采用U-Boot，x86采用LILO和GRUB，这两者是重要的Linux的加载器。

内存管理

存储管理基础

程序的链接与加载

原理

ELF文件格式请参照OS实验。

**链接的本质是合并相同的”节”**。也就是将每个程序的同一类型的节放在一起，例如：hello.o和main.o的.text和.data分别放在一块。

使用分段或分页实现加载。1.对每个段，根据其在内存中大小，为其分配足够的物理页，并映射到指定的虚地址上，再将文件内容拷贝到内存中。2.若ELF中记录的段在内存中大小大于在文件中大小，多出来部分用0填充。3.设置进程控制块中的PC为ELF文件中记载的入口地址。4.移交控制权给进程。

text段和data段都在可执行文件中，由系统从可执行文件中加载，但bss段不在可执行文件中，由系统初始化。

一个装入内存的可执行文件，除了这三个段外还有一个作为存放、交换临时数据的内存区的栈和一个作为存放进程运行中动态分配的内存段的堆。

**gcc调用包含cc1(预处理器和编译器)、as(汇编器)、collect2(链接器)**。

内存分配方法

直接指定方式

程序员编程或编译程序对源程序进行编译时，所用的为实际地址，即物理地址。

静态分配

编程或由编译程序产生目的程序，均可从地址空间零地址开始，在装配程序时进行连接装入时才确定在主存中的地址。

动态分配

作业在存储空间中位置在装入时确定，其执行过程中可根据需要申请附加存储空间，且在不需要时可归还。

单道程序的内存管理

内存中只有两个程序：用户程序、操作系统。其中，后者空间固定，则可将前者始终加载到同一个地址，用户程序的地址在运行前可计算。

优点：执行过程中无需任何地址翻译工作，运行速度快；缺点：比物理内存大的程序无法加载，而无法运行，造成空间、计算资源等的浪费

多道程序的内存管理

分区式分配

内存分为一些大小等或不等的分区，其中每个程序占一至多个，操作系统占一个。这适用于多道程序系统和分时系统，支持多程序并行运行但难进行内存分区共享。

固定式分区分配（静态），程序适应分区

内存被划分为若干个固定大小的连续分区。有单多队列的分配方式。

单一队列分配:需加载程序时，选一个当前闲的够大的分区加载，**可采用共享队列的固定分区(多个用户程序排在一个共同的队列里等待分区)**分配。

多队列分配：每个分区一个队列，程序按大小排在相应的队列中。

固定分区，优点：易实现，开销小；缺点：内碎片造成浪费，分区总数固定，限制了并发程序数。

采用：分区表记录分区大小和使用情况。

可变式分区分配，分区适应程序

分区边界可动。无内碎片(分配给作业的内存空间未被利用的部分)，但有外碎片(也就是内存上分区与分区间存在的残留空间)。

这里先介绍一下，内存空间跟踪的两种方法：**位图表示法(分区表)和链表表示法(分区链表)**。

位图表示法：为每个分配单元赋予一个字位，记录该分配单元是否闲置，例如:0表示闲置，1表示被占。空间成本固定，时间成本低，但无容错能力，例如：若一个单元为1，不能确定其本为1还是因错为1.

链表表示法：将分配单元按是否闲置链接起来。空间成本取决于程序数，时间成本较高，操作不易。有一定容错率。

内存分配有两张表：已分配和未分配。

每张表表项为内存控制块MCB，内含AMCB(分配的控制块)和FMCB(未分配)。FMCB按某种次序构成链表结构，当分区被分配出去时，其前后指针无意义。

可变分区分配操作：

先规定几个参数含义：size(不再切割的剩余分区大小)、u.size(请求的分区大小)、m.size(空闲分区大小)。

若m.size-u.size <= size，将整个分区分配给请求者，否则，从分区中按请求大小划分一块内存空间分配出去，余下部分留在空闲分区表中。

基于顺序搜索的分配算法

1.首次适应算法：每个空白区按其在内存空间中地址递增顺序相连，在为作业分配内存区域时，从这个空白区域链的始端开始查找，选择第一个足以满足请求的空白块。(也就是每次都从头开始找)。分配和释放的时间性能好，较大的空闲分区保留在内存高端，但随着低端内存被不断分配，产生很多小分区会增大开销。

2.下次适应算法：将内存空间中空白区构成一个循环链，每次为内存请求查找合适的分区时，总从上次查找结束的地方开始查找。对内存空间利用更加均衡，不会使小空闲区集中在一端，但会导致缺乏大空闲分区。

3.最佳适应算法：为一个作业选择分区时，总寻找其大小最接近于作业要求内存区域。往往使剩下空闲区非常小，在内存中留下许多难以利用的小空闲区。

4.最坏适应算法：为作业选择内存区域时，总找最大空白区

基于索引搜索的分配算法

顺序搜索算法一般只适合小系统。

快速适应算法，分类搜索法。将空闲分区按容量大小分类，其中常用到长度的空闲区设立单独的空闲区链表，系统为多个空闲链表设立一张管理索引表。

优点：查找效率高，分配时不对任何分区产生分割，不会产生内存碎片。但是分区归还主存算法复杂，开销大，分配以进程为单位，存在浪费，空间换时间。

紧凑技术

用于消除外碎片。

紧凑：移动作业从把多个分散的小分区拼接成一个大分区。

采用动态重定位：实时修改或变换在内存中位置发生变化的作业地址。

多重分区分配

由于作业往往由相对独立的程序段和数据段组成，因此多重分区分配就是将其分别装入到内存空间中不同区域内。

此处介绍分区的内存保护的概念：防止一个作业有意或无意破坏OS或其他作业，常用方法：界限寄存器法和内存保护键法

界限寄存器法

又分为上下界限寄存器法和基址、限长寄存器法。

内存保护键法

给每个内存块分配一个单独的保护键，其相当于一把锁。进入系统的每个作业也赋予一个保护键。相当于钥匙，运行作业时，检查钥匙和锁是否匹配，不匹配则系统发出保护性中断信号，停止作业运行。

内外协同，内存复用

采用覆盖与交换在多道程序环境下扩充内存，用来解决小内存空间运行大作业问题。

覆盖

主要在早期OS中，其将一个程序划分为一系列功能相对独立的程序段，执行时不要求同时装入内存的程序段组成一组(覆盖段)，共享同一区域，按照先后执行顺序，同一程序的不同时运行程序段以覆盖的方式交替运行。要求程序员指明覆盖结构，且模块间要有明确调用结构。

交换

将暂时不用的某个程序及其数据部分或全部从主存移到辅存，腾出空间，接着将指定程序或数据从辅存读到主存。这样一来可以增加并发运行程序数，给用户提供适当响应时间，但是换入换出控制增加处理及开销，程序整个地址空间都进行传送，未考虑执行过程中地址访问统计特性。

两者区别

前者由程序员实现，OS根据提供结构自动覆盖，而后者不要求程序员的参与。

前者针对同一作业或程序进行，而后者主要在作业或程序间进行。

伙伴系统

介于固定分区与可变分区间的动态分区技术。

伙伴：在分配内存块时将一个大的内存块分裂成两个大小相等的小块，这两者就称为”伙伴”。

伙伴系统规定，无论已分配或空闲分区，大小均为2的k次幂，k为整数，介于分配最小分区的幂次n和最大分区幂次m。内存管理模块保持多个空闲块链表，大小可为1、……、2^m^字节。

---

伙伴系统的内存分配流程：一开始有整个内存一个最大的空闲块。当一长度为n进程申请内存时，系统分其一个大于或等于所申请尺寸的最小2的幂次的空闲块。例如：假设2^i-1^<n<=2^i^，则在空闲分区大小为2^i^的空闲分区链表中找。若没找到，则在大小为2^i+1^中找。若存在2^i+1^的一个空闲分区，就将其分为两个相等的分区，称为一对伙伴，其中一个分区用于分配，另一个加入大小为2^i^空闲分区链表中，若其也不存在，继续往后找，找到都进行分割直到分割出一个2^i^的空闲分区，也就是一定确保该进程拿到的是最接近其申请大小的2的幂次。

---

伙伴系统的内存释放流程：先考虑将被释放块与其伙伴合并成一个大空闲块，然后继续合并下去直至不能合并，但是若有两个存储块大小相同，地址相邻，但不是同一个大块分裂出来的(不是伙伴)，则不会被合并起来。

---

伙伴系统利用二进制寻址的优点，加速了相邻空闲分区的合并，搜索速度很快，但是不能有效利用内存，进程的大小并不一定是2的幂次，造成浪费，内部碎片严重。

页式内存管理

程序、进程和作业

程序是静止存放在磁盘上的可执行文件。

进程是动态的包括程序和程序处理对象(数据集)的一个程序对某个数据集的执行过程，==是分配资源的基本单位==。常有系统进程和用户进程两种。进程相较于程序更能真实描述并发，其有生存周期，但程序相对长久。一个程序可以作为多个进程的运行程序，一个进程也可运行多个程序。

作业是用户需要计算机完成的某项任务，是要求计算机做的工作的集合。一个作业的完成通常分为作业提交、作业收容、作业执行和作业完成。作业是用户想计算机提交任务的任务实体，但进程是完成用户任务的执行实体，是向系统申请分配资源的基本单位。一个作业可由多个进程组成，且至少一个，反之不成立。

一个作业常包括程序、数据和操作说明书，一个进程由进程控制块PCB、程序和数据集合组成。因此程序是进程的一部分，一个作业可划分为若干个进程完成。

分页式内存管理

页为每个作业的地址空间分成的大小相等的片，从0开始编号；页框为主存存储空间上与页面大小相同的片。页表则为在内存中找到进程每个页面对应块的映射关系表。

页表存放在内存中，是进程的现场信息，用来记录进程的内存分配情况和实现进程运行的动态重定位，其基址和长度由页表寄存器给出。

分页的数据结构

进程页表：每个进程一个页表，描述该进程占用物理页面及逻辑排列顺序。逻辑页号->物理页框号

物理页框表：整个系统就一个，描述物理内存空间分配使用情况。

请求表：整个系统一个，描述系统内各个进程页表的位置和大小，用于地址转换。

纯分页/基本系统

不具备页面对换功能，不支持虚拟存储器功能。其调度一个作业时，必须将其所有页一次装入主存页框中。

多级页表

TLB

一种特殊的高速缓冲存储器，存储页表中最经常使用到的部分或全部内容。

其余参考CO理论 。

有的TLB在每个TLB条目中还保存地址空间标识码(ASID)，来唯一标识进程，提供地址空间保护，同时还允许TLB同时含有多个进程条目。

哈希页表

经常被用来处理超32位地址空间，以虚拟页码为哈希值。其每一条目都包含一个链表的元素，这些元素哈希成一个位置，每个元素有三个域:虚拟页码、映射帧号、指向链表中下一个元素指针。

工作流程：虚拟地址中虚拟页号转换为哈希表号，用虚拟页号与链表中每一个元素的第一个域比较：匹配，则帧号作为来组成物理地址；反之，对链表中下一个节点比较。

反向页表

段式内存管理

一个段定义为一组逻辑信息，每个作业地址空间有一些分段构成，拥有自己的名字，都是一段连续的地址空间，首地址为0。

逻辑地址由段号和段内地址组成。

段表记录了段与内存位置对应关系，保存在内存里。

段表寄存器给出对应段号的段表基址及长度，地址转换方式类似于页表。

地址转换过程：1.逻辑地址中段号S与段表长度TL比较，若前者更大，说明越界，产生越界中断；未越界则依据段表始址和段号得到段表中段表项位置，读出段在内存的基地址。2.再查段内地址d同段长SL比较，若超过，同样越界；若不超过，将其与段基址相加得到要访问内存物理地址。

段表相对于页表更便于实现信息共享。

分段管理易于实现段的共享，但对段的保护简单，为段表提供额外存储空间，要采用拼接手段完成分段的动态增长和减少外部碎片，辅存中管理不定长分段困难大。

分页分段比较

页是信息的物理单位，大小固定。段是信息的逻辑单位，长度不定，由用户程序定。分页活动用户不可见，是系统对主存的管理，分段用户可见。前者解决了碎片问题，无外碎片，内碎片不超页大小，提高内存利用率，不必连续存放。后者更好实现数据共享与保护，段长可动态增长，便于动态链接。

段页式内存管理

分段来分配和管理虚拟存储器，分页来分配和管理实存储器。

先将用户程序分段，赋予段名，再将各个段分成若干页，地址由段号、段内页号、页内地址组成，设段表和页表。每个进程一张段表，每个段一张页表。段表含段号、页表始址、页表长度，页表含页号和块号。

进程同步

信号量

一个信号量可能初始化为非负整数，P操作使其自减一，减为负的，执行当前P操作的进程被阻塞，反之进程继续执行；V操作使其自增一，值非正，则被P操作阻塞的进程解除阻塞。PV操作简单表达能力强，但不够安全，使用不当会出现死锁，难以解决复杂同步互斥问题。

二元信号量和一般信号量

前者取值仅为0/1，用于实现互斥。后者，初值可为可用物理资源总数，用于进程间协作同步问题。

二元信号量

注意：每个进程中实现互斥的P、V操作必须成对出现，按如下顺序执行：P操作、进临界区、出临界区、V操作。P、V操作分别紧靠临界区头尾，临界区代码尽可能短，信号量初值为一般为1。

一般信号量

定义了一个信号量的结构体，成员有：count(整数)和queue(队列)，这定义了三个原子操作：**初始化s(信号量变量)、释放s (V)、申请s (P)**。

count>0，其值代表资源个数；count<0，其绝对值代表等待进程个数

强信号量和弱信号量

前者规定在进程从q中释放时采用FIFO，后者不规定释放顺序。

汇合

基本的同步模式，使得两个进程在执行过程中一点汇合，直至两者都到后继续执行。可以使用信号量来实现。

多进程同步原语：Barriers

用于进程组同步，是对汇合的泛化，可用于进程组同步。

n = the number of threads
count = 0 //记录到达汇合点的进程数
mutex = Semaphore(1) //保护count
barrier = Semaphore(0) //所有进程到达前都是0或负数，到达后取正值

mutex.wait() #mutex自减一，减为负的被阻塞，仍非负，进入临界区
count = count + 1 #到达进程加一
mutex.signal() #唤醒其他被阻塞的进程

if count == n: barrier.signal() #唤醒一个进程
barrier.wait() #不满足count == n的条件，将被阻塞住直到最终全部到达来唤醒
barrier.signal() #被唤醒的进程需要唤醒下一个进程

信号量集机制

AND型信号量集

将进程需要所有共享资源一次全分配给它，待进程使用完再一起释放。

一般信号量集

在AND上扩充，进程对信号量Si的测试值ti(用于信号量判断，Si>=ti表示资源数低于ti时不予分配)，占用值为di(用于信号量的增减，即P、V操作的自增减为：Si = Si - di和Si = Si + di)，SP(S1,t1,d1,……,Sn,tn,dn)、SV(S1,d1,……,Sn,dn)

例：

SP(S,d,d)：表示每次申请d个资源，资源数少于d时，不予分配。

SP(S,1,1)：表示互斥信号量

SP(S,1,0)：作为可控开关，S>=1时，允许多个进程进入临界区；S=0时禁止任何进程进入。

管程(Monitor)

其定义了一个数据结构和能为并发进程所执行的能同步进程和改变管程中数据的操作。其由名字、内部共享数据结构说明、对数据结构进行操作的一组互斥执行过程和初始化局部于管程内部的共享数据语句。

对于互斥其采用由编译器保证的方式实现进入管程是互斥的。

对于同步，其设置**条件变量(CV)**及在其上实施PV操作实现对进程或线程的等待和唤醒。

使用条件变量来区分等待的不同原因，不同的条件变量对应不同原因的进程阻塞等待队列。其值不可增减，且wait操作一定阻塞当前进程，若无等待进程，条件变量signal将丢失。

一个进入管程的进程执行等待操作时，应释放管程互斥权，后续进入的进程执行唤醒操作时，管程中便存在两个同时处于活动状态的进程。

此时有三种处理方式：P等待Q执行(Hoare管程)、Q等待P继续执行(MESA管程)、规定唤醒操作为管程最后一个可执行操作(Hansen管程，并发pascal)

Hoare管程

Hoare管程一般有入口等待队列和紧急等待队列两种，后者是由于管程互斥但是被唤醒的比入口等待队列优先级高的队列。

同步原语

同步操作原语wait和signal，对于条件变量x,x.wait()将自身阻塞在x队列中，x.signal()将x队列中一个进程唤醒。前者判断紧急等待队列是否为空，是则释放管程互斥权；否则唤醒第一个等待者。执行此操作进程排入x队列尾部。后者判断x队列是否为空，是等效空操作；否则唤醒第一个等待者，执行此操作进程进入 紧急等待队列尾部。

信号量

mutex，用于互斥，初值为1.进程调用管程中任何过程时需进行P操作，退出管程时应进行V操作，为使进程在等待资源时其他进程亦可进入，在wait操作中须执行V(mutex)操作。

next，初值为0，凡发出signal操作的进程应进行P操作挂起自身，直至被释放进程退出管程或产生其他等待条件。进程推出过程前，须检查是否有别的进程在next上等大，有则V唤醒。

x-sem，初值为0，申请资源得不到满足时，执行P操作挂起，释放资源时需知道是否有别的进程在等待，用计数器x-count(初值为0)记录等待资源进程数。执行signal操作时若想先让等待资源的进程中某个立即运行，不让其他进程抢先进入，可使用V(x-sem)实现。

进程间通信

低级通信

只能传递状态和整数值，包括信号量和管程机制。

高级通信

适用分布式系统，基于共享内存，主要有管道、共享内存和消息系统。

管道

半双工，单方向传递信息，双方通信需建立两个。有**无名管道(只能用于父子进程或兄弟进程间)和有名管道(FIFO)**。

消息传递

两个通信原语：send和receive

阻塞调用和非阻塞

共享内存

同一块物理内存映射到进程A、B各自的进程地址空间。

经典进程同步问题

生产者-消费者

读写者问题

哲学家进餐问题

CPU调度

高级调度

宏观调度、作业调度。

中级调度

内外存交换，将进程部分或全部换到外存上，当前所需部分换入内存。

低级调度

微观调度、进程或线程调度，由于执行频繁、要求实现时达到高效率。

非抢占式、抢占式：时间片原则、优先权原则、短作业优先。

面向用户的调度性能准则

周转时间

作业提交到完成经历的时间。

响应时间

输入请求到系统给出首次响应的时间。

截止时间

开始截止时间和完成截止时间——实时系统，开始时间和完成时间的ddl。

优先级和公平性

面向系统的调度性能准则

吞吐量

单位时间完成作业数。

CPU利用率

各种资源的均衡利用

如CPU繁忙作业和I/O繁忙作业搭配。

调度算法本身调度性能准则

易实现、执行开销比小。

算法设计要点

进程分类

资源占用

I/O密集型

常会花费大量时间等待I/O操作完成。

CPU密集型

需大量CPU时间

交互方式

批处理

分时

实时

批处理系统常用调度算法

先来先服务

利于长作业、不利于短作业。利于CPU繁忙、不利于I/O繁忙。

最短作业优先

最短剩余时间优先

最高响应比优先

同时考虑作业等待时间和运行时间，改善调度性能，每次选择作业时先计算后被作业队列中每个作业的响应比RP，选择值最大的作业运行。

RP = (已等待时间 + 要求运行时间)/要求运行时间

交互式系统调度算法

时间片轮转

多级队列

引入多个就绪队列，通过各队列区别对待达到综合调度目标

多级反馈队列

实时系统调度算法

对I/O，CPU必须在确定时间范围内，恰当做出反应。

软实时

偶尔可不满足。

硬实时

绝对满足。

静态表调度

无计算、按固定方案进行、无灵活性

单调速率调度RMS

可通过对系统资源利用率的计算来进行任务可调度性分析，大致是任务周期越小、优先级越高的任务最先被调度，优先级一样，随机调度一个。

最早截止时间优先算法EDF

任务绝对截至时间越早、优先级越高，最先被调度。

优先级相同，随机调度。