计算机

硬件的发展

发展阶段	时间	逻辑元件	速度	内存	外存
第一代	1946-1957	电子管	几千-几万	汞延迟线、磁鼓	穿孔纸带、纸带
第二代	1958-1964	晶体管	几万-几十万	磁芯存储器	磁带
第三代	1964-1971	中小规模集成电路	几十万-几百万	半导体存储器	磁带、磁盘
第四代	1972-现在	大规模、超大规模集成电路	上千万-万亿	半导体存储器	磁盘、磁带、光盘、半导体存储器

操作系统的发展和分类

发展阶段	主要缺点	主要优点
手工操作阶段	用户独占全机、人际速度矛盾导致资源利用率极低
批处理阶段——单道批处理系统	内存中仅能有一道程序运行，CPU 有大量的时间是在空闲等待 I/O 完成	缓解了一定程度的人机速度矛盾，资源利用率有所提升
批处理阶段——多道批处理系统	用户响应时间长，没有人机交互功能（用户提交完作业后智能等待计算机处理完成，中间不能控制自己的作业执行）	多道程序并发执行，共享计算机资源。资源利用率大幅提升，CPU 和其他资源更能保持“忙碌”的状态，系统吞吐量增大
分时操作系统	不能优先处理一些紧急任务	用户请求可以被即时响应，解决了人机交互问题。允许多个用户同时使用一台电脑，并且操作相互独立
实施操作系统		能够优先响应一些紧急任务，某些紧急任务不需时间片排队

三层调度的联系、对比

	要做什么	调度发生在	发生频率	对进程状态的影响
高级调度	按一定的原则从外村的作业后备队列中挑选一个作业调入内存，并创建进程	外存 ➡ 内存（面向作业）	最低	无 ➡ 创建态 ➡ 就绪态
中级调度	按照某种策略决定将哪个处于挂起状态的进程重新调入内存	外存 ➡ 内存（面向进程）	中等	挂起态 ➡ 就绪态
低级调度	按照某种策略从就绪队列中选取一个进程，将处理机分配给它	内存 ➡CPU	最高	就绪态 ➡ 运行态

调度算法

基础服务	算法思想	算法规则	用于作业/进程调度	是否可抢占	优缺点	是否会导致饥饿
先进先服务	从“公平”的角度考虑	按照先后顺序进行服务	用于作业调度时，考虑的是哪个作业先到达后被队列；用于进程调度时，考虑的是哪个进程先到达就绪队列	非抢占式	公平算法简单 排在长作业后面的短作业需要等待很长时间，带权周转时间狠罚，对短作业来说用户体验不好	不会
短作业优先	追求最少的平均等待时间，最少的平均周转时间、最少的平均带权周转时间	最短的作业/进程优先得到服务	两者皆可。用于进程调度时称为“短进程优先算法”	非抢占式，但也有抢占式版本——最短剩余时间算法	“最短的”平均等待时间、平均周转时间 不公平。对短作业有利，对长作业不利。	会
高响应比优先	要综合考虑作业/进程的等待时间和要求服务的时间	在每次调度时计算各个作业/进程为其服务	既可用于作业调度，又可用于进程调度	非抢占式	综合考虑了等待时间和运行时间（要求服务时间） 等待时间相同时，要求服务时间短的优先（SJF 的优点） 要求服务时间相同时，等待时间长的优先（FCFS 的优点）	不会
时间片轮转（RR）	公平地、轮流为各个进程服务，让每个进程在一定时间间隔内都可以得到响应	按照各进程到达就绪队列地顺序，轮流让各个进程执行一个时间片。	用于进程调度（只有作业放入内存建立了相应地进程后，才能被分配处理机时间片）	抢占式	公平；响应快，适用于分时操作系统 由于高频率的进程切换，因此有一定开销；不区分任务的紧急程度	不会
优先级调度	越来越多应用场景要求根据任务的紧急程度来决定处理顺序	每个作业/进程都有各自的优先级，调度时选择优先级最高的作业/进程	既可以用于作业调度，也可用于进程调度。甚至，还会用于在之后会学习的 I/O 调度中	抢占式、非抢占式都有。非抢占式只需在进程主动放弃处理机时进行调度即可，而抢占式还需在就绪队列变化时，检查是否会发生抢占	用优先级区分紧急程度、重要程度，适用于实时操作系统。可灵活地调整对各种作业/进程的偏好程度 若源源不断地有高优先级进程到来，则可能导致饥饿	会
多级反馈队列调度算法	对其他调度算法的这种权衡	综合前几个算法	用于进程调度	抢占式	综合前几个算法的优点	会
多级队列调度算法

进程互斥的软件实现方法

	单标志法	双标志先检查	双标志后检查	Peterson 法
算法思想	两个进程在访问完临界区后会把使用临界区的权限转交给另一个进程，也就是说每个进程进入临界区的权限只能被另一个进程赋予	设置一个布尔型数组 flag[]，数组各个元素用来标记各进程想进入临界区的意愿	与双标志先检查相同，但不同之处在于：先“上锁”后“检查”	结合双标志法，单标志法的思想

内部排序各个算法的对比

算法种类	时间复杂度	空间复杂度	是否稳定	适用性	过程特征
直接插入排序	best： O(n) average: O(n²) worst: O(n²)	O(1)	是	顺序存储、链式存储、n 较小、关键字基本有序
冒泡排序	best： O(n) average: O(n²) worst: O(n²)	O(1)	是	顺序存储、链式存储、关键字基本有序	每趟处理都能产生当前的最大值和最小值
简单选择排序	best： O(n²) average: O(n²) worst: O(n²)	O(1)	否	顺序存储、链式存储、n 较小	每趟处理都能产生当前的最大值和最小值
希尔排序	不做讨论	O(1)	否	顺序存储
快速排序	best： O(nlog₂n) average: O(nlog₂n) worst: O(n²)	O(log₂n)	否	顺序存储、n 较大	一趟处理少能确定一个元素的最终位置
堆排序	best： O(nlog₂n) average: O(nlog₂n) worst: O(nlog₂n)	O(1)	否	顺序存储、n 较大	每趟处理都能产生当前的最大值和最小值
二路归并排序	best： O(nlog₂n) average: O(nlog₂n) worst: O(nlog₂n)	O(n)	是	顺序存储、链式存储、n 较大
基数排序	best： O(d(n + r)) average: O(d(n + r)) worst: O(d(n + r))	O(r)	是	顺序存储、链式存储、n 很大且记录的关键字位数较少且可以分解时

$$log_{2}n$$