10.4 前四章复(yu)习(xi)

前四章还没讲到操作系统

==目录：==

第一章 计算机体系架构

图灵机 2. 电子计算机的诞生 3. 存储程序计算机 4. 指令级架构

第二章 程序设计

1. 一个简单的程序 2. 内存访问 3. 外存访问 4. 子程序设计 5. 运行栈 6. 程序设计语言 7. 程序的链接

第三章 程序的运行

1. 程序的装入 2. 程序的执行 3. 中断响应 4. 运行时系统 5. 系统调用 6. 程序的终止

第四章 操作系统发展与形成

操作系统之前的人机交互 2. 批处理 3. 脱机输入输出 4. 多任务 5. 分时 6. 操作系统概念的形成 7. 操作系统内核 8. 内核之外 9. 操作系统结构 10. 操作系统的研发 11. 操作系统的安装与引导

第五章 CPU管理

1. 程序运行过程的描述 2. 多线程进程 3. 进程创建与撤销 4. CPU调度 5. CPU调度算法 6. 上下文切换 7. 进程通信

大概：

计算机体系架构（的发展历史）
程序设计（汇编原理层面上）
程序的运行（启动、运行、中断处理，其他软件的支持等）
操作系统的形成与发展（正式引入操作系统。我们并没有直接和操作系统打交道，而是通过程序与其打交道——操作系统就是为==应用程序==提供一个==运行平台==
操作系统可以==管理==以下内容（==重点==）：
1. CPU管理（第五章）
2. 内存管理（第六章）
3. 输入输出子系统（第七章）
4. 文件系统（第八章）
同步与互斥（新的特点，之前的程序都是顺序运行，没有考虑到程序之间的合作与干扰）
死锁（新特点）

第一章. 计算机体系架构（如今计算机体系架构逐渐发展起来的历史）

1. 图灵机

图灵把人的计算过程进行了形式化的描述，从而以此为基础设计计算机。

==图灵机==架构：存储带（纸带，用于输入输出），读写头（执行左移或者右移，判断读还是写操作），状态寄存器（保存当前状态），控制规则表（相当于一个程序，根据当前状态和读写头内容来决定新状态）

例子：==一进制加法==（详见ppt）

通用图灵机：将任意图灵机的输出和输入都能作为输入

2. 电子计算机的诞生

三个计算机

==阿塔纳索夫-贝利计算机==：第一台电子，全部用电子器件执行，用二进制运算，没有CPU，不可编程，不是图灵完备

==埃尼阿克计算机（ENIAC）==：第一台通用，算法硬化到机器，但是可以编程（重新链接线路），图灵完备

==UNIVAC I（通用自动计算机）==：第一台商用的

3. 存储程序计算机

==冯诺依曼==👍👍👍👍👍👍

第一台存储程序架构计算机==EDSAC==

照亮了工业化道路，软件与硬件分离

操作系统的功能：装入程序，管理软件与应用

装入程序，为什么要装入？

程序和数据都在外存中，需要装入内存
内存一般是容易丢失的，必须运行前装入

4. 指令集架构

不可编程的计算机：完全不行，重新造

可编程的计算机：修改程序需要修改电路或者重新装配，太麻烦

存储程序计算机：程序和数据放在存储器，成为软件👍程序猿软硬件分离👍软硬件之间需要一个界面——==指令集架构ISA==

指令集架构 Instruction Set Architecture

基本设计：

操作数保存——寄存器，主存，栈，累加器等
操作数个数——0,1,2,3
寻址方式——寄存器寻址，立即数寻址，间接寻址等
操作类型——加法减法乘法，位移等
访问外设的方式
...

ISA的发展

图灵机，简单的指令集，如读/写纸带，左/右移动
EDSAC计算机中，有14条指令，包含了算术运算、逻辑运算、转移、传送等指令，是图灵完备的
CISC——complex，复杂指令计算机，尽量使用硬件来实现功能，代表：==X86==，Intel和AMD都是生产x86架构的CPU
RISC——reduced，精简指令集计算机，降低指令数量，以软件来实现复杂功能。代表：==ARM，MIPS，RISC-V==

RISC-V

结构简单，==完全开源==，正方兴未艾

特权指令

内核模式下才能执行的指令，能对系统中的某些关键资源进行操作

第二章程序设计

1. 一个简单的程序

这段代码是用==汇编语言==写的

行数	解释
01	"#"开始，说明是注释，在0号地址开始（begins at address 0)
02	“.”开头的是伪指令（不会出现在可执行代码中），.pos 0表示当前位置往后的指令装到0号单元开始的位置上
03	iremovq 传送指令，`iremovq stack %rsp`将stack传送给rsp，设置一个栈指针（stack pointer）。==stack==是一个标识符，其值是他所在的位置对应的内存
04	`call main`调用main函数
05	`halt`停机，可以理解为返回操作系统
06
07	注释：4个元素的数组
08	`align 8`数组的名字就是数组的地址
09	==array:==
10	`.quad 0x000d000d000d`
11	...
12	...
13	...
14
15	==main：==
16	`irmovq array,%rdi`把array数组放入rdi寄存器（起始地址）
17	`irmovq $4,%rsi`把4放入rsi（元素数量）
18	call sum 调用子程序==#call sum(array,4)==
19	==ret==返回指令
20
21	#long sum(long *start, long count)
22	#start is rdi, count is rsi
23	==sum:==
24
25
26	==xorq %rax，%rax==相当于把rax清零
27
28
29
30
31

在进入main函数之前还有一段函数，在main中调用子程序sum

call 指令调用函数，两个功能：

call main把main的返回地址（halt指令）压到栈里面
call sum把sum的返回地址（ret指令）压到栈中

==有空再仔细看看ppt==

2. 内存访问

存储器：外存最大但是也最慢，寄存器最快但是最小，内存中等

寄存器用于CPU==运算==，内存用于CPU==直接访问==，外存（磁盘、U盘）用于CPU==间接访问==

因为数据的分布基于==局部性==，大部分的程序和数据都不是常用的，常用的总归是少数

物理地址

==内存==由一系列的内存单元组成，这些内存单元按照顺序编号（从0开始，连续的，线性的）
CPU通过这个编号访问内存单元，==这个编号==成为物理地址
物理地址是送到==内存地址总线==上的地址

==绝对代码==

使用的地址是==物理地址==，程序绑定在硬件上

生成方式：程序员编写，编译程序生成，汇编程序生成

特点：简单，直观；^{剩下的感觉都是劣势：}需要程序猿（编译程序）对硬件非常了解；不能跨平台，需要更新；程序独占全机内存；在多任务上的问题，需要分享内存，有安全性问题，系统分配内存，程序无法确定自己的内存位置

虚拟地址与虚拟地址空间

==MMU：内存管理单元（硬件）==

通过硬件操作（速度比较快）将程序中的地址转变为物理地址

虚拟地址：在程序中使用的是虚拟地址（自己看来地址从0开始），也是CPU从指令中解析出来的地址

==操作系统是内存（整个物理空间）的管理者，每个程序都需要操作系统来分配空间==

指令执行过程中进行的地址变换，是一个==硬件过程==，但是映射关系是由==操作系统==确定的

重定位：修改地址——是将程序内需要的地址进行修改

比如例子中500地址变成了10500地址

静态重定位：运行前进行的，比较耗时；装入时就确定了程序的位置，而且执行中是固定的不能更改的。==不需要MMU，而是操作系统利用软件方法进行重定位==

动态重定位：执行过程中进行的，==需要有硬件支持==（基地址寄存器base，限长寄存器limit，==MMU==）

3. 外存访问

IO设备

字符/块设备：随机/顺序，是/否按照地址访问

==随机访问就是按地址访问==，比如数组a[5],a[10],按照地址进行随机的访问，而顺序访问不行，比如链表

设备控制器

基本组成：总线缓冲器，IO端口，设备选择，控制逻辑等

端口就是一个设备的地址，有连接CPU，数据缓冲，状态数据，控制命令等命令。

IO接口的意义：输入输出标准化，计算和输入输出并行。

设备的地址

独立编址：IO指令的一般形式：操作码（in/out）+数据+端口地址

统一编址：将端口看做内存单元，与内存单元统一编制。这样CPU访问端口就像访问内存一样，不需要为CPU增加新的输入输出指令了

设备控制方式

==轮询：==一段循环程序，不听的检测控制器的某个显示设备状态的端口，直到发现外设工作完成

==中断：==外设完成后向CPU发送信号，然后执行中断处理

==DMA：==减少中断次数，直接访问内存，但是CPU就无法执行其他工作了

驱动程序：直接控制设备的程序

驱动程序属于==操作系统==的一部分 =^ . ^=

驱动程序是设备相关的，依赖于设备的
其他程序（应用程序）设备无关，不依赖设备

4. 子程序设计

基本问题：

调用前：==参数传递、保存返回地址==
转移：转移到子程序的第一条指令处（子程序的入口）
执行
返回：主程序中调用子函数的指令的下一条指令
调用规范：子程序调用过程是由一组操作在调用点按照特定的调用规范完成的

==早期实现==：

将返回地址放到调用规范规定的位置（比如子程序第一条指令的前面预留空单元，保存返回地址），这样子程序就知道返回地址的位置（自己已经保存好了），然后通过==链式结构==（电泳就形成一条链式结构，原路返回即可）
==call==指令，有专门的寄存器存放返回地址——缺点：无法进行递归，因为寄存器的返回地址内容会被覆盖。

==如今：子程序库==

公用的，抽象的

有标准接口：==应用程序接口（API）==，平时以库程序文件的形式单独存放，使用时与用户程序==链接==

5. 运行栈

==运行栈==

之前说道，call指令用寄存器储存返回地址会被覆盖，所以解决方法是：==用运行栈保存返回地址==——进入子程序，返回地址入栈；退出子程序，返回地址出栈

==栈帧==（stack frame）：为每个子程序在栈内分配的数据结构

储存有：

传递给子程序的参数，栈帧形成了调用者与被调用者之间的数据通道
返回地址
局部运行环境，如局部变量，寄存器的内容等

栈帧链：子程序的嵌套调用

每调用一次子程序，就会为该子程序分配一个栈帧，子程序返回后就会释放栈帧。父子程序的栈帧之间会形成链表，即栈帧链

^{10月4号23:26}

总而言之，每调用一次子程序，就会分配一块栈帧。

BP（或者叫EBP）是底部（高地址，一般画在上边），SP（或者叫ESP）是顶部（低地址，在下边，从这里删除或者添加数据）。

调用函数时，为子函数创建栈帧，接下来的都放进子函数栈帧里：如果有参数传递，先放==传递给子函数的参数==，然后是==主函数的地址==，再是==主函数的底部帧指针（基指针）EBP==，然后是==局部变量==，最后是==esp==

6. 程序设计语言

机器语言、汇编语言、高级语言

==机器语言==：硬件能直接理解的语言，ISA为程序猿提供的面向硬件的程序设计语言，形式：二进制代码

机器语言是软件与硬件的界面，CPU的好用程度很大程度取决于其提供的机器语言（例如有没有push和pop指令）

==汇编语言==：用==标识符==代替二进制编码，更容易理解、记忆和识别。汇编语言几乎和机器语言==一一对应==，编程风格和技术也没有本质的改进。提供了==伪指令==。

==高级语言==：独立于计算机，由专门的程序（编译程序，解释程序）转换为机器代码。

代码转换

graph
a[高级语言程序]---编译-->b[汇编语言程序]
b---汇编-->c[机器代码]
a--解释---->c

编译：静态的。一次编译，多次运行

解释：动态的。每次运行都要编译，和运行平台有关系

JIT编译（Just-In-Time compilation）

动态、编译（中间码==》机器码）

运行时系统 VS 程序库

运行时系统（runtime）

编译程序不仅要把程序语句翻译成机器代码，还要为程序的运行提供一定的==管理工作==，这部分代码就是所谓的==运行时系统==

程序库

普通的程序库：程序主动调用，来完成某些用户的意图

运行时系统：对程序的运行起支持作用，不是用户程序主动调用的

脚本语言

解释语言（shell，html等）

脚本程序语句更像是一条条指令，脚本程序就是将一组命令打包在一个文件中，一条条执行命令

7. 程序的链接

模块化程序设计——程序功能划分为独立部分，每个部分完成一个独立的功能。

大型程序的组织形式：程序和数据分散在若干文件中，每个程序文件包含若干子程序和全局变量，看做一个模块。还可以放在不同子目录下。

模块设计：

首先进行划分，然后基于接口，仅考虑模块自身进行设计。每个模块都有编译的必要性，但是带哪个模块不能运行，必须将所有模块连接起来才能生成可执行文件。

编译时，符号名被赋予一个地址，即在目标文件地址空间中的偏移量。连接时，符号名的地址即==模块的起始地址+该符号的偏移地址==

==地址回填==

链接要做的就是在引用的地方填上==新地址==，可以通过==链表法和间接地址法==

链表法

建一个链表，记住所有引用的位置，地址确定后回填

间接地址法

一个储存单元，存放x地址，对x引用时，间接访问该单元，地址确定后，回填该单元即可。

==链接的时机==

静态链接

程序运行前就全部链接起来，问题：可执行文件复制了所有程序，任何程序更新都需要重新链接，不能程序共享。

动态链接

推迟到不得不链接的时候才去链接，即==使用某模块时再去链接==

==可执行文件==

由多个部分（节，section）组成，目标文件合并而来，方便装入程序。包含有代码和常量（只读）

可执行文件包含：初始化的全程数据

不包含：栈、未初始化的数据

目标文件结构(节为单位)	可执行文件结构（段为单位）
ELF文件头表(Header table)	ELF文件头表
节头表(Section header table)	节头表
	程序头表(Program header table)

目标文件结构(==节==为单位)

可执行文件结构（==段==为单位，段是相似节的合并，仅在可执行文件中）

^{10月6号21:11}

第三章程序的运行

1. 程序的装入

将程序==装入==到可执行文件中，然后进行程序的==链接==

可执行文件的作用：

存放代码和数据（其中代码和数据并不是运行的状态，需要经过“装入”操作，即在内存中展开成工作时的模样才能运行。之所以不直接按照工作模样储存，目的是为了==节省储存空间==）

==装入==：最早是装入物理内存

现在是指

把程序装入虚拟地址空间，仅仅是规划，没有真的装入物理地址空间（但是规划了就认为已经装进去了，可以运行了）
运行时装入物理内存，哪里有空放那里。每个程序都有一个内存映像，每个程序在物理内存都有一个映射，但是CPU取出来的时候是虚拟地址空间

地址变换

虚拟地址到物理地址的变换，是硬件关系，但是是按照操作系统的要求，操作系统规定了地址变换的规则

3.2 程序的执行

程序的执行其实是==指令流==的执行。

从人的角度来说，程序可以有顺序，循环，条件，子程序等，但是从CPU角度来说，指令其实就是程序计数器PC的不断前进。

指令流的==连续性==，一般可以指一条指令的执行结果往往是后一条指令的输入，比如两数相加后，数据留在寄存器中，以便于下一条指令使用。

指令流的==运行环境==是指==上一条指令留下的全部信息，CPU寄存器的信息，内存以及设备的信息等==

异常一般有==溢出，除数为0，非法访问内存==等。通过CPU检测并发出警告。

可以简单的将异常分为可修复的和不可修复的：

可修复的异常：除数为0时的异常，可以将结果用NaN表示（Not a Number）；页错误的异常，可以通过页置换处理。

不可修复的异常：“整数运算中除数为0，这意味着程序中的逻辑错误 或非法操作码、地址越界”一般直接终止程序的运行。

🖐🖐ppt上说，“除数为0，处理方法：将指令的执行结果用特殊的值表示，如NaN(Not a Number)，继续执行”，这是==可修复的异常==，不过在==不可修复==的异常中，也有“整数运算中除数为0，这意味着程序中的逻辑错误”这种，都是除数为零，需要判断一下是不是逻辑出现了错误。如果逻辑错误则终止执行。

try{……}, catch(){……}也是处理异常的代码

•==UNIVAC==计算机处理异常的方式

用户程序执行前在0号单元存放一对指令；一旦出现异常，CPU暂停当前的指令执行序列,转去执行0号单元中的那两条指令;这两条指令可能会去执行另外的程序，也可能不发生转移而继续执行原先的指令序列，这由程序员设计决定

• 异常处理的意义

CPU可以执行多个不同的代码序列，从容地在多个代码序列之间进行切换

陷入（trap）是人为主动寻求帮助，比如==断点调试 int 3指令==和==系统调用 trap指令==

int 3指令相关链接

中断与子程序调用实际上很相似，但是指令不同，运行环境不同，完成的任务不同，而且==防止遭到破坏==。

3.3 中断响应

3.4 运行时系统

3.5 系统调用

3.6 程序的终止

第五章部分内容：

扩展：

　　长期调度(long-term scheduling)又叫做高级调度(High-level scheduling)或作业调度(job scheduling), 负责决定在系统中，允许哪些进程主动竞争系统资源。这个级别有时也称为准入调度，因为决定了多道程序设计的道数，也就是在一个给定的时刻，系统中的进程总数。太多的进程进入到系统，可能使系统资源饱和，造成性能降低。在这种情况下，高级调度策略可以决定临时性地禁止新作业进入，直到其他作业完成。

　　中期调度(medium-term scheduling)又叫做中级调度(intermediate-level scheduling)，一个作业被长期调度策略准许进入到系统之后，将由中期调度策略决定允许哪些进程竞争处理器。该策略要相应系统负荷的短期波动。系统超载时，中期调度程序可以禁止进程进入短期调度；当系统恢复正常时，则允许这些进程继续。

　　短期调度(short-term scheduling)又叫做低级调度(low-level scheduling), 决定了在有一个可用的处理器时，系统将哪个处于就绪状态的进程分配给该处理器。

　　在当今的系统中，短期和中期调度程序是唯一的调度程序（在这种情况下，作业初始化由中期调度程序执行）. 长期调度程序通常只有执行批处理的大型主机系统才会采用。

　　短期调度策略通常为每个进程都分配一个优先级，这个优先级反映了进程的重要性——进程越重要，月容易被调度策略选中成为下一个要执行的进程。短期调度程序（也成为分派程序(dispatcher)还要将一个处理器分配给选中的进程。分派程序每秒钟要工作许多次，所以始终都存在与主内存当中。

第八章文件系统

8.1 文件

文件是由==操作系统==管理的，在==外存==上的，数据的逻辑单元。

访问外存的方式是==按名存取==，文件有名字和数据，只关心存入什么和取出什么。

文件的逻辑结构是程序猿看到的文件组织形式，是对外存的抽象表示；而物理结构是指文件的存放方式，程序看不到。

逻辑结构可以有记录结构，索引结构，字节流结构等

文件由{==文件名==；==文件控制块FCB==（描述部分，文件的属性如文件位置、文件大小、建立日期、访问权限等）；==数据部分==}

文件类型可以从：

逻辑结构：有字节流、记录结构的区分
从操作系统管理的角度：普通文件、目录文件、设备文件
从应用层面：.doc、.pdf、.xls 等

文件的访问不仅有打开、关闭、读、写，还有插入、删除、移动读写指针等…

可以顺序访问，随机访问（按照地址访问，也就是按照字节编制的==偏移量==），或者指定读写位置，按照当前的读写指针