概述

执行一个程序前,需要先将程序放入内存。

单核CPU在同一时刻,只能执行一个程序,因此各个程序只能并发地执行。

系统调用,也称广义指令,是应用程序请求操作系统服务的唯一方式。

中断是让操作系统重新夺回CPU的唯一方式。

CPU中有程序状态字寄存器,有个二进制位,“1”表示内核态,“0”表示用户态。

在CPU设计和生产的时候,就已经划分了特权指令和非特权指令。

内核态 -> 用户态:执行一条特权指令,修改PSW的状态为用户态。

用户态 -> 内核态:由中断引起,硬件自动完成。

若当前执行的指令是非法的,就会引发一个中断信号。

假如没有中断机制,那么一旦应用程序上CPU,就会一直运行。

内中断和外中断的区分,依据其是否与当前执行的指令有关。内中断与当前执行的指令有关,也称异常、例外,信号的来源为CPU内部。

异常:(陷入)由陷入指令引发,是应用程序故意引发的,例如请求系统调用;(故障)由错误条件引起,可能被内核程序修复,其修复后会把CPU使用权还给应用程序,让其继续执行;(终止)由致命错误引起,内核程序无法修复该错误,因此一般不再将CPU使用权还给引发终止的应用程序,而是直接终止它。

中断处理程序一定是内核程序,需要运行在“内核态”。

内核态下即可执行特权指令,也可执行非特权指令。

凡是与共享资源有关的操作,都必须通过系统调用的方式向操作系统内核提出服务请求,由操作系统内核代为完成。这样可以保证系统的稳定性和安全性。

系统调用的过程:传递系统调用参数 -> 执行陷入指令(用户态) -> 执行相应的内请求核程序处理系统调用(核心态) -> 返回应用程序

错题整理

操作系统主要向用户提供命令接口和程序接口(程序接口也称系统调用),此处还提供图形接口;当然,图形接口其实是调用了系统调用而实现的功能。

系统调用是操作系统为应用程序使用内核功能所提供的接口,并不是命令接口中的命令。

程序接口、图形接口和命令接口三者之间并没有从属关系。按命令控制方式不同,命令接口分为联机用户接口和脱机用户接口。

脱机技术用于解决独占设备的问题。虚拟技术和交换技术以多道程序设计技术为前提。多道程序设计技术由于同时在主存中运行多个程序,让一个程序等待时,可以去执行其他程序,因此提高了系统资源的利用率。

引入多道程序以后,程序的执行就失去了封闭性和和顺序性。程序执行因为共享资源和相互协同的原因产生了竞争,相互制约。考虑到竞争的公平性,程序的执行是断续的。

多道程序设计技术允许同时把多个程序放入内存,并允许它们交替在CPU中运行,它们共享系统中的各种软/硬件资源,当一道程序因I/O请求而暂停运行时,CPU便立即转去运行另一道程序,即多道批处理系统的I/O设备可与CPU并行工作,这都是借助于中断技术实现的。

中断指来自CPU执行指令以外的事件的发生,如设备发出I/O请求结束中断,表示设备输入/输出处理已经完成,希望处理机能够向设备发下一个输入/输出请求,同时让完成输入/输出后的程序继续运行。

中断是让操作系统内核重新夺回CPU的唯一途径。

广义指令就是系统调用命令。

系统中的缓存全部由操作系统管理,对用户是透明的,操作系统不提供管理系统缓存的系统调用。

实时系统普遍用高优先级,并用“可抢占”来确保实时处理。

分时系统的响应时间T的比例关系可表达为 T 近似等于 Q * N ,其中 Q 是时间片,而 N 是用户数。

只要能支持多个进程并发运行,即可称为多任务操作系统。多任务操作系统具有并行的特点,原因在于CPU和I/O设备可以同时运行。

CPU和I/O可以同时运行的解释

CPU 计算文件地址 -> 委派 DMA 读取文件 -> DMA 接管总线 -> CPU 的 A 进程阻塞挂起 -> CPU 切换到 B 进程 -> DMA 读取文件后通知 CPU(一个中断异常) -> CPU 切换回 A 进程 操作文件

批处理的主要缺点是缺少交互性,此为常考点,读者对此应当非常敏感。

输入/输出指令需要中断操作,中断必须在核心态下执行。

多道性是为了提高系统利用率和吞吐量而提出的。

I/O通道实际上是一种特殊的处理器,它具有执行I/O指令的能力,并通过执行通道程序来控制I/O操纵。因此,通道技术是一种硬件技术。

中断系统和地址映射显然都需要硬件的支持,因为中断指令和地址映射中的重定位都是离不开硬件支持的。

时钟管理中的重置时钟等是由硬件直接完成的。

进程调度由调度算法决定CPU使用权,由操作系统实现,无须硬件支持。

计算机通过硬件完成操作系统由用户态到核心态的转换,这是通过中断机制来实现的,发生中断事件时(有可能是用户程序发出的系统调用),触发中断,硬件中断机制将计算机状态置为核心态。因此可以说,计算机通过硬件(中断机制)完成由用户态到核心态的转换。

进程切换属于系统调用执行过程中的事件,只能发生在核心态。

缺页产生后,在用户态发生缺页中断,然后进入核心态执行缺页中断服务程序。

若在用户态下执行置时钟指令,则一个用户进程可在时间片还未到之前把时钟改回去,从而导致时间片永远也用不完,进而导致用户进程一直占用CPU。

输入/输出指令涉及中断操作,而中断处理是由系统内核负责的,工作在核心态。

操作系统是管理内存的,管理的是内存中的数据放在哪里、哪里可以放数据、哪里不可以放数据、哪里空闲等问题,而内存中的数据是什么、怎么读和写,都不是核心态关心的。

程序的非法操作码、地址越界、算术溢出、虚存系统的缺页及专门的陷入指令引起的事件,都属于异常。

外部中断处理过程,PC 值由中断隐指令自动保存,而通用寄存器内容由操作系统保存。

缺页中断指的是当前软件试图访问已映射在虚拟地址空间中,但是目前并没有被加载在物理内存中的一个分页时,由中央处理器的内存管理单元发出的中断。

传递系统调用参数 -> 执行陷入指令 -> 执行相应的服务程序 -> 返回用户态

设备管理属于操作系统的职能之一,包括对输入/输出的分配、初始化、维护等,用户程序需要通过系统调用使用操作系统的设备管理服务。

操作系统不同,底层逻辑、实现方式均不同,为应用程序提供的系统调用接口也不同。

一般来说内核的服务越少,内核越稳定。

防止死锁和避免死锁是两种方法。

操作系统是虚拟机。

外部中断是由外部事件引起的中断,比如单击鼠标和键盘输入等操作引起的中断。

目态即用户态。

操作系统的主要功能包括处理器管理、存储管理、文件管理和设备管理。数据管理属于文件管理的范畴。网络管理不是操作系统的功能。

并行执行和并发执行不存在包含关系。

进程管理

进程是程序的一次执行过程。

程序的运行过程

同时挂3个QQ号,会对应3个QQ进程,它们的PCB和数据段各不相同,但程序段的内容都是相同的(都是运行着相同的QQ程序)。

动态性是进程最基本的特征。

PCB 是进程存在的唯一标志。

进程是系统进行资源分配和调度的一个独立单位。

CPU 每执行完一条指令都会例行检查是否由中断信号需要处理,如果有,则暂停运行当前这段程序,转而执行相应的中断处理程序。

在进程切换时先在 PCB 中保存这个进程的运行环境(保存一些必要的寄存器信息)。

管道通信:写满时,不能再写。读空时,不能再读。没写满,不能读。没读空,不能写。

高级调度中,每个作业只调入一次,调出一次。

七状态模型

进程调度与状态模型之间的对应关系

进程在操作系统内核临界区中不能进行调度与切换。但是在非内核的临界区中是可以的。普通临界区访问的临界资源不会直接影响操作系统内核的管理工作。(临界区:访问临界资源的那段代码)

关于等待时间

对于既有计算又有 I/O 操作的进程,其等待时间就是周转时间(完成时间 - 到达时间) - 运行时间 - I/O 操作时间。

在所有进程都几乎同时到达时,采用短进程调度算法的平均等待时间、平均周转时间最少。

实现临界区互斥的基本方法

单标志法

基本思想:两个进程在访问临界区后会把使用临界区的权限转交给另一个进程。也就是说,每个进程进入临界区的权限只能被另一个进程赋予。

双标志先检查法

双标志后检查法

当等待时间给进程推进和响应带来明显影响时,称发生了进程“饥饿”,当“饥饿”到一定程度的进程所赋予的任务即使完成也不再具有实际意义时,称该进程被“饿死”。

进程是系统资源的使用者,系统的资源大部分都是以进程为单位分配的。而用户使用计算机是为了实现一串相关的任务,通常把用户要求计算机完成的这一串任务称为作业。

错题整理

在单处理器系统中,任何时刻都只有一个进程处于运行态。错误的原因:系统发生死锁时有可能进程全部都处于阻塞态,或无进程任务。

一个进程由阻塞态转变为就绪态就不会引起其他进程的状态变化。

在单处理器系统中,不可能所有进程都处于就绪态。

进程封闭性是指进程执行的结果只取决于进程本身,不受外界影响。

假如有一个内核线程,它映射到用户级后有多个线程,那么这些线程的切换不需要在内核级切换线程,也就不需要内核的支持。

在多对一的多线程模型中,一个线程在使用内核服务时被阻塞,整个进程都会被阻塞。内核级线程运行在内核态,由操作系统负责线程管理。内核级线程是处理机分配的单位。

从运行态转变为阻塞态是主动行为,而从阻塞态变成就绪态是被动行为。

C语言编写的程序在使用内存时一般分为三个段,它们一般是正文段(即代码和赋值数据段)、数据堆段和数据栈段。二进制代码和常量存放在正文段,动态分配的存储区在数据堆段,临时使用的变量在数据栈段。

同一个系统的进程或者线程可以由系统调用的方法被不同的进程或者线程多次使用。

对进程的管理和控制功能是通过执行各种原语来实现的。

信号量机制是一种功能较强的机制,可用来解决互斥与同步问题,它只能被两个标准的原语访问。

设备分配是通过在系统中设置相应的数据结构来实现的,不需要创建进程。

用户级线程由应用程序完成线程的管理,内核级线程由内核完成线程管理。

两个合作进程可以利用文件系统(比如管道)来交换数据。

处理机空闲或者就绪队列非空时,一定会导致进程的切换或者调度。而当进程的时间片用完后,若不降低其优先级,很可能它会很快继续上处理机运行。

当一个进程被唤醒时,这个进程就进入来就绪态,等待进程调度而占有CPU运行。进程唤醒即从阻塞态转变到就绪态。

当管道满是,进程在写管道时会被阻塞,而当管道空时,进程在读管道时会被阻塞。

操作系统为每个内核级线程建立一个线程控制块(TCB)。

用户级线程的切换比内核级线程的切换的效率要高。

用户级线程可以在不支持内核级线程的操作系统上实现。

所谓CPU繁忙型作业,是指该类作业需要大量的CPU进行计算,而很少请求I/O操作。

一般来说,I/O型作业的优先权要计算型作业的优先权,这是由于I/O操作需要及时完成,它没办法长时间保存所要输入/输出的数据。

时间片轮转调度算法是绝对可抢占的。

关于在进程结束时、创建新进程后、系统调用完成返回用户态时能进行处理机调度和进程处于临界区时不能进行处理机调度的解释

进程之间地址空间独立,全局变量也就只有在同一个进程内的线程之间可以共享。

内存管理

内部碎片:已经被分配出去,明确指出属于哪个进程,却不能被利用的内存空间。

外部碎片:还没有被分配出去,此时尚不属于任何进程,但由于太小而难以利用。

分页存储管理的基本思想

把主存空间划分为大小相等且固定的块,块相对较小,作为主存的基本单位。每个进程也以块为单位进行划分,进程在执行时,以块为单位逐个申请内存中的块空间。

页表记录页面(进程中的块)在内存中对应的物理块号。

局部性原理

(1)时间局部性:程序中的某条指令一旦执行,不久后该指令可能再次执行;某数据结构被访问过,不久后该数据结构可能再次被访问。产生时间局部性的典型原因是程序中存在大量的循环操作。

(2)空间局部性:一旦程序访问了某个存储单元,在不久后,其附近的存储单元也将被访问,即程序在一段时间内所访问的地址,可能集中在一定的范围之内,因为指令通常是顺序存放、顺序执行的,数据也一般是以向量、数组、表等形式簇聚存储的。

I/O管理

块设备:可寻址

字符设备:不可寻址,常采用中断驱动方式

I/O逻辑负责接收和识别CPU的各种命令,并负责对设备发出命令。

两种寄存器的编址方式

内存映射I/O:控制器中的寄存器与内存统一编址;可以采用对内存进行操作的指令来对控制器进行操作。

寄存器独立编址:控制器中的寄存器独立编址;需要设置专门的指令来操作控制器。

I/O控制方式


一轮复习


处理机调度是多道程序操作系统的基础,是操作系统设计的核心问题。

作业调度的主要任务是按一定的原则从外存上处于后备状态的作业中挑选一个(或多个)作业,给它(们)分配内存、输入/输出设备等必要的资源,并建立相应的进程,使它(们)获得竞争处理机的权利。

内存调度是将暂时不能运行的进程调至外存等待,把此时的进程状态称为挂起态。

进程调度的主要任务是按照某种方法和策略从就绪队列中选取一个进程,将处理机分配给它。

IO设备可以和CPU并行工作。

挂起和阻塞都是暂时不能获得CPU的服务,但是挂起态是将进程映像调到外存中去,而阻塞态下,进程映像还在内存中。

操作系统具有异步性。

将一次仅允许一个进程使用的资源称为临界资源。访问临界资源的那段代码称为临界区。

进程间的直接制约关系源于它们之间的相互合作。

互斥也称间接制约关系。

有限等待:对请求访问的进程,应保证能在有限时间内进入临界区。 让权等待:当进程不能进入临界区时,应立即释放处理器,防止进程忙等待。

在进入区设置并检查一些标志来标明是否有进程在临界区中,若已有进程在临界区,则在进入区通过循环检查进行等待。

单标志算法设置一个公用整型变量,用于指示被允许进入临界区的进程编号。

双标志先检查算法的问题出在检查和修改操作不能一次进行。

所有的解决方案都无法实现让权等待。

CPU只在发生中断时引起进程切换,因此屏蔽中断能够保证当前运行的进程让临界区代码顺利地执行完。

信号量机制只能被两个标准的原语(P、V操作)访问。

在互斥问题中,P,V 操作要紧夹使用互斥资源的那个行为,中间不能有其他冗余代码。

管程:代表共享资源的数据结构,以及由对该共享数据结构实施操作的一组过程所组成的资源管理程序。

每次仅允许一个进程进入管程,从而实现进程互斥。

只有初始化和PV操作才能改变信号量的值。通常,信号量分为互斥量和资源量,互斥量的初值一般为1,表示临界区只允许一个进程进入,从而实现互斥。互斥量的绝对值表示在临界区外等待进入的进程数。资源量的绝对值表示等待的进程数。当信号量 K < 0 时,表示有 |k| 个进程在等待该资源。

进程进入临界区必须满足互斥条件,当进程进入临界区但尚未离开时就被迫进入阻塞是可以的,系统中经常出现这样的情形。在此状态下,只要其它进程在运行过程中不寻求进入该进程的临界区,就应允许其运行,即分配CPU。该进程所锁定的临界区是不允许其它进程访问的,其它进程若要访问,必定会在临界区的“锁”上阻塞,期待该进程下次运行时可以离开并将临界区交给它。

公用队列可供多个进程使用,但一次只可供一个进程使用,试想若多个进程同时使用公共队列,势必会造成队列中的数据混乱而无法使用。

并发进程是异步的。

共享程序段可能同时被多个进程使用,所以必须可重入编码,否则无法实现共享的功能。

管程中的signal操作是针对某个条件变量的,若不存在因该条件而阻塞的进程,则signal不会产生任何影响。信号量机制中的V操作一定会改变信号量的值。

PV操作是一种低级的进程通信原语,不是系统调用。

CPU 在执行指令的过程中,就是在处理内存或者寄存器中的一些数据。那么如何找到和处理这些数据呢,就是基于“地址”。

暂时换出外存等待的进程状态为挂起态。

覆盖是在同一个程序或进程中的。交换是在不同进程(或作业)之间的。

Peterson算法的伪代码


// 进程 P0
void P0()
{
  while(true)
  {
    flag[0] = true;
    turn = 1;
    while(flag[1] && (turn == 1));
    临界区;
    flag[0] = false;
  }
}

// 进程 P1
void P1()
{
  while(true)
  {
    flag[1] = true;
    turn = 0;
    while(flag[0] && (turn = 0));
    临界区;
    flag[1] = false;
  }
}

两个不同的进程,并不共享内存空,其内的变量对应的存储单元也就不相同。

动态分区分配就是增加了内存移动的功能。由于若干次内存分配与回收之后,各个空闲的内存块不连续了。通过“重定位”将已经分配的内存“紧凑”在一块,从而空出一大块空闲的内存。“紧凑”是需要开销的,比如需要重新计算地址。

虽然进程的各个页面是离散存放的,但是页面内部是连续存放的。

如果要访问逻辑地址 A,则

(1)确定逻辑地址A对应的“页号” P

(2)找到P号页面在内存中的起始地址(需要查页表)

(3)确定逻辑地址A的“页内偏移量” W

逻辑地址 A 对应的物理地址 = P 号页面在内存中的起始地址 + 页内偏移量 W

将内存空间分为一个个大小相等的分区(比如每个分区4KB),每个分区就是一个“页框”(页框=页帧=内存块=物理块=物理页面)。每个叶框有一个编号,即“页框号”,页框号从0开始。

将进程的逻辑地址空间也分为与页框大小相等的一个个部分,每个部分称为一个“页”或“页面”。每个页面也有一个编号,即“页号”,页号也是从0开始。

一个进程对应着一张页表;进程的每一个页面对应着一个页表项;每个页表项由“页号”和“块号”组成;页表记录进程页面和实际存放的内存块之间的映射关系。

虽然进程的各个页面是离散存放的,但是页面内部是连续存放的。

页表长度指的是这个页表总共有几个页表项,即总共有几个页;页表项长度指的是每个页表项占多大的存储空间;页面大小指的是一个页面占多大的存储空间。

页面不是按照逻辑模块划分的,这就很难实现共享。

分页管理的内存空间利用率较高,不会产生外部碎片,只会有少量的页内碎片。分段管理中,如果段长过大,为其分配的连续空间会很不方便。段式管理会产生外部碎片。

段号的位数决定了每个进程最多可以分为几个段;页号的位数决定了每个段最大有多少页;页内偏移量决定了页面的大小、内存块大小是多少。

与进程管理一样,为实现目录管理,操作系统引入了文件控制块的数据结构。

树形目录结构可以很方便地对文件进行分类,层次结构清晰,也能够更有效地进行文件的管理和保护。但是,树形结构不便于实现文件的共享。

共享文件不同于复制文件,在共享文件中,各用户指向的是同一个文件。

读取某个磁盘块时,需要移动磁头。访问的两个磁盘块相隔越远,移动磁头所需实际就越长。因此,连续分配的文件在顺序读/写时的速度最快。

索引分配允许文件离散地分配在各个磁盘中,系统会为每个文件建立一份索引表,索引表记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表–建立逻辑页面到物理页面之间的映射关系)。

在显示链接的链式分配中,文件分配表FAT是一张磁盘对应一张。而索引分配方式中,索引表是一个文件对应一张 😴