进程的地址空间按照程序自身的逻辑关系划分为若干个段,每个段都有一个段名(在低级语言中,程序员使用段名来编程),每段从0开始编址。以段为单位进行分配,每个段在内存中占据连续空间,但各段之间可以不相邻，与 “分页” 最大的区别就是离散分配时所分配地址空间的基本单位不同 由于是按逻辑功能模块划分，用户编程更方便，程序的可读性更高 1. 逻辑地址结构分段系统的逻辑地址结构由段号（段名）和段内地址（段肉偏移量）所组成。如: 31 $\cdots\cdots$ 16 15 $\cdots\cdots$ 0 段号 段内地址 段号的位数决定了每个进程最多可以分几个段，段内地址位数决定了每个段的最大长度是多少 若系统是按字节寻址的，段号占16位，因此在该系统中，每个进程最多有 $2^{16}=64K$个段，段内地址占16位，因此每个段的最大长度是 $2^{16}=64KB$。 2. 段表程序分多个段,各段离散地装入内存,为了保证程序能正常运行,就必须能从物理内存中找到各个逻辑段的存放位置。为此,需为每个进程建立一张段映射表,简称 “段表”。 每个段对应一个段表项，其 ...

基本分页存储管理的思想:把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分 1. 分页思想将内存空间分为一个个大小相等的分区(比如: 每个分区 4 KB)，每个分区就是一个 “页框”，每个页框有一个编号，即 “页框号”，页框号从 0 开始。 将用户进程的地址空间也分为与页框大小相等的一个个区域，称为 “页” 或 “页面” 。每个页面也有一个编号，即“页号”，页号也是从 0 开始。 注: 进程的最后一个页面可能没有一个页框那么大。因此，页框不能太大，否则可能产生过大的内部碎片 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。 各个页面不必连续存放，世不必按先后顺序来，可以放到不相邻的各个页框中。 2. 地址转换逻辑地址为80 的内存单元: 应该在1号页，该页在内存中的起始位置为 450，逻辑地址为 80 的内存单元相对于该页的起始地址而言，”偏移量” 应该是 30。实际物理地址 = 450 + 30 = 480 要算出逻辑地址对应的页号 页号=逻辑地址/页面长度 ...

在多道程序系统中,进程的数量往往是多于处理机的个数的,这样不可能同时并行地处理各个进程。处理机调度,就是从就绪队列中按照一定的算法选择一个进程并将处理机分配给它运行,以实现进程的并发执行。 当有一堆任务要处理,但由于资源有限,这些事情没法同时处理。这就需要确定某种规则来决定处理这些任务的顺序 1. 高级调度(作业调度)由于内存空间有限,有时无法将用户提交的作业全部放入内存,因此就需要确定某种规则来决定将作业调入内存的顺序。 高级调度(作业调度)。按一定的原则从外存上处于后备队列的作业中挑选一个(或多个)作业,给他们分配内存等必要资源,并建立相应的进程(建立PCB),以使它(们)获得竞争处理机的权利。 高级调度是辅存(外存)与内存之间的调度。每个作业只调入一次,调出一次。作业调入时会建立相应的PCB,作业调出时才撤销PCB。高级调度主要是指调入的问题,因为只有调入的时机需要操作系统来确定,但调岀的时机必然是作业运行结束才调出 2. 中级调度(内存调度)引入了虚拟存储技术之后,可将暂时不能运行的进程调至外存等待。等它重新具备了运行条件且内存又稍有空闲时,再重新调入内存。 这 ...

CPU 无法直接控制 IO 设备的机械部件，因此 IO 设备还要有个电子部件作为 CPU 和 IO 设备机械部件之间的”中介”，用于实现 CPU 对设备的控制。这个电子部件就是 IO 控制器，又称为设备控制器。CPU 可控制 IO 控制器，IO 控制器来控制设备的机械部件。 1. 脱机技术手工操作阶段：主机直接从 I/O 设备获得数据，由于设备速度慢，主机速度很快。人机速度矛盾明显，主机要浪费很多时间来等待设备 批处理阶段引入了脱机输入/输出技术了用磁带完成）: 引入脱机技术后，缓解了 CPU 与慢速 I/O 设备的速度矛盾。另一方面，即使 CPU 在忙碌，也可以提前将数据输入到磁带：即使慢速的输出设备正在忙碌，也可以提前将数据输出到磁带。 为什么称为“脱机”? 一一脱离主机的控制进行的输入/输出操作。 2. SPOOLing“假脱机技术”，又称 “SPOOLing 技术” 是用软件的方式模拟脱机技术。SPOOLing 系统的组成如下: 在磁盘上开辟出两个存储区域一一”输入井”和”输出井” 2.1.输入井输入井模拟脱机输入时的磁带，用于收容 I/O 设备输入 ...

一、概述Parser 模块生成的 Unresolved LogicalPlan 仅仅是一种数据结构，不包含任何数据信息。Analyzer 模块使用事先定义好的规则(Rule)以及 Catalog 等信息对未解析的逻辑计划 Unresolved Logical Plan 进行补充和替换 logicalPlan 中的各个节点，让语法树包含元数据信息。 二、实现Analyzer 的父类是 RuleExecutor，所以，调用 Analyzer 的 $apply()$ 方法时，实际上会调用 RuleExecutor 的 $apply()$ 方法中，并传入一个 Unresolved LogicalPlan。 2.1. RuleExecutorAnalyzer 模块中 RuleExecutor 为 Analyzer，Analyzer 调用 $executeAndCheck$ 方法执行模块规则批次～ 123456789101112131415def executeAndCheck(plan: LogicalPlan, tracker: QueryPlanningTracker): Logical ...

MapReduce 1.x 的架构是主从架构。一个 JobTracker[主节点] 带多个 TaskTracker[从节点]，从节点通过向主节点发送心跳信息来告诉它自己的运行情况，而主节点则是负责管理调度的工作。 1. 设计架构1.1. Hadoop 1. xMapReduce1 的架构是主从架构。一个 JobTracker[主节点] 带多个 TaskTracker[从节点]，从节点通过向主节点发送心跳信息来汇报自己的健康情况和作业运行情况，而主节点则是负责管理调度的工作。 MapReduce 1.X 的架构如图所示，由 Client[客户端]、JobTracker[作业跟踪器]、TaskTracker[任务跟踪器]、Task[任务]组成。 1.1.1. JobClient用户编写的 MapReduce 程序通过 JobClient 提交给 JobTracker。 1.1.2. JobTrackerJobTracker 主要负责集群资源管理和作业调度，并且监控所有 TaskTracker 的健康情况，一旦有失败情况发生，就会将相应的任务分配到其他结点上去执行。 1.1.3. T ...

一、概述从 SQL 语句的解析一直到提交之前，上述整个转换过程都在 Spark 集群的 Driver 端进行，不涉及分布式环境。SparkSession 类的 sql 方法调用 SessionState 中的各种对象，包括上述不同阶段对应的 SparkSqlParser 类、Analyzer 类、Optimizer 类和 SparkPlanner 类等，最后封装成一个 QueryExecution 对象。因此，在进行 Spark SQL 开发时，可以很方便地将每一步生成的计划单独剥离出来分析。 二、实现2.1. executedPlan经过 Analyzer 的处理，Unresolved LogicalPlan 解析为 Analyzed LogicalPlan。Analyzed LogicalPlan 中自底向上节$QueryExecution.executedPlan$～， 123456lazy val executedPlan: SparkPlan = { assertOptimized() // 逻辑优化 executePhase(QueryPlanningTrac ...

一、概述数据处理首先需要考虑如何表示数据。对于关系表来讲，通常操作的数据都是以 “行” 为单位的。在 SparkSQL 内部实现中， InternalRow 就是用来表示一行行数据的类。此外，InternalRow 中的每一列都 是 Catalyst 内部定义的数据类型。 二、结构从类的定义来看，InternalRow 作为一个抽象类，包含 $numFields()$ 和 $update$ 方法，以及各列数据对应的 $get$ 与 $set$ 方法，但具体的实现逻辑体现在不同的子类中。 需要注意的是， InternalRow 中都是根据下标来访问和操作列元素的。 三、InternalRow 继承体系 3.1. BaseGenericInternalRow同样是一个抽象类，实现了 InternalRow 中定义的所有 get 类型方法，这些方法的实现都通过调用类中定义的 genericGet 虚函数进行 3.1.1. GenericInternalRow使用数组作为底层存储的 InternalRow 实现。 1def this(size: Int) = th ...

一、概述Expression 是 Catalyst 中的表达式体系。 二、实现在 Expression 类中，主要定义了包括基本属性、核心操作、输入输出、字符串表示和等价性判断 核心操作 $eval$ 函数实现了表达式对应的处理逻辑，也是其他模块调用该表达式的主要接口，而 $genCode$ 和 $doGenCode$ 用于生成表达式对应的 Java 代码。字符串表示用于查看该 Expression 的具体内容，如表达式名和输入参数等。 2.1. 属性2.1.1. deterministic标记表达式是否为确定性的，即每次执行 $eval$ 函数的输出是否都相同。如果在固定输入值的情况下返回值相同，该标记为true；如果在固定输入值的情况下返回值是不确定的，则说明该 expression 是不确定的，deterministic 参数应该为 false。 1lazy val deterministic: Boolean = children.forall(_.deterministic) 2.1.2. _references表示该 Expression 中会涉及的属性值 ...

一、概述Spark SQL 逻辑计划在实现层面被定义为 LogicalPlan 类。LogicalPlan 作为数据结构记录了对应逻辑算子树节点的基本信息和基本操作，包括输入输出和各种处理逻辑等。 二、实现LogicalPlan 属于 TreeNode 体系，继承自 QueryPlan 父类。 2.1. 结构LogicalPlan 继承自 QueryPlan，包含了两个成员变量和多个方法。 2.1.1. 成员变量 resolved，用来标记该 LogicalPlan 是否为经过了解析 canonicalized，重载了 QueryPlan 中的对应赋值，默认实现消除了子查询别名之后的 LogicalPlan。 三、继承体系LogicalPlan 仍然是抽象类，根据子节点数目，绝大部分的 LogicalPlan 可以分为 3 类，即叶子节点 LeafNode 类型(不存在子节点)、一元节点 UnaryNode 类型(仅包含一个子节点)和二元节点 BinaryNode 类型(包含两个子节点)。此外，还有几个子类直接继承自 LogicalPlan，不属于这 3 种类型。 3.1. ...