计算机操作系统
2017-03-20 19:34:18 0 举报AI智能生成
计算机系统前3章知识点
作者其他创作
大纲/内容
第一章 操作系统引论
1.1 操作系统的概述
计算机系统= 硬件+软件
操作系统的定位:
它是裸机之上的第一层软件
裸机：没有配置任何软件的物理计算机
1.2 操作系统的目标和作用
1.操作系统的目标
方便性:方便使用计算机系统，避免用户自己编写程序的繁琐工作。
有效性:合理组织计算机的工作流程，进一步改善资源的利用率，提高系统的吞吐量。
可扩充性
开放性
2. 操作系统的作用
它作为用户和计算机硬件之间的接口
它作为计算机系统资源的管理者
它作为扩充机器
3. 推动操作系统发展的主要动力
不断提高计算机资源利用率
方便用户使用
器件的不断更新换代
计算机体系结构的不断发展
1.3 操作系统的发展过程
1. 无操作系统的计算机系统
1） 人工操作方式
2） 脱机输入/输出方式
2. 单道批处理系统
1） 联机批处理（慢速I/O直接与主机相连）
2） 脱机输入/输出方式
3. 多道批处理系统
4. 分时系统
5. 实时系统
概述：计算机能及时响应外部事件的请求，在规定的时间内完成对原事件的处理，并且控制所有实时设备和实时任务协调一致的工作。
系统特征 ：
（1）响应时间要快
（2）系统可靠性要高
（3）具有连续的人-机对话能力
（4）具有保护过载能力
（5）系统整体性要强
6. 实时系统和分时系统的比较
1.4 操作系统的基本特性
1. 并发性（Concurrence）：指多个事件同时发生。
并发：是一种逻辑的或者宏观的同时性概念，即并发是宏观上的并行。
（在各自的起点和终点之间）；
并行：是一种物理的或者微观的同时性概念。
2. 共享性（Sharing）:OS追求的主要目标之一，并发和共享是OS的两个最基本的特征。
3. 不确定性（Nondeterminacy）:指事件的不可预测（时间和次序）随机性事件是造成OS不确定性的基本原因。
4. 虚拟性（Virtual）:虚拟是指将一个物理的实体变换（映射）为若干个逻辑上的对应物。例如分时CPU。
1.5 操作系统的主要功能
1. 处理机管理
主要任务：对CPU进行分配，且对其运行控制和管理
进行控制：为作业创建、撤销已结束的进程；
进程同步：进程互斥和进程同步；
进程通信：进程之间的信息交换；
调度：作业调度和进程调度。
2. 存储器管理
主要任务：为多道程序分配内存，方便用户使用存储器，提高 存储器利用率并且在逻辑上扩充内存。
内存分配：为每道程序静态或者动态地分配内存；
内存保护：保证每道用户程序都在自己的内存空间运行，互不干扰；
地址映射：将应用程序的地址空间映射为逻辑地址或相对地址；
内存扩充：借助虚拟存储技术，从逻辑上扩充内存。
3. 设备管理功能
主要任务：完成I/O请求，分配I/O设备，提高CPU和I/O设备的利用率，提高I/O速度，方便使用I/O设备。
缓冲管理：管理好各类缓冲区，提高系统吞吐量；
设备分配：根据I/O请求，分配所需要的设备；
设备处理：实现CPU与设备控制器之间的通信；
设备独立性：指应用程序独立于物理设备；
虚拟设备：将一个物理设备变换（改造）为多个对应的逻辑设备，是每个用户感觉自己独占该设备（spooling技术）。
4. 文件管理
主要任务：对用户文件和系统文件进行管理，方便用户使用，并保证文件的安全性 。
文件存储空间的管理：为文件分配必要的外存空间，提高外存利用率，并提高文件系统的运行速度；
目录管理：为每个文件建立其目录项，并对众多的目录项加以有效的组织，实现方便的按名存取；
文件读/写管理：从外存中读写数据；
文件保护：防止未经核准的用户存取文件，防止冒名存取文件，防止不正确的方式存取文件。
5. 用户接口
主要任务：方便用户使用操作系统，以命令、系统调用或者图形方式为用户提供接口 。
1.6 操作系统的结构设计
1. 传统的操作系统结构
无结构操作系统:OS可以看做一组过程的集合，过程之间互相调用。
模块化结构: OS由许多标准的、可兼容的基本单位构成，称为模块。各模块功能上相互独立，模块间通过规定的接口相互调用，将各模块连接起来构成完整的系统。
分层式操作系统:将模块按照某种逻辑关系排成若干层、层间只能单向依赖，不构成循环，系统的正确性由各层的正确性来保证。
2. 微内核操作系统结构
客户/服务器模式（Client-Server Model）
面向对象的设计技术（Object-Oriented Programming）
微内核技术（MicroKernel）:是指精心设计的、能实现现代OS核心功能的小型内核。
a. 进程管理
b. 存储器管理
c. 进程通信管理
d. I/O设备管理
第2章 进程的描述与控制
2.1 进程的基本概念
1. 程序的顺序执行与特征
前趋图： 是一个有向无循环图DAG(Directed Acyclic Graph)
特征：
(1)顺序性
(2)封闭性
(3)可再现性
2.程序的并发执行和特征
(1)不可再现性 ：并发程序的执行结果与它们的相对速度有关。
(2)制约性 ：并发程序之间相互依赖和制约。
(3)程序与计算不再一一对应
3.进程的定义和特征
定义：一个具有独立功能的程序在一个数据集合上的一次动态执行过程。是系统进行资源分配和调度的一个独立单位。
进程和程序的区别：
程序是静态概念，是一组指令的有序集合；进程是程序的执行，是动态概念。
进程的存在是暂时的，而程序的存在是永久的。
进程和程序是密切相关的，但是无一一对应关系。一个程序可对应多个进程；通过调用关系，一个进程也可包含多个程序。
进程是一个能独立运行的单位，能与其它进程并发执行。而程序是不能作为一个独立运行的单位而并发执行的。
进程是程序的执行，因此进程的组成应包括程序、数据和进程控制块（即进程状态信息）。
特征
动态性 进程是程序在并发系统内的一次执行，一个进程有一个从产生到消失的生命期；
并发性 正是为了描述程序在并发系统内执行的动态特性才引入了进程，没有并发就没有进程；
独立性 每个进程的程序都是相对独立的顺序程序，可以按照自己的方向和速度独立地向前推进；
制约性 进程之间的相互制约，主要表现在互斥地使用资源和相关进程之间必要的同步和通讯；
结构性 进程 = PCB（进程控制块） + 程序 + 数据集合。
4.进程的状态和组成
进程的基本状态:
运行状态
就绪状态
阻塞状态
创建状态
退出状态
进程队列、PCB组织方式：
线性方式
链接方式
索引方式
2.2 进程控制
原语：
原语操作也称做“原子操作”，即一个操作中的所有动作要么全做，要么全不做。
进程的创建
进程可借助创建原语建立一个子进程
进程的终止
撤销原语一般由其父进程或祖先发出，不会自己撤销自己。一旦系统中出现要求终止进程的事件后，便调用进程终止原语。
进程的阻塞
正在运行的进程通过调用阻塞原语主动地把自己阻塞。
进程的唤醒
当被阻塞进程所等待的事件出现时，则由另外的与被阻塞进程相关的进程调用唤醒原语，将等待该事件的进程唤醒。可见，被阻塞进程不能唤醒自己。
进程的挂起
调用挂起原语的进程只能挂起它自己或它的子孙。
进程的激活
一个进程只能将自己的子孙进程解挂。一个进程可以将自己挂起，却不能将自己解挂。
2.3 进程同步
1.进程同步的基本概念
(1)同步（直接相互制约关系、相互合作的关系）
(2)互斥（间接相互制约关系、对资源争用的关系）
2.临界资源和临界区
(1)临界资源(Critical Resouce )
一次只允许一个进程使用的资源。
(2) 临界区(critical section)
在每个进程中访问临界资源的那段程序，简称CS区。
(3) 临界区的调用原则
空闲让进
忙则等待
有限停留
让权等待
3.临界区互斥执行的解决方法
(1)软件方法
单标志算法
双标志、先检查算法
双标志、先修改后检查算法
双标志、先检查算法
双标志、先修改后检查算法
先修改、后检查、后修改者等待算法（算是对两个进程同步最好的实现）
(2)硬件方法
4.信号量机制
1. 整型信号量
即PV操作对应的wait(S)，signal(S).S表示资源数 mutex互斥
执行一次signal操作意味着释放一个单位资源
执行一次wait操作意味着申请分配一个单位资源
2. 记录型信号量
信号量的值（s.value，计数）
指向PCB的指针（s.L，标识进程等待队列）
3. AND型信号量
区别：上述的进程互斥问题，是针对各进程之间要共享一个临界资源而言的。在有些应用场合，是一个进程需要先获得两个或更多的共享资源后，方能执行其任务。
Swait(S1,S2,…,Sn)
Ssignal(S1,S2,…,Sn)
4. 信号量集
区别：在记录型信号量机制中，wait(S)和signal(S)操作仅能对信号量施以加1或减1操作，当一次需要N个某类临界资源时，便要进行N次wait(S)操作，很低效；另外，在有些情况下，当资源数量低于某一下限值时，便不予以分配。
S为信号量，d为需求值，t为下限值。
Swait(S1, t1, d1, …, Sn, tn, dn)
5.信号量的应用
利用信号量实现进程互斥
用信号量实现进程同步
利用信号量实现前趋关系
2.4 经典的同步问题
生产者—消费者问题
2. 读者-写者问题（reader-writers problem)
3. 哲学家进餐问题（The Dinning Philosophers Problem)
用AND信号量机制可获得最简洁的解法。
每个哲学家先获得两个临界资源(筷子)后方能进餐，
2.5 管程机制
1.管程的基本概念
基本思想:把信号量及其操作原语封装在一个对象中。
2.管程(monitor)的定义
管程由三部分组成：
(1)局部于管程的共享变量说明；
(2) 对该数据结构进行操作的一组过程；
(3) 对局部于管程的数据设置初始值的语句。此外，还须为管程赋予一个名字。
为了实现对临界资源的互斥访问，管程每次只允许一个进程进入其内（即访问管程内的某个过程）
3.引入管程的优点
(1)具有良好的封装性，可增强模块的独立性。
(2)引入管程可以提高代码的可读性，便于修改和维护并保证代码的正确性。
4.管程和进程的区别
(1)进程是为了描述程序的动态执行过程，而管程是为了协调进程的同步和对共享资源的访问。
(2)操作系统维护进程的数据结构是PCB，而与管程相关的数据结构是等待队列。
(3)管程可被进程调用，管程与操作系统的共享资源相关。
(4)进程有创建和撤消，而管程没有。
2.6 进程通信
进程通信的类型
1. 共享存储器系统(Shared-Memory System)
2. 管道(Pipe)通信
3. 消息传递系统(Message passing system)
2.7 线程
线程的基本概念
线程的引入正是为了简化线程间的通信，减小程序在并发执行时所付出的时空开销，提高进程内的并发程度。
2.线程和进程的对比
(1)线程和进程的关系
线程是进程的一个组成部分。一个进程可以有多个线程，一个进程的多个线程都在进程的地址空间活动。
资源的分配对象是进程，而不是线程。
调度的基本单位是线程而不是进程，即处理机是分配给线程的；真正在处理机上执行的是线程，但线程所用到的资源是进程所分配到的资源。
线程在执行过程中，需要协作同步。
(2)进程和线程的比较
地址空间资源：不同进程的地址空间是相互独立的，而同一进程的各个线程共享同一地址空间。
通信关系：进程通信必须使用操作系统提供的进程间通信机制，而同一进程的各个线程间可以通过直接读写进程数据段来进行通信。
调度切换：同一进程中的线程上下文切换比进程上下文切换要快得多。
3. 线程的属性
(1)轻型实体。
(2) 独立调度和分派的基本单位。
(3) 可并发执行。
(4) 共享进程资源。
4. 线程的状态
就绪状态：线程已具备执行条件，正在等待CPU。
备用状态：由调度程序选定为一个执行对象。
运行状态：正在CPU上执行其程序。
等待状态：正在执行，由于某种原因不能继续运行下去。
转换状态：若线程已准备好执行，但突然资源不可用，从而成为转换状态。
终止状态：线程完成了它的执行。
2.8 例题选讲
第3章 处理机调试与死锁
3.1 处理机调度的基本概念
1．高级调度——又称作业调度或长调度
定义：用于决定把外存上后备队列中哪些作业调入内存，并为它们创建进程、分配必要的资源，然后将新创建的进程插入到就绪队列中，准备运行。
任务：
接纳多少个作业——取决于多道程序度
接纳多少个作业——取决于多道程序度
接纳哪些作业——取决于调度算法
2．低级调度--又称进程调度或短调度。是最基本的调度
定义：用来决定就绪队列中的哪个进程应获得处理机，然后再由分派程序执行把处理机分配给该进程的具体操作。
调度方式：
（1）非抢占方式
（2）抢占方式
优先权原则；
短作业优先原则；
时间片原则。
3. 中级调度--挂起和激活，存储器管理中的对换功能。
三种调度相比较：
进程调度的运行频率最高
作业调度频率最低
中级调度界于之间
3.2 调度算法
1.调度队列模型
1. 仅有进程调度的调度队列模型
2. 具有高级和低级调度的调度队列模型
3. 同时具有三级调度的调度队列模型
2.调度算法
3.2.1 先来先服务调度算法(FCFS)
FCFS算法比较有利于长作业（进程），不利于短作业（进程）。
有利于CPU繁忙型作业（进程），不利于I/O繁忙型作业（进程）——因非抢占式
3.2.2 短作业(进程)优先调度算法（SJF）（SPF)
从后备队列中选择一个或几个估计运行时间最短的作业，将它调入内存运行。
优点：当多个作业同时到达时，SJF算法可使平均周转时间最短。
3.2.3 高优先权优先调度算法
目的：照顾紧迫型作业，使之在进入系统后便获得优先处理。
系统从后备中选择一个或几个优先权最高的作业，将它调入内存运行。
优先权的类型
静态优先权
静态优先权——它是在创建进程时确定的，且在进程整个运行期间保持不变。
动态优先权
在创建进程时所赋予的优先权，是可以随进程得推进，或随其等待时间的增加而改变的，以便获得更好的调度性。
3.2.4 高响应比优先调度算法
响应比＝(等待时间+要求服务时间)/要求服务时间
每次要进行作业调度时，系统首先计算后备队列中各作业的响应比，然后选择一个或若干个响应比最高的作业调入内存执行。
优点：综合了FCFS和SJF算法的优点
缺点是会增加系统开销——每次调度都要计算响应比。
3.2.5 基于时间片的轮转调度算法
1．时间片轮转法
系统把就绪队列中的所有进程，按先来先服务的原则，排成一个队列；
每次调度时，把CPU分配给队首进程，并让它执行一个时间片；
2．多级反馈队列调度算法
3.3 实时调度
目的：满足实时系统对调度的要求
具备下述几个条件：
1．提供必要的信息
2．系统处理能力强
3．采用抢占式调度机制
4．具有快速切换机制
常用的几种实时调度算法
1．最早截止时间优先算法
即EDF(Earliest Deadling First)算法
根据任务的开始截止时间来确定任务的优先级。截止时间愈早，其优先级愈高。
2．最低松弛度优先算法
即LLF(Least Laxity First)算法
根据任务紧急(或松弛)的程度来确定任务的优先级。任务紧急程度愈高，其优先级愈高。
3.4 产生死锁的原因和必要条件
定义：一组竞争系统资源或相互通信的进程间相互的“永久”阻塞。
产生死锁的原因
（1）竞争资源
（2）进程间推进顺序非法
产生死锁的必要条件
互斥条件
请求和保持条件
不剥夺条件
环路等待条件
处理死锁的基本方法
预防死锁、避免死锁、检测死锁、解除死锁
3.5 预防和避免死锁的方法
预防死锁
1．破坏“互斥”条件
2．屏弃“请求并保持”条件
3．屏弃“不剥夺”条件
4．屏弃“环路等待”条件
避免死锁——银行家算法
1. 安全状态
存在一个安全序列<P2，P1，P3>，即只要系统按此进程序列分配资源，就能使每一个进程都顺利完成。
2. 安全状态之例
3. 利用银行家算法避免死锁
1）银行家算法中的数据结构
可利用资源向量Available
最大需求矩阵Max
分配矩阵Allocation
需求矩阵Need
3.6 死锁的检测和解除
预防死锁的方法——破坏死锁必要条件
避免死锁——银行家算法
死锁的检测
1. 利用资源分配图检测死锁
(1) 若资源分配图中无环路，则此时系统中无死锁；
(2) 如果资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁。此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程；
子主题
死锁的解除
剥夺资源
从其它进程剥夺足够资源给死锁进程，以解除死锁状态。(教科书) 或者：
剥夺死锁进程占用的资源，但并不撤消它，直到死锁解除。
撤消进程
撤消全部死锁进程
按某个顺序逐个撤消死锁进程，直至使死
锁状态解除为止。
0 条评论
下一页
