杭州企业营销网站建设公司,中文静态网站下载,谷歌推广seo,直接进网站的浏览器我是技术搬运工,好东西当然要和大家分享啦.原文地址
操作系统基本特征
1. 并发
并发性是指宏观上在一段时间内能同时运行多个程序#xff0c;而并行性则指同一时刻能运行多个指令。
并行需要硬件支持#xff0c;如多流水线或者多处理器。
操作系统通过引入进程和线程#xf…我是技术搬运工,好东西当然要和大家分享啦.原文地址
操作系统基本特征
1. 并发
并发性是指宏观上在一段时间内能同时运行多个程序而并行性则指同一时刻能运行多个指令。
并行需要硬件支持如多流水线或者多处理器。
操作系统通过引入进程和线程使得程序能够并发运行。
2. 共享
共享是指系统中的资源可以供多个并发的进程共同使用。
有两种共享方式互斥共享和同时共享。
互斥共享的资源称为临界资源例如打印机等在同一时间只允许一个进程访问否则会出现错误需要用同步机制来实现对临界资源的访问。
3. 虚拟
虚拟技术把一个物理实体转换为多个逻辑实体。主要有两种虚拟技术时分复用技术和空分复用技术例如多个进程能在同一个处理器上并发执行使用了时分复用技术让每个进程轮流占有处理器每次只执行一小个时间片并快速切换这样就好像有多个处理器进行处理。
4. 异步
异步是指进程不是一次性执行完毕而是走走停停以不可知的速度向前推进。
系统调用
如果一个进程在用户态需要用到操作系统的一些功能就需要使用系统调用从而陷入内核由操作系统代为完成。
可以由系统调用请求的功能有设备管理、文件管理、进程管理、进程通信、存储器管理等。
中断分类
1. 外中断
由 CPU 执行指令以外的事件引起如 I/O 结束中断表示设备输入/输出处理已经完成处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。
2. 异常
由 CPU 执行指令的内部事件引起如非法操作码、地址越界、算术溢出等。
3. 陷入
在用户程序中使用系统调用。
大内核和微内核
1. 大内核
大内核是将操作系统功能作为一个紧密结合的整体放到内核由于各模块共享信息因此有很高的性能。
2. 微内核
由于操作系统不断复杂因此将一部分操作系统功能移出内核从而降低内核的复杂性。移出的部分根据分层的原则划分成若干服务相互独立。但是需要频繁地在用户态和核心态之间进行切换会有一定的性能损失。
第二章 进程管理
进程与线程
1. 进程
进程是操作系统进行资源分配的基本单位。
进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态所谓的创建进程和撤销进程都是指对 PCB 的操作。
2. 线程
一个线程中可以有多个线程是独立调度的基本单位。同一个进程中的多个线程之间可以并发执行它们共享进程资源。
3. 区别
① 拥有资源进程是资源分配的基本单位但是线程不拥有资源线程可以访问率属进程的资源。
② 调度线程是独立调度的基本单位在同一进程中线程的切换不会引起进程切换从一个进程内的线程切换到另一个进程中的线程时会引起进程切换。
③ 系统开销由于创建或撤销进程时系统都要为之分配或回收资源如内存空间、I/O 设备等因此操作系统所付出的开销远大于创建或撤销线程时的开销。类似地在进行进程切换时涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置。而线程切换时只需保存和设置少量寄存器内容开销很小。此外由于同一进程内的多个线程共享进程的地址空间因此这些线程之间的同步与通信非常容易实现甚至无需操作系统的干预。
④ 通信方面进程间通信 (IPC) 需要进程同步和互斥手段的辅助以保证数据的一致性而线程间可以通过直接读/写进程数据段如全局变量来进行通信。
举例QQ 和 浏览器是两个进程浏览器进程里面有很多线程例如 http 请求线程、事件响应线程、渲染线程等等线程的并发执行使得在浏览器中点击一个新链接从而发起 http 请求时浏览器还可以响应用户的其它事件。
进程状态的切换阻塞状态是缺少需要的资源从而由运行状态转换而来但是该资源不包括 CPU缺少 CPU 会让进程从运行态转换为就绪态。
只有就绪态和运行态可以相互转换其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间转为运行状态而运行状态的进程在分配给它的 CPU 时间片用完之后就会转为就绪状态等待下一次调度。
调度算法
需要针对不同环境来讨论调度算法。
1. 批处理系统中的调度
1.1 先来先服务FCFS
first-come first-serverd。
调度最先进入就绪队列的作业。
有利于长作业但不利于短作业因为短作业必须一直等待前面的长作业执行完毕才能执行而长作业又需要执行很长时间造成了短作业等待时间过长。
1.2 短作业优先SJF
shortest job first。
调度估计运行时间最短的作业。
长作业有可能会饿死处于一直等待短作业执行完毕的状态。如果一直有短作业到来那么长作业永远得不到调度。
1.3 最短剩余时间优先SRTN
shortest remaining time next。
2. 交互式系统中的调度
2.1 优先权优先
除了可以手动赋予优先权之外还可以把响应比作为优先权这种调度方式叫做高响应比优先调度算法。
响应比 (等待时间 要求服务时间) / 要求服务时间 响应时间 / 要求服务时间
这种调度算法主要是为了解决 SJF 中长作业可能会饿死的问题因为随着等待时间的增长响应比也会越来越高。
2.2 时间片轮转
将所有就绪进程按 FCFS 的原则排成一个队列每次调度时把 CPU 分配给队首进程该进程可以执行一个时间片。当时间片用完时由计时器发出时钟中断调度程序便停止该进程的执行并将它送往就绪队列的末尾同时继续把 CPU 分配给队首的进程。
时间片轮转算法的效率和时间片有很大关系。因为每次进程切换都要保存进程的信息并且载入新进程的信息如果时间片太短进程切换太频繁在进程切换上就会花过多时间。
2.3 多级反馈队列① 设置多个就绪队列并为各个队列赋予不同的优先级。第一个队列的优先级最高第二个队列次之其余各队列的优先权逐个降低。该算法赋予各个队列中进程执行时间片的大小也各不相同在优先权越高的队列中为每个进程所规定的执行时间片就越小。
② 当一个新进程进入内存后首先将它放入第一队列的末尾按 FCFS 原则排队等待调度。当轮到该进程执行时如它能在该时间片内完成便可准备撤离系统如果它在一个时间片结束时尚未完成调度程序便将该进程转入下一个队列的队尾。
③ 仅当前 i -1 个队列均空时才会调度第 i 队列中的进程运行。
优点实时性好也适合运行短作业和长作业。
2.4 短进程优先
3. 实时系统中的调度
实时系统要一个服务请求在一个确定时间内得到响应。
分为硬实时和软实时前者必须满足绝对的截止时间后者可以容忍一定的超时。
进程同步
1. 临界区
对临界资源进行访问的那段代码称为临界区。
为了互斥访问临界资源每个进程在进入临界区之前需要先进行检查。
// entry section
// critical section;
// exit section2. 同步与互斥
同步指多个进程按一定顺序执行互斥指多个进程在同一时刻只有一个进程能进入临界区。
同步是在对临界区互斥访问的基础上通过其它机制来实现有序访问的。
3. 信号量
**信号量Samaphore**是一个整型变量可以对其执行 down 和 up 操作也就是常见的 P 和 V 操作。
down : 如果信号量大于 0 执行 - 1 操作如果信号量等于 0将进程睡眠等待信号量大于 0up对信号量执行 1 操作并且唤醒睡眠的进程让进程完成 down 操作。
down 和 up 操作需要被设计成原语不可分割通常的做法是在执行这些操作的时候屏蔽中断。
如果信号量的取值只能为 0 或者 1那么就成为了互斥量Mutex0 表示临界区已经加锁1 表示临界区解锁。
typedef int samaphore;
samaphore mutex 1;
void P1() {down(mutex);// 临界区up(mutex);
}void P2() { down(mutex); // 临界区 up(mutex); }
使用信号量实现生产者-消费者问题
使用一个互斥量 mutex 来对临界资源进行访问empty 记录空缓冲区的数量full 记录满缓冲区的数量。
注意必须先执行 down 操作再用互斥量对临界区加锁否则会出现死锁。如果都先对临界区加锁然后再执行 down 操作考虑这种情况生产者对临界区加锁后执行 down(empty) 操作发现 empty 0此时生成者睡眠。消费者此时不能进入临界区因为生产者对临界区加锁了也就无法对执行 up(empty) 操作那么生产者和消费者就会一直等待下去。
#define N 100
typedef int samaphore;
samaphore mutex 1;
samaphore empty N;
samaphore full 0;void producer() { while(TRUE){ int item produce_item; down(empty); down(mutex); insert_item(item); up(mutex); up(full); } }
void consumer() { while(TRUE){ down(full); down(mutex); int item remove_item(item); up(mutex); up(empty); consume_item(item); } }
4. 管程使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制而管程把控制的代码独立出来不仅不容易出错也使得客户端代码调用更容易。
c 语言不支持管程下面的示例代码使用了类 Pascal 语言来描述管程。示例代码中的管程提供了 insert() 和 remove() 方法客户端代码通过调用这两个方法来解决生产者-消费者问题。
monitor ProducerConsumer
integer i;
condition c;
procedure insert();
beginend;procedure remove();
beginend;end monitor;
管程有一个重要特性在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程必须将进程阻塞否者其它进程永远不能使用管程。
管程引入了 条件变量 以及相关的操作wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞把管程让出来让另一个进程持有。signal() 操作用于唤醒被阻塞的进程。
使用管程实现生成者-消费者问题
monitor ProducerConsumer
condition full, empty;
integer count : 0;
condition c;
procedure insert(item: integer);
beginif count N then wait(full);insert_item(item);count : count 1;if count 1 ten signal(empty);
end;function remove: integer;
beginif count 0 then wait(empty);remove remove_item;count : count - 1;if count N -1 then signal(full);
end;end monitor;
procedure producer begin while true do begin item produce_item; ProducerConsumer.insert(item); end end;
procedure consumer begin while true do begin item ProducerConsumer.remove; consume_item(item); end end;
进程通信进程通信可以看成是不同进程间的线程通信对于同一个进程内线程的通信方式主要使用信号量、条件变量等同步机制。
1. 管道
管道是单向的、先进先出的、无结构的、固定大小的字节流它把一个进程的标准输出和另一个进程的标准输入连接在一起。写进程在管道的尾端写入数据读进程在管道的首端读出数据。数据读出后将从管道中移走其它读进程都不能再读到这些数据。
管道提供了简单的流控制机制进程试图读空管道时在有数据写入管道前进程将一直阻塞。同样地管道已经满时进程再试图写管道在其它进程从管道中移走数据之前写进程将一直阻塞。
Linux 中管道是通过空文件来实现。
管道有三种
① 普通管道有两个限制一是只支持半双工通信方式即只能单向传输二是只能在父子进程之间使用
② 流管道去除第一个限制支持双向传输
③ 命名管道去除第二个限制可以在不相关进程之间进行通信。
2. 信号量
信号量是一个计数器可以用来控制多个进程对共享资源的访问。它常作为一种锁机制防止某进程正在访问共享资源时其它进程也访问该资源。因此主要作为进程间以及同一进程内不同线程之间的同步手段。
3. 消息队列
消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。
4. 信号
信号是一种比较复杂的通信方式用于通知接收进程某个事件已经发生。
5. 共享内存
共享内存就是映射一段能被其它进程所访问的内存这段共享内存由一个进程创建但多个进程都可以访问。共享内存是最快的 IPC 方式它是针对其它进程间通信方式运行效率低而专门设计的。它往往与其它通信机制如信号量配合使用来实现进程间的同步和通信。
6. 套接字
套接字也是一种进程间通信机制与其它通信机制不同的是它可用于不同机器间的进程通信。
经典同步问题
生产者和消费者问题前面已经讨论过。
1. 读者-写者问题
允许多个进程同时对数据进行读操作但是不允许读和写以及写和写操作同时发生。
一个整型变量 count 记录在对数据进行读操作的进程数量一个互斥量 count_mutex 用于对 count 加锁一个互斥量 data_mutex 用于对读写的数据加锁。
typedef int semaphore;
semaphore count_mutex 1;
semaphore data_mutex 1;
int count 0;void reader() { while(TRUE) { down(count_mutex); count; if(count 1) down(data_mutex); // 第一个读者需要对数据进行加锁防止写进程访问 up(count_mutex); read(); down(count_mutex); count–; if(count 0) up(data_mutex); up(count_mutex); } }
void writer() { while(TRUE) { down(data_mutex); write(); up(data_mutex); } }
2. 哲学家进餐问题五个哲学家围着一张圆周每个哲学家面前放着饭。哲学家的生活有两种交替活动吃饭以及思考。当一个哲学家吃饭时需要先一根一根拿起左右两边的筷子。
下面是一种错误的解法考虑到如果每个哲学家同时拿起左手边的筷子那么就无法拿起右手边的筷子造成死锁。
#define N 5
#define LEFT (i N - 1) % N
#define RIGHT (i N) % N
typedef int semaphore;
semaphore chopstick[N];void philosopher(int i) { while(TURE){ think(); down(chopstick[LEFT[i]]); down(chopstick[RIGHT[i]]); eat(); up(chopstick[RIGHT[i]]); up(chopstick[LEFT[i]]); } }
为了防止死锁的发生可以加一点限制只允许同时拿起左右两边的筷子方法是引入一个互斥量对拿起两个筷子的那段代码加锁。
semaphore mutex 1;void philosopher(int i) { while(TURE){ think(); down(mutex); down(chopstick[LEFT[i]]); down(chopstick[RIGHT[i]]); up(mutex); eat(); down(mutex); up(chopstick[RIGHT[i]]); up(chopstick[LEFT[i]]); up(mutex); } }
第三章 死锁
死锁的条件互斥请求与保持一个进程因请求资源而阻塞时对已获得的资源保持不放。不可抢占环路等待
死锁的处理方法
1. 鸵鸟策略
把头埋在沙子里假装根本没发生问题。
这种策略不可取。
2. 死锁预防
在程序运行之前预防发生死锁。
2.1 破坏互斥条件
例如假脱机打印机技术允许若干个进程同时输出唯一真正请求物理打印机的进程是打印机守护进程。
2.2 破坏请求与保持条件
一种实现方式是规定所有进程在开始执行前请求所需要的全部资源。
2.3 破坏不可抢占条件
2.4 破坏环路等待
给资源统一编号进程只能按编号顺序来请求资源。
3. 死锁避免
在程序运行时避免发生死锁。
3.1 安全状态图 a 的第二列 has 表示已拥有的资源数第三列 max 表示总共需要的资源数free 表示还有可以使用的资源数。从图 a 开始出发先让 B 拥有所需的所有资源运行结束后释放 B此时 free 变为 4接着以同样的方式运行 C 和 A使得所有进程都能成功运行因此可以称图 a 所示的状态时安全的。
定义如果没有死锁发生并且即使所有进程突然请求对资源的最大需求也仍然存在某种调度次序能够使得每一个进程运行完毕则称该状态是安全的。
3.2 单个资源的银行家算法
一个小城镇的银行家他向一群客户分别承诺了一定的贷款额度算法要做的是判断对请求的满足是否会进入不安全状态如果是就拒绝请求否则予以分配。上图 c 为不安全状态因此算法会拒绝之前的请求从而避免进入图 c 中的状态。
3.3 多个资源的银行家算法上图中有五个进程四个资源。左边的图表示已经分配的资源右边的图表示还需要分配的资源。最右边的 E、P 以及 A 分别表示总资源、已分配资源以及可用资源注意这三个为向量而不是具体数值例如 A(1020)表示 4 个资源分别还剩下 1/0/2/0。
检查一个状态是否安全的算法如下
① 查找右边的矩阵是否存在一行小于等于向量 A。如果不存在这样的行那么系统将会发生死锁状态是不安全的。
② 假若找到这样一行将该进程标记为终止并将其已分配资源加到 A 中。
③ 重复以上两步直到所有进程都标记为终止则状态时安全的。
4. 死锁检测与死锁恢复
不试图组织死锁而是当检测到死锁发生时采取措施进行恢复。
4.1 死锁检测算法
死锁检测的基本思想是如果一个进程所请求的资源能够被满足那么就让它执行释放它拥有的所有资源然后让其它能满足条件的进程执行。上图中有三个进程四个资源每个数据代表的含义如下
E 向量资源总量A 向量资源剩余量C 矩阵每个进程所拥有的资源数量每一行都代表一个进程拥有资源的数量R 矩阵每个进程请求的资源数量
进程 P1 和 P2 所请求的资源都得不到满足只有进程 P3 可以让 P3 执行之后释放 P3 拥有的资源此时 A (2 2 2 0)。P1 可以执行执行后释放 P1 拥有的资源 A (4 2 2 2) P2 也可以执行。所有进程都可以顺利执行没有死锁。
算法总结如下
每个进程最开始时都不被标记执行过程有可能被标记。当算法结束时任何没有被标记的进程都是死锁进程。
① 寻找一个没有标记的进程 Pi它所请求的资源小于等于 A。② 如果找到了这样一个进程那么将 C 矩阵的第 i 行向量加到 A 中标记该进程并转回 ①。③ 如果有没有这样一个进程算法终止。
4.2 死锁恢复
① 利用抢占恢复② 杀死进程
第四章 存储器管理
虚拟内存
每个程序拥有自己的地址空间这个地址空间被分割成多个块每一块称为一 页。这些页被映射到物理内存但不需要映射到连续的物理内存也不需要所有页都必须在物理内存中。
当程序引用到一部分在物理内存中的地址空间时由硬件立即执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。
分页与分段
1. 分页
用户程序的地址空间被划分为若干固定大小的区域称为“页”。相应地内存空间分成若干个物理块页和块的大小相等。可将用户程序的任一页放在内存的任一块中实现了离散分配由一个页表来维护它们之间的映射关系。
2. 分段上图为一个编译器在编译过程中建立的多个表有 4 个表是动态增长的如果使用分页系统的一维地址空间动态递增的特点会导致覆盖问题的出现。分段的做法是把每个表分成段一个段构成一个独立的地址空间。每个段的长度可以不同可以动态改变。
每个段都需要程序员来划分。
3. 段页式
用分段方法来分配和管理虚拟存储器。程序的地址空间按逻辑单位分成基本独立的段而每一段有自己的段名再把每段分成固定大小的若干页。
用分页方法来分配和管理实存。即把整个主存分成与上述页大小相等的存储块可装入作业的任何一页。程序对内存的调入或调出是按页进行的。但它又可按段实现共享和保护。
4. 分页与分段区别
① 对程序员的透明性分页透明但是分段需要程序员显示划分每个段。
② 地址空间的维度分页是一维地址空间分段是二维的。
③ 大小是否可以改变页的大小不可变段的大小可以动态改变。
④ 出现的原因分页主要用于实现虚拟内存从而获得更大的地址空间分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。
页面置换算法
在程序运行过程中若其所要访问的页面不在内存而需要把它们调入内存但是内存已无空闲空间时系统必须从内存中调出一个页面到磁盘对换区中并且将程序所需要的页面调入内存中。页面置换算法的主要目标是使页面置换频率最低也可以说缺页率最低。
1. 最佳Optimal
所选择的被换出的页面将是最长时间内不再被访问通常可以保证获得最低的缺页率。
是一种理论上的算法因为无法知道一个页面多长时间会被再访问到。
举例一个系统为某进程分配了三个物理块并有如下页面引用序列
70120304230321201701
进程运行时先将 7,0,1 三个页面装入内存。当进程要访问页面 2 时产生缺页中断会将页面 7 换出因为页面 7 再次被访问的时间最长。
2. 先进先出FIFO
所选择换出的页面是最先进入的页面。
该算法会将那些经常被访问的页面也被换出从而使缺页率升高。
3. 最近最久未使用LRU, Least Recently Used
虽然无法知道将来要使用的页面情况但是可以知道过去使用页面的情况。LRU 将最近最久未使用的页面换出。
可以用栈来实现该算法栈中存储页面的页面号。当进程访问一个页面时将该页面的页面号从栈移除并将它压入栈顶这样最近被访问的页面的页面号总是在栈顶而最近最久未使用的页面的页面号总是在栈底。
470710121264. 时钟Clock
Clock 页面置换算法需要用到一个访问位当一个页面被访问时将访问为置为 1。
首先将内存中的所有页面链接成一个循环队列当缺页中断发生时检查当前指针所指向页面的访问位如果访问位为 0就将该页面换出否则将该页的访问位设置为 0给该页面第二次的机会移动指针继续检查。
第五章 设备管理
磁盘调度算法
当多个进程同时请求访问磁盘时需要进行磁盘调度来控制对磁盘的访问。磁盘调度的主要目标是使磁盘的平均寻道时间最少。
1. 先来先服务FCFS, First Come First Serverd
根据进程请求访问磁盘的先后次序来进行调度。优点是公平和简单缺点也很明显因为未对寻道做任何优化使平均寻道时间可能较长。
2. 最短寻道时间优先SSTF, Shortest Seek Time First
要求访问的磁道与当前磁头所在磁道距离最近的优先进行调度。这种算法并不能保证平均寻道时间最短但是比 FCFS 好很多。
3. 扫描算法SCAN
SSTF 会出现进行饥饿现象。考虑以下情况新进程请求访问的磁道与磁头所在磁道的距离总是比一个在等待的进程来的近那么等待的进程会一直等待下去。
SCAN 算法在 SSTF 算法之上考虑了磁头的移动方向要求所请求访问的磁道在磁头当前移动方向上才能够得到调度。因为考虑了移动方向那么一个进程请求访问的磁道一定会得到调度。
当一个磁头自里向外移动时移到最外侧会改变移动方向为自外向里这种移动的规律类似于电梯的运行因此又常称 SCAN 算法为电梯调度算法。
4. 循环扫描算法CSCAN
CSCAN 对 SCAN 进行了改动要求磁头始终沿着一个方向移动。
参考资料
Tanenbaum A S, Bos H. Modern operating systems[M]. Prentice Hall Press, 2014.汤子瀛, 哲凤屏, 汤小丹. 计算机操作系统[M]. 西安电子科技大学出版社, 2001.Bryant, R. E., O’Hallaron, D. R. (2004). 深入理解计算机系统.小土刀的面试刷题笔记进程间的几种通信方式
