操作系统1复习

SHUSHU OS1复习笔记 有整合前人笔记

第一章 操作系统引论

操作系统是一组能有效地组织和管理计算机硬件和软件资源，
合理地对各类任务进行调度，以及方便用户使用的程序的集合

操作系统的目标和作用

操作系统的目标

  • 方便性 （脱离硬件运行程序）
  • 有效性 （提高资源利用率）
  • 可扩充性 （模块化结构->层次化结构->微内核结构）
  • 开放性 （遵循开放系统互连OSI国际标准）
    其中，方便性和有效性是设计OS的最重要两个目标

操作系统的作用

用户接口

  • 用户和计算机硬件之间的接口
    • 三种接口：（书p2）
      1. 系统调用 （应用程序使用、用户间接使用）
      2. 命令 （用户直接使用）
        • 联机命令接口（交互式，说一句做一句；键盘操作命令+解释程序）
        • 脱机命令接口（批处理文件；作业控制语言JCL写作业控制说明书）
      3. 图标-窗口（图形用户接口） （用户直接使用）
  • 计算机系统资源的管理者
    • 对四种资源的管理：处理机、存储器、IO设备、文件
  • OS实现对计算机资源的抽象
    • OS将计算机的硬件操作进行了多个层次的抽象，抽象层次越高，OS接口实现的功能就越强

如何理解抽象：

  • 裸机+IO操作软件=扩充机器/虚拟机 IO设备管理软件实现对计算机硬件操作的第一层抽象
  • 为方便用户使用文件系统，使用文件管理软件再对上述机器进行抽象
  • 以此类推，还可以覆盖一面向用户的窗口软件
    只要是覆盖了软件的机器就可以被称作扩充机器或者虚拟机

操作系统的发展过程

  1. 人工操作方式：用户独占全机，CPU等待人工操作。
  2. 脱机输入输出方式：事先将装有用户程序和数据的纸带装入纸带输入机，在外围机的控制下，把纸带上的数据输入到磁带上（类似于磁盘）。当CPU需要时，从磁带将其高速地调入内存。反之类同。优点：减少了CPU的空闲时间，提高了I/O速度。
  3. 单道批处理系统：首先监督程序将磁带第一个作业装入内存，运行控制权在该作业，该作业处理完成时，控制权交回到监督程序，再由监督程序把磁带上的第二个作业调入内存。系统自动对作业成批处理。（内存始终只保持一道作业单道批处理）。
    缺点：
    • 内存浪费，不能充分利用系统资源。
    • CPU等IO的情况，CPU利用率低。
    • 如果有多个IO设备，也会存在IO设备的浪费。
  4. 多道批处理系统：用户所提交的作业先存放在外存，排成一个“后备队列”，再由作业调度程序按一定的算法从队列选择若干作业调入内存，使他们共享CPU和系统中的各种资源。多道程序可以交替运行。
    优缺点：资源利用率提高，系统吞吐量大，平均周转时间长，无交互能力。
  5. 分时系统：在一台主机上连接了多个带有显示器和键盘的终端，同时允许多个用户通过自己的终端，以交互方式使用计算机，共享主机中的资源。因此，作业直接进入内存，采用轮转运行方式，系统配置一个多路卡（实现分时多路复用），及时接收用户终端命令（数据）。
    • 以时间片轮流服务用户，但是不能处理紧急任务。
    • 特征：多路性、独立性、及时性、交互性。
  6. 实时系统：系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务的协调一致的运行。
    • 分为硬实时和软实时
      • 硬实时任务：系统必须满足任务对截止时间的要求，否则可能会出现难以预料的后果
      • 软实时任务：偶尔错过截止时间，对系统的影响不会太大
    • 特征：多路性（周期性信息采集，多个对象或执行机构进行控制）、独立性、及时性、交互性、可靠性（多级容错措施）。
  7. 微机操作系统：配置在微型机上的操作系统

操作系统的基本特性

并发性、共享性、虚拟性、异步性

并发

并行性和并发性

并行性：两个或多个事件在同一时刻发生

并发性：两个或多个事件在同一时间间隔内发生(宏观上同时发生)

引入进程：提高了系统资源的利用率和系统吞吐量，并改善了系统的性能。
进程是系统中能独立运行并作为资源分配的基本单位，由一组机器指令、数据和堆栈等组成，是一个能够独立运行的活动实体。

共享

资源共享=资源复用

互斥共享：在一段时间内只允许一个进程访问的资源称为临界资源或独占资源。

同时访问：允许在一段时间内由多个进程同时对它们进行访问。（同时是宏观上的，微观上访问还是交替进行的）

虚拟

通过某种技术把一个物理实体变为若干个逻辑上的对应物

时分复用技术：

  • 虚拟处理机技术：利用处理机的空闲时间运行其他程序，提高处理机的利用率。
  • 虚拟设备技术：

空分复用技术：利用存储器的空闲空间存放其他程序，提高内存的利用率。

异步

并发性会导致异步，由于资源等限制，程序会以“停停走走”的方式运行，同时，程序会以不可预知的速度向前推进。

操作系统的主要功能

处理机管理功能

处理机的分配和运行都以进程为基本单位，因此对处理机的管理就可以归结为对进程的管理。

  1. 进程控制
    为作业创建进程、撤销进程、为进程创建线程，分配资源、资源回收，控制进程运行过程中的状态转换。

  2. 进程同步
    为多个进程（或线程）的运行进行协调，常见的协调方式有：

  • 进程互斥（设置锁）
  • 进程同步（信号量机制）。
  1. 进程通信
    实现相互合作之间的进程之间的信息交换
  2. 调度
    作业调度

进程调度

存储器管理功能

存储器管理的主要任务：为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率，并能从逻辑上扩充内存。

功能：

  1. 内存分配：静态分配、动态分配。
  2. 内存保护：确保每道用户程序都只在自己的内存空间内运行，彼此互不干扰。一种比较简单的内存保护机制是设置两个界限寄存器。
  3. 地址映射：将地址空间中的逻辑地址转换为内存空间中与之对应的物理地址。
  4. 内存扩充：借助于虚拟存储技术，逻辑上扩充内存容量。

设备管理功能

设备管理的主要任务：完成用户进程提出的I/O请求，为其分配所需的I/O设备；提高CPU和I/O设备的利用率，提高I/O速度，方便用户使用I/O设备。

功能：

  1. 缓存管理：缓和CPU和I/O设备速度不匹配的矛盾。
  2. 设备分配：根据用户进程I/O请求、系统现有资源情况以及按照某种设备的分配策略，为之分配其所需的设备。
  3. 设备处理：用于实现CPU和设备控制器之间的通信。

文件管理功能

文件管理的主要任务：对用户文件和系统文件进行管理，方便用户使用，并保证文件的安全性。

功能：

  1. 文件存储空间的管理：为每个文件分配必要的外存空间，提高外存的利用率，并能有助于提高文件系统的存、取速度。
  2. 目录管理：为每个文件建立其目录项，并对众多的目录项加以有效的组织，以实现方便的按名存取，即用户只须提供文件名便可对该文件进行存取。
  3. 文件的读/写管理和保护

操作系统和用户之间的接口

接口部分在操作系统的作用中有讲过

用户接口

  • 联机用户接口
  • 脱机用户接口
  • 图形用户接口
    程序接口
    如果一个进程在用户态需要使用内核态的功能，就进行系统调用从而陷入内核，由操作系统代为完成。

应用程序->库函数（封装系统调用）/直接调用系统调用->传递系统调用函数->执行陷入指令（此时处于用户态）->执行相应系统调用（核心态）->返回应用程序

系统调用

  • 把应用程序的请求传送至内核，调用相应的内核函数完成所需的处理，将处理结果返回给应用程序
  • 系统调用的作用
    • 内核可以基于权限和规则对资源访问进行裁决，保证系统安全性
    • 对资源进行抽象，提供一致性接口，避免用户在使用资源时发生错误，使编程效率提高

系统调用是应用程序获得操作系统服务的唯一途径
内核的主体是系统调用的集合，内核可以看成是特殊的公共子程序

  • 系统调用的参数传递：
    • 由访管指令或陷入指令自带参数（直接参数/间接参数）
    • 通过CPU通用寄存器传递参数，或在主存的一个块或表中存放参数，将其首地址送入寄存器，实现参数传递
    • 在主存中开辟专用堆栈区传递参数
      Linux 的系统调用主要有以下这些：

进程控制 fork(); exit(); wait();

进程通信 pipe(); shmget(); mmap();

文件操作 open(); read(); write(); 设备操作 ioctl(); read(); write();

信息维护 getpid(); alarm(); sleep();

安全 chmod(); umask(); chown()。

操作系统结构设计

传统的操作系统结构

无结构操作系统 --> 模块化结构OS --> 分层式结构OS

  • 模块化：内核=主模块（只负责核心功能）+可加载内核模块（驱动程序等）
    • 优点：便于维护、动态加载新模块、任何模块可以直接调用其他模块
    • 缺点：模块间接口未必合理，模块之间相互依赖，难以调试
  • 分层：每层只能单向调用更低（相邻的）一层的接口
    • 优点：便于调试验证、易于维护
    • 缺点：只能调用相邻层，不能合理定义边界、效率低，不能跨层调用

内核、宏内核与微内核

内核

内核的定义：内核是一组程序模块，作为可信软件来提供支持进程并发执行的基本功能和基本操作，通常驻留在内核空间，运行于核心态，具有访问硬件设备和所有主存空间的权限，是仅有的能执行特权指令的程序

目的：

  1. 便于对软件进行保护，防止遭受其它应用程序的破坏
  2. 提高OS的运行效率

大内核（宏内核）

大内核是将操作系统功能作为一个紧密结合的整体放到内核。 由于各模块共享信息，因此有很高的性能。

  • 优点：性能高，内核内部各种功能可以互相调用
  • 缺点：内核庞大功能复杂难以维护；如果某个模块出错就会导致整个系统崩溃。

微内核

由于操作系统不断复杂，因此将一部分操作系统功能移出内核，留下一个尽量小的内核，从而降低内核的复杂性。

提高了OS的正确性、灵活性、易维护性、可扩充性

移出的部分根据分层的原则划分成若干服务，相互独立。 在微内核结构下，操作系统被划分成小的、定义良好的模块，只有微内核这一个模块运行在内核态，其余模块运行在用户态。

微内核OS的一些基本概念：

  1. 足够小的内核（与硬件处理紧密相连的部分、一些基本功能、客户和服务器之间的通信）
  2. 基于客户/服务器模式：将OS除基本功能的绝大部分功能（进程管理、线程管理、虚拟存储器管理、I/O设备管理）放在微内核外面的一组服务器（进程）中实现，（进程服务器、虚拟存储服务器、I/O设备管理服务器），这些服务器运行在用户态，客户/服务器借助微内核提供的消息传递机制进行通信。
  3. 应用“机制与策略分离”原理：将机制（实现某功能的具体执行机构）微内核，策略（在机制基础上的算法优化）放在服务器。
  4. 采用面向对象技术

微内核的基本功能

  1. 进程（线程）管理
  2. 低级存储器管理
  3. 中断和陷入处理

优点：

  1. 提高系统可扩展性
  2. 增强系统可靠性
  3. 增强可移植性
  4. 提供对分布式系统的支持
  5. 融入面向对象技术

缺点：
运行效率有所降低

  • 原因：因为微内核OS中，客户和服务器、服务器和服务器之间通信都需要经过微内核（都要请求内核服务，切换用户态与内核态耗费时间长），同样的服务至少需要四次上下文切换而早期OS只需要两次。
  • 改善：重新把常用的OS基本功能从服务器移入微内核

第二章 进程的描述与控制

前趋图与程序执行

使用前趋图来描述进程的顺序和并发执行的情况

程序顺序执行

程序顺序执行：按照某种先后次序顺序执行，仅当前一程序执行完后，才能执行后继操作。

  • 特征：
    • 顺序性
    • 封闭性(独占全机资源)
    • 可再现性

程序的并发执行

程序的并发执行：不存在前趋关系的程序之间可以并发执行

  • 特征：
    • 间断性、
    • 失去封闭性（系统中各种资源受到各个程序共享）
    • 不可再现性

进程的描述

进程的定义

进程是程序一次执行的过程（动态）；进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。
程序是指令集合（静态）

进程的特征
进程除了有程序没有的PCB之外，还有以下特征

  • 动态性（有生命周期，创建产生，调度执行，撤销消亡）
  • 并发性（多个进程实体可并发执行）
  • 独立性（没有建立PCB的程序都不能作为一个独立单位运行）
  • 异步性

进程与程序的区别？

  • 进程是动态的，程序是静态的
  • 进程是暂时的，程序是“永恒”的
  • 进程包含程序、数据和PCB
  • 进程可以包含多个程序，同意个程序可以对应多个进程

进程基本状态及转换

进程的状态

  1. 创建态：OS进行进程资源分配，初始化PCB;确保进程的调度在创建工作后进行
  2. 就绪态：已具备运行条件但没有空闲CPU，暂时不能运行
  3. 执行状态（单核，同一时刻只有一个进程，多核心：同一时刻有多个进程）
  4. 阻塞状态（进程因为等待某个事件而被阻塞）
  5. 终止态 发出exit系统调用之后，OS回收资源与PCB
    （进入终止态后，OS不会立马删除进程，会保留一个记录，包含状态码和计时统计数据，供其他进程收集，一旦其它进程收集完毕，那么OS才会删除进程）

其中，2、3、4是进程生命周期内可能存在的状态·
其它重点看图：

注意，运行->阻塞是进程自身做出的主动行为，反之，阻塞->运行是不受进程自身控制的被动行为；所以这里只有单向箭头

挂起操作和进程状态的转换

挂起状态：进程处于静止状态，暂停执行（执行状态下挂起），暂不接受调度（就绪状态下挂起）。与挂起对应的操作时激活操作。
挂起原语Suspend
激活原语Active
注意：挂起是将进程映像调到外存，阻塞态进程映像还在内存

（图上的活动阻塞->执行，大胆猜测是箭头标反了）
执行、就绪状态挂起变成静止就绪，处于静止就绪的进程被安置在外存，不参与调度，进程的将建工作并未完成
原则，阻塞可以到就绪，同时活动与静止可以互相转换

进程管理中的数据结构

进程的组成：PCB（OS使用）、程序段、数据段（进程使用）
OS为每个资源和进程设置了一个数据结构表征其实体，包括：内存表、设备表、文件表和进程表（进程控制块）

进程控制块PCB

PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。是操作系统中最重要的记录型数据结构。

PCB中的信息：

  • 进程标识符 PID 用户标识符UID
  • 处理机状态（处理机中的各个寄存器中的内容）
  • 进程调度信息（进程状态、进程优先级、调度所需信息、引起阻塞的事件）
  • 进程控制信息（程序和数据的地址、进程同步和通信机制、资源清单、链接指针【下一个进程PCB首地址】）

PCB的组织方式：

  • 线性方式：所有内容存在线性表里
  • 链接方式：具有相同状态的进程PCB放在ige队列里，（如，执行指针、就绪队列指针等）
  • 索引方式：建立就绪状态索引表

进程控制

进程控制的实现：原语
原语的实现：关中断、开中断指令

操作系统内核

（联动此前在微内核、宏内核中提到的定义,以及图片）
OS内核包含以下功能：

支撑功能

  • 中断处理
  • 时钟管理：管理时间片
  • 原语操作：数条指令的集合，原语不可被打断

资源管理功能

  • 进程管理
  • 存储器管理
  • 设备管理

操作系统运行机制

  • 内核态/系统态/管态：较高特权，执行一切指令，包括特权指令
  • 用户态/目态：较低特权，只能运行应用程序、非特权指令
    内核态->用户态：执行一条特权指令，修改PSW为用户态
    用户态->内核态：由中断引发（硬件完成“变态”）

中断：使CPU由用户态变为内核态，使OS内核重新夺回队友CPU的控制权

中断类型：

  • 内中断：与当前执行指令有关
    • 异常 由 CPU 执行指令的内部事件引起，如非法操作码、地址越界、算术溢出等。
    • 陷入 在用户程序中使用系统调用。
  • 外中断：由 CPU 执行指令以外的事件引起
    如 I/O 完成中断，表示设备输入/输出处理已经完成，处理器能够发送下一个输入/输出请求。此外还有时钟中断、控制台中断等。

中断处理程序一定是内核程序，运行在内核态

进程的创建

创建原语：

  1. 申请空白PCB。
  2. 为新进程分配资源。
  3. 初始化进程控制块。
  4. 将新进程插入就绪队列（如果进程就绪队列能够接纳新进程）。
    引起创建的事件：用户登录、作业调度、提供服务（OS会新建一个进程处理用户请求）、应用请求（进程主动创建子进程）

进程的终止过程

撤销原语：

  1. 根据被终止进程的标识符，从 PCB 集合中检索出该进程的 PCB，从中读出该进程的状态。
  2. 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。
  3. 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防它们成为不可控的进程。
  4. 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。
  5. 将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。
    引起原语的事件：
  6. 正常结束（exit系统调用）
  7. 异常结束（整数除以0等，被os强行kill）
  8. 外界干预（用户杀掉进程）

进程的阻塞和唤醒

阻塞原语 block
唤醒原语 wakeup

进程的切换

进程的挂起与激活

挂起原语：

  1. 首先检查被挂起进程的状态，改成对应的静止状态
  2. PCB复制到指定区域
  3. 若被挂起程序正在执行，则转调度程序重新调度

激活原语：

  1. 改静止为活动
  2. 检查是否重新调度

进程同步

主要任务：对多个相关进程在执行次序上进行协调，使并发执行的进程之间按照一定规划共享系统资源，很好地互相合作，从而使程序的执行具有可再现性

并发进程之间的制约关系

  1. 间接相互制约关系。源于资源共享。多个程序的互相执行导致。
  2. 直接相互制约关系。源于进程间的合作。共享同一个缓冲区。同任务之间使用通过管道实现的同步

同步：系统中多个进程发生的事件存在时序关系，需要互相合作完成同一任务
互斥：个进程要求共享资源，有些资源需要互斥使用
临界资源：系统中一次只允许一个进程使用的资源
临界区：每个进程中访问临界资源的那段代码称为临界区。保证各个进程互斥地进入自己的临界区，便可实现诸进程对临界资源互斥访问。

为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查。
可把一个访问临界资源的循环进程描述如下：

1
2
3
4
5
6
7
while(TRUE)
{
    进入区（检查是否可进入临界区，如可进入，则上锁，组织其他进程进入临界区）
    临界区
    退出区（解锁）
    剩余区（其它处理）
}

同步机制应遵循的规则：

  1. 空闲让进
  2. 忙则等待
  3. 有限等待（保证有限时间内可访问资源，避免陷入死等）
  4. 让权等待（进程不能进入临界区时应该立即释放处理及，避免陷入忙等，CPU忙）

硬件同步机制

  1. 关中断
  2. Test-and-Set指令 （不满足让权等待原则）
  3. 利用Swap指令（不满足让权等待原则）
    上述两个指令都是硬件实现的，执行过程中不允许被中断

信号量机制

  1. 整型信号量
    用于表示资源数目的整型量，仅能通过原子操作wait（S）和signal（S）来访问，也就是常见的 P 和 V 操作，执行时不可中断，通常的做法是在执行这些操作的时候屏蔽中断。

    1
    2
    3
    4
    5
    6
    7
    wait(S){
        while(S<=0);
        S--;
    }
    signal(S){
        S++;
    }

    如果S<=0，则进程就会不断进行测试，会陷入忙等。

  2. 记录型信号量
    这是一种不存在“忙等”现象的进程同步机制，遵循了“让权等待”的准则。

    记录型信号量semaphore数据结构：
    int value：代表资源数目的整型变量
    进程链表指针list：用于链接等待访问临界区的所有等待进程
    value>0表示有可用资源
    vlaue<0时，它的绝对值表示已阻塞的进程数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    wait(semaphore S)
    {
        S.value--;
        if(S.value<0){
            block(S.list);  //剩余资源不足，则使用block原语使进程进入阻塞态，并挂起到S的等待队列中
        }
    }
    signal(semaphore S)
    {
        S.value++;
        if(S.value<=0)//+1后，若还是小于等于0，则还有别的进程在等待资源
        {
            wakeup(S.list);//唤醒队列中的进程，从阻塞态变为就绪态
        }
    }

    如果信号量的取值只能为0或者1，那么就成为了互斥量（Mutex），0表示临界区已经加锁，1表示临界区解锁。用于进程互斥。

  3. AND型信号量
    将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。
    Swait(S1,S2,...,Sn)
    Ssignal(S1,S2...,Sn)

    进程使用资源且任意所需资源(Si<0)不足时，该进程进入阻塞队列且释放所有资源
    进程释放资源且任意释放资源不足(Si<0)时，唤醒所有需要该资源的进程

    缺点：要么全给，要么不给，效率低

  4. 信号量集
    AND型信号量基础上，对进程所申请的所有资源以及每类资源不同的资源需求量，在一次P、V原语操作中完成申请或释放。（即规避了多次wait操作）
    Swait(S1,t1,d1,...,Sn,tn,dn)
    Ssignal(S1,t1,d1,...,Sn,tn,dn)
    一次请求t1个S1，如果成功则消耗d1个S1；t1是资源分配的下限值；
    如果Si>=ti,才允许分配，则Si=Si-di，反之不给分配

    特殊情况：

    1. Swait(S,d,d)：每次申请d个，资源少于d时，不分配
    2. Swait(S,1,1)：退化为记录型信号量(S>1)，互斥型信号量(S=1)
    3. Swait(S,1,0)：成为一个可控开关，如果S>=1时，允许多个进程进入某个特定区，如果S=0，则禁止任何进程进入特定区

信号量的应用

信号量实现互斥

wait、signal在同一个进程中（或者用P、V）
互斥信号量mutex的初值为1
在进入区：wait(mutex)
在退出区：signal(mutex)

1
2
3
4
5
6
semaphore mutex=1;
...
wait(mutex);
临界区代码
signal(mutex);
...

利用信号量实现同步

wait、signal不在同一个进程中
同步实现方法：

  1. 分析什么地方需要“一前一后”执行两个操作
  2. 设置同步信号量S，改信号量初值为0 semaphore S=0;
  3. “前操作”之后执行signal(V)
  4. “后操作”之前执行wait(P)
    前V后P：需要前操作先释放资源，此后后操作才能取用资源

利用信号量实现前趋关系

每一对前趋关系都是一个进程同步关系，需要为每一对前趋关系都设置一个信号量

管程机制

引入管程：用来解决信号量机制变成麻烦、易出错的问题
管程是一种特护的软件模块，包含

  1. 管程的名称
  2. 局部于管程的共享数据结构说明
  3. 对数据结构进行操作的一组过程
  4. 对管程共享数据设置初始值的语句

管程将共享资源的数据结构和操作过程都封装在对象内部，隐藏实现细节

管程的基本特征：

  1. 模块化
  2. 抽象数据类型
  3. 信息掩蔽
  4. 各外部进程/线程只能通过管程提供的特定“入口”才能访问共享数据
  5. 每次只允许一个进程在管程内执行某个内部过程

各进程必须互斥访问管程的特性是由编译器实现的

管程中的条件变量：
通过设置条件变量区分进程被阻塞或挂起的原因，每个条件变量都有wait和signal操作以及一个进程链表

x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其它进程可以使用该管程。
x.signal：正在调用管程的进程发现x条件发生了变化，则调x.signal，重新启动一个因x条件而阻塞或挂起的进程。如果存在多个这样的进程，则选择其中的一个，如果没有，则继续执行原进程，而不产生任何结果。

经典进程同步问题

进程通信

Inter Process Communication IPC
进程之间的信息交换，为了能够达到进程同步的目的，需要让进程进行通信，传输一些进程同步所需要的信息
进程通信需要OS介入

进程通信的类型

  1. 共享存储
    • 基于共享数据的通信方式（数据结构；低级，慢，不灵活）
    • 基于共享存储区的通信方式（内存；高级，快，灵活）
  2. 消息传递
    以格式化消息为单位（消息头+消息体）
    • 直接通信方式，通过原语操作
    • 简介通信方式：通过中间实体（邮箱）发送和接收
  3. 管道通信系统
    管道又名pipe文件（内存中大小固定的缓冲区）
    • 写进程将数据送入管道，读进程取出
    • pipe满，写阻塞，pipe空，读阻塞
      只支持半双工通信，如果需要双向同时传递，需要设置两个管道；只能在父子进程中使用
  4. 客户-服务器系统
    • 套接字：基于文件型与基于网络型
    • 远程过程调用和远程方法调用

消息传递通信的实现方式

  1. 直接消息传递系统
    使用原语直接发送
    直接通信原语有两类：

    • 对称寻址方式：监听者监听一个发送者的消息；receive(sender,message)一旦改变进程名称，对该进程所有旧名称的引用都要查到、替换
    • 非对称寻址方式：监听者监听所有消息；receive(id,message)，不需要命名发送进程

    消息格式：定长/变长

    进程同步方式：

    通信链路：单向/双向链路

  2. 信箱通信
    通过某种中间实体（如共享数据结构）来暂存消息
    信箱结构：

    • 信箱头：存放信箱的描述信息，（标识符、拥有者、信箱口令、空格数）
    • 信箱体：若干信箱格组成

    信箱通信原语：

    • 创建和撤销
    • 消息的发送和接收

    信箱类型：

    • 私用信箱：进程创建，其它进程只能发送信件但不能读取消息，进程结束，信箱消失
    • 公用邮箱：由操作系统创建，提供给所有核准进程使用（发送和读取），在系统运行期间一直存在
    • 共享信箱：进程创建，指出可以共享的进程名字

线程的基本概念

线程的引入

进程的基本属性：

  1. 进程是一个可拥有资源的独立单位（必须拥有一定的资源）
  2. 进程是一个可独立调度和分派的基本单位。（每个进程都有唯一的PCB）

进程并发性所付出的时空开销：
创建进程，系统会为其分配资源、建立PCB
撤销进程，系统会回收其占有的资源、撤销PCB
进程切换，保留CPU环境，设置新选中进程的环境（主要开销）

线程的引入：为了减少程序在并发执行时所付出的时空开销，使OS具有更好的并发性

线程和进程的比较：

  • 调度的基本单位：进程调度需要切换上下文，线程切换仅需要保留和设置少量寄存器内容吗，线程切换的代价远低于进程
  • 并发性：都可以并发执行
  • 拥有资源：进程是拥有资源的基本单位，线程不拥有系统资源，只拥有一点必不可少、能够保证独立运行的资源（如TCB、程序计数器、局部变量、状态参数、返回地址、一组寄存器和堆栈）；线程可以共享进程所拥有的资源
  • 独立性：线程之间的独立性较低。每个进程的地址空间和资源都是独立的（共享全局变量除外）；线程共享进程的内存地址空间和资源
  • 系统开销：进程需要切换上下文，开销较大；线程切换代价远低于进程（多进程具有相同地址空间、同步和通信也很简单）
  • 支持多处理机系统：进程（单线程进程）必须在单处理机上运行，多线程进程可以分配到不同处理机上执行。

同一进程中线程切换，不会引起进程切换，不同进程中线程切换会引起进程切换

线程的实现

线程的实现方式

（暂略，好像这块没这么重要？）

  1. 内核支持线程（OS内核直接管理线程，线程切换必须在核心态完成）
  2. 用户级线程（应用程序管理线程，线程切换在用户态完成）
  3. 组合方式
    • 多对一模型（多个用户级线程->一个内核级线程）
      • 内核级线程是处理及分配单位，多个线程不能在多处理机上运行
      • 一个阻塞，整个阻塞
    • 一对一模型（一个用户级线程->一个内核级线程）
      • 线程管理要切换态，开销大
    • 多对多模型（多个用户级线程->小于等于用户级线程数的内核级线程）
      • 两者优点都有

内核级线程是处理机分配单位

线程的实现

  1. 内核支持线程：
    在内核空间中分配一个任务数据区PTDA（per task data area），其中存放若干TCB以及优先级、CPU等信息
  2. 用户级线程的实现
    • 运行时系统
    • 内核控制线程

线程也有就绪、运行、阻塞三种状态

TCB数据结构

第三章 处理机调度与死锁

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

处理机调度层次

  1. 高级调度（作业调度）：外存作业调入内存，并创建一个进程
  2. 低级调度（进程调度）：给进程分配处理机，使用频率高
  3. 中级调度（内存调度）：提高内存利用率和系统吞吐量；从挂起队列中选择合适的进程调回内存

调度算法目标
共同目标：

  1. 资源利用率，一般用CPU利用率
    CPU利用率=CPU有效工作时间÷总时间CPU利用率=CPU有效工作时间\div总时间
  2. 公平性（进程之间公平）
  3. 平衡性（资源使用平衡）
  4. 策略强制执行

批处理系统目标：

  1. 平均周转时间短
    周转时间：作业提交->作业完成的时间间隔
    平均周转时间：计算周转时间的平均值
    作业提交一般会经过：等待作业调度、等待进程调度、进程执行、等待I/O完成；其中，后三可能有多次
  2. 系统吞吐量高
    吞吐量：单位时间内完成作业的数量，总作业量÷总时间总作业量\div总时间
  3. 处理机利用率高
    补充：
    1. 带权周转时间：周转时间是运行时间的多少倍，必然大于等于1，越小越好，作业周转时间÷作业实际运行时间作业周转时间\div作业实际运行时间
    2. 等待时间：等待的时间之和（周转时间-运行时间）
      • 对于进程来说，等待时间不包括等待IO时间，因为这时候进程是在被服务的
      • 对于作业来说，作业在外存后被队列的等待时间以及建立进程后等待的时间
    3. 响应时间：提交请求到产生响应的时间

分时系统目标：响应快（外设响应速度快）、均衡（响应时间快慢于服务复杂性一致）
实时系统目标：截止时间保证、可预测性（如视频连续播放）

作业与作业调度

进程：程序段+数据+PCB
作业：程序+数据+作业说明书
作业步：完成作业的一个个步骤
作业控制块JCB：系统对作业进行调度管理所需要的资料；作业在系统内存在的标志

作业调度算法

饥饿：等待时间给进程/进程推进和响应带来明显影响

  1. 先来先服务（FCFS）:按照等待时间长短进行调度，等待时间越长优先级越高。（作业[后备队列]、进程调度[就绪队列]都适用）；可能导致饥饿
  2. 短作业优先（SJF）：按照作业运行时间长短进行调度，时间越短优先级越高。（作业、进程都可以用）
  • 缺点：
    • 必须预知作业运行时间，但是这通常不准
    • 长作业不利，可能出现饥饿
    • 人机交互无法实现
    • 不考虑紧迫程度
  1. 优先级调度算法（PSA）priority-scheduling algorithm：根据作业紧迫程度进行调度，紧迫程度越高，优先级越高。（作业、进程都可以使用）
  2. 高响应比优先算法（HRRN）:SJF和FCFS的折中，考虑等待时间和运行时间，响应比越高，优先级越高；
    • 优先权=(等待时间+要求服务时间)/要求服务时间
    • 书上又把等待时间+要求服务时间作为响应时间；所以认为响应时间=周转时间

进程调度

进程调度的任务、机制和方式

进程调度的任务：保存处理及现场，按照某种算法选取进程，把处理机分配给进程
进程调度机制：三个基本部分

  • 排队器
  • 分派器
  • 上下文切换器（两对上下文切换）

进程调度方式

  1. 继承所有作业调度的算法

  2. 轮转调度算法（Round Robin，RR）：根据FCFS策略排成一个就绪队列，每隔一个时间片产生一次中断，将CPU分配给队首进程。抢占式算法。
    只有作业被 放入内存、建立进程后才会被分配时间片

  • 进程切换的时机：
    1. 进程提前运行结束
    2. 时间片用完
  • 时间片的选择：太长，退化成FCFS，太短，频繁调度、切换上下文，增加开销

优先级调度算法的一些概念：

  • 调度类型：
    1. 非抢占式：队列中优先级最高的进程可不间断地执行完
    2. 抢占式：只要出现了优先级更高的进程，就可以终端当前进程
  • 优先级类型：
    1. 静态优先级：创建进程时分配，全程不变
    2. 动态优先级：进程执行时，优先级可以改变
  1. 多队列调度算法:设置多个就绪队列，每个就绪队列采用不同的调度算法（例如，按照进程类型设置队列）
  1. 多级反馈队列调度算法
  • 算法：
    1. 设置多级就绪队列，各级优先级从高到低，时间片由小到大
    2. 新进程先进入第1级队列（最高级），按照FCFS原则排队等待被分配时间片，若时间片用完，进程结束，进入下一级队列尾，如果已经在最下级就绪队列，则重新放回队列尾
    3. 只有当K级队列为空的时候，K+1级队列中的进程才会开始运行

如果引入了抢占式，那么如果K级队列中进程正在运行时，更高级队列中有了进程，就先把当前进程放到K级队列的队尾，先执行更高级别的进程

可能会出现饥饿

  1. 基于公平原则的调度算法
    计算 进程获得处理及时间的比率，（实际执行的处理机时间除以应获得处理及时间）
    比较 各个进程获得处理机时间的比率选择最小的，一直给他分配处理机直到超过最接近它的进程比率。

实时调度

实时调度实现的基本条件

  1. 提供必要信息：就绪时间、开始截止时间和完成截止时间、处理时间、资源要求、优先级
  2. 系统处理能力强：单处理机：满足限制∑i=1mCiP1≤1\sum_{i=1}^{m}\frac{C_i}{P_1}\leq1(m个周期性硬实时任务，处理时间Ci，周期时间Pi)
  3. 采用抢占式调度机制
  4. 快速切换机制

实时调度算法的分类

非抢占式调度算法：

  1. 非抢占式轮转调度算法
  2. 非抢占式优先调度算法

抢占式调度算法

  1. 基于时钟中断的抢占式优先级调度算法：如果有高优先级来，先等当前任务的时间片用完再剥夺当前任务
  2. 立即抢占的优先级调度算法：一旦出现外部中断，只要当前任务没有处于临界区，则立即剥夺当前任务的执行

实时调度算法

  1. 最早截止时间优先算法（EDF，earliest deadline）：任务截止时间越早优先级越高
  • 非抢占式：用于非周期实时任务
  • 抢占式：用于周期实时任务
    （忽略2、3行，2、3行引入了优先级）
  1. 最低松弛度优先算法（LLF，least laxity）：任务紧急程度越高优先级越高
    松弛度计算：截止时间-运行时间
    如果是在时间轴上计算松弛度：松弛度=必须完成时间-运行所需时间-当前时间
    松弛度最低的任务排在最前面，如果某个任务松弛度变为0，则立即剥夺正在执行的任务，将松弛度为0的任务上处理机

优先级倒置

优先级倒置：高优先级进程被低优先级进程延迟/阻塞
例子：
任务来顺序：p3->p2->p1
优先级：p1>p2>p3
p1优先级最高，但是最晚才执行完

解决方法：

  1. 进入临界区的话不会被剥夺处理机（如果临界区很长，则不行）
  2. 动态优先级：高优先级进入临界区但是已经有一个低优先级进程在使用临界资源，那么将高优先级进程阻塞并且让那个使用临界资源的进程继承它的优先级

死锁

死锁：计算机系统中多道程序并发执行时，两个或两个以上进程由于竞争系统资源而造成的一种互相等待的现象，若无外力作用，这组进程将永远不能继续执行；一定处于阻塞态，两个或者两个以上进程同时发生
饥饿：可能只有一个进程，可能是阻塞状态，也有可能是就绪态
死循环：代码逻辑错误导致

资源问题

了解即可

  • 可重用性资源（数目固定）
  • 可消耗性资源（生产创建，消费小号，如进程中通信消息）
  • 可抢占性资源（处理机）
  • 不可抢占性资源（打印机）

计算机系统中的死锁的情况

  1. 由于竞争不可抢占性资源引起（分别持有对方想要的资源而且不释放）
  2. 竞争可消耗性资源引起死锁（资源都消耗完了，还在要）
  3. 进程推进顺序不当引起死锁

死锁的定义、必要条件和处理方法

死锁的定义：一组进程中的每个进程都在等待仅由该组进程中的其他进程才能引发的事件，那么该组进程就是死锁的。

死锁产生的必要条件：

  1. 互斥条件：资源独占，进程对分配到的资源进行排他性使用
  2. 请求和保持条件：进程已经保持了至少一个资源，又提出新的资源请求，如果请求失败，则请求进程被阻塞且不释放已有资源
  3. 不可抢占条件：进程已获得的资源在未使用完不能被抢占，只能在进程用完时自己释放
  4. 循环等待条件：一定存在进程-资源的循环连，环路中的进程形成等待链

如果同类资源数大于1，即使循环等待，未必会发生死锁，如果只有一个同类资源，循环等待是死锁的从充要条件

处理死锁的方法：

  1. 预防死锁：破坏死锁产生的必要条件
  2. 避免死锁：防止系统进入不安全状态（银行家算法）
  3. 检测死锁：通过检测机构及时发现死锁，再采取措施（资源分配图）
  4. 解除死锁：当死锁发生，撤销一些进程，回收资源再分配
    从1到4 对死锁的防范程度逐渐减弱，对资源的利用率逐渐提高

预防死锁

  • 破坏请求和保持条件
    通过两个协议实现
    1. 第一种协议：进程在开始运行之前，必须一次性申请其在整个运行过程中所需要的全部资源
      • 缺点：资源被严重浪费，可能会发生饥饿现象（不断申请、放弃）
    2. 第二种协议：只申请初期资源便开始运行，运行过程中逐步释放已有的，再请求新的
  • 破坏不可抢占条件：资源得不到满足，必须主动释放已有资源
  • 破坏循环等待条件：（顺序资源分配法）对资源排序，进程必须按照序号递增顺序申请资源，如果还想申请序号低的资源，需要释放所有高序号的资源；如果申请同类资源（编号相同）必须一次申请完
    • 缺点：不方便新增设备；进程使用资源可能与编号顺序不一样；编程不便

避免死锁

避免死锁与预防死锁的区别：
预防死锁是对进程的资源申请命令施加限制，是规定死的
避免死锁是在进程请求分配资源的时候进行动态检查，根据检查结果决定分配

系统安全状态

安全状态：系统能够按照某种进程推进顺序为每个进程分配所需资源，直至满足每个进程对资源的最大需求，使每个进程都能顺利完成，则该序列成为安全序列
如果不存在安全序列，那么系统就处于不安全状态
系统进入不安全状态后，可能转为死锁状态

银行家算法

每个进程在进入系统时，必须申明在运行过程中可能需要的每种资源类型的最大单元数目

银行家算法中的数据结构

  1. Available：可利用资源向量，表示当前系统中还有多少可用资源
  2. Max：最大需求矩阵，定义了系统中n各进程对m类资源的最大需求
  3. Allocation：分配矩阵，表示系统中每一类资源当前已分配给每一进程的资源数（记录每个进程得到的资源）
  4. Need：需求矩阵，表示每一个进程还需要的资源数 Need=Max-Allocation

银行家算法的过程

两个判断三个调整

  1. 检查是需要的资源是否已经超过它宣布的最大数（Requesti[j]<=Need[i][j]），如果超出，则报错
  2. 检查资源是否不足（Requesti[j]<=Available[i][j]），如果没有足够资源，则该进程需要等待
  3. 试探进行分配
    Available[j]=Available[j]-Requesti[j] 可用资源减少
    Allocation[i,j]=Allocation[i,j]+Requesti[j] 该进程已分配资源增加
    Need[i,j]=Need[i,j]-Requesti[j] 该进程需求矩阵减少
  4. 执行安全性算法；如果安全，正是分配资源，如果不安全，则本次试探作废，恢复原来的资源分配状态，让该进程等待

安全性算法

两个向量：

  1. Work 工作向量：表示系统可以供给进程继续运行所需的各类资源；开始时，Work=Availbale；如果安全，Work最后应该变为系统拥有的所有资源数量（初值）
  2. Finish：bool数组，表示系统是否有足够的资源分配给进程
    算法过程：
  3. 挑一个剩余资源数能直接满足进程执行条件的进程分配给其资源，然后执行完毕后释放该进程所有资源给下一个资源
  4. 重复以上过程直至无该类进行
  5. 如果最终所有进程全都执行了一遍，所有进程的Finish都为true，那么系统安全

银行家算法与安全性算法例子：
书p113吧，懒得写了；银行家算法一张表，安全性检查一张表
（银行家算法表）先假设分配资源，修改Available、Allocation和Need
（安全性算法表）然后按照此表检查安全性：（模拟分配）看看剩余的资源能满足哪个进程 Work，Need，Allocation，Work+Allocation，Finish

银行家算法的不足：对资源分配保守，计算多，需要预知未来的进程变化和资源请求（MAX）

死锁的检测与解除

死锁的检测

需要保存有关资源的请求和分配信息
提供算法，检测系统是否进入死锁
资源分配图：

  • 资源结点与进程结点
  • 资源指向进程：进程占用该资源
  • 进程指向资源：进程请求该资源

死锁定理

  1. 找到一个既不阻塞又不独立的进程节点，释放它占有的全部资源，使之成为孤立结点
  2. 重复此过程，如果能消去图中的所有边，使所有的进程结点都成为孤立结点，那么该图是可完全简化的

如果化简完后还存在连着边的就是死锁进程

S死锁->当且仅当S状态的资源分配图是不可完全简化的（死锁定理，死锁的充分条件）
不存在环路，一定没有死锁，存在环路，可能不存在死锁

死锁的解除

  1. 资源剥夺法：挂起某些死锁进程，抢占资源分配给其它进程，同时防止饥饿
  2. 撤销进程法（终止进程法）：强制终止所有死锁进程，之只有足够资源
  3. 进程闪回法：让多个进程回退到足以避免死锁
  4. 逐个终止进程：需要按照某种顺序考虑如下因素：
    1. 进程的优先级
    2. 执行时间
    3. 还需执行时间
    4. 已使用资源
    5. 交互式or批处理式

题目总结

死锁与调度

Q；银行家算法满足一个导致不安全状态的分配后，是否会立即进入死锁状态？
A：不会，满足请求后，没有其他进程继续申请资源，并因为得不到资源而进入阻塞状态，只有当其他进程提出新的请求后，导致没有执行完的多个进程因得不到资源而阻塞形成循环等待链的时候系统才会死锁

LFF复习

管程了解一下就好
哲学家进餐 了解
进程间通信：管道（其实是文件），消息传递，了解一下，客户服务器了解
信箱通信：间接通信方式
进程：拥有资源的独立单位
线程：调度和分派的基本单位
线程和进程的比较6个方面
线程实现方式：用户级线程:内核不知道线程的切换；但是内核级线程，内核会知道切换

调度只存在于多道处理机
平均周转时间的定义，计算
低级调度、、
周转时间、吞吐量

系统态和用户态；特权指令和非特权指令；用户只能执行非特权指令
系统调用:运行在系统态；通过中断机制实现

阻塞：进程通信等消息，等键盘输入，网络数据没有到来，
如果一个进程处于执行状态，时间片用完之后，并不会唤醒别的进程
PV操作会唤醒其他进程从

进程状态：
进程优先级可以更改
进程要调度才能就绪
进程的要求得不到满足，会进入阻塞态，时间片用完会转到就绪态
处理机不是在任何时候都处于运行态，可能没有进程在运行（比如，出现死锁，所有进程都在等待）

核心态可以执行所有指令，用户态不能执行特权指令
什么时候会从用户态-》核心态？

  • 例如，read系统掉哟，读取文件，从用户态->系统态，会发生切换
  • 程序运行中出现错误，如越界、坟墓为0 ，程序需要从用户态切换到核心态，处理错误

常见命令：kill ps ls cat命令的用法（稍微复杂一点）
fork
exec
wait （不是原语，是等待进程结束）
sleep

题目类型：
判断
选择
填空
简答：重点已经复习过了
综合：银行家、信号量、作业调度（SJF,高相应比） 读一个程序，知道这个程序是什么意思，实验课绝对接触过

复习课没讲的就是不考的

题目类型：
判断
选择
填空
简答：重点已经复习过了
综合：银行家、信号量、作业调度（SJF,高相应比） 读一个程序，知道这个程序是什么意思，实验课绝对接触过

操作系统引论

操作系统的目标

  • 方便性 （脱离硬件运行程序）
  • 有效性 （提高资源利用率）
  • 可扩充性 （模块化结构->层次化结构->微内核结构）
  • 开放性 （遵循开放系统互连OSI国际标准）
    其中，方便性和有效性是设计OS的最重要两个目标

操作系统的作用

  • 用户和计算机硬件之间的接口
  • 计算机系统资源的管理者
  • OS实现对计算机资源的抽象

单道批处理系统

顺序执行
内存始终只保持一道作业

多道批处理系统

为了提高资源的利用率和系统吞吐量而产生
无交互能力
多道批处理系统中产生了作业的调度问题

操作系统的发展

Unix的历史，Unix不是微内核
Linux之父，Linux的历史

OS的结构

微内核OS结构，重要
微内核的基本功能

  1. 进程（线程）管理
  2. 低级存储器管理
  3. 中断和陷入处理
    微内核操作系统的优点
  4. 提高系统可扩展性
  5. 增强系统可靠性
  6. 增强可移植性
  7. 提供对分布式系统的支持
  8. 融入面向对象技术
    微内核操作系统存在的问题

进程的描述与控制

前趋图不管

进程相关

进程的特征（以及与线程特征的比较）：

  • 动态性（有生命周期，创建产生，调度执行，撤销消亡）
  • 并发性（多个进程实体可并发执行）
  • 独立性（没有建立PCB的程序都不能作为一个独立单位运行）
  • 异步性
    进程的基本状态以及转换【3种状态，4种转换，搞懂什么时候转换】
    运行态到就绪态，时间片用完只是最常见的情况
    如果一个进程处于执行状态，时间片用完之后，并不会唤醒别的进程，但是PV操作会唤醒其它进程

阻塞态不能直接变成运行态

进程的创建：与进程创建相关的系统调用【fork，exec，wait…?含义是什么，程序要明白】

进程的阻塞与唤醒：
引起进程阻塞和唤醒的事件（举例）

  • 向系统请求共享资源失败
  • 等待某种操作完成
  • 新数据尚未达到
  • 等待新任务的到达

进程的同步
临界资源的定义，临界区是什么（访问临界资源的那段代码）
为了互斥访问临界资源，每个进程在进入临界区之前，需要先进行检查:进入区；相应地，临界区后面也要加上一段代码，成为退出区
可把一个访问临界资源的循环进程描述如下：

1
2
3
4
5
6
7
while(TRUE)
{
    进入区（检查是否可进入临界区，如可进入，则上锁，组织其他进程进入临界区）
    临界区
    退出区（解锁）
    剩余区（其它处理）
}

同步机制应遵循的规律

  1. 空闲让进
  2. 忙则等待
  3. 有限等待（保证有限时间内可访问资源，避免陷入死等）
  4. 让权等待（进程不能进入临界区时应该立即释放处理机，避免陷入忙等，CPU忙）

信号量相关

（硬件同步机制可以不要）
信号量机制：

  1. 整型信号量
  2. 记录型信号量
  3. AND型信号量（了解）
    标准的原子操作：PV

信号量应用

  • 互斥信号量的初始值？信号量值得范围？
  • 非互斥信号量初始值可能不为1

PV操作是低级通信原语

经典进程同步问题：

  • 生产者消费者问题（2种类型的信号量，使用次序）
    • 1个互斥型信号量
    • 2个缓冲池相关：空/满
    • mutex=0不代表另一个进程在等待
    • 如果有一个进程在等待，信号量的值应该是？（是-1吧！
    • 如果允许两个（或多个）进程访问，信号量的初始值应该是多少？信号量值的范围？

进程通信相关

管道是一种特殊类型的文件
信箱通信：间接通信，公共缓冲区；有关信箱通信需要看看

线程

进程：拥有资源的独立单位
线程：调度和分派的基本单位
线程和进程的比较：

  • 调度的基本单位：线程切换的代价远低于进程
  • 并发性：都可以并发执行
  • 拥有资源：进程是拥有资源的基本单位，线程不拥有系统资源，只拥有一点必不可少、能够保证独立运行的资源（如TCB、程序计数器、局部变量、状态参数、返回地址、一组寄存器和堆栈）；线程可以共享进程所拥有的资源
  • 独立性：线程之间的独立性较低。每个进程的地址空间和资源都是独立的；线程共享进程的内存地址空间和资源
  • 系统开销：进程需要切换上下文，开销较大；线程切换代价远低于进程
  • 支持多处理机系统：进程（单线程进程）必须在单处理机上运行，多线程进程可以分配到不同处理机上执行。

线程的实现：
内核支持线程和用户级线程得区别要了解清楚

  • 内核级线程得创建、阻塞、撤销和切换等都是在内核空间实现的
  • 用户及线程得调度是以进程为单位进行的，内核不知道用户级线程的存在，线程切换不需要切换到内核空间
  • 线程实现的数据交换方式…？
  • 属于一个进程的多个线程，这些线程会共享该程序的程序段…

处理机的调度与死锁

调度存在于多道处理机，实质是一种资源分配
高级调度与低级调度是重点
平均周转时间的定义，计算
周转时间（ 作业提交->作业完成的时间间隔）、吞吐量

多道批处理系统中，作业时用户提交给系统的一项相对独立的工作，操作员把用户提交的作业通过相应设备输入到磁盘存储器，保存在一个后备队列中，并保存在一个后备作业队列种，再由作业调度程序将其从外存调入内存。

重要的调度算法：
SJF和抢占式的SJF，lff上课说，被调度者的运行时间会变短，优先级会变化…
HRRN：要会计算优先权，比较公平
RR：唯一不会导致饥饿的调度算法；多个用户可以得到及时的响应；每个进程运行一个时间片
多级反馈队列调度算法：注意调度机制，优缺点；各种细节都要注意一下；调度算法的性能
【时间片用完不会唤醒进程】

静态优先级和动态优先级
可能在某一时刻，优先级出现反转；当前执行的进程优先级不一定是最高的

实时调度，知道概念

死锁相关

引起死锁的主要原因：

  1. 竟争资源
  2. 推进顺序不当

产生死锁的必要条件

  1. 互斥条件
  2. 请求和保持条件
  3. 不可抢占条件
  4. 循环等待条件

预防死锁：破坏循环等待条件：所有资源类型进行线性排序

安全状态
安全状态例子
银行家算法、安全性算法

死锁的解除：抢占资源一定是抢占属于死锁集合中的进程的资源

操作系统接口

系统调用的基本概念：系统态和用户态；特权指令和非特权指令
系统调用由中断实现

常见命令：kill ps ls cat命令的用法（稍微复杂一点）
常用系统调用
fork
exec
wait （不是原语，是等待进程结束）
sleep

哪个系统是谁做的
Linux Unix都属于微机操作系统中的多用户多任务操作系统
多用户多任务操作系统，多个用户通过各自终端使用一台机器，每个用户又可以进一步分为多个任务
UNIX 20 60s，Windows 20 80s，Linux 20 90s
Linux之父：林纳斯·本纳第克特·托瓦兹；Linus Torvalds
Unix之父：肯•汤普森（Ken Thompson） 丹尼斯•里奇（Dennis Ritchie）发明
c之父——丹尼斯•里奇（Dennis Ritchie）
单用户单任务：CP/M,MS-DOS
单用户多任务：Windows
多用户多任务：UNIX,Linux

计算机基础 > 操作系统
#StudySHUSHU
操作系统1复习
https://mapllle.site/2023/10/16/StudySHUSHU/OS/OS1/
作者
MAple
发布于
2023年10月16日
许可协议