返回

OS 复习

不知道放在哪里的内容

有老师说要考当前优先级 请求优先级 程序优先级（cpl rpl dpl），这些优先级是记录在CS（这里指的是CS寄存器代码段寄存器）的最后面两位保存，剩下的涉及到汇编了，想了解的在网上搜吧。

互斥类的指令有哪些，应该值得是进程同步的一些信号量，包括开关中断、交换质量、信号量、signal kill等

semphore信号量：属于信号量机制中的内容，除了使用value标识资源数目以外，还使用一个进程链表指针来链接所有等待进程：

PCB和中断也有一定的关系。PCB能实现间断性运行方式。在多道程序环境下，程序是采用停停走走间断性的运行方式运行的。当进程因阻塞而暂停运行时，它必须保留自己运行时的CPU现场信息。在有了PCB后，系统就可以将CPU现场信息保存在被中断进程的PCB中，供该进程再次被调度执行时恢复CPU现场时使用。由此，可在此明确，在多道程序环境下，作为传统意义上的静态程序，因其并不具有保护或保存自己运行现场的手段，无法保证其运行结果的可再现性，从而失去运行的意义。

因为试卷是fyc出的，据说会考中断：https://www.jianshu.com/p/eac05373f30f。或者可以参考书上P189的内容。

操作系统实验内容（ 5道判断+3道选择+1道大题）

虽然比重很小，但是大致了解一下考试方向：

判断题内容：一道系统功能调用，包括：fork,exec,wait,signal,kill,pipe,exit,dup指令，两道关于shell的内容，两道关于linux的基础指令

选择题内容：getpid,getppid功能，文件链接（win系统下无文件链接https://blog.csdn.net/bitboss/article/details/53940236），文件组成

大题内容：读程序，注意几个要点，fork()的执行。execlp的返回（从PATH 环境变量中查找文件并执行）。exit直接终止进程，注意其返回值。wait()等待子进程结束。输出不是printf而是puts

函数 功能
fork() 创建子进程。系统调用返回值可以是 n=0、n>0、n=-1。其中返还给子进程为0，返回给父进程子进程的标识符，创建失败返回-1
getpid() 获取进程标识
getppid() 获取父进程标识
wait() 等待子进程结束
exec() 执行新程序。execlp()通过获取环境变量并执行，可以看作使用/bin/sh执行
exit() 结束进程，返回0为正常，否则不正常
signal() 接受信号并执行函数
kill() 发送信号给某一个或某一组进程
pipe() 创建一个管道文件，其中file[0]为读入口，[1]为写入口。

-DBCFSl

第一章：操作系统引论

操作系统是⼀组能有效地组织和管理计算机硬件和软件资源，合理地对各类作业进⾏调度，以及⽅便⽤户使⽤的程序的集合。是计算机硬件上的第一层软件。其主要目标是实现：方便性、有效性、可扩充性和开放性。

操作系统的作用

  • 作为用户与计算机硬件系统之间的接口：⽤户通过命令⽅式、系统调⽤⽅式和图标-窗⼝⽅式来实现与操作系统的通信
  • 作为系统资源的管理者。计算机系统的资源通常分为：处理机、存储器、I/O设备及文件
  • 实现了计算机资源的抽象

操作系统发展史

  • 无操作系统

    • 人工操作
    • 脱机操作

  • 单道批处理系统

    其仍然无法充分利用系统资源

  • 多道批处理系统（单道批系统 虽然系统对作业的处理是成批处理的，但在内存中始终只保持⼀道作业）

  • 分时系统（注意：linux是分时系统）

  • 实时系统，分为两类，硬实时和软实时。实时系统不意味着程序必须及时完成，软实时可以超时。

多路性 独立性 及时性 交互性 可靠性
批处理系统 无 无 差 差 一般
分时系统 多终端任务 有 好 好 可靠
实时系统 多路采集、多路控制 有 最好 一般 高度可靠

除上述发展史外，书中还对三种微机操作系统进行了说明，主要分为：单用户单任务操作系统(MS-DOS)、单用户多任务操作系统(Windows)、多用户多任务操作系统(Linux)。

操作性系统的基本特性

基本特征：并发、共享、虚拟、异步

  • 并发

注意并发和并行的区别：前者是多个任务可以在同一时间间隔内运行，后者是多个任务在同一时刻内运行（多处理机时才可能）

进程是指在系统中能独立运行的并作为资源分配的基本单位，由一组机器指令、数据和堆栈等组成

  • 共享

在操作系统中的共享指的是资源共享（资源复用），指系统中的资源可以供内存中多个并发执行的进程共同使用。因而其有两种资源共享方式：

    • 互斥共享方式：同时访问同一资源时必须等待
    • 同时共享方式：允许多个进程同时进行访问

  • 虚拟

这里的虚拟指的是将物理实体变为若干个逻辑上的对应物。OS是通过时分复用和空分复用来实现“虚拟”的。（OS具有并发和共享的特性）。

  • 异步

指程序无法一气呵成，只能走走停停运行。（由于并发的特性）

操作系统的主要功能

OS主要具有处理机管理、存储器管理、设备管理和文件管理等基本功能。

处理机管理功能

处理机的分配和运行都是以进程为基本单位。所以其管理就是进行了进程的控制、通信、同步和调度。

进程控制：进程控制的主要功能就是为作业创建进程、撤销已结束的进程和控制进程在运行中的状态转换。

进程同步：两种方式实现。进程互斥方式和进程同步方式。前者可以通过锁来实现，后者则由信号量机制进行进程同步

进程通信：指进程需要协调完成任务时，需要进行通信息交换。在同一计算机系统上主要通过直接通信方式，即由原进程利用发送命令直接将消息挂到目标进程的消息队列上，以后由目标进程利用接受命令从消息队列中取出消息。

调度：包括作业调度和进程调度

操作系统与用户的接口

貌似说了要考。

  • 命令接口 提供一组命令供用户直接或间接操作。根据作业的方式不同，命令接口又分为联机命令接口和脱机命令接口。
  • 程序接口 程序接口由一组系统调用命令组成，提供一组系统调用命令供用户程序使用。
  • 图形界面接口 通过图标 窗口 菜单 对话框及其他元素,和文字组合,在桌面上形成一个直观易懂 使用方便的计算机操作环境.

剩余的基本功能没有太多涉及到，所以不说了。

OS结构设计

操作系统有多个开发方法。

传统操作系统

由三个阶段：

  • 无结构操作系统
  • 模块化结构
  • 分层式结构

除此之外还有CS模式结构。但我们的重点是微内核结构。

微内核结构OS

其具有一下四个方面的特性：

  • 微内核具有足够小的内核，并非是一个完整的OS，而只是将操作系统中最基本的部分放入微内核。通常包含了：与硬件处理密切相关的部分、一些较基本的功能、客户和服务器之间的通信
  • 基于C/S模式。单机微内核都采用客户/服务器模式。将最基本的放在内核中，把操作系统的绝大部分功能放在微内核外面的一组服务器（进程）中实现。
  • 应用“机制与策略隔离”原理 。将机制放在OS的微内核中
  • 采用了面向对象技术

微内核有以下几部分内容

  • 进程管理
  • 低级存储器管理
  • 中断和陷入处理

微内核也有很多优点

  • 提高了系统的可扩展性
  • 增强了系统的可靠性
  • 可移植性强
  • 提供了对分布式系统的支持
  • 融入了面向对象技术

但是其也存在很大的问题，微内核的效率可能会较低。这是因为客户和服务器、服务器和服务器之间的通信都需要通过微内核，所以同样的服务请求至少需要进行四次上下文切换，从而导致效率低，在这方面效率还不如大内核。（FS核心外、性能差、非主流）

进程

这可是重中之重，建议好好理解。

前驱图和顺序执行没什么好说的。关于并发执行，其具有以下几个特性：间断性、失去封闭性和不可再现性。

进程的描述

进程有多种定义，我们书中将其定义为“进程是进程实体的运行过程，是系统进行资源分配和调度的独立单位”。进程实体由程序段、相关的数据段和PCB三部分构成

进程具有：动态性、并发性、独立性和异步性四个特征。具有三个基本状态：就绪态（只要再获得CPU便可立即执行）、执行态（指已获得CPU，正在执行的状态）、阻塞态（指暂时无法继续执行的状态）图2-8有一处错误，建议自己好好康康。

但是仅有上述的状态还不够，还需要挂起操作，这是基于系统和用户的如下需要：终端用户的需要、父进程请求、符合调节的需要、操作系统的需要。

还要了解进程表（PCB），PCB是进程存在的唯一标识，记录了操作系统所需的，用于描述进程当前情况以及管理进程运行的全部信息，是操作系统中最重要的记录型数据结构。

PCB的作用是是一个在多道程序环境下不能独立运行的程序（含数据）成为一个能独立运行的基本单位，一个能与其他进程并发执行的进程。

PCB中主要包含了四个方面的信息：进程标识符、处理机状态、进程调度信息和进程控制信息

进程控制

涉及到了操作系统的内核（注意已经不是微内核了）。现代操作系统将OS划分成若干层次，再将不同功能分别设置在不同的层次，将一些与硬件相关的模块（如中断处理）、各种常用设备的驱动程序和运行频率较高的模块（如时钟管理、进程调度等）安排在紧靠硬件的软件层。为了防止OS遭到破坏，处理机的状态分为了用户态和系统态。

系统态又称管态和内核态。用户态又称目态。

绝大多数的OS内核都包括了下面两大方面的内容：

  • 支撑功能
    • 中断处理
    • 时钟管理
    • 原语操作内核态（）
  • 资源管理功能
    • 进程管理
    • 存储器管理
    • 设备管理

关于进程的各个状态和其细节，可以自己细看，貌似没说要考。

进程同步

指的是进程共享资源按照一定的规则。有两种形式的制约关系：间接相互制约和直接相互制约，前者是共享系统资源时发生冲突，后者是数据缓冲区共享时发生冲突。

什么是临界资源，在第一章的时候就提到了，进程对于这些资源的调度应该是互斥的。

根据一些例子，我们要知道进程在共享临界资源，进行进程间同步时需要遵循如下规则：空闲让进、忙则等待、有限等待、让权等待。

为了实现进程临界资源的互斥访问，有软件和硬件同步机制，这里主要是硬件同步机制，包括：关中断、Test-and-Set(TS)指令互斥、Swap指令实现进程互斥。然后有人（Dijkstra）提出了信号量机制。（要拿这些东西解决问题的）

整型信号量：wait和signal分别称为P、V操作。注意一下信号和信号量的区别。

由于wait操作会不停的测试，所以不是让权等待，而是忙等，所以有了记录型信号量。

记录型信号量

当资源数量<0时说明分配完毕，所以使用block阻塞，放弃处理机。从而遵循了让权等待。

AND型信号量：解决多个临界资源的共享问题

题目后面再说。

管程机制则是高于信号量机制的一种方案。使用少量的信息和对该资源所执行的操作来标识资源，从而忽略细节和内部结构。但貌似不是重点。

进程通信

拉跨的信号量机制不是很顶，所以还有其他高级的通讯工具，主要归为4类：

  • 共享存储器系统（分为基于共享数据结构和基于共享存储区的通信方式）
  • 管道通信系统（连接一个读和写结成以实现两者之间通信的一个共享文件，又叫pipe文件）
  • 消息传递系统（以格式化的信息为单位传递信息）
  • 客户机-服务器系统（套接字、远程过程调用和远程方法调用）

线程

在完成了进程的处理之后就到了更加轻量的线程部分，要注意区分：

  • 进程：分配资源的最小单位
  • 线程：处理机调度的最小单位

从调度性、并发性、系统开销和拥有系统资源等方面将两者对比：

引入了线程的os，已经将线程作为调度和分派的基本单位。在同一进程中，线程的切换不会引起进程的切换。但是一个进程中的线程切换到另一个进程中的线程时，必然会引起进程的切换。

进程和线程都可以并发。

进程可以拥有资源，且是拥有资源的一个基本单位。但是线程本身不拥有系统资源，而是由能保证独立运行的资源（也就是说线程有资源）

进程间的独立性高于线程间的独立性

线程的系统开销远小于进程

多线程可以加速同一进程。

上述都是两者的对比。线程运行同样有基本状态：执行状态、就绪状态和阻塞状态

同样，线程也有一个TCB，其具有：线程标识符、一些寄存器（程序计数器、状态寄存器和通用寄存器等）、线程运行状态、优先级、专有存储区、信号屏蔽、堆栈指针。

线程的实现

不同系统的线程实现方式不完全相同，主要包括：内核支持线程、用户级线程和组合方式。而组合模式根据连接方式不同也有多对一模型、一对一模型和多对多模型

至于具体的实现还是细看书吧，貌似还是考点

处理机调度与死锁

计算题大多来自这里。

处理机调度的层次和调度算法的目标

处理机调度的层次分为三级：

  • 高级层次：对象为作业，决定将外存尚处于后备队列中的哪几个作业调入内存
  • 中级层次：又称为内存调度，把暂时不能运行的进程调至外存等待，此时进程的状态就是挂起状态。
  • 低级层次：对象为进程（或内核级线程）根据某种算法决定就绪队列中的哪个进程获得处理机。

调度算法的目标很多，共同目标：

  • 资源利用率： $$CPU的利用率=\frac{CPU有效工作时间}{CPU有效工作时间+CPU空闲等待时间}$$
  • 公平性，不会发生进程饥饿现象
  • 平衡性，对于不同类型的进程（计算型、IO型），使得设备都处于忙碌状态，尽可能保持系统资源使用的平衡性。
  • 策略强制执行

接下来的两个很重要：对于批处理系统，其目标还有一个是平均周转时间短，周转时间是指从任务提交到系统开始到完成的时间间隔。$T=\frac{1}{n}[\sum_{i=0}^nT_i]$。除此之外还有另一种反应方式：带权平均周转时间：$W=\frac{1}{n}\sum_{i=1}^n\frac{T_i}{T_s}$其中的$T_s$指系统为他提供服务的时间（也就是需要的时间）。

分时系统的目标为：响应时间快和均衡性

实时系统的目标为：截至时间的保证和可预测性

作业与作业调度

至于具体的算法题目放在最后，这里主要说明作业的概念。作业是一个比程序更加程序更加广泛的概念，不仅包含了程序和数据，还包括一份作业说明书，系统根据该说明书来对程序进行控制。为了管理和调度作业，设置了JCB，其为作业在系统中存在的标志，包含有：作业表示、用户名称、用户账号、作业类型、作业状态、调度信息、资源需求、资源使用情况等。

至于作业的调度算法，有很多：

  • FCFS（最简单）
  • SJF（短作业优先算法，作业越短，优先级越高）
  • PSA（优先级调度算法，基于优先级，类似于SJF，但是优先级又外部赋予，注意，该方法是抢占式的）
  • HRRN（高相应比优先调度算法，为每个任务引入一个动态优先级$优先权=\frac{等待时间+要求服务器时间}{要求服务器时间}=R_P=\frac{响应时间}{要求服务时间}$）

进程调度

进程调度机制主要分为三部分：排队器、分派器、进程调度方式（分为抢占式和非抢占方式（这里的抢占基于一定的原则，优先权原则、短进程优先原则和时间片原则））

那么进程调度的算法如下：

  • RR（时间片轮转法，让就绪队列的每个进程每次仅运行一个时间片）
  • 优先级调度算法（分为静态和动态）
  • 多队列调度算法
  • 多级反馈队列调度算法

实时调度不考，所以还能接受

死锁

死锁的主要原因是存在需要采用互斥访问方法的、不可被抢占的资源，即临界资源。也可以分为两种，可重用性资源消耗性资源以及可抢占性资源和不可抢占性资源。

计算机系统的死锁起因于资源的争夺，对不可抢占资源争夺会引起死锁，对可消耗资源进行争夺也会引起死锁，除此之外，进程推进顺序不当也会引起死锁。

死锁的定义：如果一组进程中的每一个进程都在等待仅由改组进程中的其它进程才能引发的事件，那么该组进程是死锁的。产生死锁的有四个必要条件：

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

死锁的处理方法有四种：

  • 预防死锁
  • 避免死锁
  • 检测死锁
  • 解除死锁

预防死锁不是重点，避免才是，这里就不得不说到银行家算法了。画表，具体的方法见下面的大题。

死锁的检测和解除，检测通过寻找安全序列进行。根据死锁定理：S为死锁状态的充分条件是：当且仅当S状态的资源分配图式不可完全简化的。

这里就无了。

简答题

用户态和内核态

库函数和系统调用区别

特权指令

进程通信

看书吧，书上都有

中断和异常

这个甚至是面试题

一些需要掌握的题目

进程同步

生产者消费者

哲学家吃饭问题

读者写者问题

汽车通行问题

image-20211123001738581
image-20211123001738581

image-20211123001746265
image-20211123001746265

image-20211123001754584
image-20211123001754584

人过桥问题

和汽车通行问题一样。

请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。

解答： 信号量brigde表示独木桥互斥访问，初值为1；变量eastcount和westcount分别表示从东西方上独木桥的行人数量，初值为0，信号量eastmutex和westmutex是对变量eastcount和westcount数据读写的保护，初值为1。

东方：
while（true）{
	P(eastMutex);
	if(eastCount == 0) 
		P(brigde);
	V(eastMutex);
	上桥
	下桥
	P(eastMutex);
		eastCount--;
	if(eastCount == 0) 
		V(brigde);
	V(eastMutex);
}

西方：
while（true）{
	P(westMutex);
	if(westCount == 0)  
		P(brigde);
	V(westMutex);
	上桥
	下桥
	P(westMutex);
		westCount--;
	if(westCount == 0)				
        V(bridge);
	V(westMutex);
}

学生老师上下课问题

《操作系统》课程的期末考试即将举行，假设把学生和监考老师都看作进程，学生有N人，教师1人。考场门口每次只能进出一个人，进考场的原则是先来先进。当N个学生都进入了考场后，教师才能发卷子。学生交卷后即可离开考场，而教师要等收上来全部卷子并封装卷子后才能离开考场。

(1)问共需设置几个进程?

(2)请用P、V操作解决上述问题中的同步和互斥关系

semaphore S_Door;         // 能否进出门，初值1
semaphore  S_StudentReady; // 学生是否到齐，初值为0
semaphore  S_ExamBegin;   // 开始考试，初值为0
semaphore  S_ExamOver;    // 考试结束，初值为0
int nStudentNum = 0;       // 学生数目
semaphore  S_Mutex1;       //互斥信号量，初值为1
int  nPaperNum = 0;       // 已交的卷子数目
semaphore  S_Mutex2;       //互斥信号量，初值为1

void  student( )
{

    P(S_Door);
    进门;
    V(S_Door);
    P(S_Mutex1)；
    nStudentNum ++;   // 增加学生的个数
    if(nStudentNum == N)  V(S_StudentReady);
    V(S_Mutex1);
    P(S_ExamBegin);  // 等老师宣布考试开始
    考试中…
    交卷;
    P(S_Mutex2);
    PaperNum ++;    // 增加试卷的份数
    if(nPaperNum == N) 
    V(S_ExamOver);
    V(S_Mutex2);
    P(S_Door);
    出门;
    V(S_Door);
}
void  teacher( )
{
    P(S_Door);
    进门;
    V(S_Door);
    P(S_StudentReady);    //等待最后一个学生来唤醒
    发卷子;
    for(i = 1; i <= N; i++)   
    V(S_ExamBegin);
    P(S_ExamOver);    //等待考试结束
    封装试卷;
    P(S_Door);
    出门;
    V(S_Door);
}

一家人吃水果问题

mutex = 1; 盆子剩下空间 = N 苹果数 = 0 梨子数 = 0

父亲: 盆子有空就放苹果.满了就不放了. 母亲: 盆子有空就放梨子.满了就不放了. 女儿: 盆子有苹果就吃, 没有就等 儿子: 盆子有梨子就吃, 没有就等

父亲: p(盆子剩下空间) p(mutex) ………. v(mutex) v(苹果数) 母亲: p(盆子剩下空间) p(mutex) ………. v(mutex) v(梨子数) 女儿: p(苹果数) p(mutex) ………. v(mutex) v(盆子剩下空间) 儿子: p(梨子数) p(mutex) ………. v(mutex) v(盆子剩下空间)

过红绿灯问题

没找到类似的题，自己理解吧。

同步问题

image-20211123002301881
image-20211123002301881

image-20211123002320682
image-20211123002320682

生产消费Plus

image-20211123002340343
image-20211123002340343

image-20211123002350529
image-20211123002350529

调度问题

例题

综合性课后题

银行家算法

例题

综合性课后题

Licensed under CC BY-NC-SA 4.0