【软件设计师】——3.操作系统基本原理

目录

3.1 进程管理

3.2 存储管理

3.3 文件管理

3.4 设备管理

3.5 作业管理

3.6 操作系统

---

3.1 进程管理

• 线程、进程、程序

  1. 线程共享内容：进程代码段、进程的公有数据（线程利用共享数据实现相互之间的通讯)、进程打开的文件描述符、信号处理器、进程当前目录、进程用户ID与进程组ID

  2. 线程独有内容：线程ID、寄存器组的值、线程的堆栈、错误返回码、线程的信号屏蔽码

  3. 进程：是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。它由程序块、进程控制块 PCB 、数据块组成

  4. 进程与程序的区别：进程是程序的一次执行过程，没有程序就没有进程。程序是完成某个特定功能的一系列程序语句的集合，只要不被破坏，它就永远存在。程序是一个静态概念，而进程是一个动态概念，它由创建而产生，完成任务后因撤销而消亡；进程是系统进行资源分配和调度的独立单位，而程序不是

• 进程控制块的组织方式

  1. 链接方式：把具有同一状态的PCB，用其中的链接字链接成一个队列，可形成就绪队列、若干阻塞队列、空白队列等。对其中的就绪队列常按进程优先级高低排列，把优先级高的进程PCB排在队列前面。也可根据阻塞原因的不同而把处于阻塞状态的进程PCB排成等待I/O操作完成的队列和等待分配内存的队列等

  2. 索引方式：系统根据所有进程的状态建立若干索引表。如就绪索引表、阻塞索引表等，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表表目中，记录具有相应状态的某个PCB在PCB表中的地址

• 状态转换过程

  1. 进程正在被创建时，它的状态是“创建态”，在这个阶段操作系统会为进程分配资源、初始化PCB

  2. 当进程创建完成后，进入“就绪态”，进程已经具备运行条件但由于没有空闲CPU，暂时不能运行

  3. 若一个进程此时在CPU上运行，这个进程处于“运行态”，CPU会执行该进程对应的程序（执行指令序列)

  4. 在进程运行过程中，可能会请求等待某个事件的发生（如等待某种系统资源的分配，或等待其他进程的响应）。在这个事件发生之前，进程无法继续往下执行，此时操作系统会让这个进程下CPU，让它进入“阻塞态”，当CPU空闲时又会选择另一个“就绪态”进程上CPU运行

  5. 一个进程可执行exit系统调用，请求操作系统终止该进程。该进程会进“终止态”，操作系统会让该进程下CPU，回收内存空间等资源，最后还要回收该进程的PCB。当终止进程工作完成后，这个进程就彻底消失

• 状态转换模型

  ① 就绪态 = > 运行态：进程被调度

  ② 运行态 = > 就绪态：时间片到，或处理机被抢占

  ③ 运行态 = > 阻塞态：进程用系统调用方式申请系统资源，或请求等待某事件发生，是一种进程自身做出的主动行为

  ④ 阻塞态 = > 就绪态：申请的资源被分配，或等待的事件发生，不是进程自身能控制的，是一种被动行为

  注意：不能由阻塞态直接转换为运行态，也不能由就绪态直接转换为阻塞态（因为进入阻塞态是进程主动请求的，必然需要进程在运行时才能发出这种请求)

  

• 信号量机制

  1. 临界资源：诸进程间需要互斥方式对其进行共享的资源，如：打印机、磁带机等。临界资源不能采用时间片轮转分配算法，若打印机轮流为不同进程打印文档，将造成文档打印混乱

  2. 临界区：每个进程中访问临界资源的那段代码称为临界区

  3. 信号量：是一种特殊变量（可以是一个整数、更复杂的记录型变量)，可以用一个信号量表示系统中某种资源的数量，如：系统中只有一台打印机，就可以设置一个初值为1的信号量

  4. 原语：

     ① 由关中断/开中断指令实现，是一种特殊的程序段，其执行只能一气呵成，不可被中断。可以把wait(S)/P(S)、signal(S)/V(S)原语理解为函数，函数名分别为wait和signal，括号里的信号量S就是函数调用时传入的一个参数

     ② wait(S)、signal(S)两个操作分别写操作系统提供的一对原语来对信号量进行操作，从而方便的实现进程互斥、进程同步、进程的前驱关系

     ③ 一个信号量对应一种资源信号量的值 = 这种资源的剩余数量（信号量的值小于0，说明此时有进程在等待这种资源)

     P(S)：申请一个资源S，如果资源不够就阻塞等待，即S-1 V(S)：释放一个资源S，如果有进程在等待该资源，则唤醒一个进程，即S+1

     

• 进程调度：指当有更高优先级的进程到来时如何分配CPU

  1. 可剥夺式：强行将正在运行进程的 CPU分配给高优先级的进程

  2. 不可剥夺式：必须等待正在运行进程自动释放占用的CPU，然后将CPU分配给高优先级的进程

• 死锁问题

  1. 进程管理是操作系统的核心，设计不当就会出现死锁问题。如果进程在等待一件不可能发生的事，则进程就死锁了，如果多个进程产生死锁就会造成系统死锁

  2. 若系统中有m个单位的存储器资源，它被n个进程使用，当每个进程都要求w个单位的存储器资源，当m < nw时，可能会引起死锁

  3. 系统不可能发生死锁的最小资源数：(w-1) * m + 1<= n，w：单个进程需要的资源数；m：进程数

  4. 死锁必须同时满足以下四个条件

     ①互斥：只有对必须互斥使用的资源的争抢才会导致死锁，如打印机

     ②不剥夺：进程所获得的资源在未使用完之前，不能由其他进程强行夺走，只能主动释放

     ③请求和保持：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，此时请求进程被阻塞，但又对自己已有的资源保持不放

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

• 死锁处理策略

  1. 预防死锁：破坏死锁产生的四个必要条件中的一个或几个

  2. 死锁检测和解除：允许死锁的发生，不过操作系统会负责检测出死锁的发生，然后采取某种措施解除死锁

  3. 避免死锁：用某种方法防止系统进入不安全状态，从而避免死锁（有序资源分配法\银行家算法)

     ①银行家算法思想：若系统按照一个安全序列分配资源，每个进程都能顺利完成，系统处于安全状态，就一定不会发生死锁；若分配了资源后，系统中找不出任何一个安全序列，系统就进入了不安全状态，可能所有进程都无法顺利的执行下去；系统处于不安全状态未必就是发生了死锁，但发生死锁时一定是在不安全状态；可以在资源分配前预判这次分配是否会导致系统进入不安全状态以此决定是否答应资源分配请求

     ②银行家算法分配资源原则：当一个进程对资源的最大需求量不超过系统中的资源数时可以接纳该进程；进程可以分期请求资源，但请求的总数不能超过最大需求量；当系统现有的资源不能满足进程尚需资源数时，对进程的请求可以推迟分配，但总能使进程在有限的时间里得到资源

3.2 存储管理

• 动态分区分配

  1. 首次适应算法

     思想：每次都从低地址开始查找，找到第一个能满足大小的空闲分区

     实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链/表，找到大小能满足要求的第一个空闲分区

  2. 最佳适应算法

     思想：动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。为了保证“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区，即优先使用更小的空闲区

     实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链/表，找到大小能满足要求的第一个空闲分区

  3. 最差适应算法

     思想：为解决最佳适应算法留下太多难以利用的小碎片问题，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用

     实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链/表，找到大小能满足要求的第一个空闲分区

  4. 邻近适应算法

     思想：首次适应算法每次都从链头开始查找，可能导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，增加了查找开销。若每次都从上次查找结束位置开始检索，就能解决上述问题

     实现：空闲分区以地址递增的顺序排列（可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链/表，找到大小能满足要求的第一个空闲分区

• 分页存储

  1. 定义：将程序与内存均划分为同样大小的块，以页为单位将程序调入内存

  2. 优点：利用率高，碎片小，分配及管理简单；缺点：增加系统开销，可能产生抖动

  3. 逻辑地址：程序语言使用 = 页号 + 页内地址；物理地址：运行内存使用 = 物理块号/页帧号 + 页内地址

  4. 页表的作用：实现从页号到物理块号的地址映射

  5. 地址变换机构的基本任务：利用页表把用户程序中的逻辑地址变换成内存中的物理地址

  6. 每个页的大小为4KB，逻辑地址：10 1100 1101 1110，对应的物理地址为:110 1100 1101 1110

     

• 分段存储

  1. 定义：按用户作业中的自然段来划分逻辑空间，然后调入内存，段的长度可以不一样

  2. 优点：多道程序共享内存，各段程序修改互不影响；缺点：内存利用率低，内存碎片浪费大

  3. 段表 = 段号 + 段内地址

     

• 段页式存储

  1. 定义：段、页式的综合体，先分段，再分页，1个程序有若干段，每个段中可以有若干页，每个页大小相同，但每个段大小不同

  2. 优点：空间浪费小、存储共享容易、存储保护容易、能动态连接；缺点：由于管理软件的增加，复杂性和开销也随之增加，需要的硬件以及占用的内容也有所增加，使得执行速度大大下降

  3. 段号S + 段内页号P + 页内地址W

     

• 快表：是一块小容量的相联存储器，由高速缓存器组成。速度快，可以从硬件上保证按内容并行查找，一般用来存放当前访问最频繁的少数活动页面的页号

• 页面置换算法

  1. 解决问题：不管使用哪种存储管理，最后内存都会被基本装满，而在后续程序执行过程中，当所需要的数据信息又不在内存时的问题。由操作系统负责将内存中暂时用不到的信息换出到外存，页面置换算法用来决定应该将哪个页面换出内存

  2. 分类

     随机算法 RAND

     时钟置换算法 CLOCK

     先进先出置换算法 FIFO：每次选择淘汰的页面是最早进入内存的页面，可能“抖动”

     最近最少使用置换算法 LRU：每次淘汰的页面是最近最久未使用的页面。可以往前找在内存中的几个页面号，最后一个出现的页号就是要淘汰的页面。不会“抖动”，理论依据是“局部性原理“

     最优/最佳置换算法 OPT：每次选择淘汰的是以后永不使用，或在最长时间内不再被访问的页面，这样可以保证最低的缺页率。按最佳置换的规则往后寻找，最后一个出现的页号就是要淘汰的页面

• 在由高速缓存、主存、硬盘构成的三级存储体系中，CPU执行指令时需要读取数据，DMA控制器、中断CPU发出的数据地址是主存物理地址，程序中用到的是虚拟地址，硬件中访问的通常是物理地址

3.3 文件管理

• 索引分配

  UNIX系统采用直接、一、二、三级间接索引技术访问文件，其索引结点有13 个地址项

  若每个盘块的大小为1KB，每个盘块号占4B，那么，一个盘块可以存放256个盘块号。若进程A访问文件F中第11264字节处的数据，该数据应该放在第11264 / 1024 = 11个（10号）逻辑盘块中，应采用一级间接索引

  

• 文件属性

  R：只读文件属性；A：存档属性；S：系统文件；H：隐藏文件

• 文件名的组成

  1. 驱动器号、路径、主文件名、扩展名

  2. 若系统中一个文件有两个名字，它与一个文件保存有两个副本的区别是：前者改变与某个名字相联系的文件时，另一个名字相连的文件也改变；后者的另一个副本不改变

• 路径

  全文件名：文件的全文件名应包括盘符及从根目录开始的路径名

  绝对路径：从盘符开始的路径

  相对路径：从当前路径开始的路径

• 空闲存储空间管理

  1. 位示图：在外存上建立一张位示图，记录文件存储器使用情况。每一位对应文件存储器上的一个物理块，取值0/1分别表示空闲/占用

  2. 空闲区表：空闲文件目录，将外存空间上一个连续未分配区域称为空闲区。操作系统为外存上所有空闲区建立一张空闲表来管理空闲存储空间

  3. 空闲链表：每个空闲物理块都有指向下一个空闲物理块的指针，所有空闲物理块构成一个链表，链表的头指针放在文件存储器特定位置（如管理块中)

  4. 成组链接法：UNIX系统将空闲块分成若干组，每100个空闲块为一组，每组第一个空闲块登记下一组空闲块的物理盘块号和空闲块总数。若一个组的第一个空闲块号为0，则该组是最后一组，即无下一组空闲块

• 常见目录结构

  1. 一级目录结构：整个目录组织是一个线性结构，整个系统只需建立一张目录表，系统为每个文件分配一个目录项（文件控制块）。结构简单、查找速度慢、不允许重名、不便于文件共享，主要用在单用户环境

  2. 二级目录结构：由主文件目录 MFD、用户目录 UFD 组成。能有效将多个用户隔离，这在各用户间完全无关时是一个优点。但当多用户间要相互合作，且一个用户又需要访问其他用户的文件时，这种隔离便成为一个缺点，使得诸用户间不便于共享文件

  3. 多级目录结构：允许不同用户的文件可以具有相同的文件名

• 打开文件

  在使用已存在的文件前，要通过“打开(Open)”文件操作建立起文件和用户间的联系，目的是把文件的控制管理信息从辅存读到内存。打开文件应完成如下功能

  1. 在内存的管理表中申请一个空表目，用来存放该文件的文件目录信息

  2. 根据文件名在磁盘上查找目录文件，将找到的文件目录信息复制到内存的管理表中。如果打开的是共享文件，则应进行相关处理，如共享用户数加1

  3. 文件定位，卷标处理。文件一旦打开，可被反复使用直至文件关闭。优点是减少查找目录的时间，加快文件存取速度，提高系统的运行效率

3.4 设备管理

• 虚设备与SPOOLING技术

  理解：SPOOLING是关于慢速字符设备如何与计算机主机交换信息的一种技术/假脱机技术，通过磁盘实现

  场景：A，B，C，D共用一台打印机X，要进行资料打印时，很容易出现“打印机正在使用”，如何处理该问题?

  

• 数据传输控制方式：效率越来越高

  CPU与外设之间的数据传送方式。每一个阶段的优点都是解决了上一阶段的最大缺点。整个发展过程就是要尽量减少CPU对I/O过程的干预，把CPU从繁杂的I/O控制事务中解脱出来，以便更多地去完成数据处理任务

  1. 程序控制方式

     ① CPU发出I/O命令后不断轮询，CPU干预频率极高，每次I/O数据传输单位字

     ② 方法简单，硬件开销小；I/O能力不高，严重影响CPU利用率。设备→CPU→内存；内存→CPU→设备

     无条件传送方式：无条件地与CPU交换数据

     程序查询方式：先通过CPU查询外设状态，准备好之后再与CPU交换数据

  2. 程序中断方式

     ① 与程序控制相比，中断方式因CPU无需等待而提高了传输请求的响应速度

     ② CPU发出I/O命令后可以做其他事，本次I/O完成后设备控制器发出中断信号

     ③ CPU干预频率高，每次I/O数据传输单位字；设备→CPU→内存；内存→CPU→设备

     ④ 微型计算机中，管理键盘最适合采用的 I/O 控制方式是中断方式，键盘是慢速设备，无法预知I/O时间

  3. 直接存储器存取方式 DMA

     ① 内存/存储器与I/O设备直接传送数据块的过程中，不需CPU任何干涉，完全由DMA硬件完成I/O操作

     ② CPU发出I/O命令后可以做其他事，本次I/O完成后DMA控制器发出中断信号。在主存与外设间实现高速、批量数据交换，比程序控制、中断方式都高效

     ③ CPU干预频率中，每次I/O的数据传输单位块，设备→内存；内存→设备

     ④ DMA响应过程：DMA控制器对DMA请求判别优先级及屏蔽，向总线裁决逻辑提出总线请求。当CPU执行完当前总线周期即可释放总线控制权。此时总线裁决逻辑输出总线应答，表示DMA已经响应，通过DMA控制器通知I/O接口开始DMA传输。CPU是在（一个总线周期）结束时响应DMA请求；DMA是直接内存存取，传送数据的时间只与内存相关，与CPU的时间无关，采用DMA方式传送数据时，每传送一个数据都需要占用一个存储周期

  4. 通道

     ① CPU发出I/O命令后可以做其他事，通道会执行通道程序以完成I/O，完成后通道向CPU发出中断信号

     ② CPU干预频率极低，每次I/O的数据传输单位一组块。设备→内存；内存→设备

  5. IO处理机

3.5 作业管理

• 作业调度算法：先来先服务法；时间片轮转法；短作业优先法；最高优先权优先法；高响应比优先法

3.6 操作系统

• 作用

  管理系统的硬件、软件、数据资源；控制程序运行；人机之间的接口；应用软件与硬件之间的接口

  计算机硬件/裸机 => 操作系统 => 语言处理程序 => 应用程序

• 特殊的操作系统

  1. 批处理操作系统：

     单道批：一次一个作业入内存，作业由程序、数据、作业说明书组成

     多道批：一次多个作业入内存。多道、宏观上并行，微观上串行

  2. 分时操作系统：采用时间片轮转方式为多个用户提供服务，每个用户感觉独占系统。多路性、独立性、交互性、及时性

  3. 实时操作系统：实时控制系统、实时信息系统

     ① 实时：指计算机对外来信息能以足够快的速度处理，并在被控对象允许的时间范围内做出快速响应

     ② 系统能及时响应外部事件请求，在规定时间内完成对该事件的处理，并控制所有实时任务协调一致运行。交互能力要求不高，可靠性要求高

     ③ 对比分时操作系统

     a. 交互性强弱不同，分时系统交互型强，实时系统交互性弱但可靠性要求高

     b. 对响应时间的敏感性强，对随机发生的外部事件必须在被控制对象规定时间做出及时响应并进行处理

     c. 系统设计目标不同，分时系统是设计成一个多用方的通用系统，交互能力强；实时系统大都是专用系统

  4. 网络操作系统：方便有效共享网络资源，提供服务软件和有关协议的集合，如Unix、Linux、Windows Server

  5. 分布式操作系统：任意两台计算机可以通过通信交换信息。是网络操作系统的更高级形式，具有透明性、可靠性、高性能特性

  6. 微机操作系统：

     Windows：Microsoft 开发的图形用户界面、多任务、多线程操作系统

     Linux：免费使用和自由传播的类 Unix 操作系统，多用户、多任务、多线程、多CPU的操作系统

  7. 嵌入式操作系统：运行在智能芯片环境中，微型化、可定制（针对硬件变化配置)、实时性、可靠性、易移植（HAL、BSP支持)

  8. Windows XP操作系统：支持FAT、FAT32或NTFS文件系统，利用“磁盘管理”程序可以对磁盘进行初始化，创建卷，并可以选择使用FAT、FAT32或NTFS文件系统格式化卷

• 微内核操作系统

  1. 单体内核：

     ① 实质：将图形、设备驱动、文件系统功能全部在内核中实现，运行在内核状态和同一地址空间

     ② 优点：减少进程间通信、状态切换的系统开销，获得较高运行效率

     ③ 缺点：内核庞大，占用资源较多且不易剪裁，系统稳定性、安全性不好

  2. 微内核：

     ① 实质：只实现基本功能，将图形系统、文件系统、设备驱动、通信功能放在内核之外

     ② 优点：内核精练，便于剪裁移植。系统服务程序运行在用户地址空间，系统可靠性、稳定性、安全性较高，可用于分布式系统

     ③ 缺点：用户状态和内核状态需频繁切换，导致系统效率不如单体内核

     

• 嵌入式系统初始化过程

  按自底向上、从硬件到软件的次序依次为：

  1. 片级初始化：完成嵌入式微处理器的初始化，包括设置嵌入式微处理器的核心寄存器和控制寄存器、嵌入式微处理器核心工作模式和嵌入式微处理器的局部总线模式等，片级初始化把嵌入式微处理器从上电时的默认状态逐步设置成系统所要求的工作状态，是一个纯硬件的初始化过程

  2. 板级初始化：完成嵌入式微处理器以外的其他硬件设备的初始化。还需设置某些软件的数据结构和参数，为随后的系统级初始化和应用程序运行建立硬软件环境。是一个同时包含软硬件两部分在内的初始化过程

  3. 系统初始化过程：软件初始化为主，主要进行操作系统的初始化。BSP将对嵌入式微处理器的控制权转交给嵌入式操作系统，由操作系统完成余下的初始化操作，包含加载和初始化与硬件无关的设备驱动程序，建立系统内存区，加载并初始化其他系统软件模块，如网络系统、文件系统等。最后操作系统创建应用程序环境，并将控制权交给应用程序的入口

• UNIX

  1. Shell定义变量$$、$@、$#、$*的含义

     1. $$：当前命令的进程标识数

     2. $#：位置参数的个数，不包括命令名

     3. $*：表示所有位置参量，即相当于$1,$2,$3,…

     4. $@：与$*基本相同，但当用双引号转义时，"$@"还是能分解成多个参数，但"$*"则合并成一个参数

  2. 把输入/输出设备看作是特殊文件。UNIX系统中包括块设备、字符设备。设备特殊文件有一个索引节点，在文件系统目录中占据一个节点，但其索引节点上的文件类型与其他文件不同，是“块”或者是“字符”特殊文件。文件系统与设备驱动程序的接口是通过设备开关表。硬件与驱动程序之间的接口：控制寄存器、I/O指令，一旦出现设备中断，根据中断矢量转去执行相应的中断处理程序，完成所要求的I/O任务。可以通过文件系统与设备接口，对设备进行相关操作，因为每个设备有一个文件名，可以向访问文件那样操作

• Linux

  1. 对文件的访问设定了3级权限：文件所有者、同组用户、其他用户

  2. 对文件的访问设定了3种处理操作：读取、写入、执行

  3. chmod命令：用于改变文件或目录的访问权限。默认情况下，系统将新创建的普通文件的权限设置为-rw-r-r--，将每一个用户所有者录的权限都设置为drwx----。只存文件所有者或超级用户root才有权用chmod改变文件或目录的访问权限

• 常用命令

  1. ping：检查网络是否连通，分析、判定网络故障

  2. nslookup：查询DNS记录生存时间，可指定查询类型、使用哪个DNS服务器解释

  3. ipconfig / ifconfig ：显示TCP/IP网络配置值，IP/MAC/网关地址

  4. tracert/ traceroute：路由跟踪实用程序，确定 IP数据包访问目标所采取的路径，若网络不通，能定位到具体哪个结点不通。使用 IP 生存时间 TTL 字段和 ICMP 错误消息确定从一个主机到网络上其他主机的路由

  5. netstat：监控TCP/IP网络的有用工具，显示网络连接、路由表、网络接口信息、网络接口设备状态信息、网络开放端口对应的应用程序信息，不能用于诊断DNS故障

     netstat命令连接状态包括：

     LISTEN：侦听来自远方的TCP端口的连接请求

     SYN-SENT：在发送连接请求后等待匹配的连接请求

     SYN-RECEIVED：在收到和发送一个连接请求后等待对方对连接请求的确认

     ESTABLISHED：代表一个打开的连接

     FIN-WAIT-1：等待远程TCP连接中断请求，或先前的连接中断请求的确认

     FIN-WAIT-2：从远程TCP等待连接中断请求

     CLOSE-WAIT：等待从本地用户发来的连接中断请求

     CLOSING：等待远程TCP对连接中断的确认

     LAST-ACK：等待原来的发向远程TCP的连接中断请求的确认

     TIME-WAIT：等待足够的时间以确保远程TCP接收到连接中断请求的确认

     CLOSED：没有任何连接状态