- 操作系统期末复习
- 二、操作系统概述
- 1.操作系统的概念
- 2.操作系统（系统软件）和应用软件的区别
- 3.OS的目标和功能
- 4.操作系统发展史
- 5.OS有几个模块
- 6.多道批处理系统和分时系统的比较
- 7.中断在批处理/分时系统中的应用
- 8.OS为什么是一个虚拟机
- 三、进程描述和控制
- 9.进程的概念？进程process和程序program的区别
- 10.进程控制块（解释，重要性，构成）
- 11.OS为了实现进程，需要哪些硬件支持？
- 12.程序是怎么变成进程的，以HelloWorld为例
- 13.列举与进程控制相关的系统调用，以Linux为例
- 14.简述进程创建的流程，并以fork为例
- 进程创建的流程
- fork()系统调用的“一次调用和两次返回”特点
- 15.五状态模型（画图，理解）
- 16.三种角度（进程角度，OS角度，处理器角度）
- 17.多个切换及其关系
- 模式切换
- 进程切换
- 四、线程
- 18.线程的概念，产生背景，和进程的关系
- 19.线程的实现方式
- 20.ULT,KLT优缺点
- 用户进程
- 内核线程
- 21.描述Linux线程机制的系统调用有哪些
- 五、并发性：互斥和同步
- 22.同步互斥的解决方法有哪些（软件、硬件、系统）
- 23.简述同步互斥的硬件方法
- 24.竞争条件
- 25.简述并发性解决的4个问题：同步，互斥，饥饿，死锁
- 六、并发：死锁和饥饿
- 26.死锁概念，产生背景，举例描述
- 27.两种数学方法描述死锁（资源分配图，向量）
- 28.死锁的条件（三必要一充分）
- 29.死锁的解决方法（四种）
- 七、内存管理
- 30.
- 31.段表/页表构造的七种方案
- 32.段/页异同，固定/动态分区异同
- 段/页异同
- 固定/动态分区异同
- 33.首次、临近（下次）、最佳适配
- 八、虚拟内存
- 34.驻留集管理
- 九、单处理器调度
- 35.长中短调度概念
- 十一、I/O管理和磁盘调度
- 十二、文件管理
- 36.文件系统架构
- 37.五种基本组织（逻辑层）
- 38.三个文件分配方法（物理层）
- 大题考点
- 信号量
- 生产者/消费者问题
- 读者-写者问题
- 银行家算法
- 页面置换算法
- 进程调度算法
- 磁盘调度策略
操作系统是控制应用程序执行的程序，是应用程序和计算机硬件间的接口。
2.操作系统（系统软件）和应用软件的区别（1）定义不同：系统软件是指控制和协调计算机及外部设备，支持应用软件开发和运行的系统；应用软件使用户可以使用的各种程序设计语言，以及各种程序语言编制的应用程序的集合。
（2）运行环境不同：操作系统可以直接安装到相应的硬件设备中，应用软件不能直接安装在无OS的电脑上。
目标：方便（易于使用），有效（有效使用资源），扩展能力（开发、测试、引入新功能）
功能：作为用户/计算机接口，作为资源管理器，易扩展性
4.操作系统发展史串行处理Serial Processing
简单批处理系统Simple Batch Systems
多道批处理系统
分时系统
进程管理
存储管理
I/O设备管理
文件管理
作业管理
相同点：都使用了多道程序设计
不同点：多道批处理系统的主要目标是充分利用处理器(CPU)，而分时系统的主要目标是减小响应时间；多道批处理系统的操作系统指令源是作业控制语言命令和作业提供的命令，而分时系统的操作系统指令源是终端键入的命令。
批处理——一个进程在等待I/O时，中断以切换另一个进程
分时——每隔一段时间中断一次，操作系统恢复控制权，并将处理器分配给另一个用户
8.OS为什么是一个虚拟机操作系统本身就是一个虚拟机，将我们有限的硬件资源进行虚拟，通过软件模拟的方式，或者使用部分硬件资源模拟出来。
三、进程描述和控制 9.进程的概念？进程process和程序program的区别进程是一个具有独立功能的程序关于某个数据集合的一次运行活动，是系统进行资源分配和调度的独立单位。
进程是：一个正在执行的程序；一个正在计算机上执行的程序实例；能分配给处理器并由处理器执行的实体；由一组执行的命令、一个当前状态和一组相关的系统资源表征的活动单元。
进程由程序代码、代码相关联的数据集和程序运行的环境构成。
process和program的区别：程序是一套做数据处理的步骤，是静态的，进程是程序的一次实现，是动态的。一个程序，可以进行多次执行（表现为多个进程）；甚至可以同时执行（多个进程同时存在）
10.进程控制块（解释，重要性，构成）解释：进程控制块是用来描述和控制进程的运行的一个数据结构，是进程实体的一部分，是操作系统中最重要的记录型数据结构。
重要性：PCB是操作系统为支持多进程并提供多重处理技术的关键工具。
构成：ID标识符、状态、其他控制描述信息
11.OS为了实现进程，需要哪些硬件支持？ 12.程序是怎么变成进程的，以HelloWorld为例1.Load程序的相关代码及静态数据到内存中
2.为进程分配一些内存，创建一些数据结构，初始化与I/O相关的一些任务
3.程序开始执行，从main函数开始，所以需要先跳转到main（）函数，OS将CPU控制权交给新创建的进程，进程获取到CPU后就可以开始执行，执行printf()函数，打印HelloWorld。
fork()创建新进程
wait()进程等待
exit()结束进程
exec()以新进程代替原有进程，但PID保持不变
1.为新进程分配一个唯一的进程标识符
2.为进程分配空间
3.初始化进程控制块
4.设置正确的链接
5.创建或补充其他数据结构
fork函数用于创建一个新进程，称为子进程，它与调用fork函数的进程同时运行，此进程称为父进程。在调用fork函数时，子进程复制了父进程的堆栈段，所以两个进程都停留在了fork函数中等待返回，所以会返回两次，一次在父进程中返回，一次在子进程中返回。
如果子进程创建成功，父进程的fork()函数返回子进程的pid号码（大于0），这时，子进程的fork()函数返回0;
如果子进程创建失败，父进程的fork()函数返回-1，子进程没有返回。
15.五状态模型（画图，理解） 16.三种角度（进程角度，OS角度，处理器角度） 17.多个切换及其关系进程切换一定会导致模式切换（从用户态切换到核心态，产生中断）
模式切换不一定会导致进程切换
用户模式/内核模式（kernel mode）
出现中断时，处理器会做如下工作：
1.将程序计数器置为中断处理程序的开始地址
2.从用户模式切换到内核模式，以便处理中断处理代码包含特权指令
1.系统中断
普通中断：控制权首先交给中断处理器，中断处理器完成工作后，再将控制权还给进程。
陷阱：致命时，进程置为退出态，并切换进程；不致命时，尝试恢复。
2.系统调用：使用系统调用时，当前用户进程置为阻塞态。
概念：线程是进程中的一个实体，是被系统独立调度和分派的基本单位。
特点：线程自己不拥有系统资源，只拥有一点在运行中必不可少的资源，但它可与同属一个进程的其它线程共享进程所拥有的全部资源。一个线程可以创建和撤消另一个线程，同一进程中的多个线程之间可以并发执行。
产生背景：长期以来，进程都是操作系统中可以拥有资源并作为独立运行的基本单位，为的是使多个程序能并发执行，以提高资源利用率和系统吞吐量。由于进程是一个资源的拥有者，因而在创建、撤销和切换中，系统必须为之付出较大的时空开销。也正因如此，在系统中所设置的进程，其数目不宜过多，进程切换的频率也不宜过高，这也就限制了并发的进一步提高。若能将进程的两个属性（拥有资源的独立单位、独立调度和分派的基本单位）分开，由系统进行分开处理，即对于作为调度和分派的基本单位，不同时拥有资源单位，以做到“轻装上阵”；而对于拥有资源的基本单位，又不对之进行频繁的切换。那么，在操作系统再引入线程，则使为了减少程序在并发执行时所付出的时空开销，线程作为独立调度和分派的基本单位，进程作为拥有系统资源的的基本单位，使OS具有更好的并发性。线程也更适合多处理器环境下的调度、分派和切换。
和进程的关系：线程，被称为轻量级进程。 每一个程序都至少有一个线程，那就是程序本身。线程是程序中一个单一的顺序控制流程。 在单个程序中同时运行多个线程完成不同的工作，称为多线程。
19.线程的实现方式1.使用内核级线程（KLT）实现
2.使用用户级线程（ULT）实现
3.使用KLT、ULT混合实现
优点：
（1） 线程的调度不需要内核直接参与，控制简单。
（2） 可以在不支持线程的操作系统中实现。
（3） 创建和销毁线程、线程切换代价和线程管理的代价比内核线程少得多。
（4） 允许每个进程定制自己的调度算法，线程管理比较灵活。
（5）所有线程管理数据结构均在进程的用户空间中， 线程切换不需要内核模式， 能节省模式切换开销和内核的宝贵资源；
（5）能运行在任何OS上， 内核在支持ULT方面不需要做任何工作；
缺点：
（1）资源调度按照进程进行，多个处理机下，同一个进程中的线程只能在同一个处理机下分时复用；不能利用多处理器的优点， OS调度进程，仅有一个ULT能执行；
（2）一个ULT的阻塞， 将引起整个进程的阻塞；
优点：
(1) 进程中的一个线程被阻塞了， 内核能调度同一进程的其它线程占有处理器运行；
(2)多处理器环境中， 内核能同时调度同一进程中多个线程并行执行；
(3) 内核自身也可用多线程技术实现， 能提高操作系统的执行速度和效率
缺点：由内核进行调度。应用程序线程在用户态运行， 线程调度和管理在内核实现， 在同一进程中， 控制权从一个线程传送到另一个线程时需要模式切换，系统开销较大；
21.描述Linux线程机制的系统调用有哪些pthread_create()创建新线程
pthread_exit() 结束一个线程
pthread_join()阻塞调用它的线程
pthread_cancle()终止线程执行
软件方法：Dekker
硬件方法：
1.中断禁用：为保证互斥，只需保证一个进程不被中断即可（适用于单处理器）
2.特殊指令：
（1）testset指令
（2）exchange/swap指令
系统方法：
（1）信号量
（2）管程
1.中断禁用：保证临界区不能被中断，故可以保证互斥。
2.专用机器指令：
（1）exchange/swap指令：共享变量bolt被初始化为0，唯一可以进入临界区的进程是发现bolt=0的那个进程。所有试图进入临界区的其他进程进入忙等待（busy waiting）模式。
（2）testset指令：有一个锁变量，一个执行单元要想访问被自旋锁保护的共享资源，必须先得到锁，在访问完共享资源后，必须释放锁。如果在获取自旋锁时，没有任何执行单元保持该锁，那么将立即得到锁；
硬件对同步的支持-TAS和CAS指令
竞争条件发生在多个进程或线程读写数据时，其最终结果取决于多个进程的指令执行顺序。
25.简述并发性解决的4个问题：同步，互斥，饥饿，死锁（1）同步：同步是在互斥的基础上（大多数情况），通过对其他机制实现访问者对资源的有序访问
（2）互斥：当一个进程在临界区访问共享资源时，其他进程不能进入该临界区访问任何共享资源
（3）饥饿：指一个可运行的进程尽管能继续执行，但被调度程序无限期地忽视，而不能调度执行的情形
（4）死锁：两个或两个以上的进程因其中的每个进程都在等待其他进程做完某些事情而不能继续执行，这种情形称为死锁
概念：一组相互竞争系统资源或进行通信的进程间的”永久”堵塞。
产生背景：
系统资源不足。
进程运行推进的顺序不合适。
资源分配不当。
场景描述：死锁是因为多线程访问共享资源，由于访问的顺序不当所造成的，通常是一个线程锁定了一个资源A，而又想去锁定资源B；在另一个线程中，锁定了资源B，而又想去锁定资源A以完成自身的操作，两个线程都想得到对方的资源，而不愿释放自己的资源，造成两个线程都在等待，而无法执行的情况。
27.两种数学方法描述死锁（资源分配图，向量）1.资源分配图
2.向量
三个必要条件：1.互斥2.占有且等待3.不可抢占
一个充分条件：循环等待
1.允许死锁发生
无为而治：鸵鸟算法
死锁检测
2.不允许死锁发生
静态：死锁预防
（1）间接死锁预防：防三个必要条件之一
（2）直接死锁预防：防止循环等待的发生
动态：死锁避免（允许三个必要条件）
（1）若一个进程的请求会导致死锁，则不启动该进程。
（2）若一个进程增加的资源请求会导致死锁，则不允许这一资源分配。
- 固定分区
（1）分区大小相等：程序太大不能放入一个分区；内存的利用率非常低，造成内部碎片
（2）分区大小不相等：把每个进程分配到能够容纳它的最小分区 - 动态分区
（1）优点：没有内部碎片；可以更充分地使用内存
（2）缺点：会产生外部碎片；可以通过压缩克服外部碎片，但压缩费时 - 简单分页
（1）内存被划分成许多大小固定、相等的块，称为页框；每个进程被划分成许多大小与页框相等的块，称为页；要加载一个进程，需要把进程所包含的所有页都加载进内存内不一定连续的某些页框中。
（2）缺点：会产生内部碎片 - 简单分段
（1）每个进程被划分成许多段；要加载一个进程，需要把进程包含的所有段都加载入内存内不一定连续的某些动态分区中.
（2）无内部碎片，会产生外部碎片。相对于动态分区，提高了内存利用率，减少了开销 - 虚存分页
- 虚存分段
- 段页式
用户的地址空间被划分为许多段，每一段被划分为许多固定大小的页，每个进程有一个段表和多个页。
相同点：
1.都是将一个进程划分成了很多的小的部分页或者段，在将整个进程放入内存当中时使用的的内存空间不一定是连续的。
2.都是为了提高内存利用率，减少内存碎片
不同点：
1.分页存在内部碎片的问题，而分段存在外部碎片的问题。
2.页的大小固定且由系统决定；而段的长度却不固定，决定于用户所编写的程序。
相同点：将进程放入这些内存分区时，同一个进程占用一片连续的内存空间。
不同点：
1.固定分区在系统生成阶段将内存划分为静态分区，而动态分区的分区是根据进程的大小动态创建的。
2.固定分区有内部碎片，而动态分区克服了这个缺点，但动态分区有外部碎片。
3.因为静态分区的数量固定，所以固定分区的最大进程数量是固定的，而动态分区的最大进程数量不固定。
最佳适配（Best-fit）：选择与要求的大小最接近的块
首次适配（First-fit）：从头开始扫描内存，选择大小足够的第一个可用块
下次适配（Next-fit）：从上一次放置的位置开始扫描内存，选择下一个大小足够的可用块
长程调度：决定加入待执行进程池
中程调度：决定加入部分或全部位于内存中的进程集合
短程调度：决定处理器执行哪个可运行进程
I/O调度：决定可用I/O设备处理哪个进程挂起的I/O请求
1.底层设备驱动程序直接与外围设备通信，负责启动设备上的I/O操作，处理I/O请求的完成。
2.基本文件系统也叫物理I/O层，这一层处理在磁盘间或磁带系统间交换的数据块。
3.基本I/O管理程序负责所有文件I/O的初始化和终止。
4.逻辑I/O使用户和应用程序能够访问记录。
5.在往上就是访问方法（access method），它在应用程序和文件系统以及保存数据的设备之间提供了一个标准接口。
文件管理功能
1.堆
最简单的文件组织形式，数据按它们到达的顺序被收集，堆的目的仅仅是积累大量数据并保存数据，其没有结构，所以对记录的访问是通过穷举查找进行的。
2.顺序文件
最常见的文件组织形式，有一个特殊的域叫关键域，通常是每条记录的第一个域，它唯一的标识这条记录。在访问时，为了匹配关键域，需要顺序查找文件。
3.索引顺序文件
克服了顺序文件的缺点。要查找某个特定的域，首先要查找索引，找到索引后，再在该索引的指针所指的主文件中的位置处开始查找。
4.索引文件
索引顺序文件保留了顺序文件的一个限制：基于文件的一个域进行处理。因此，索引文件摒弃了顺序性和关键字的概念，只能通过索引来访问记录。（索引文件大多用于对信息的及时性要求比较严格且很少会对所有数据进行处理的应用程序中）
5.直接文件或散列文件
直接文件或散列文件开发直接访问磁盘中任何一个地址已知的块的能力。直接文件使用基于关键字的散列。
semWait可以理解为申请资源；semSignal可以理解为释放资源。
生产者/消费者问题问题描述：
系统中有一组生产者进程和一组消费者进程，生产者进程每次生产一个产品放入缓冲区，消费者进程每次从缓冲区中取出一个产品并使用。（“产品”实际是某种数据）生产者、消费者共享一个初始为空、大小为N的缓冲区。只有缓冲区没满时，生产者才能把产品放入缓冲区，否则必须等待。只有缓冲区不空时，消费者才能从中取出产品，否则必须等待。缓冲区是临界资源，各进程必须互斥地访问。
分析：
有两类进程，即生产者和消费者进程。题面是一个混合关系，既有间接关系，也有直接关系：
直接关系：生产者和消费者不能同时进入临界区；
间接关系：缓冲区满，生产者不能放入；缓冲区空，消费者不能取出
问题描述：
有一个文件，被若干个读者和若干个写者共同访问，要求：
1）允许多个读者同时访问一个文件；
2）有写者在写文件时，不允许读者访问；
分析：
两类进程：读者与写者，读者与写者之间的关系是直接关系，但是为了判断“特殊的读者”，还要多考虑一个关系。
银行家算法核心思想：在进程提出资源申请时，先预判此分配是否会导致系统进
页面置换算法1.最佳置换算法OPT
2.先进先出页面置换算法FIFO
3.最近最少使用页面算法LRU——每次选择内存中离当前时刻最久未使用过的页面淘汰
4.Clock置换算法
1、First In First Out( FIFO算法)（非抢占）
与短进程相比，FCFS更适用于长进程。
2、round-robin(轮转算法）（抢占）
这种算法周期性地产生时钟中断，出现中断时，当前正运行的进程会放置到就绪队列中，然后基于FCFS 策略选择下一个就绪作业运行。轮转法最主要的设计问题是所用的时间段(片）长度。
3、Shortest Process Next（最短进程优先）（非抢占）
下一次选择所需处理时间最短的进程，非抢占。
4、Shortest Remaining Time （最短剩余时间）（抢占）
总是选择预期剩余时间最短的进程，相较于SPN增加了抢占机制的策略。
5、Highest Response Ratio Next（最高响应比）(非抢占)
最高响应比优先，R=(w+s)/s，其中R表示响应比，w表示已经等待的时间，s表示期待服务的时间.调度规则如下:当前进程完成或被阻塞时，选择R值最大的就绪进程。
每次进程结束都要更新R的值。
6.FeedBack（反馈）
一个进程首次进入系统中时，会放在RQ0中。当它首次被抢占并返回就绪态时，会放在RQ1中。在随后的时间里，每当它被抢占时，都降级到下一个低优先级队列中。短进程很快就会执行完毕，不会出现在就绪队列中多次降级的现象，长进程则会多次降级。因此，新到的进程和短进程会优先于老进程和长进程。在每个队列中，除优先级最低的队列外，都使用简单的FCFS机制。进程处于优先级最低的队列中后，就不会再降低，但会重复返回该队列，直到运行结束。
总结
使用与表11.2类似的方式，分析下列磁道请求：27，129，110，186，147，41，10，64，120。初始磁道为100
1.FIFO先进先出
2.SSTF最短服务时间优先
FIFO和SSTF与磁头运动方向无关
3.SCAN电梯算法（直上直下）
（1）往磁道号减少的方向
（2）往磁道号增加的方向
4.C-SCAN（一个方向走到底）
（1）往磁道号减少的方向
（2）往磁道号增加的方向
