操作系统复习

第一章绪论

单道批处理

联机-》CPU处理

脱机-》卫星机

→多道

多道程序设计技术脱机方式，多个作业进入内存

多道批处理

分时系统分时联机方式分时技术

实时系统

特性

并发、

虚拟、虚实转换

共享、时分、空分

不确定执行顺序随机

作用

处理机调度，内存管理，设备管理，软件资源管理

第二、三章操作系统的物质基础、结构和用户接口

物质基础：

CPU特权级（管态/核态、目态/用户态）、中断机制（interrupt / exception / syscall，中断响应过程）

什么是向量中断？当中断发生时，由中断源自己引导处理机进入中断服务程序的中断过程称为向量中断。

中断向量每类中断类型都有自己的中断向量，包含：中断服务例程的入口地址和程序状态字

中断向量表主存中用于存放中断向量服务地址的一组存储单元组成的表。

静态连接和动态链接

静态：

一个源程序经编译后，生成一个可重定位的目标模块，并产生内部符号表和外部调用表，供连接程序使用。

静态连接将所需的外部函数链接到目标文件中形成为一个可执行文件。若多个应用程序都调用了同一个库中的外部函数，则每个执行文件中都会包含这个外部函数对应的代码。

动态：

动态链接不需要将外部函数链接到目标文件中。而是在应用程序中需要调用外部函数的地方作记录，并说明要使用的外部函数名和引用入口号，形成函数调用链表。

所需支持 —— 动态链接库（DLL）

OS的装载程序将应用程序和DLL装入主存后，装载程序会遍历函数调用链表，将DLL中函数在主存的入口（段：偏移）填入链表中的每个结点

缺点：可执行文件的执行需要执行环境找到并加载所有它依赖的函数库。

操作系统的用户接口

系统调用是用户在程序一级请求操作系统服务的一种手段

(1) 每个系统调用对应一个系统调用号；

(2) 每个系统调用对应一个执行程序段；

(3) 每个系统调用要求一定数量的输入参数和返回值。

第四章进程管理

进程与程序的区别

进程的三个基本状态

运行，等待，就绪

基本进程控制原语

创建原语

create (name，priority)

fork()

对父进程返回子进程的进程号，对子进程返回零

父子资源的逻辑地址相同，但是互不影响

exec()

更换进程执行代码，更换正文段，数据段。

撤消原语

Kill ( ) 或 exit( )

若子进程调用exit()，而父进程并没有调用wait()或waitpid()获取子进程的状态信息，那么子进程的PCB仍然保存在系统中。这种进程称之为僵尸进程。

当一个父进程由于正常完成工作而退出或由于其他情况被终止，它的一个或多个子进程却还在运行，那么那些子进程将成为孤儿进程

等待原语

susp(chan) 入口参数chan：进程等待的原因

中止调用进程的执行，并加入到等待chan的等待队列中；

wait() ：等待子进程结束。wait()函数使父进程暂停执行，直到它的一个子进程结束为止，该函数的返回值是终止运行的子进程的PID。参数status所指向的变量存放子进程的退出码，即从子进程的main函数返回的值或子进程中exit()函数的参数。

waitpid() ：等待某个特定子进程结束。 waitpid(pid_t pid, int * status, int options) • pid为要等待的子进程的PID； • status的含义与wait()函数中的status相同。

唤醒原语

wakeup(chan) 入口参数chan：进程等待的原因。

进程切换

进程互斥

临界资源、临界区、互斥的定义

进程同步的定义

用锁实现进程互斥

P:取信号灯值减1，若相减结果为负，则调用P(s)的进程被阻，并插入到该信号灯的等待队列中，否则该进程继续执行。

V:取信号灯值加1，若相加结果大于零，进程继续执行，否则，唤醒在该信号灯等待队列上的第一个进程。

进程流图：

生产者-消费者问题

首先掌握几种错误的情况。

问题在于V(s)后生产者可以直接直接放入，而之后的if不会正确执行。

两个delay，死锁了。

相比于1就是用m储存了改变后的n，从而正确执行（？

直接用n表示满缓冲区数量，开始前先判断n是否大于1，是再判断临界区互斥

缓冲区有界时怎么办？

一个互斥信号量

mutex：表示有界缓冲区是否被占用，初值 = 1
两个同步信号量

sa ：表示满缓冲区的数目，初值 = 0

sb ：表示空缓冲区的数目，初值 = n

这个可以展现出信号灯的作用了。

这个会死锁

掌握伪代码的写法

main( )
{
	semaphore sa=0； ∕* *∕
	semaphore sb=n； ∕* *∕
	semaphore mutex=1； ∕*对有界缓冲区进行操作的互斥信号灯*∕ 
	cobegin
		p1( )； p2( )；… pm ( )；
		c1( )； c2( )；… ck( )；
	coend
}

pi()
{
    while(生产未完成)
    {
        ...
        生产一个产品;
        p(sb);
        p(mutex);
        送一个产品到有界缓冲区;
        v(mutex);
        v(sa);
    }
}

pi()
{
    while(还要消费)
    {
        p(sa);
        p(mutex);
        到有界缓冲区取一个产品;
        v(mutex);
        v(sb);
        消费一个产品;
        ...
    }
}

进程通信

直接，间接（信箱）

信号机制

管道，无名、命名，消息队列

线程

• 把进程的两项功能——“独立分配资源”与“被调度执行”分离开来

• 进程作为系统资源分配和保护的独立单位

• 在进程内增加一类实体——线程

• 线程作为调度的基本单位

• 同一进程内的线程共享相同的地址空间

优点：

• 创建和撤销一个线程比创建一个进程的开销要小得多（10 ~ 100倍）。 • 因为共享地址空间和数据，线程间通信十分方便且高效。 • 同一个进程的线程间切换速度快（纳秒级）。 • 在进程内创建多线程，可以提高系统的并行处理能力，加快进程的处理速度。

缺点：

• 一个线程崩溃，会导致其所属进程内的所有线程崩溃。

第五章资源分配与调度

系统对作业一级采用资源静态分配方法。

系统对进程一级采用资源动态分配方法。

资源分配策略

先请求先服务：按请求的先后次序排序。

优先调度：按优先级的高低排序。

死锁

必要条件

① 互斥条件涉及的资源是非共享的，即为临界资源。

② 不剥夺条件（非抢占）进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走。

③ 占有并等待（部分分配）进程每次申请它所需要的一部分资源。在等待一新资源的同时，进程继续占用已分配到的资源。

④ 环路条件（循环等待）存在一种进程的循环链，链中的每一个进程已获得的资源同时被链中下一个进程所请求。

死锁预防

静态分配策略

有序资源分配法

死锁避免

银行家算法

• 对每个资源请求进行检查，看是否会导致不安全状态。若是，则拒绝该请求；否则便满足该请求。

• 检查状态是否安全的方法是看其是否有足够的资源满足一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全状态，最初的请求可以批准。

• 按某种顺序并发进程都能获得最大资源而顺序完成的序列为安全序列。

其实要考的话很简单。最多考一个安全序列。

死锁的解除

① 立即结束所有进程的执行，并重启操作系统。 ② 撤销陷于死锁的所有进程。 ③ 逐个撤销陷于死锁的进程，回收其资源，直至死锁解除。 ④ 剥夺陷于死锁的进程占用的资源，但并不撤销它，直至死锁解除。 ⑤ 根据系统保存的checkpoint，让所有进程回退，直到足以解除死锁。

经典问题：哲学家

第六章处理机调度

性能衡量指标

可能考

作业调度算法

先来先服务调度算法（FCFS）
短作业优先调度算法（SJF：Shortest Job First）
响应比高者优先调度算法（HRN：Highest Response Ratio Next）响应比 = 响应时间/运行时间

进程调度

时机：

非剥夺方式，剥夺方式

进程调度算法

优先数调度算法

静态优先数

• 优先数根据进程所需使用的资源来计算 • 优先数基于程序运行时间的估计 • 优先数基于进程的类型

动态优先数

• 进程使用CPU超过一定数值时，降低优先数； • 进程进行I/O操作后，增加优先数； • 进程等待时间超过一定数值时，提高优先数。

循环轮转调度算法

当CPU空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。

时间片的取选

简单循环轮转调度，可变时间片轮转调度

多重时间片循环调度：

又称反馈循环队列或多队列策略。主要思想是将就绪进程分为两级或多级，系统相应建立两个或多个就绪进程队列，较高优先级的队列一般分配给较短的时间片。处理器调度先从高级就绪进程队列中选取可占有处理器的进程，只有在其为空时，才从较低级的就绪进程队列中选取

第七章主存管理

逻辑地址、程序（逻辑）地址空间、物理地址、主存（物理地址）空间

地址映射

编译时确定

装入时确定

在程序装入过程中随即进行的地址变换方式称为静态地址映射。

运行时确定

在程序执行期间，随着每条指令和数据的访问自动地连续地进行地址映射，这种地址变换方式称为动态地址映射。

虚拟存储器

存储保护

界地址保护

分区存储管理

静态

动态

放置策略

首次适应算法

最佳适应算法

最坏适应算法

页式存储管理

跟组原差不多。略。

(4) 采用联想存储器加快查表速度在联想存储器中存放正在运行的进程当前用到的页号和对应的块号，又称为快表。

置换算法

① 最佳算法(OPT算法)

当要调入一新页而必须先淘汰一旧页时，所淘汰的那一页应是以后不再要用的，或者是在最长的时间以后才会用到的那页。 OPT算法建立在已知未来页面访问顺序的前提下，因此是不现实的，它只是一个理想算法，但是对于评价其他算法的效果是有帮助的。

② 先进先出淘汰算法(FIFO算法)

③ 最久未使用淘汰算法(LRU算法)

④ LRU近似淘汰算法（CLOCK算法 / 时钟算法）

注意，CLOCK算法在碰到设为0的已有

时要置为1

段式存储管理

① 页式系统中用户地址空间：一维地址空间

② 段式系统中用户地址空间：二维地址空间

多级页表

第八章设备管理

访问时间：

寻道时间Ts = m*n+s 启动时间 + 速度乘路程

旋转延迟时间 TT 指定扇区移动到磁头下面所经历的时间

传输时间Tt 把数据从磁盘读出或向磁盘写入数据所经历的时间

Tt = b/(r*n) b:转速，r：每秒转数，N一条磁道上的字节数

磁盘调度算法

• 先来先服务FCFS

• 最短寻道时间优先SSTF 就近原则

• 扫描算法（SCAN）电梯算法

• 循环扫描算法（CSCAN）首位相接，变成环形扫描

多缓冲技术

SPOOLING系统

假脱机技术

第九章文件管理

文件的逻辑结构

流式无结构
记录式 ~

文件存取方法

随机

顺序

空间储存管理

位示图法

空闲文件目录

空闲块链

文件物理结构

块：块是主存和辅存间信息交换的物理单位，每次交换一块或整数块。

连续文件连续文件结构是由一组分配在磁盘连续区域的物理块组成的。
串联文件串联文件结构由按顺序串联的块组成，即文件的信息存于若干个物理块中，每个物理块的最末一个字作为链接字，指出后继块的物理地址。文件的最后一块的链接字为结束标记“ ^ ” ，它表示文件至本块结束。
索引文件用索引表和数据区实现

直接索引，n级间接索引

文件分配表FAT是以链接方式存储文件的系统中记录磁盘分配和跟踪空白磁盘块（簇）的数据结构。

文件存储空间管理

• 位示图 01标志

• 空闲文件目录做一个第一个空闲块号和个数的表

• 空闲块链链表

-文件控制块FCB

文件目录：基于FCB来实现文件的按名存取

一级文件目录文件名、存放地址及有关的说明信息（重命名问题）

树型文件目录

成组链接法：很妙的一个空闲块管理方法。重点在于主存中的超级块的变换。

Tags: 笔记

← 美赛笔记操作系统课设 →

赏

使用支付宝打赏

使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章

第一章 绪论