操作系统原理笔记

前段时间和同事聊到面试,几个非科班出身(数据分析岗)的说操作系统之类的不重要,面试也不怎么考,实践中也用得少。

我一时语塞,想争论一番,考虑之后还是放弃。当然这里不是在讨论所谓科班or非科班的优越性。我也在想,这些知识能带给我们什么。

开始实习之后,身边有很多数学、信管、金融甚至完全不搭边专业的同事,他们同样在自己的岗位上做的很好,这时候不禁在想,是他们更用功把这些gap补齐了,还是这一行的门槛其实本身就很低,又或者是以我为代表的人没有把科班的东西真正掌握好。

又或者说,假使我学的不是CS专业,想要进入这个专业,是不是我只需要学一部分课程就够了呢?

当然,我自然是相信,学得越多,掌握的越多,对于日后的长久发展越有利。

稍微扯了一些,这篇文章的主题还是操作系统,这里把下面这本书copy一遍,列出一个提纲,希望在这个过程中有所得,也便于日后回顾。

对于考试而言,重点掌握几个算法应对大题应该无虞。

一、操作系统引论

操作系统的主要功能

操作系统的主要任务,是为多道程序的运行提供良好的运行环境,以保证多道程序能有条不紊地、高效地运行,并能最大程度地提高系统中各种资源的利用率和方便用户的使用。

处理机管理功能

创建和撤销进程(线程),对诸如进程(线程)的运行进行协调,实现进程(线程)的交换,以及按照一定的算法把处理机分配给进程(线程)。

  • 进程控制:为作业创建进程,撤销已结束的进程,以及控制进程在运行过程中的状态转换。
  • 进程同步:为多个进程(含线程)的运行进行协调,有两种协调方式。
    • 进程互斥方式:对临界资源访问时,应采用互斥方式
    • 进程同步方式:相互合作完成共同任务的诸进程间,由同步机构对他们的执行顺序加以协调,例如信号量等。
  • 进程通信:当想相互合作的进程处于同一计算机系统时,通常在它们之间采用直接通信方式,即由源进程利用发送命令直接将消息(Message)挂到目标进程的消息队列上,以后由目标进程接受命令从其消息队列中取出消息。
  • 调度:在后备队列上等待的每个作业都需经过调度才能执行。在传统的操作系统中,包括作业调度进程调度两步。
    • 作业调度:作业调度的基本任务是从后备队列中按照一定的算法,选择出若干个作业,为它们分配运行所需的资源(首先是分配内存),在将它们调入内存后,便分别为它们建立进程,使它们都成为可能获得处理机的就绪进程,并按照一定的算法将它们插入就绪队列。
    • 进程调度:进程调度的任务是从进程的就绪队列中,按照一定的算法选出一个进程, 把处理机分配给它,并为它设置运行现场,使进程投入执行。值得提出的是,在多线程 OS 中,通常是把线程作为独立运行和分配处理机的基本单位,为此,须把就绪线程排成一个队列,每次调度时,是从就绪线程队列中选出一个线程,把处理机分配给它。

操作系统的发展

无操作系统

存储器管理

存储器管理的主要任务是为多道程序的运行提供良好的环境,方便用户使用存储器, 提高存储器的利用率以及能从逻辑上扩充内存。为此,存储器管理应具有内存分配、内存 保护、地址映射和内存扩充等功能。

  • 内存分配:为每道程序分配内存空间;提高存储器的利用率,减少不可用的内存空间;允许正在运行的程序申请附加的内存空间,以使用程序和数据动态增长的需要。分配方式有静态和动态分配之分。内存分配应具有的结构和功能:
    • 内存分配数据结构
    • 内存分配功能
    • 内存回收功能
  • 内存保护:确保每道用户程序只在自己的内存空间运行,彼此互不干扰;决不允许用户程序访问操作系统程序的程序和数据;也不允许用户程序转移到非共享的其它用户程序中去执行。
  • 地址映射:逻辑地址到物理地址的转换
  • 内存扩充:借助虚拟存储结束,从逻辑上扩充内充容量。
    • 请求调入功能:从磁盘调入内存
    • 置换功能:将内存中暂时不用的程序和数据调至磁盘,腾出空间。

设备管理和文件管理。

二、进程管理

进程的基本概念

进程:作为资源分配和独立运行的基本单位,程序段、相关的数据段和PCB(Process Control Block)组成进程实体。

进程的特征:

  • 结构特性:程序段相关的数据段PCB(Process Control Block)组成进程实体。
  • 动态性:进程的实质是指进程实体的一次执行过程,“由创建而产生,由调度而执行,由撤销而消亡”
  • 并发性:多个进程同时存在于内存中,且能在一段时间内同时运行。
  • 独立性在传统的 OS 中,独立性是指进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。
  • 异步性:进程按照各自独立的、不可预知的速度向前推进。

前趋图 (Precedence Graph):是一个有向无循环图,记为 DAG(Directed Acyclic Graph),用于描述进程之间执行的前后关系。

进程控制块(PCB)中的信息:

  • 进程标识符:
  • 外部标识符
  • 处理机状态:处理机中断时,信息保存在PCB中,以便于重新执行时,从断点继续执行。
    • 1.通用寄存器:
    • 2.指令寄存器
    • 3.程序状态字(PSW)
    • 4.用户栈指针
  • 进程调度信息:
    • 1.进程状态,进程调度和对换时的依据
    • 2.进程优先级
    • 3.进程调度所需其余信息
    • 4.事件,执行到阻塞所发生的时间,即阻塞原因

进程控制块的组织方式

  • 链接方式
  • 索引方式

进程与程序对比

试从动态性,并发性和独立性上比较进程和程序.

  • a. 动态性是进程最基本的特性,可表现为由创建而产生,由调度而执行,因得不到资源而暂停执行,
    以及由撤销而消亡,因而进程由一定的生命期;而程序只是一组有序指令的集合,是静态实体.
  • b. 并发性是进程的重要特征,同时也是OS的重要特征.引入进程的目的正是为了使其程序能和其它进程
    的程序并发执行,而程序是不能并发执行的.
  • c. 独立性是指进程实体是一个能独立运行的基本单位,同时也是系统中独立获得资源和独立调度的基本
    单位.而对于未建立任何进程的程序,都不能作为一个独立的单位参加运行.

进程的三种状态

  • 就绪:进程获得出CPU以外所有资源,只要获得CPU就可以立即执行。
  • 执行:进程获得CPU,程序正在执行。
  • 阻塞:正在执行的进程由于发生某些时间而暂时无法继续执行时,从而放气处理机处于暂停状态。(例如IO请求、申请缓存空间)


1.试说明进程在三个基本状态之间转换的典型原因.

a. 处于就绪状态的进程,当进程调度程序为之分配了处理机后,该进程便由就绪状态变为执行状态.
b. 当前进程因发生某事件而无法执行,如访问已被占用的临界资源,就会使进程由执行状态转变为阻
塞状态.
c. 当前进程因时间片用完而被暂停执行,该进程便由执行状态转变为就绪状态.

2.为什么要引入挂起状态?该状态具有哪些性质?

a. 引入挂起状态处于5中需要: 终端用户的需要,父进程的需要,操作系统的需要,对换的需要和负荷
调节的需要.
b. 处于挂起状态的进程不能接收处理机调度.

顺序执行

  • 顺序性
  • 封闭性
  • 可再现性

并发执行

  • 间断性
  • 失去封闭
  • 不可再现性

进程控制

在进行进程切换时,所要保存的处理机状态信息主要有哪些?

a. 进程当前暂存信息;b. 下一条指令地址信息;c. 进程状态信息;d. 过程和系统调用参数及调用地址信息.

试说明引起进程创建的主要事件

a. 用户登陆;b. 作业调度;c. 提供服务;d. 应用请求.

试说明引起进程撤消的主要事件

a. 正常结束;b. 异常结束;c. 外界干预;

在创建一个进程时,需完成的主要工作是什么?

a. 操作系统发现请求创建新进程事件后,调用进程创建原语Creat();b. 申请空白PCB;c. 为新进程分配资源;d. 初始化进程控制块;e. 将新进程插入就绪队列.

在撤消一个进程时,需完成的主要工作是什么?

a. OS调用进程终止原语;
b. 根据被终止进程的标志符,从PCB集合中检索出该进程的PCB,从中读出该进程的状态;
c. 若被终止进程正处于执行状态,应立即中止该进程的执行,并设置调度标志为真;
d. 若该进程还有子孙进程,还应将其所有子孙进程予以终止;
e. 将该进程所拥有的全部资源,或者归还给其父进程,或者归还给系统;
f. 将被终止进程(它的PCB)从所在队列(或链表)中移出,等待其它程序来搜集信息.

试说明引起进程阻塞或被唤醒的主要事件是什么?

a. 请求系统服务;b. 启动某种操作;c. 新数据尚未到达;d. 无新工作可做.

进程同步

同步机构应遵循哪些基本准则?为什么?

a. 空闲让进.b. 忙则等待.c. 有限等待.d. 让权等待.

进程通信

线程

进程与线程对比

在OS中引入进程的目的是为了使多个程序并发执行,从而提高资源利用率和系统吞吐量,引入线程这是为了减少程序在并发执行时所付出的时空开销,使得OS具有更好的并发性。

进程是可拥有资源的独立单位,同时进程也是一个可独立调度和分派的基本单位。

线程的实现方式

  • 内核支持线程KST(Kernel Supported Threads):所谓的内核支持线程 KST(Kernel Supported Threads),也都同样是在内核的支持下运行的
  • 用户级线程ULU(User Level Threads):仅存在于用户空间中,对于这种线程的创建、撤 消、线程之间的同步与通信等功能,都无须利用系统调用来实现

线程的同步和通信

  • 互斥锁(mutex):互斥锁是一种比较简单的、用于实现线程间对资源互斥访问的机制。由于操作互斥锁 的时间和空间开销都较低,因而较适合于高频度使用的关键共享数据和程序段。
  • 条件变量:条件变量和互斥锁结合
  • 信号量机制 :
    • 私用信号量(private samephore)
    • 公用信号量(public semaphort)

三、处理机及调度与死锁

死锁的必要条件

  • 互斥条件
  • 请求和保持
  • 不可抢占
  • 循环等待

处理死锁

  • 预防死锁:采用限制条件,破坏产生条件。(银行家算法)
  • 避免死锁:资源动态分配中,运用某种方法防止系统进入不安全状态。
  • 检测死锁:运行时检测死锁,然后采用适当的措施,把进程从死锁中解脱出来。
  • 解除死锁

处理机调度的层次

高级调度(High Level Scheduling)

高级调度又称为作业调度长程调度(LongTerm Scheduling),其 主要功能是根据某种算法,把外存上处于后备队列中的那些作业调入内存,也就是说,它的调度对象是作业。

低级调度(Low Level Scheduling)

通常也把低级调度称为进程调度或短程调度(ShortTerm Scheduling),它所调度的对象是进程(或内核级线程)。进程调度是最基本的一种调度,在多 道批处理、分时和实时三种类型的 OS 中,都必须配置这级调度。

低级调度的功能:

  • 保存处理机的现场信息
  • 按照某种算法选取进程
  • 把处理机分配给进程

进程调度的三个基本机制

  • 排队器
  • 分派器
  • 上下文切换机制

进程调度方式

  • 非抢占式(Nonpreemptive Mode)
  • 抢占方式(Preemptive Mode)

中级调度(Intermediate Level Scheduling)

中级调度又称中程调度(Medium-Term Scheduling)。引入中级调度的主要目的是为了提高内存利用率和系统吞吐量。为此,应使那些暂时不能运行 的进程不再占用宝贵的内存资源,而将它们调至外存上去等待。

事务是一个原子执行的程序单元,即要么与其相关的所有操作都执行完,要么什么操作都不做。

四、存储器管理

存储器的层次结构

存储器的多层结构

  • 操作系统管理:寄存器、高速缓存、主存储器和磁盘缓存,掉电后存储的信息不再存在
  • 设备管理:底层的固定磁盘 和可移动存储介质,其存储信息被长期保存

主存储器和寄存器

  • 主存储器又称内存或主存,是计算机系统中的主要部件,用来保存进程运行时的程序和数据,也称为可执行存储器。由于主存储器访问速度远低于CPU执行指令的速度,为缓和这一矛盾,在计算机操作系统中引入了寄存器和高速缓存。
  • 寄存器:寄存器具有与处理机相同的速度,因此对于寄存器的访问速度最快。

高速缓存和磁盘缓存

高速缓存

介于寄存器和存储器之间的存储器,主要用于备份主存中较常用的数据,减少处理机对于主存储器的访问次数,从而大幅度提高程序执速度。

将一些常用数据存储在高速缓存中是有效的,这一点可以通过程序执行的局部性原理解释。

  • 局部性原理 ·是指CPU访问存储器时,无论是存取指令还是存取数据,所访问的存储单元都趋于聚集在一个较小的连续区域中。

通常,进程的程序和数据是存放在主存储器中,每当使用时,被临时复制到一个速度较快的高速缓存中。当 CPU 访问一组特定信 息时,首先检查它是否在高速缓存中,如果已存在,可直接从中取出使用,以避免访问主存,否则,再从主存中读出信息。如大多数计算机有指令高速缓存,用来暂存下一条欲执行的指令,如果没有指令高速缓存,CPU 将会空等若干个周期,直到下一条指令从主存中 取出。由于高速缓存的速度越高价格也越贵,故有的计算机系统中设置了两级或多级高速缓存。紧靠内存的一级高速缓存的速度最高,而容量最小,二级高速缓存的容量稍大,速度也稍低。

磁盘缓存

由于目前磁盘的 I/O 速度远低于对主存的访问速度,因此将频繁使用的一部分磁盘数据 和信息,暂时存放在磁盘缓存中,可减少访问磁盘的次数。

要注意的是,磁盘缓存本身并不是一种实际存在的存储介质,它依托于固定磁盘,提供对主存储器存储空间的扩充,即利用主存中的存储空间,来暂存从磁盘中读出(或写入)的信息

程序的装入和链接

将一个模块装入内存的时候,有以下三种方式:

  • 1.绝对装入方式(Absolute Loading Mode)
  • 2.可重定位装入方式(Relocaltion Loading Mode)
  • 3.动态运行时装入方式(Dynamic Run-time Loading)

动态运行时的装入程序在把装入模块装入内存后,并不立即把装入模块中的相对地址转换为绝对地址,而是把这种地址转换推迟到程序真正要执行时才进行。因此,装入内存 后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度,这种方式需要一个重定位寄存器的支持。

链接

源程序经过编译后,可得到一组目标模块,再利用链接程序将这组目标模块链接,形 成装入模块。根据链接时间的不同,可把链接分成如下三种:

  • 1.静态链接。在程序运行之前,先将各目标模块及它们所需的库函数,链接成一个完 整的装配模块,以后不再拆开。我们把这种事先进行链接的方式称为静态链接方式。
  • 2.装入时动态链接。这是指将用户源程序编译后所得到的一组目标模块,在装入内存 时,采用边装入边链接的链接方式。
  • 3.运行时动态链接。这是指对某些目标模块的链接,是在程序执行中需要该(目标)模 块时,才对它进行的链接。

连续分配方式

连续分配方式,是指为一个用户程序分配一个连续的内存空间。

单一连续分配

这是最简单的一种存储管理方式,但只能用于单用户、单任务的操作系统中。采用这种存储管理方式时,可把内存分为系统区和用户区两部分,系统区仅提供给 OS 使用,通常是放在内存的低址部分;用户区是指除系统区以外的全部内存空间,提供给用户使用。

固定分区分配

固定分区式分配是最简单的一种可运行多道程序的存储管理方式。这是将内存用户空间划分为若干个固定大小的区域,在每个分区中只装入一道作业,这样,把用户空间划分为几个分区,便允许有几道作业并发运行。当有一空闲分区时,便可以再从外存的后备作 业队列中选择一个适当大小的作业装入该分区,当该作业结束时,又可再从后备作业队列中找出另一作业调入该分区。

划分分区的方法:
1.分区大小相等:缺点是缺乏灵活性
2.分区大小不等:可划分为小分区、中分区和大分区

动态分区分配

为了实现分区分配,系统中必须配置相应的数据结构,用来描述空闲分区和已分配分区的情况,为分配提供依据。

数据结构

分区分配算法 为把一个新作业装入内存,须按照一定的分配算法,从空闲分区表或空闲分区链中选出一分区分配给该作业

  • 1.首次适应算法(first fit)

  • 2.循环首次适应算法(next fit)

在为进程分配内存空间时,不再是每次都从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区,从中划出一块与请求大小相等的内存空间分配给作业。

  • 3.最佳适应算法(best fit)

所谓“最佳”是指每次为作业分配内存时,总是把能满足要求、又是最小的空闲分区 分配给作业,避免“大材小用”。

  • 4.最坏适应算法(worst fit)
  • 5.快速适应算法(quick fit)

可重定位分配

虚拟存储器

为什么引入虚存:内存容量不够大,物理增加内存系统程序成本大。

所谓虚拟存储器,是指具有请求调入和置换功能,能从逻辑上对内存容量加以扩充的存储器结构。其逻辑容量是由内存容量和外存容量纸盒所决定,运行速度接近于内存,每位的成本接近外存。

虚拟存储器具有以下特性

  • 多次性:内存中的程序和数据无需一次性装入。\
  • 对换性:一个作业的程序和数据无需常驻内存。
  • 虚拟性:从逻辑上扩充内存容量,是用户看到的内存容量远大于实际。

五、设备管理

六、文件管理

参考

  • 《计算机操作系统》 第四版 课本及习题
曹真 wechat
欢迎关注公众号:一时博客