ZERO

内存管理概念引入多道程序的并发执行后，进程之间共享的不仅仅是处理机，还有主存储器。然而，共享主存会形成一些特殊的挑战。若不对内存进行管理，则易导致内存数据的混乱，以至于限制进程的并发执行。因此，为了更好地支持多道程序并发执行，必须进行内存管理 基本原理和要求 内存管理 操作系统对内存的划分和动态分配 内存管理目的 方便用户 提高内存利用率 内存管理主要功能 内存空间的分配与回收 地址转换（逻辑 → 物理） 内存空间的扩充（逻辑上） 内存共享（受控访问） 存储保护 将用户程序变为可在内存中执行的程序的步骤 编译 由编译程序(compiler)对用户源程序进行编译，形成若干个目标模块(object module) 链接 由链接程序(linker)将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块(load module) 装入 由装入程序(loader)将装入模块装入内存 目标文件 目标文件有三种形式： 可重定位目标文件 包含二进制代码和数据，其形式可以在编译时与其他可重定位目标文件合并起来，创建一个可执行目标文件 可执行目 ...

基本概念 图 G 由顶点的有限非空集 V 和边集 E 组成 → G = (V, E) 线性表可以是空表，树可以是空树，但图不可以是空图（边集可空，顶点集一定非空） |V| 表示 G 中顶点 vertex 的个数，|E| 表示 G 中边 edge 的条数 有向图：每条边都有方向 无向图：每条边都没有方向 弧/有向边 有向图中的边，是顶点的有序对，记为 <$v_i$, $v_j$>，$v_j$ 为弧头，$v_i$ 为弧尾 <$v_i$, $v_j$> 称从 $v_i$ 到 $v_j$ 的弧，也称 $v_i$ 邻接到 $v_j$ 无向图中，边是顶点的无序对，记为 ($v_i$, $v_j$)，等价于有向图中 <$v_i$, $v_j$> 和 <$v_j$, $v_i$> 两条边 可以说 $v_i$ 和 $v_j$ 互为邻接点 边 ($v_i$, $v_j$) 依附于 $v_i$ 和 $v_j$，或称边 ($v_i$, $v_j$) 和 $v_i$、$v_j$ 相关联 度 TD($v$)：无向图中依附于顶点 $v$ 的边的条数 入度 ID ...

树概念 定义 唯一根结点与若干棵互不相交的子树组成（每一棵子树又是一棵树，递归定义） 是一种非线性的数据结构 属于分层结构 特点 根结点无前驱，其他所有结点有且只有一个前驱 所有结点可以有零个或多个后继 基本术语 空树、结点的度（结点的孩子个数）、树的度（树中结点的最大度数）、叶子/终端结点（度为 0）、分支/非终端结点（度大于 0）、内部结点、孩子、双亲、兄弟、祖先、子孙、层次（根结点为第 1 层）、树的高度/深度（树中结点的最大层数）、结点深度（自顶向下逐层累加）、结点高度（自底向上逐层累加）、堂兄弟（双亲在同一层）、有序树（各子树左右有序，不能互换）、无序树、路径（结点序列）、路径长度（路径上所经过的边的个数）、丰满树/理想平衡树（除最底层外其他层都是满的）、森林（若干棵互不相交的树的集合） 分支有向（双亲指向孩子），路径只能自顶向下，故同一双亲的两个孩子之间不存在路径 “路径长度” 结点的路径长度：根到该结点经过的边数 树的路径长度：所有结点的路径长度之和 结点的带权路径长度：该结点路径长度与其权值的乘积 树的带权路径长度 WPL：所 ...

二分法左闭右闭 [left, right] 1234567891011121314public int search(int[] nums, int target) { int l = 0, r = nums.length - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { l = mid + 1; } else { r = mid - 1; } } return -1;} 1234567891011121314int search(vector<int>& nums, int target) { ...

栈概念栈的数学性质：出栈排列数目（$n$ 个不同元素以某种顺序依次进栈，并可在任意时刻出栈）满足函数 $Catalan()$：$N=\frac{1}{n+1}C^n_{2n}$ 栈的基本操作：初始化、判空、进栈 push、出栈 pop、读栈顶、销毁 顺序存储结构顺序栈、共享栈（两个顺序栈共享存储空间） 采用共享栈的好处：节省存储空间，降低发生上溢的可能 链式存储结构链栈 代码实现顺序栈1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465/* 顺序栈 */#define MaxSize 50typedef struct { ElemType data[maxSize]; int top;} SqStack;/** * 初始化 */void initStack(SqStack &st) { st.top = -1;}/** * 判栈 ...

定义和基本操作 线性表 具有相同数据类型的 $n$ 个数据元素的有限序列（$n \geq 0$） 空表：表长 $n$ 为 0 线性表逻辑特性 只有一个表头元素 只有一个表尾元素 表头无前驱、表尾无后继 除表头表尾，每个元素只有一个直接前驱和一个直接后继 线性表特点 表中元素的个数有限 表中元素具有逻辑上的顺序性，在序列中各个元素有其先后次序 表中元素都是数据元素。每个元素都是单个元素 表中元素的数据类型都相同，这意味着每个元素都占有相同大小的存储空间 表中元素具有抽象性。即讨论元素间一对一的逻辑关系，而不考虑元素究竟表示的内容 线性表基本操作 初始化、求表长、判空、插入、删除、按值查找、按位查找、打印、销毁 存储结构 顺序表示 顺序表 线性表的顺序存储 顺序表特点 1）表中元素的逻辑顺序与其物理顺序相同 2）随机访问 每个数据元素的存储位置都和线性表的起始位置相差一个和该数据元素的位序成正比的常数 通过首地址和元素序号可在时间 O(1) 内找到指定的元素 通常用高级程序设计语言中的数组来描述线性表的顺序存储结构 线性表中元素的位序从 1 开始，数组中元素下标从 0 开始 ...

数据结构的基本概念 数据 信息的载体，是描述客观事物属性的数、字符以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合 例如：整数、实数、字符串 数据元素 数据的基本单位，通常作为一个整体进行考虑和处理 例如：一本书的目录信息 数据项/数据域 构成数据元素的不可分割的最小单位 例如：书目信息的每一项 数据对象 性质相同的数据元素的集合，是数据的一个子集 例如，整数数据对象是集合 N = {0, ±1, ±2, ……} 数据类型 一个值的集合和定义在此集合上的一组操作的总称 分为： 1）原子类型：其值不可再分的数据类型 2）结构类型：其值可以再分解为若干成分（分量）的数据类型 3）抽象数据类型：抽象数据组织及与之相关的操作 抽象数据类型 ADT (Abstract Data Type) 可以看作一些数据对象以及附加在这些数据对象上的操作的集合 重在对功能的描述而不关心具体的实现 数据结构 相互之间存在一种或多种特定关系的数据元素的集合 二元组 (D, S) 表示：D 是数据元素的有限集，S 是 D 上关系的有限集 三要素：逻辑结构、存储结构/物理结构/映像、数据的运算 ...

存储器概述存储器的分类按在计算机中的作用（层次）分类 主存储器/主存/内存储器/内存 用来存放计算机运行期间所需的程序和数据 CPU 可直接随机地对其进行访问，也可以和高速缓冲存储器(Cache)及辅助存储器交换数据 特点：容量较小、存取速度较快、每位的价格较高 辅助存储器/辅存/外存储器/外存 用来存放当前暂时不用的程序和数据，以及一些需要永久保存的信息 辅存的内容需要调入主存后才能被 CPU 访问 特点：容量大、存取速度较慢、单位成本低 高速缓冲存储器 Cache 位于 CPU 和主存之间，用来存放当前 CPU 经常使用的指令和数据，以便 CPU 能高速地访问它们 存取速度可与 CPU 的速度相匹配 特点：存储容量小、价格高，现代计算机通常将它们制作在 CPU 中 按存储介质分类 磁表面存储器（磁盘、磁带） 磁芯存储器 半导体存储器 MOS 型半导体存储器（读写速度慢、集成度高、功耗小） SRAM、DRAM、非易失型 MOS 存储器（ROM） 双极型半导体存储器（读写速度快、集成度低、功耗大） 光存储器（光盘） 按存取方式分类 随机存储器 RAM (Ran ...

计算机发展历程本节内容已从大纲删除 计算机硬件的发展计算机的四代变化 第一代计算机 —— 电子管时代 逻辑元件采用电子管 使用机器语言进行编程 主存使用延迟线或磁鼓存储信息，容量极小 体积庞大，成本高 运算速度较低，一般只有几千次到几万次每秒 第二代计算机 —— 晶体管时代 逻辑元件采用晶体管 软件开始使用高级语言，如 FORTRAN，有了操作系统的雏形 主存使用磁芯存储器 运算速度提升到几万次到几十万次每秒 第三代计算机 —— 中小规模集成电路时代 逻辑元件采用中小规模集成电路 高级语言发展迅速，操作系统也进一步发展，开始有了分时操作系统 半导体存储器开始取代磁芯存储器 第四代计算机 —— 超大规模集成电路时代 逻辑元件采用大规模集成电路和超大规模集成电路，产生了微处理器 诸如并行、流水线、高速缓存和虚拟存储器等概念用在了这代计算机中 第五代计算机 —— 智能计算机 具备人工智能 运算速度极快 软件系统能够处理知识信息 神经网络计算机是智能计算机的重要代表 第六代计算机 —— 生物计算机与量子计算机 未来计算机发展的方向和趋势 1~4 代都采用冯·诺依曼体系结构（控制 ...

进程与线程进程的概念和特征 程序顺序执行的特征 顺序性 严格按序 封闭性 程序一旦开始运行，其结果不受外界因素影响 程序运行时独占各种资源，这些资源的状态（除初始状态外）只有本程序才能改变 可再现性 只要初始条件和执行环境相同 程序并发执行的特征 间断 程序间相互制约关系导致走走停停 失去封闭性 资源是共享的 不可再现性 失去封闭性导致的 引入进程的目的 更好地使多道程序并发执行，提高资源利用率和系统吞吐量，实现操作系统最基本的两个特性（并发性和共享性） 进程概念 —— “动态的” “过程性的” 程序的一次执行过程 一个程序及其数据在处理机上顺序执行时所发生的活动 具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位 进程映像/进程实体（组成） 程序段 相关数据段 原始数据、中间数据、结果数据 进程控制块 PCB (Process Control Block) 进程存在的唯一标志 常驻内存，系统通过控制 PCB 来控制进程 当进程被创建时，系统为它申请和构造一个相应的 PCB 撤销进程，实际上是撤销进程的 ...