操作系统相关知识

进程

多进程如何组织

使用PCB+状态+队列进行组织

进程的状态：新建 就绪 运行 阻塞 终止

使用每个状态的列表进行组织，这样就完成了进程的调用。

多进程如何交替执行？

1. 启动磁盘读写
2. pCur.state=’W’
3. 把当前进程的PCB放到WaitQueue
4. schedule()

其中schedule函数:

schedule(){
    //其中找到的是进程的进程控制块PCB
    pNew=getNext(ReadQueue);
    switch_to(pCur,pNew);
}

多进程间的影响怎么解决？

多进程之间进行运行的时候会出现这种情况：

即线程A使用了地址为0x1000的地址，那么进程B也使用了0x1000的地址，这样的话进程A就可能破坏B进程中的数据导致B程序崩溃，这时候我们就想了一个办法，使用地址变换机构将每个进程之间的地址进行隔离，这样做到多进程之间没有影响。即进行内存空间管理

使用地址映射机构，可以使得每个变量虽然具有相同的逻辑地址，但是被映射到不同的物理内存地址，这样的话使相应的进程没有地址使用上冲突。

多进程如何进行合作？

为了防止多进程对共享资源的使用出现竞争导致出现问题，提出了锁的概念，通过使用锁来实现进程间顺序的推进。

线程为什么使用起来代价比较小？

因为进程之间的切换回涉及到PCB的切换，进程=资源+指令进程是拥有着操作系统的资源的（内存），因为进程间的切换要涉及到资源映射表的使用，而使用线程的话不需要进行资源映射表的切换使用，所以线程比进程的切换代价更小。

内核级线程切换过程

1. 首先用户通过运行系统调用的函数，比如fock()函数
2. fork()函数会 执行Int 0x80 中断处理，0x80是系统调用的入口，以此入口进入int 0x80的系统调用函数
3. 将用户态程序SS:ip压入到内核栈，然后执行systemCall(systemCall即系统调用的入口函数)
4. 进入中断的处理函数，将用户态寄存器的信息压栈。然后去执行sys_fork()函数
5. 执行sys_fork()函数的时候可能阻塞，操作系统就会去调度。

进程调度

操作系统中进程调度策略有哪几种？

批处理系统

• FCFS(先来先服务，队列实现，非抢占的)：先请求CPU的进程先分配到CPU

• SJF(最短作业优先调度算法)：平均等待时间最短，但难以知道下一个CPU区间长度

• 最短剩余时间优先 （SRTN）最短作业优先的抢占式版本，按剩余运行时间的顺序进行调度。 当一个新的作业到达时，其整个运行时间与当前进程的剩余时间作比较。如果新的进程需要的时间更少，则挂起当前进程，运行新的进程。否则新的进程等待。

交互式系统

• 优先级调度算法(可以是抢占的，也可以是非抢占的)：优先级越高越先分配到CPU，相同优先级先到先服务，存在的主要问题是：低优先级进程无穷等待CPU，会导致无穷阻塞或饥饿；解决方案：老化
• 时间片轮转调度算法(可抢占的)：队列中没有进程被分配超过一个时间片的CPU时间，除非它是唯一可运行的进程。如果进程的CPU区间超过了一个时间片，那么该进程就被抢占并放回就绪队列。
• 多级队列调度算法：将就绪队列分成多个独立的队列，每个队列都有自己的调度算法，队列之间采用固定优先级抢占调度。其中，一个进程根据自身属性被永久地分配到一个队列中。
• 多级反馈队列调度算法：与多级队列调度算法相比，其允许进程在队列之间移动：若进程使用过多CPU时间，那么它会被转移到更低的优先级队列；在较低优先级队列等待时间过长的进程会被转移到更高优先级队列，以防止饥饿发生。

进程间通信方法

• 管道（pipe）及命名管道（named pipe）：管道可用于具有亲缘关系的父子进程间的通信，有名管道除了具有管道所具有的功能外，它还允许无亲缘关系进程间的通信；
• 消息队列：消息队列是消息的链接表，它克服了上两种通信方式中信号量有限的缺点，具有写权限得进程可以按照一定得规则向消息队列中添加新信息；对消息队列有读权限得进程则可以从消息队列中读取信息；
• 共享内存：可以说这是最有用的进程间通信方式。它使得多个进程可以访问同一块内存空间，不同进程可以及时看到对方进程中对共享内存中数据得更新。这种方式需要依靠某种同步操作，如互斥锁和信号量等；
• 信号量：主要作为进程之间及同一种进程的不同线程之间得同步和互斥手段；
• 套接字：这是一种更为一般得进程间通信机制，它可用于网络中不同机器之间的进程间通信，应用非常广泛。

操作系统对内存的管理

分段管理

为什么要用分段管理

1. 方便编程：用户可以把自己的作业按照逻辑关系划分为若干个段，而且每一个段的地址都是从0开始编址的，并且具有自己的段名和长度。逻辑地址是由段名（段号）和段内偏移量（段内地址）组成的。
2. 信息共享：在实现对程序和数据的共享时，是以信息的逻辑单位为基础的，而段恰恰是这样的逻辑单位（页只是存放信息的物理块，并无实际的含义）。
3. 信息保护：在实现对信息的保护时，也是以信息的逻辑单位为基础的。
4. 动态增长：在实际的应用中，有些段（数据段）会随着程序的运行而不断的动态增长，而且事前不知道数据段会增长到多大。
5. 在运行时动态链接中，主程序会在运行过程中调用某段时才将该段调入内存并进行链接。可见运行时动态链接也要求以段作为内存管理单位。
6. 方便管理，如果不采用分段管理的话，那么我们运行一个程序要把整个程序装入内存，但是使用分段管理的话我们就可以让不同的段分别进行内存的装入，这样的话我们就可以更加高效的使用内存。

内存分区的两种方式

分区即对内存进行区域的划分，其中可变分区需要对内存已经使用的部分和未使用的部分进行记录。其中有两种方法：

1. 固定分区的方法 对内存进行等大小的划分，这显然是不合理的，有些应用使用比较大块的内存，有些应用使用比较小的内存，这样划分的话可能导致太耗内存的应用无法装入，小的内存才能运行。
2. 可变分区的方法 对内存进行记录，此时需要记录内存的哪些地址已经使用，哪些地址没有被使用。

当然可变分区还要选择与之相应的算法，比如，有两块大小不同的区域，一个区域是10K，另一个空闲区域是100K，此时来了一个需要内存为7K的程序，应该怎样使用。

可变分区的问题

内存碎片 即现在内存并没有用完，只是在划分的过程中因为不合理的划分导致没有一块连续的内存可以给应用程序使用，如果发生这种情况的话那我们就需要进行内存紧缩，即把使用过的内存忘一起放，留下来一块整体的内存结构，如下图所示：

但是这样的内存紧缩是非常耗费操作系统资源的，对每段内存的移动还需要修改对应的内存记录的值，此外对数据的移动也是非常耗费时间的，而且在此期间我们不能运行任何的应用程序。这对操作系统是及其不友好的，那么这样的话我们就要使用分页的方法进行内存的分配。

分页管理

我们把程序分成等长的小块。这些小块叫做“页（Page）”，同样内存也被我们分成了和页面同样大小的”页框（Frame）“，一个页可以装到一个页框里。在执行程序的时候我们根据一个页表去查找某个页面在内存的某个页框中，由此完成了逻辑到物理的映射。

多级页表为什么省内存

做个简单的数学计算，假设虚拟地址空间为32位（即4GB）

每个页面映射4KB以及每条页表项占4B：

• 一级页表：进程需要1M个页表项（4GB / 4KB = 1M, 2^20个页表项），即页表（每个进程都有一个页表）占用4MB（1M * 4B = 4MB）的内存空间。

• 二级页表：一级页表映射4MB（2^22）、二级页表映射4KB，则需要1K个一级页表项（4GB / 4MB = 1K, 2^10个一级页表项）、每个一级页表项对应1K个二级页表项（4MB / 4KB = 1K），这样页表占用4.004MB（1K * 4B + 1K * 1K * 4B = 4.004MB）的内存空间。

如果以这种方式去理解，那么多级页表反而使用了更多的内存空间。

我们反过来想，每个进程都有4GB的虚拟地址空间，而显然对于大多数程序来说，其使用到的空间远未达到4GB，何必去映射不可能用到的空间呢？

也就是说，一级页表覆盖了整个4GB虚拟地址空间，但如果某个一级页表的页表项没有被用到，也就不需要创建这个页表项对应的二级页表了，即可以在需要时才创建二级页表。做个简单的计算，假设只有20%的一级页表项被用到了，那么页表占用的内存空间就只有0.804MB（1K * 4B + 0.2 * 1K * 1K * 4B = 0.804MB）

段页内存管理

段页式存储组织是分段式和分页式结合的存储组织方法，这样可充分利用分段管理和分页管理的优点。

　 (1) 用分段方法来分配和管理虚拟存储器。程序的地址空间按逻辑单位分成基本独立的段，而每一段有自己的段名，再把每段分成固定大小的若干页。

(2) 用分页方法来分配和管理实存。即把整个主存分成与上述页大小相等的存储块，可装入作业的任何一页。程序对内存的调入或调出是按页进行的。但它又可按段实现共享和保护。

(3) 逻辑地址结构。一个逻辑地址用三个参数表示：段号S；页号P；页内地址d。

4）段表、页表、段表地址寄存器。为了进行地址转换，系统为每个作业建立一个段表，并且要为该作业段表中的每一个段建立一个页表。系统中有一个段表地址寄存器来指出作业的段表起始地址和段表长度。

虚拟内存

虚拟内存的目的是为了让物理内存扩充成更大的逻辑内存，从而让程序获得更多的可用内存。

为了更好的管理内存，操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。当程序引用到不在物理内存中的页时，由硬件执行必要的映射，将缺失的部分装入物理内存并重新执行失败的指令。

页面如何换入

对于用户而言，用户看到的是一个整体的内存入4G，而且用户可以随便访问4G内存空间的任意位置；但是对于真实的物理内存可能只有1G大小，当用户访问内存时，如果内存里面有需要的内容，就直接访问；如果没有，就去磁盘上查找，然后再把需要找到的数据，再将这些数据载入到内存中供用户使用。那么在这个过程中就需要把磁盘上的数据写到内存里面（换入），也需要把内存中的一些数据写回磁盘上（换出）。

请求调页（换入）

当用户访问一个页时，MMU回去查询一个操作系统维护的页表，看看用户访问的页是否存在于内存当中，如果存在，就直接调用；如果没有，就需要开启中断，执行页错误处理程序，在磁盘中找到相应的数据页，并在内存中找到一块空闲，将其载入进来，然后中断返回，执行用户程序，在去访问内存中用户需要的页。

页面换出

当我们不断地将页面换入内存当中，内存肯定会不足的，我们需要选择一些页面进行换出，为新的数据腾出空间，但是我们应该选择那些页面换出呢？以下主要讨论一些常用的换出策略。

FIFO：先进先出页面置换

访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理块1	7	7	7	2		2	2	4	4	4	0			0	0			7	7	7
物理块2		0	0	0		3	3	3	2	2	2			1	1			1	0	0
物理块3			1	1		1	0	0	0	3	3			3	2			2	2	1
缺页否	√	√	√	√		√	√	√	√	√	√			√	√			√		√

优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

最近最久未使用(LRU)置换算法

访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理块1	7	7	7	2		2		4	4	4	0			1		1		1
物理块2		0	0	0		0		0	0	3	3			3		0		0
物理块3			1	1		3		3	2	2	2			2		2		7
缺页否	√	√	√	√		√		√	√	√	√			√		√		√

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

最佳置换算法(OPT)

最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。

访问页面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理块1	7	7	7	2		2		2			2			2				7
物理块2		0	0	0		0		4			0			0				0
物理块3			1	1		3		3			3			1				1
缺页否	√		√	√		√		√			√			√				√

第二次机会算法(SCR)

FIFO 算法可能会把经常使用的页面置换出去，为了避免这一问题，对该算法做一个简单的修改：

当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

我们用循环队列组织这个结构更加合适

对于SCR算法，有一个问题，就是程序是具有局部性的，所以经常出现在替换间期内每一页都被访问过，当需要替换时，每一页的引用位都是1，这样每次被替换出去的就是指针所指的那一页，从而退化成了FIFO算法。

Clock算法

SCR算法中的问题原因就是替换期间比较长，在这个期间内每页都被访问了，那么解决方式就是引入一根更新指针，每隔一段时间，把所有页的引用位设置为0，通过这样的防止SCR算法的退化。