[Learning]操作系统笔记

进程

作业，进程，线程，管程

1. 作业：用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合。它包括用户程序，所需要的数据及控制命令等。作业是由一系列有序的步骤组成的。

2. 进程：一个程序在一个数据集合上的一次运行过程。所以一个程序在不同数据集合上运行，乃至一个程序在同样数据集合上的多次运行都是不同的进程。

3. 线程：线程是进程中的一个实体，是被系统独立调度和执行的基本单位。

4. 管程：管程实际上是定义了一个数据结构和在该数据结构上的能为并发进程所执行的一组操作，这组操作能同步进程和改变管程中的数据。

进程间的通信如何实现

1. 信号：信号是Linux系统中用于进程之间通信或操作的一种机制，Linux提供了几十种信号，分别代表着不同的意义。信号可以在任何时候发送给某一进程，而无须知道该进程的状态。如果该进程并未处于执行状态，则该信号就由内核保存起来，知道该进程恢复执行并传递给他为止。如果一个信号被进程设置为阻塞，则该信号的传递被延迟，直到其阻塞被取消时才被传递给进程。

2. 信号量：是一个计数器，可以用来控制多个进程对共享资源的访问。它常作为一种锁机制，防止某进程正在访问共享资源时，其他进程也访问该资源。因此，主要作为进程间以及同一进程内不同线程之间的同步手段。

3. 消息队列：就是一个消息的链表，是一系列保存在内核中消息的列表。用户进程可以向消息队列添加消息，也可以向消息队列读取消息。优势是对每个消息指定特定的消息类型，接收的时候不需要按照队列次序，而是可以根据自定义条件接收特定类型的消息。

4. 共享内存：允许两个或多个进程共享一个给定的存储区，这一段存储区可以被两个或两个以上的进程映射至自身的地址空间中，一个进程写入共享内存的信息，可以被其他使用这个共享内存的进程，通过一个简单的内存读取错做读出，从而实现了进程间的通信。采用共享内存进行通信的一个主要好处是效率高，因为进程可以直接读写内存，而不需要任何数据的拷贝，对于消息队列等通信方式，则需要在内核和用户空间进行四次的数据拷贝，而共享内存则只拷贝两次：一次从输入文件到共享内存区，另一次从共享内存到输出文件。

互斥器（mutex）和临界区（critical section）

1. 互斥器：用于进程间互斥，慢。

2. 临界区：用于线程间互斥，快。

死锁的4个必要条件

1. 互斥条件：一个资源每次只能被一个进程使用。

2. 请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。

3. 不剥夺条件：进程已获得的资源，在未使用完之前，不能强行剥夺。

4. 循环等待条件：若干进程之间形成一种头尾相接的循环等待资源关系。

最出名的解决死锁的算法是银行家算法。

进程的3种状态

1. 就绪（Ready）：当进程已分配到除CPU以外的所有必要的资源，只要获得处理机便可立即执行。

2. 执行（Running）：当进程已获得处理机，其程序正在处理机上执行。

3. 阻塞（Blocked）：正在执行的进程，由于等待某个事件发生而无法执行时。

线程

线程与进程的差别

1. 进程间时独立的，这表现在内存空间，上下文环境上；线程运行在进程空间内。一般来讲（不使用特殊技术），进程无法突破进程边界存取其他进程内的存储空间；而线程由于处于进程空间内，所以同一进程所产生的线程共享同一内存空间。

2. 同一进程中的两段代码不能同时执行，除非引入线程。

3. 线程是属于进程的，当进程退出时该进程所产生的线程都会被强制退出并清除。线程占用的资源要少于进程。进程和线程都可以有优先级。

4. 进程间可以通过IPC通信，线程不可以。

什么是PE文件

可移植的执行体（Portable Execute）。常见的有EXE，DLL，OCX，SYS，COM。

定位DLL文件的默认顺序

1. 内存

2. KnownDLLs

3. 清单与.local

4. 应用程序目录

5. 当前工作目录

6. 系统目录

7. 路径变量

动态链接库与静态链接库

静态链接库（Static Libary）和动态链接库（DLL）都是共享代码的方式。如果采用静态链接库，lib中的指令都被直接包含在最终生成的exe文件中了。但若采用DLL，该dll不必被包含在最终exe中，exe文件执行时可以“动态”地引用和卸载这个与exe独立的dll文件。

静态链接库不能再包含其他动态链接库或静态库，而动态链接库中还可以再包含其他动态或静态库。

动态链接库允许可执行模块（.dll或.exe）仅包含在运行时定位dll函数的可执行代码所需要的信息。在静态链接库的使用中，链接器从静态链接库获取所有被引用的函数，并将库同代码一起放到可执行文件中。

内存

Windows内存管理的三种方式

页式管理

将各进程的虚拟空间划分为若干个长度相等的页。把内存空间按页的大小划分为片或者页面，然后把页式虚拟地址与内存地址建立一一对应的页表，并用相应的硬件地址转换机构来解决离散地址变换问题。页式管理采用请求调页和预调页技术来实现内外存存储器的统一管理。

优点：没有外碎片，每个内碎片不超过页的大小。

缺点：程序全部装入内存，要求有相应的硬件支持，如地址变换机构缺页中断的产生和选择淘汰页面等都要求有相应的硬件支持。增加了机器成本和系统开销。

段式管理

把程序按内容或过程函数关系分成段，每段有自己的名字。一个用户作业或者进程所包含的段对应一个二维线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换为实际内存物理地址。

优点：可以分别编写和编译，可以针对不同类型的段采取不同的保护，可以按段为单位来进行共享，包括通过动态链接进行代码共享。

缺点：会产生碎片。

段页式管理

系统必须为每个作业或者进程建立一张段表以管理内存分配与释放、缺段处理等。另外由于一个段又被划分为若干个页，每个段必须建立一张页表以把段中的虚页变换为内存中的实际页面。显然与页式管理时相同，页表也要有相应的实现缺页中断处理和页面保护等功能的表项。

优点：段页式管理是段式管理和页式管理相结合而成，具有两者的优点。

缺点：由于管理软件的增加，复杂性和开销也增加。另外需要的硬件以及占用的内存也有所增加，使得执行速度下降。

MMU（Memory Management Unit）负责从虚拟地址到物理地址转换。

地址类型

1. 物理地址：CPU通过地址总线的寻址，找到真实的物理内存对应地址。

2. 线性地址（虚拟地址）：在32位CPU架构下，可以表示4G的地址空间，用16进制表示就是0x00000000—0Xffffffff。

3. 逻辑地址：程序代码经过编译后出现在 汇编程序中地址。

CPU将一个逻辑地址转换为物理地址需要两步：

1. 首先CPU利用段式内存管理单元，将逻辑地址转换成线性地址；

2. 再利用页式内存管理单元，把线性地址转换为物理地址。

段式地址

16位CPU内部拥有20位地址线。寻址范围是1M。但是16位CPU的地址寄存器（IP，sp）只有16位。

逻辑地址=段基地址：偏移地址

线性地址=段基地址 * 16 + 偏移地址

页式地址

给定32位线性地址，地址转换步骤如下：

1. 装入进程的页目录地址（操作系统在调度进程时，把这个地址装入CR3）

2. 根据线性地址前十位，在页目录中，找到对应的索引项，即页表地址。

3. 根据线性地址中间十位，在页表中，找到对应的索引项，即页的起始地址。

4. 将页的起始地址与线性地址最后12位相加，等到物理地址。

其他注意事项

对用户而言，段式管理可以对内存有效利用，在汇编中体现在数据段，代码段等。
对计算机而言，页式管理可以提高内存的使用效率。多级页目录可以减少页索引所占用的内存。

Linux内存管理

简化了Intel的内存管理。有限度地使用了分段机制，所有的段基地址都是0，即每个段的逻辑地址和线性地址保持一致，而完整利用了分页机制。

一致性协议

分布式系统中常见的一致性协议有：两阶段提交协议，三阶段提交协议，向量时钟，Paxos协议。

两阶段提交协议（2PC）

两阶段提交协议（2PC），是比较常用的解决分布式事务问题的方式，要么所有参与进程都提交事务，要么都取消事务，即实现ACID中的原子性(A)的常用手段。

两阶段提交将提交过程划分为连续的两个阶段：表决阶段(Voting)和提交阶段(Commit)。假设在没有故障发生的情形下，两阶段提交协议由下列操作序列构成。

协调者的有限状态机如下：

协调者初始处于INIT状态，当接收到系统发出的Commit消息后，向参与者多播Vote-request消息后转入WAIT状态，在此进入阻塞状态，因为要等待所有参与者发送返回的消息，当收到所有参与者的返回消息后，如果其中包含Vote-Abort消息，则多播Global-abort消息后转入ABORT状态，否则多播Global-commit消息后转入COMMIT状态。

参与者的有限状态机如下：

参与者初始处于INIT状态，当接收到Vote-Request消息时，发出Vote-commit会转入READY状态，告诉协调者已经准备做好提交准备，否则就返回一个VOTE-ABORT消息。等待协调者行为，如果收到Global-Abort消息，就会进入Abort状态，如果收到Global-commit消息，就会转入COMMIT状态。

三阶段提交协议（3PC）

3PC就是在2PC基础上将2PC的提交阶段细分位两个阶段：预提交阶段和提交阶段。

向量时钟（Vector Clock）

通过向量空间祖先继承的关系比较, 使数据保持最终一致性,这就是向量时钟的基本定义。

下面给出一个场景来说明向量时钟的作用：

Vector Clock就是为了解决这种问题而设计的，简单来说，就是为每个商议结果加上一个时间戳，当结果改变时，更新时间戳。所以加上时间戳之后，我们再一次描述上面的场景，如下：

以上这个决策用到了向量时钟，有个图还比较清晰了说明整个过程

• Previous
  [Learning]剑指Offer
• Next
  [Learning]数据库笔记