阅读笔记--现代操作系统

1. 操作系统面试

1.https://www.nowcoder.com/discuss/325668?type=all&order=time&pos=&page=1&channel=1005&source_id=search_all

2. 同步、异步、阻塞与非阻塞

1. 同步与异步，阻塞与非阻塞的关系
2. 聊聊同步、异步、阻塞与非阻塞

2.1 基本概念

2.1.1 同步和异步

所谓同步就是一个任务的完成需要依赖另外一个任务时，只有等待被依赖的任务完成后，依赖的任务才能算完成，这是一种可靠的任务序列。要么成功都成功，失败都失败，两个任务的状态可以保持一致。

所谓异步是不需要等待被依赖的任务完成，只是通知被依赖的任务要完成什么工作，依赖的任务也立即执行，只要自己完成了整个任务就算完成了。至于被依赖的任务最终是否真正完成，依赖它的任务无法确定，所以它是不可靠的任务序列。

2.1.2 消息通知

异步的概念和同步相对。当一个同步调用发出后，调用者要一直等待返回消息（结果）通知后，才能进行后续的执行；当一个异步过程调用发出后，调用者不能立刻得到返回消息（结果）。实际处理这个调用的部件在完成后，通过状态、通知和回调来通知调用者。

这里提到执行部件和调用者通过三种途径返回结果：状态、通知和回调。使用哪一种通知机制，依赖于执行部件的实现，除非执行部件提供多种选择，否则不受调用者控制。

2.1.3 比喻

举个例子，比如我去银行办理业务，可能会有两种方式：

1. 选择排队等候；
2. 另种选择取一个小纸条上面有我的号码，等到排到我这一号时由柜台的人通知我轮到我去办理业务了；

第一种：前者(排队等候)就是同步等待消息通知，也就是我要一直在等待银行办理业务情况；

第二种：后者(等待别人通知)就是异步等待消息通知。在异步消息处理中，等待消息通知者(在这个例子中就是等待办理业务的人)往往注册一个回调机制，在所等待的事件被触发时由触发机制(在这里是柜台的人)通过某种机制(在这里是写在小纸条上的号码，喊号)找到等待该事件的人。

2.2 阻塞与非阻塞

阻塞和非阻塞这两个概念与程序（线程）等待消息通知(无所谓同步或者异步)时的状态有关。也就是说阻塞与非阻塞主要是程序（线程）等待消息通知时的状态角度来说的。

2.2.1 概念描述

阻塞调用是指调用结果返回之前，当前线程会被挂起，一直处于等待消息通知，不能够执行其他业务。函数只有在得到结果之后才会返回。

2.3 举个例子

小明下载文件的例子

1. 聊聊同步、异步、阻塞与非阻塞

2.4 总结

同步/异步和阻塞/非阻塞是完全不同的概念。同步不能和阻塞画等号(只能说同步往往是阻塞的)，是不是阻塞咱们可以通过判断此刻主线程处于什么状态来判断。比如：在NIO中，我们有一种的多路复用模式。概念就是：我们不是采用一个线程去负责一个socket的方式，如果那样一定是阻塞的。我们采用一个线程管理多个socket的方式，该线程不断轮询所有socket，我们叫做Selector,通过select()方法，我们可以找到某一时刻真正需要io资源的socket，避免资源浪费。那么此时，我们的主线程是一直处于running状态的，因为他在不断轮询，但它同时又是非阻塞的，因为没有处于等待状态。

同时异步也不一定是非阻塞的（只能说异步常常是非阻塞的），例如我们往线程池里面提交任务的时候，调用Future.get()来试图获取处理结果时，由于结果还没有运行出来，所以该方法会被阻塞。但是从多线程角度来看，此时它是异步执行的。

再用大白话解释一下，不敢保证一定准确无误，同步和异步我们描述的是多个线程之间的关系，而阻塞和非阻塞描述的是一个线程的属性。我们既然选择了多线程也就选择了异步编程的方式，但是却要解决同步的问题，而同步往往意味着性能的缺失和安全性的保障。而对于阻塞和非阻塞来说，传统的方式大多是阻塞的，如果采用异步非阻塞往往意味着更多的代码和资源投入。

3. IO模型

1. 聊聊Linux五种IO模型

3.1 几个重要的知识

1. 用户空间和内核空间

1. Linux用户态和内核态

在 CPU 的所有指令中，有些指令是非常危险的，如果错用，将导致系统崩溃，比如清内存、设置时钟等。如果允许所有的程序都可以使用这些指令，那么系统崩溃的概率将大大增加。因此为了保护内核空间就设置了用户空间。区分内核空间和用户空间本质上是要提高操作系统的稳定性及可用性。

1. 如何从用户空间进入内核空间？

   用户态的进程必须切换成内核态才能使用系统的资源，从用户态进入到内核态有三种方式：系统调用、软中断、硬件中断和异常。

2. 进程切换

为了控制进程的执行，内核必须有能力挂起正在CPU上运行的进程，并恢复以前挂起的某个进程的执行。这种行为被称为进程切换。因此可以说，任何进程都是在操作系统内核的支持下运行的，是与内核紧密相关的。从一个进程的运行转到另一个进程上运行，这个过程中经过下面这些变化：

1. 保存处理机上下文，包括程序计数器和其他寄存器。
2. 更新PCB信息。
3. 把进程的PCB移入相应的队列，如就绪、在某事件阻塞等队列。
4. 选择另一个进程执行，并更新其PCB。
5. 更新内存管理的数据结构。
6. 恢复处理机上下文。

3 进程的阻塞

正在执行的进程，由于期待的某些事件未发生，如请求系统资源失败、等待某种操作的完成、新数据尚未到达或无新工作做等，则由系统自动执行阻塞原语(Block)，使自己由运行状态变为阻塞状态。可见，进程的阻塞是进程自身的一种主动行为，也因此只有处于运行态的进程（获得CPU），才可能将其转为阻塞状态。当进程进入阻塞状态，是不占用CPU资源的。

4. 缓存IO

缓存 IO 又被称作标准 IO，大多数文件系统的默认 IO 操作都是缓存 IO。在 Linux 的缓存 IO 机制中，操作系统会将 IO 的数据缓存在文件系统的页缓存（ page cache ）中，也就是说，数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。

缓存 IO 的缺点：

数据在传输过程中需要在应用程序地址空间和内核进行多次数据拷贝操作，这些数据拷贝操作所带来的 CPU 以及内存开销是非常大的。

文件描述

文件描述符（File descriptor）是计算机科学中的一个术语，是一个用于表述指向文件的引用的抽象化概念。

3.2 Linux IO模型

网络IO的本质是socket的读取，socket在linux系统被抽象为流，IO可以理解为对流的操作。对于一次IO访问（以read举例），数据会先被拷贝到操作系统内核的缓冲区中，然后才会从操作系统内核的缓冲区拷贝到应用程序的地址空间。

一共有5种网络IO模型

1. 同步模型（synchronous IO）
2. 阻塞IO（bloking IO）
3. 非阻塞IO（non-blocking IO）
4. 多路复用IO（multiplexing IO）
5. 信号驱动式IO（signal-driven IO）
6. 异步IO（asynchronous IO）

其中信号驱动式IO模型并不常用

3.2.1 同步阻塞 IO（blocking IO）

3.2.2 同步非阻塞IO

3.2.3 IO多路复用

1. 对select，poll，epoll非常好的讲解

由于同步非阻塞方式需要不断主动轮询，轮询占据了很大一部分过程，轮询会消耗大量的CPU时间，而 “后台” 可能有多个任务在同时进行，人们就想到了循环查询多个任务的完成状态，只要有任何一个任务完成，就去处理它。如果轮询不是进程的用户态，而是有人帮忙就好了。那么这就是所谓的 “IO 多路复用”

3.2.3 信号驱动 IO （不是很重要）

3.2.4 异步非阻塞 IO

4. IO多路复用之select，poll，epoll

本质就是利用一个线程监听多个Socket，谁有数据就处理谁。

整体的思想如下：

while(1){
	for Fdx in Fda~Fde{
		if(Fdx 有数据){
			读取Fdx；处理
			}
		}
}
           

4.1 select

1. select函数的第一个参数的解释

//   struct sockaddr_in addr = {0}; // 绑定套接字

 sockfd = socket(AF_INET, SOCK_STREAM, 0); // 创建套接字
 memset(&addr, 0, sizeof (addr)); // 初始化为0
 addr.sin_family = AF_INET; // 使用IP_V4地址
 addr.sin_port = htons(2000); // 端口
 addr.sin_addr.s_addr = INADDR_ANY;
 bind(sockfd,(struct sockaddr*)&addr ,sizeof(addr)); // 绑定到套接字
 listen (sockfd, 5); // 进入监听状态
 
/*以下就是select的执行过程*/
  for (i=0;i<5;i++) 
  {
    memset(&client, 0, sizeof (client));
    addrlen = sizeof(client);
    fds[i] = accept(sockfd,(struct sockaddr*)&client, &addrlen); // 为每一个client创建文件描述符（也就是套接字描述符）
    if(fds[i] > max)
    	max = fds[i];
  }

/*通过while循环监视每一个socket，来了数据就处理*/
  while(1){
	FD_ZERO(&rset); // 置零
  	for (i = 0; i< 5; i++ ) {
  		FD_SET(fds[i],&rset); //置位
  	}
 
   	puts("round again");
	select(max+1, &rset, NULL, NULL, NULL);
 
	for(i=0;i<5;i++) {
		if (FD_ISSET(fds[i], &rset)){
			memset(buffer,0,MAXBUF);
			read(fds[i], buffer, MAXBUF);
			puts(buffer);
		}
	}	
  }
           

注意上述代码中有一个rset，他其实就是一个bitmap。这了的bitmap最大时1024，他指示了哪个文件描述符被创建。比如我们上述代码中创建了1，2，5，7，9五个描述符，那么这个1024位的bitmap中的1，2，5，7，9的位置就为1，其他的全为0.

select的缺点：

• bitmap默认时1024，这就限制了可以监视的socket的数量
• 从用户态到内核态的切换会产生开销
• FD_set不可以重复使用
• while中O(n)的再次遍历

4.2 poll

poll主要解决了select中的前两个缺陷，但是后续的工作原理时相似的，所以就两个问题并没有解决。

4.3 epoll

• epoll中内核态和用户态共享epfd，因此也就解决了内核态和用户态切换的开销问题。
• epoll中并没有类似于select和poll的置位，在epoll是一种变相的置位–重排。有数据的epfd会被放在前面，并且epoll_wait函数会返回被置位的个数。while中的遍历只需要遍历nfds次就可以，也就解决了select中的O(n)问题。

5. Socket建立的方式

5.1 S端

• 设定端口和IP
• 初始化socket，创建监听socket
• bind 绑定IP地址端口
• listen 开始监听
• 有事件进来就添加到时间表里面（epoll模式的状态）
• 服务器使用结束就close

什么是操作系统

操作系统（operate system）就是综合管理计算机硬件和软件资源的程序，同是也是计算机系统的内核和基石。操作系统需要处理如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统也提供一个让用户与系统交互的操作界面。

第二章 进程与线程

1. 什么是进程：

• 进程是对运行时程序的封装，是系统进行资源调度和分配的基本单位，实现了操作系统的并发；
• 优点：内存隔离，单个进程的崩溃不会导致这个系统的崩溃。而且进程方便测试以及编程简单
• 缺点：创建销毁比较麻烦，进程间数据的共享麻烦，并且消耗的资源比较多。

2. 什么是线程：

• 线程是进程的子任务，是CPU调度和分派的基本单位，用于保证程序的实时性，实现进程内部的并发。（线程自身是不能拥有系统资源的，但是它可以拥有自己的堆、栈、局部变量以及程序计算器。）
• 优点：可以提高系统的并行性，数据共享比较方便，切换比较快。
• 缺点：没有内存隔离，一个线程的崩溃会导致整个进程的崩溃。编程复杂以及调试困难。

3. 进程包括什么：

进程由程序、数据和进程控制块组成。进程控制块是记录进程有关信息的一块主存，是进程存在的程序唯一标识。

4. 进程组织方式

5. 阻塞和挂起的区别

• 理解一：挂起是一种主动行为，因此恢复也应该要主动完成，而阻塞则是一种被动行为，是在等待事件或资源时任务的表现，你不知道他什么时候被阻塞(pend)，也就不能确切的知道他什么时候恢复阻塞。而且挂起队列在操作系统里可以看成一个，而阻塞队列则是不同的事件或资源（如信号量）就有自己的队列。
• 理解二：阻塞（pend）就是任务释放CPU，其他任务可以运行，一般在等待某种资源或信号量的时候出现。挂起（suspend）不释放CPU，如果任务优先级高就永远轮不到其他任务运行，一般挂起用于程序调试中的条件中断，当出现某个条件的情况下挂起，然后进行单步调试。
• 理解三：pend是task主动去等一个事件,或消息.suspend是直接悬挂task,以后这个task和你没任何关系,任何task间的通信或者同步都和这个suspended task没任何关系了,除非你resume task;
• 理解四：任务调度是操作系统来实现的，任务调度时，直接忽略挂起状态的任务，但是会顾及处于pend下的任务，当pend下的任务等待的资源就绪后，就可以转为ready了。ready只需要等待CPU时间，当然，任务调度也占用开销，但是不大，可以忽略。可以这样理解，只要是挂起状态，操作系统就不在管理这个任务了。
• 理解五：挂起是主动的，一般需要用挂起函数进行操作，若没有resume的动作，则此任务一直不会ready。而阻塞是因为资源被其他任务抢占而处于休眠态。两者的表现方式都是从就绪态里“清掉”，即对应标志位清零，只不过实现方式不一样。

2.2 线程

2.2.1 线程存在的必要性

1. 为什么要有线程

1）进程一时间只能干一件事，如果被阻塞，整个进程都会被挂起，线程有利于实现真正的并行；

2）线程的上下文切换的开销更小；

3）如果是I/O密集型的处理，多线程会加快执行的速度。

2. 进程和线程的区别

1）一个线程只能属于一个进程，而一个进程可以有多个线程，但至少有一个线程。线程依赖于进程而存在。

2）进程在执行过程中拥有独立的内存单元，而多个线程共享进程的内存。（资源分配给进程，同一进程的所有线程共享该进程的所有资源。同一进程中的多个线程共享代码段（代码和常量），数据段（全局变量和静态变量），扩展段（堆存储）。但是每个线程拥有自己的栈段，栈段又叫运行时段，用来存放所有局部变量和临时变量。）

3）进程是资源分配的最小单位，线程是CPU调度的最小单位；

4）进程在进行上下文切换时，由于他们有自己的内存空间，系统要重新为其分配内存、I/O等资源，然后回收旧的进程的内存、I/O等资源，切换的开销比较大。但是线程不存在这些问题，开销比较小。

5）由于线程共享地址空间，因此线程之间的通信比较方便。但是进程间的通信比较麻烦

3. 进程间的通信/同步方式

方式: 套接字，管道，信号量，消息队列，共享内存，信号

3.1 管道( pipe )：管道是一种半双工的通信方式，数据只能单向流动，而且只能在具有亲缘关系的进程间使用。进程的亲缘关系通常是指父子进程关系。

3.2 有名管道 (namedpipe) ： 有名管道也是半双工的通信方式，但是它允许无亲缘关系进程间的通信。

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

3.4 消息队列( messagequeue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

3.5 信号 (sinal ) ： 信号是一种比较复杂的通信方式，用于通知接收进程某个事件已经发生。

3.6 共享内存(shared memory ) ：共享内存就是映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问。共享内存是最快的 IPC 方式，它是针对其他进程间通信方式运行效率低而专门设计的。它往往与其他通信机制，如信号两，配合使用，来实现进程间的同步和通信。

3.7 套接字(socket ) ： 套解口也是一种进程间通信机制，与其他通信机制不同的是，它可用于不同及其间的进程通信。

3.4 线程之间的通信

临界区、互斥量（mutex）、锁机制（分为读写锁和自旋锁）、信号量（分为有名信号量和无名信号量）、事件等

2.2.4 用户级线程和内核级线程

线程的实现可以分两类：用户级线程，内核级线程和混合式线程。

用户级线程是指不需要内核支持而在用户程序中实现的线程，它的内核的切换是由用户态程序自己控制内核的切换，不需要内核的干涉。但是它不能像内核级线程一样更好的运用多核CPU。

优点：

（1） 线程的调度不需要内核直接参与，控制简单。

（2） 可以在不支持线程的操作系统中实现。

（3） 同一进程中只能同时有一个线程在运行，如果有一个线程使用了系统调用而阻塞，那么整个进程都会被挂起，可以节约更多的系统资源。

缺点：

（1） 一个用户级线程的阻塞将会引起整个进程的阻塞。

（2） 用户级线程不能利用系统的多重处理，仅有一个用户级线程可以被执行。

内核级线程:切换由内核控制，当线程进行切换的时候，由用户态转化为内核态。切换完毕要从内核态返回用户态。可以很好的运用多核CPU，就像Windows电脑的四核八线程，双核四线程一样。

优点：

（1）当有多个处理机时，一个进程的多个线程可以同时执行。

（2） 由于内核级线程只有很小的数据结构和堆栈，切换速度快，当然它本身也可以用多线程技术实现，提高系统的运行速率。

缺点：

（1） 线程在用户态的运行，而线程的调度和管理在内核实现，在控制权从一个线程传送到另一个线程需要用户态到内核态再到用户态的模式切换，比较占用系统资源。（就是必须要受到内核的监控）

关联性

（1） 它们之间的差别在于性能。

（2） 内核支持线程是OS内核可感知的，而用户级线程是OS内核不可感知的。

（3） 用户级线程的创建、撤消和调度不需要OS内核的支持。

（4） 用户级线程执行系统调用指令时将导致其所属进程被中断，而内核支持线程执行系统调用指令时，只导致该线程被中断。

（5） 在只有用户级线程的系统内，CPU调度还是以进程为单位，处于运行状态的进程中的多个线程，由用户程序控制线程的轮换运行；在有内核支持线程的系统内，CPU调度则以线程为单位，由OS的线程调度程序负责线程的调度。

（6） 用户级线程的程序实体是运行在用户态下的程序，而内核支持线程的程序实体则是可以运行在任何状态下的程序。

2.3 进程间通信/同步

进程间通信方式：管道、共享内存、socket、消息、信号量、共享队列等

进程通信的方式也适用于线程

2.3.1 竞争条件

2.3.2 临界区

1. 什么是临界区

临界区指的是一个访问共用资源（例如：共用设备或是共用存储器）的程序片段，而这些共用资源又无法同时被多个线程访问的特性。当有线程进入临界区段时，其他线程或是进程必须等待（例如：bounded waiting 等待法），有一些同步的机制必须在临界区段的进入点与离开点实现，以确保这些共用资源是被互斥获得使用，例如：semaphore。只能被单一线程访问的设备

2.3.3 忙等待互斥

为了实现临界区中的思想，需要确定如何使得一时间只有一个进程进入到临界区，在该临界区被某一个进程占用后，其他进程都不可再进入临界区：

1. 屏蔽中断

一个进程进入临界区后，把所有中断都屏蔽，包括时钟中断，这样就不可能发生进程之间的切换。但是如果该进程不再打开中断，整个系统就会直接崩溃。

2.锁变量

3. 严格轮换法（自旋锁）

两个进程轮流进入临界区，轮流执行。

但是有一个问题是，如果进程0很快完成了一个时间片上的临界区操作，并且需要再次进入临界区。但是进程1还在忙着其他操作而没有进入临界区，这就会导致0无法再次快速的进入临界区并完成操作，这就会导致效率的降低。

4. Peterson解法

5. TSL指令

备注：

Peterson和TSL的本质都是先检查是否允许进程进入，如果不允许就在原地等待，直到允许为止。

2.3.4 睡眠和唤醒

1.生产者-消费者问题

#define N 100
int countor = 0;
void producer(void):
{
	int item;
	while(True){
		item=produce_item();
		if(countor==N) sleep();
		insert_item(item);
		countor++;
		if(countor==1) wakeup(consumer);
	}
void consumer(void):
{
	int item;
	while(True){
		if(countor==0) sleep();
		item=remove_item();
		countor--;
		if(countor==N-1) wakeup(producer);
		consume_item(item)
	}
}
           

2.3.5 信号量

1. 进程同步之信号量机制（pv操作）及三个经典同步问题

信号量机制即利用pv操作来对信号量进行处理。

（1）什么是信号量？

信号量（semaphore）的数据结构为一个值和一个指针，指针指向等待该信号量的下一个进程。信号量的值与相应资源的使用情况有关。当它的值大于0时，表示当前可用资源的数量；当它的值小于0时，其绝对值表示等待使用该资源的进程个数。注意，信号量的值仅能由PV操作来改变。

一般来说，信号量S>=0时，S表示可用资源的数量。执行一次P操作意味着请求分配一个单位资源，因此S的值减1；当S<0时，表示已经没有可用资源，请求者必须等待别的进程释放该类资源，它才能运行下去。而执行一个V操作意味着释放一个单位资源，因此S的值加1；若S<=0，表示有某些进程正在等待该资源，因此要唤醒一个等待状态的进程，使之运行下去。

（2）什么是PV操作

p操作（wait）：申请一个单位资源，进程进入。

wait(S){
	while(s<=0)	//如果没有资源则会循环等待；
		;
	S-- ;
}
           

v操作（signal）：释放一个单位资源，进程出来。

signal(S){
	S++ ;
}
           

PV操作的含义：PV操作由P操作原语和V操作原语组成（原语是不可中断的过程），对信号量进行操作，具体定义如下：

• P（S）：
  • 将信号量S的值减1，即S=S-1；
  • 如果S<=0，则该进程继续执行；否则该进程置为等待状态，排入等待队列。
• V（S）：
  • 将信号量S的值加1，即S=S+1；
  • 如果S>0，则该进程继续执行；否则释放队列中第一个等待信号量的进程。

PV操作的意义：我们用信号量及PV操作来实现进程的同步和互斥。PV操作属于进程的低级通信。

2.3.6.互斥量（Mutex）

一个进程中的多个线程访问同一个互斥量是没有问题的，因为线程共享地址空间，可以很轻松的访问同一个互斥量。但是进程间如何共同访问一个互斥量呢？

1）把一些共享数据结构放在内核中

2）让进程和其他进程共享部分地址空间

2.3.7 管程

2.3.8 消息传递

在消息传递系统中，进程间的数据交换是以格式化的消息(Message)为单位的。若通信的进程之间不存在可直接访问的共享空间，则必须利用操作系统提供的消息传递方法实现进程通信。进程通过系统提供的发送消息和接收消息两个原语进行数据交换。

1. 直接通信方式：发送进程直接把消息发送给接收进程，并将它挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中取得消息。
2. 间接通信方式：发送进程把消息发送到某个中间实体中，接收进程从中间实体中取得消息。这种中间实体一般称为信箱，这种通信方式又称为信箱通信方式。该通信方式广泛应用于计算机网络中，相应的通信系统称为电子邮件系统。

2.4 调度

2.4.1 调度简介

调度算法有三种

• 批处理
• 交互式
• 实时

2.4.2 批处理系统中的调度

先来先服务

最短作业时间优先

剩余最短时间优先

2.4.3 交互式系统中的调度

1. 轮转调度

进程挨个执行，未获得CPU时间片的进程先被阻塞。

2. 优先级调度

3. 多级队列

4. 最短进程优先

5. 保证调度

6. 彩票调度

7. 公平分享调度

2.3.4 实时系统中的调度

2.3.5 策略和机制

第三章 内存管理

3.2 一种存储器抽象：地址空间

知乎解释一：

1. 地址空间是一个进程可用于寻址内存的一套地址集合。

2. 为什么要寻址，寻址的目的是找到指令中操作数所在的地址（位置）。好比我要联系你，我得知道你的手机号码一样。

知乎解释二：

• 所谓寻址，就是要找存放某个东西的位置。以下用日常生活中的情形来打比方，虽然不是很精准，但还是能方便理解。
• 隐含寻址：就是说存放东西的位置是相对固定的，东西a永远存在A处，东西b永远存在B处，以此类推。所以不用你费劲找，做事要用到某个东西时，会自动去固定的地方取。
• 立即寻址：就是在让你做事的时候，同时把你要用的东西也给你，也是不用你忙活着去找。
• 直接寻址：就是告诉你储物柜的号码，你自己去该储物柜里把东西拿出来用。
• 寄存器寻址：就是有几个固定的门房收发室，你找门房问，就能告诉你储物柜的号码，然后就能从储物柜拿到东西。寄存器间接寻址：还是去找门房，问到储物柜号码，然后去打开储物柜一看，里面是个纸条，纸条上说东西在另一个储物柜，号码是XXX。
• 偏移寻址：去找门房，门房告诉你一个储物柜号码，但是实际东西放在离告诉你的储物柜的左边或右边一个偏移量的储物柜里。
• 堆栈寻址：有个门房名字比较奇怪，叫堆栈。

什么是逻辑地址空间与物理地址空间？

编译后，每个目标模块都是从0号单元开始编址，称为该目标模块的相对地址（或逻辑地址)。当链接程序将各个模块链接成一个完整的可执行目标程序时，链接程序顺序依次按各个模块的相对地址构成统一的从0号单元开始编址的逻辑地址空间。用户程序和程序员只需知道逻辑地址，而内存管理的具体机制则是完全透明的，它们只有系统编程人员才会涉及。不同进程可以有相同的逻辑地址，因为这些相同的逻辑地址可以映射到主存的不同位置。

物理地址空间是指内存中物理单元的集合，它是地址转换的最终地址，进程在运行时执行指令和访问数据最后都要通过物理地址从主存中存取。当装入程序将可执行代码装入内存时，必须通过地址转换将逻辑地址转换成物理地址，这个过程称为地址重定位。

什么是重定位？

3.3 虚拟内存

虚拟存储器基于局部性原理，在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。另一方面，操作系统将内存中暂时不使用的内容换出到外存上，从而腾出空间存放将要调入内存的信息。这样，系统好像为用户提供了一个比实际内存大得多的存储器，称为虚拟存储器。

虚拟内存 使得应用程序认为它拥有连续的可用的内存（一个连续完整的地址空间），而实际上，它通常是被分隔成多个物理内存碎片，还有部分暂时存储在外部磁盘存储器上，在需要时进行数据交换。与没有使用虚拟内存技术的系统相比，使用这种技术的系统使得大型程序的编写变得更容易，对真正的物理内存（例如RAM）的使用也更有效率。目前，大多数操作系统都使用了虚拟内存，如Windows家族的“虚拟内存”；Linux的“交换空间”等。

页：将进程划分的块，对应的大小就叫页面大小。

页框：将内存划分的块。页和页框二者一一对应，一个页放入一个页框，（理论上）页的大小和页框的大小相等。

页表：就是一个页和页框一一对应的关系表。【存放在内存中】 关系表只是起到一个索引的作用，说白了就是能根据关系表能查到某一个页面和哪一个页框所对应。

3.3.1 分页

参考清华大学的笔记来理解

先说说为什么会有虚拟内存和物理内存的区别。正在运行的一个进程，他所需的内存是有可能大于内存条容量之和的，比如你的内存条是256M，你的程序却要创建一个2G的数据区，那么不是所有数据都能一起加载到内存（物理内存）中，势必有一部分数据要放到其他介质中（比如硬盘），待进程需要访问那部分数据时，在通过调度进入物理内存。所以，虚拟内存是进程运行时所有内存空间的总和，并且可能有一部分不在物理内存中，而物理内存就是我们平时所了解的内存条。有的地方呢，也叫这个虚拟内存为内存交换区。

那么，什么是虚拟内存地址和物理内存地址呢。假设你的计算机是32位，那么它的地址总线是32位的，也就是它可以寻址00xFFFFFFFF（4G）的地址空间，但如果你的计算机只有256M的物理内存0x0x0FFFFFFF（256M），同时你的进程产生了一个不在这256M地址空间中的地址，那么计算机该如何处理呢？回答这个问题前，先说明计算机的内存分页机制。

计算机会对虚拟内存地址空间（32位为4G）分页产生页（page），对物理内存地址空间（假设256M）分页产生页帧（page frame），这个页和页帧的大小是一样大的，所以呢，在这里，虚拟内存页的个数势必要大于物理内存页帧的个数。在计算机上有一个页表（page table），就是映射虚拟内存页到物理内存页的，更确切的说是页号到页帧号的映射，而且是一对一的映射。但是问题来了，虚拟内存页的个数 > 物理内存页帧的个数，岂不是有些虚拟内存页的地址永远没有对应的物理内存地址空间？不是的，操作系统是这样处理的。操作系统有个页面失效（page fault）功能。操作系统找到一个最少使用的页帧，让他失效，并把它写入磁盘，随后把需要访问的页放到页帧中，并修改页表中的映射，这样就保证所有的页都有被调度的可能了。这就是处理虚拟内存地址到物理内存的步骤。

现在来回答什么是虚拟内存地址和物理内存地址。虚拟内存地址由页号（与页表中的页号关联）和偏移量组成。页号就不必解释了，上面已经说了，页号对应的映射到一个页帧。那么，说说偏移量。偏移量就是我上面说的页（或者页帧）的大小，即这个页（或者页帧）到底能存多少数据。举个例子，有一个虚拟地址它的页号是4，偏移量是20，那么他的寻址过程是这样的：首先到页表中找到页号4对应的页帧号（比如为8），如果页不在内存中，则用失效机制调入页，否则把页帧号和偏移量传给MMC（CPU的内存管理单元）组成一个物理上真正存在的地址，接着就是访问物理内存中的数据了。总结起来说，虚拟内存地址的大小是与地址总线位数相关，物理内存地址的大小跟物理内存条的容量相关。

1. 什么是缺页中断？

3.3.3 加速分页过程

3.4 页面置换算法

功能: 当缺页中断发生时,需要调入新的页面而内存已满时, 选择内存当中哪个物理页面被置换。

目标: 尽可能地减少页面的换进换出次数(即缺页中断的次数).具体的说,把未来不再使用的或者短期内较少使用的页面换出,通常只能在局部性原理指导下依据过去统计数据来进行预测。

页面锁定: 用于描述必须常驻内存的操作系统的关键部分或时间关键的应用进程.实现方法是: 在页表中添加锁定标志位.

3.4.1 最优页面置换算法

基本思路: 当一个缺页中断发生时, 对于保存在内存中的每一个逻辑页面.计算他的下一次访问前,还需要等待多长时间.从中选择等待时间最长的那个,作为被置换页面.

但是这只是理想情况,因为操作系统无法知道一个页面需要等多长时间才能被访问。然而这个想法可以作为其他算法的一个评价指标。

3.4.2 最近未使用页面置换算法（NRU）

3.4.3 先进先出算法（FIFO）

基本思路: 选择在内存中驻留时间最长的页面并淘汰.具体来说,系统维护着一个链表,记录了所有位于内存中的逻辑页面.从链表的排列顺序来看.链首的页面驻留时间最长,链尾的驻留时间最短, 当一个缺页中断发生时,把链首页面淘汰出局, 把新的页面加入到链表。性能比较差, 调出的页面可能是要经常访问的页面,并且有bBelady现象.

3.4.4 第二次机会页面是换置换算法

该算法相当于FIFO算法的改进版本。

3.4.5 时钟页面置换算法（Clock）

3.4.6 最近最少使用页面置换算法（LRU）

选择最久未使用的那个页面淘汰掉. 这是对最优置换算法的近似,以过去推测未来。根据局部性原理,如果最近一段时间内某些页面被频繁访问,那么在将来还可能被频繁访问. 反之未被访问的将来也不会被访问.

3.4.8 工作集页面置换算法

工作集是指在某段时间间隔内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。为了防止系统出现抖动现象，需要选择合适的工作集大小。

工作集模型的原理是让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。

————————————————————————————————

工作集模型:

如果局部性原理不成立，那各种算法都没啥区别，比如是单调递增，那不管哪种都会缺页中断。如果局部性原理成立, 那么如何来证明他的存在, 如何对它进行定量的分析?这就是工作集模型!

工作集: 一个进程当前正在使用的逻辑页面的集合,可以用一个二元函数 W ( t , Δ ) W(t, \Delta) W(t,Δ)来表示:

• t是当前的执行时刻
• Δ \Delta Δ称为工作集窗口, 即一个定长的页面访问时间窗口
• W ( t , Δ ) W(t, \Delta) W(t,Δ)=在当前时刻t之前的 Δ \Delta Δ时间窗口当中的所有页面所组成的集合(随着t的变化, 该集合也在不断的变化);
• | W ( t , Δ ) W(t, \Delta) W(t,Δ)|指工作集的大小, 即页面数目

  

3.4.9 工作集时钟页面置换算法

3.4.10 算法小结

3.5 分页系统的设计问题

3.5.1 局部分配策略和全局分配策略

3.5.7 内存映射文件

1. 内存映射文件详解–C++实现

1. 什么是内存映射文件

内存映射文件，是由一个文件到一块内存的映射。 Win32提供了允许应用程序把文件映射到一个进程的函数 (CreateFileMapping)。内存映射文件与虚拟内存有些类似，通过内存映射文件可以保留一个地址空间的区域，同时将物理存储器提交给此区域，内存文件映射的物理存储器来自一个已经存在于磁盘上的文件，而且在对该文件进行操作之前必须首先对文件进行映射。使用内存映射文件处理存储于磁盘上的文件时，将不必再对文件执行I/O操作，使得内存映射文件在处理大数据量的文件时能起到相当重要的作用。

3.7 分段

以下为清华大学OS课程笔记

• 程序的分段地址空间
• 分段寻址方案

段访问机制：

• 一个段：一个内存“块”
  • 一个逻辑地址空间
• 程序访问内存地址需要
  • 一个2维的二元组（s, addr）
  • s–段号
  • addr–段内偏址

    

    

    

第六章 死锁

1. ​死锁的产生、防止、避免、检测和解除

什么是死锁：

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态，这些在互相等待的进程称为死锁进程。

产生死锁的必要条件：

• 互斥条件：一个资源一次只能被一个进程使用
• 请求与保持条件：一个进程因请求资源而阻塞时，对已获得资源保持不放
• 不可剥夺条件：进程获得的资源，在未完全使用完之前，不能强行剥夺
• 循环等待条件：若干进程之间形成一种头尾相接的环形等待资源关系

死锁避免：

系统对进程发出每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，如果分配后系统可能发生死锁,则不予分配，否则予以分配。这是一种保证系统不进入死锁状态的动态策略。

死锁预防：

只要打破四个必要条件之一就能有效预防死锁的发生。

• 打破互斥条件： 改造独占性资源为虚拟资源，大部分资源已无法改造。
• 打破不可抢占条件： 当一进程占有一独占性资源后又申请一独占性资源而无法满足，则退出原占有的资源。
• 打破占有且申请条件： 采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然就等待，这样就不会占有且申请。
• 打破循环等待条件： 实现资源有序分配策略，对所有设备实现分类编号，所有进程只能采用按序号递增的形式申请资源。

死锁避免和死锁预防的区别：

死锁预防是设法至少破坏产生死锁的四个必要条件之一，严格的防止死锁的出现；而死锁避免则不那么严格的限制产生死锁的必要条件的存在，因为即使死锁的必要条件存在，也不一定发生死锁。死锁避免是在系统运行过程中注意避免死锁的最终发生。

避免死锁的算法

银行家算法(分为单资源和多资源)等等。

什么是内存抖动

内存抖动一般是内存分配算法不好，内存太小或者程序的算法不佳引起的页面频繁地从内存调入/调出的行为。

6.1 资源

6.1.2 资源获取

6.2 死锁简介

什么是死锁：

死锁是指两个或两个以上的进程在执行过程中，由于竞争资源或者由于彼此通信而造成的一种阻塞的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态，这些在互相等待的进程称为死锁进程。

产生死锁的必要条件：

• 互斥条件：一个资源一次只能被一个进程使用
• 请求与保持条件：一个进程因请求资源而阻塞时，对已获得资源保持不放
• 不可剥夺条件：进程获得的资源，在未完全使用完之前，不能强行剥夺
• 循环等待条件：若干进程之间形成一种头尾相接的环形等待资源关系

以上四个条件必须是同时满足的，否则便不会发生死锁

6.3 鸵鸟算法

6.4 死锁检测和死锁恢复

对资源的分配加以适当限制可防止或避免死锁发生，但不利于进程对系统资源的充分共享。

6.4.1 每种类型一个资源的死锁检测

(1) 如果进程 - 资源分配图中无环路，此时系统没有发生死锁。

(2) 如果进程 - 资源分配图中有环路，则可分为以下两种情况：

• 每种资源类中仅有一个资源，则系统发生了死锁。此时，环路是系统发生死锁的充分必要条件，环路中的进程就是死锁进程。
• 每种资源类中有多个资源，则环路的存在只是产生死锁的必要不充分条件，系统未必会发生死锁。

上图为资源分配图，其中方框表示资源，圆圈表示进程。资源指向进程表示该资源已经分配给该进程，进程指向资源表示进程请求获取该资源。图 a 可以抽取出环，如图 b，它满足了环路等待条件，因此会发生死锁。

比如：进程D需要的资源是U、T；进程G需要的资源是V、U；进程E需要的资源是T、V；此时进程D占有资源U，进程E占有资源T，进程G占有资源V；所以此时导致进程D、E、G所申请的资源不能得到全部满足，陷入死锁。

死锁检测算法

每种类型一个资源的死锁检测算法是通过检测有向图是否存在环来实现，从一个节点出发进行深度优先搜索，对访问过的节点进行标记，如果访问了已经标记的节点，就表示有向图存在环，也就是检测到死锁的发生。

6.4.2 每种类型一个资源的死锁检测

6.4.3 死锁恢复算法

• 资源剥夺法

  剥夺陷于死锁的进程所占用的资源，但并不撤销此进程，直至死锁解除。

• 进程回退法

  根据系统保存的检查点让所有的进程回退，直到足以解除死锁，这种措施要求系统建立保存检查点、回退及重启机制。

• 进程撤销法

  1.撤销陷入死锁的所有进程，解除死锁，继续运行；2.逐个撤销陷入死锁的进程，回收其资源并重新分配，直至死锁解除。

  可选择符合下面条件之一的先撤销： 1.CPU消耗时间最少者； 2.产生的输出量最小者；3.预计剩余执行时间最长者； 4.分得的资源数量最少者后优先级最低者

• 系统重启法

  结束所有进程的执行并重新启动操作系统。这种方法很简单，但先前的工作全部作废，损失很大。

6.5 死锁避免

6.5.3 单个资源的银行家算法

1. 操作系统——银行家算法（Banker’s Algorithm）

银行家算法是死锁检测算法的扩展

总结：单个资源的银行家算法就是对每一个进程的请求进行检查如果满足这个请求是否会达到安全状态，如果可以达到安全状态就满足其资源请求，在满足后其他进程在得到时间片的时候可能会进入阻塞状态，否则就推迟满足其请求。

6.5.4 多个资源的银行家算法

和单个资源的银行家算法接近，只不过可分配的资源的有增加。

6.6 死锁预防

就是破坏四个必要条件（互斥条件、占有和等待条件、不可抢占条件、环路等待条件）中的一个或者多个。

6.7 其他问题

6.7.4 饥饿

什么是死锁

死锁是指一组线程被阻塞的情况，因为拥有资源的每个进程都试图访问另一个进程所拥有的其他资源，从而最终阻止了公平的系统调度。 当以下四个条件成立时，就会出现死锁情况：互斥意味着一次只能有一个进程访问资源； 没有抢占条件意味着资源只能由拥有该资源的进程自愿释放； 保留并等待意味着拥有资源的进程可以请求其他进程拥有的其他资源； 循环等待意味着将两个或多个进程卡在循环链中，等待每个进程释放各自的资源。

　

什么是饥饿

饥饿是这样一种情况,当进程无限期地进入等待期时，由于高优先级进程不断访问同一资源，因此低优先级进程从未获得访问资源的机会。 这是资源管理问题，因为拒绝进程访问其所需的资源，从而将进程推入不确定的等待时间。 之所以会发生这种情况，是因为它所需要的资源从未分配给进程，从而导致该进程缺少资源，因此得不到名称。 避免饥饿的最佳方法是使用老化技术，该技术会逐渐增加长时间处于等待期的进程的优先级，以确保公平的调度系统。