算法导论

目标一：解决计算问题，除此之外还有更多。more than that
目标二：证明正确性
目标三：证明更高效
目标四：可以和其他人讲明白为什么正确且高效

算法基础

算法就是用来求解问题的，我们想求解一组通用的问题，而不是固定的问题。算法的实现就是一个函数，给定一组输入，得到一个正确的输出。

数学归纳法证明算法的正确性。

循环不变式主要用来帮助我们理解算法的正确性。我们必须证明三条性质

1. 初始化：循环的第一次迭代之前它为真
2. 保持：如果循环的某次迭代之前它为真，那么下次迭代之前它仍为真
3. 终止：在循环终止时，不变式为我们提供一个有用的性质，该性质有助于证明算法是正确的

通过循环不变式证明插入排序是正确的，下面是插入排序的伪代码：

1
2
3
4
5
6
7
8

insert_sort(A)
    for j = 2 to A.length
        key = A[j]
        i = j - 1
        while i > 0 and A[i] > key
            A[i+1] = A[i]
            i--
        A[i+1] = key

循环不变式开始的时候，j = 2的时候，A[1]…A[j-1]里面只有一个元素A[1]，当然是已排序的。循环不变式成立
保持：证明每次迭代保持循环不变式，非形式化的来看，4-7行将A[j-1],A[j-2]等向右移动，第8行将key插入合适的位置，子数组由原来的A[1]…A[j-1]组成，且已经排好序，下一次迭代增加j将保持循环不变式。

如果是形式化的处理，还需要证明while循环的循环不变式。我们不愿陷入形式主义的困境，所以只根据非形式化的来看。
终止：for 循环的终止条件是 j > A.length, 因为每次循环j+1，所以必然会有j = A.length + 1,我们的子数组A[1]…A[j-1]，就变成了A[1]…A[A.length]由原来的A[1]…A[A.length]组成，且已排好序。因此算法正确

练习1.重新insert_sort，使排序变成降序

1
2
3
4
5
6
7
8

insert_sort(A)
    for j = 2 to A.length
        key = A[j]
        i = j - 1
        while i > 0 and A[i] < key
            A[i+1] = A[i]
            i--
        A[i+1] = key

数据结构和动态数组

• Interface(API/ADT): 你想做什么？是一种规范，定义了支持哪些操作。可以理解为问题。
• Data Structure: 实际怎么做，数据实际的表示形式。算法对于操作的支持。可以理解为解决方案。

接口：

• Sequence
  • Static Sequence Interface: 静态的，数量不可变的。
    • build(x): 新建一个Static Sequence。
    • len(): 返回数量
    • iter_seq(): 迭代器
    • get_at(i): 获取i下标的元素
    • set_at(i, x): 设置i下标的元素为x
    • get_first()
    • get_last()
    • set_first()
    • set_last()
  • Dynamic Sequence Interface: 动态的，数量可变的
    • 支持上面所有
    • insert_at(i, x): 插入某一个位置
    • delete_at(i): 删除某一个位置的元素
    • insert_first()
    • insert_last()
    • delete_fist()
    • delete_last()

数据结构：

• Linked List

Set And Sorting

接口

• Set
  • Container
    • build(A): 根据一个iterable的A,创建
    • len(): 返回数量
  • Static
    • find(k): 返回一个set中的元素
  • Dynamic
    • insert(k): 插入一个元素到set
    • delete(k): 从set中删除一个元素
  • Order
    • iter_ord(): 迭代器
    • find_min(): 获取最小的key
    • find_max(): 获取最大的key
    • find_next(k): 获取比k大的下一个key
    • find_pre(k): 获取比k小的上一个key

数据结构

• Array
• Sorted Array

排序

• 破坏性：用一个新的排序后的数组B覆盖数组A
• 原地排序：仅仅用O(1)空间来排序

permutation Sort

线性代数

线性代数的基本问题是求解线性方程组

Ax = b

给定两个方程：2x - y = 0 和 -x + 2y = 3。
对于row picture 矩阵是

1
2
3

[2, -1] [x] = [0]
[-1, 2] [y]   [3]
A        X  =  b

画图为

对于column picture 矩阵是下图，矩阵叫做列的线性组合，解出来x = 1, y = 2

1
2

x [2 ]   + y [-1] = [0]
  [-1]       [2 ]   [3]

画图为

矩阵和向量的乘法：

1 2 3
4 5 6
7 8 9 = 1｜5 6｜ - 2 |4 6| + 3 |4 5|
|8 9| |7 9| |7 8| = 1 * -3 - (2 * -6) + (3 * -3) = -3 + 12 - 9 = 0

JAM核心技术

基础知识

springCloudStream

简介

Spring Cloud Stream是一个框架，用于构建与共享消息传递系统连接的高度可扩展的事件驱动微服务。

该框架提供了一个灵活的编程模型，该模型建立在已经建立和熟悉的 Spring 习惯用语和最佳实践之上，包括对持久发布/订阅语义、消费者组和有状态分区的支持。

核心模块

• Destination Binders： 负责提供与外部消息系统集成的组件
• Destination Bindings： 外部消息系统和用户程序代码之间的桥梁(生产者-使用者之间的桥梁)
• Message：生产者和消费者用于与Destination Binders（以及通过外部消息系统与其他应用程序）通信的规范数据结构。

历史

Spring 的数据集成之旅始于 Spring Integration。通过其编程模型，它提供了一致的开发人员体验来构建应用程序，这些应用程序可以采用企业集成模式来连接外部系统，例如数据库、消息代理等。

快进到云时代，微服务在企业环境中变得突出。Spring Boot 改变了开发人员构建应用程序的方式。借助 Spring 的编程模型和 Spring Boot 处理的运行时职责，可以无缝开发独立的、基于 Spring 的生产级微服务。

为了将其扩展到数据集成工作负载，Spring Integration 和 Spring Boot 被放在一个新项目中。Spring Cloud Stream 诞生了。

架构模型

这张图是spring-stream官网的，里面的Middleware指的就是RabbitMQ或者KafKa这些消息队列。

下图是我们原来和消息队列通信的方式。我们的程序直接发送数据给MQ或者监听到MQ的数据。

通过spring stream来做的话，就增加了Binder层来做统一调度，我们的程序只需要和Binder层通信，不需要关注底层的MQ是RabbitMQ还是Kafka。

目前官方提供了两个Binder，分别是RabbitMQ的和Kafka的，其余队列的有一些第三方维护的。同时我们也可以自己实现Binder。

一开始图中的Input和Output是对于spring stream来说的，input就是输入消息到stream中，output就是输出消息到我们的程序中。

简单介绍一下Binder，其实就是策略模式，统一接口实现，比如MQ1里面发送消息到MQ的方法叫Publish，MQ2里面发送消息到MQ的方法叫Release，但是在Binder接口里面提供了一个方法，就叫做add。也只需要提供一个Message消息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public interface Binder{
    function add(Message msg);
}

// 连接MQ1的Binder
public class Binder1 implements Binder{
    public function add(Message msg){
        // 消息处理
        // 发送到MQ1
        publish(msg);
    }
}

// 连接MQ2的Binder
public class Binder2 implements Binder{
    public function add(Message msg){
        // 消息处理
        // 发送到MQ2
        release(msg);
    }
}

当我们使用的时候只需要自己决定使用哪个Binder就可以了。就是就和连接数据库一样，不需要关心连接的是Mysql还是PostgreSql。

1
2
3
4
5
6
7

public class main{
    public static function main() {
        Binder binder = new Binder1();
        Message msg = new Message();
        binder.add(msg);
    }
}

Bindings

Bindings作为一个桥梁，负责连接MQ和用户代码。比如绑定一个代码作为input往某一个Queue里面输入信息，绑定一个代码作为output从某个Queue里面接收信息。然后我们使用Binder来实现推送消息到MQ和消费消息。

1

这里是官网原文：The application communicates with the outside world by establishing bindings between destinations exposed by the external brokers and input/output arguments in your code. Broker specific details necessary to establish bindings are handled by middleware-specific Binder implementations.

下图为Bindings和Binder的关系

source 和 sink

source其实就是发送方的发送的Message. sink就是接收方接受的Message

注解实现

1

注解的实现已经被彻底删除,只有之前低版本的还能使用

函数式编程实现示例

依赖引入

将下面的代码加入pom文件，然后使用maven导入相关依赖即可。

1
2
3
4
5
6
7
8
9
10
11
12

// 引入spring cloud stream依赖
<dependency>
    <groupId>org.springframework.cloud</groupId>
    <artifactId>spring-cloud-stream</artifactId>
</dependency>
// 引入spring cloud stream的rabbit binder依赖
// 如果是kafka，那么把这个换成kafka的binder
// 在这个binder里面已经引入了 rabbit MQ依赖，所以不需要再单独引入rabbit MQ了
<dependency>
    <groupId>org.springframework.cloud</groupId>
    <artifactId>spring-cloud-stream-binder-rabbit</artifactId>
</dependency>

配置文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

server:
  port: 8801

spring:
  application:
    name: cloud-stream-provider
  cloud:
    stream: # stream的配置
      binders: # 在此处配置要绑定的rabbitmq的服务信息；
        defaultRabbit: # 表示定义的名称，用于于binding整合
          type: rabbit # 消息组件类型
          environment: # 设置rabbitmq的相关的环境配置
            spring:
              rabbitmq:
                host: localhost
                port: 5672
                username: guest
                password: guest

生产者

配置文件修改

对于函数式编程来说，spring cloud stream有一些约定或者说规定。比如我们注册了一个logPub的Bean，那么它对应的bindings配置的名称就是logPub-in-0或者logPub-out-0，前面是我们的方法名，中间表示生产者或消费者，in表示消费者，out表示生产者。这里的in or out是对于我们的代码来说的。后面的0就是一个序号。

写生产者之前我们需要加上对应的bindings配置。如果注册了多个Bean作为生产者或消费者，那么还需要配置哪些Bean是生产者和消费者。

1
2
3
4
5
6
7
8
9
10

spring:
  cloud:
    function: # 配置哪些Bean是Stream可以用的
        definition: log;logPub;sendLog
    stream: # stream的配置
        bindings: # 服务的整合处理
            logPub-out-0:
                destination: log # 表示要使用的Exchange名称定义,不存在会自动创建
                content-type: application/json # 设置消息类型，本次为json，文本则设置“text/plain”

写代码

随便新建一个类，并标记为@Component，主要是要让spring知道这个类。类名可以随便起。

1
2
3
4

@Component
public class logProducer {

}

然后开始编写生产者的代码。加入主要的方法log，方法名可以随便起，只需要记得把这个方法注册为一个Bean就可以了。一定要在上面加@Bean注解。

方法的返回值只能是Supplier函数接口类型。不能是其他的。

方法里面可以写生产者的具体代码。会注册一个名为logPub的Bean作为生产者。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

@Component
public class logListener {
    @Bean
    public Supplier<logListener.Person> logPub() {
        return () -> {
            Person person = new Person();
            person.setName("张三");
            System.out.println("生产者:"+person);
            return person;
        };
    }

    public static class Person {
        private String name;
        public String getName() {
            return name;
        }
        public void setName(String name) {
            this.name = name;
        }
        @Override
        public String toString() {
            return this.name;
        }
    }
}

关于Supplier，这个是java提供的函数式编程的接口。从java8开始提供的，java8里面的stream功能也用到了函数式编程。

下面是Supplier的注释和定义

1
2
3
4
5

//Represents a supplier of results.
//There is no requirement that a new or distinct result be returned each time the supplier is invoked.
//This is a functional interface whose functional method is get().

public interface Supplier<T>

翻译过来大概就是：一个结果的提供者或者一个结果的生产者。正好对应我们的生产者。该接口只有一个方法T get()，没有参数并且仅返回一个结果。

运行

运行的话会发现控制台一直在打印。我们的队列里面也一直在新增。

StreamBridge

当前的运行方式是当写完生产者以后，spring cloud stream会1/s次来调用我们的生产者，但是我们一般是自己来控制生产者的调用。就可以使用下面的方法。

我们可以通过StreamBridge来做到这一点。他有四个send方法。

• public boolean send(String bindingName, Object data)：第一个参数是bindingName，我们输入的是sendLog,就需要增加sendLog的配置，我们也可以用之前的logPub-out-0。第二个参数是发送的数据。
• public boolean send(String bindingName, Object data, MimeType outputContentType)：比上面的多了一个数据类型。
• public boolean send(String bindingName, @Nullable String binderName, Object data)：还可以指定Binder的name
• public boolean send(String bindingName, @Nullable String binderName, Object data, MimeType outputContentType): 四个参数放在一起了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

@RestController
public class logController {

    @Autowired
    private StreamBridge streamBridge;

    @GetMapping("/sendLog")
    public void sendLog() {
        logListener.Person person = new logListener.Person();
        person.setName("李四");
        System.out.println("生产者发送消息"+person);
        streamBridge.send("sendLog", person);
    }
}

消费者

随便新建一个类，并标记为@Component，主要是要让spring知道这个类。类名可以随便起。

1
2
3
4

@Component
public class logListener {

}

然后开始编写消费者的代码。加入主要的方法log，方法名可以随便起，只需要记得把这个方法注册为一个Bean就可以了。一定要在上面加@Bean注解。

方法的返回值可以是Consumer，也可以是Function。不能是其他的。

方法里面就可以写消费的具体代码了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

@Component
public class logListener {
    @Bean
    public Consumer<logListener.Person> log() {
        return person -> {
            System.out.println("Received: " + person);
        };
    }

    public static class Person {
        private String name;
        public String getName() {
            return name;
        }
        public void setName(String name) {
            this.name = name;
        }
        @Override
        public String toString() {
            return this.name;
        }
    }
}

关于Consumer和Function，这两个是java提供的函数式编程的接口。从java8开始提供的，java8里面的stream功能也用到了函数式编程。

下面是Consumer接口的注释和接口的定义。

1
2
3
4

//Represents an operation that accepts a single input argument and returns no result. Unlike most other functional interfaces, Consumer is expected to operate via side-effects.
//This is a functional interface whose functional method is accept(Object).

public interface Consumer<T>

翻译过来大概就是说Consumer接口仅接收一个参数并且没有返回值，我们的代码里面也可以看到，接收了一个person参数，没有return。

该接口只有一个方法void accept(T t)，T类型就是我们的Person类型。

下面是Function接口的注释和定义

1
2
3

//Represents a function that accepts one argument and produces a result.
//This is a functional interface whose functional method is apply(Object).
public interface Function<T, R>

翻译过来大概就是说Function接口仅接收一个参数并且返回一个结果。该接口只有一个方法R apply(T t)，接收一个T类型的参数，返回一个R类型的结果。

手动ACK

通过禁止使用死信队列来执行手动的ACK,这个时候如果抛出异常，则会重试。如果开启了死信队列，那么抛出异常以后则会进入死信队列。

1
2
3

log-in-0:
    consumer:
        auto-bind-dlq: false

队列持久化

上面可以看出来，创建的都是匿名队列，当程序启动的时候自动创建，当程序关闭的时候自动删除。

但是正常开发中，很少使用这种，都会指定一个持久化的队列，不管程序是否运行，队列都存在。

我们可以在bindings的配置里面增加group配置来显式指定哪个队列，我们指定log123队列。

1
2
3
4
5
6
7
8

log-in-0:
    destination: log
    content-type: application/json # 设置消息类型，本次为json，文本则设置“text/plain”
    group: log123
sendLog:
    destination: log
    content-type: application/json # 设置消息类型，本次为json，文本则设置“text/plain”
    group: log123

再次运行程序，可以看到该队列被创建。接下来停止程序，可以看到队列还存在那里。

bindings重命名

默认约定的名称为log-in-0这种形式

但是我们也可以将它重命名。通过配置文件可以将log-in-0重命名为input，不过这样的话，所有的log-in-0的bindings配置都需要修改成input，使用上也是。注意官方并不推荐这种做法，他们认为在大多数情况下，这有点矫枉过正。

1
2
3
4
5
6

spring:
    cloud:
        stream:
            function:
                bindings:
                    log-in-0: input

显式绑定创建

默认约定的是log-in-0负责输入，log-out-0负责输出，我们也可以显式的创建这些。

通过配置文件

1
2
3
4
5

spring:
    cloud:
        stream:
            input-bindings: login;fooin
            output-bindings: logout;fooout

轮询配置属性

1
2
3
4
5
6
7
8
9

spring:
    integration:
        poller:
            # 全局配置
            fixedDelay: 1000L # 默认轮询器的延迟 单位毫秒，默认1000L 
            maxMessagesPerPoll: 1L # 默认轮询器的每个轮询事件的最大消息数。默认 1L
            cron: none # Cron 触发器的 Cron 表达式值。默认 none
            initialDelay: 0 # 周期性触发的初始延迟。 默认0
            timeUnit: MILLISECONDS # 要应用于延迟值的 TimeUnit。默认 MILLISECONDS

也可以单独为某个bindings来配置

1
2
3
4
5
6
7
8
9
10
11
12
13

spring:
    cloud:
        stream:
            bindings:
                log-out-0:
                    producer:
                        poller:
                            # log-out-0的单独配置
                            fixedDelay: 1000L # 默认轮询器的延迟 单位毫秒，默认1000L 
                            maxMessagesPerPoll: 1L # 默认轮询器的每个轮询事件的最大消息数。默认 1L
                            cron: none # Cron 触发器的 Cron 表达式值。默认 none
                            initialDelay: 0 # 周期性触发的初始延迟。 默认0
                            timeUnit: MILLISECONDS # 要应用于延迟值的 TimeUnit。默认 MILLISECONDS

函数组合

假设我们有两个处理Bean,enrich负责检查header，如果缺少foo,就添加为foo,bar。然后第二个echo则负责检查是否包含foo这个Header然后输出消息内容。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

@Bean
public Function<Message<String>, Message<String>> enrich() {
    return message -> {
        Assert.isTrue(!message.getHeaders().containsKey("foo"), "Should NOT contain 'foo' header");
        return MessageBuilder.fromMessage(message).setHeader("foo", "bar").build();
    };
}

@Bean
public Function<Message<String>, Message<String>> echo() {
    return message -> {
        Assert.isTrue(message.getHeaders().containsKey("foo"), "Should contain 'foo' header");
        System.out.println("Incoming message " + message);
        return message;
    };
}

通过配置将这两个bean组合起来,组合之后，这个bean名称就编程了enrich|echo,后续的配置都需要这种冗长的名称，所以这里官方推荐使用重命名的方式将它变成简单的名称。

1
2
3
4
5
6
7
8

spring:
    cloud:
        function:
            definition: enrich|echo # 函数组合
        stream:
            function: 
                bindings:
                    enrich|echo-in-0: input # 重命名

南京大学操作系统

教材是OSTEP,课程官网

操作系统概述

这里概述了操作系统做什么，怎么做。

总共有三个大模块，虚拟化，并发,持久化。

操作系统的几个目标：

1. 高性能：高效率的运行多个程序。
2. 保护每个程序独立运行：不能让一个程序访问另外一个程序的内存数据
3. 可靠性：操作系统必须一直运行，不能停止，因为一旦停止，所有依赖他的软件程序都会停止。

Cache Lab

cache lab 缓存实验

代码下载

从CSAPP上面下载对应的lab代码

http://csapp.cs.cmu.edu/3e/labs.html

环境准备

需要安装 valgrind。可以参考文章Valgrind centos。

安装好以后执行valgrind --version可以看到版本号。

Cache simulator

• cache simulator not a cache。我们不是实现一个真正的缓存，只是实现一个模拟器。
• 不存储内容
• 不使用block offset
• 只计算命中数，不命中数和驱逐数(hit count, miss count,eviction count)
• 缓存模拟器需要在不同的s,b,E下运行。
• 使用LRU替换策略

Hints

• 使用二维数组 struct cache_line cache[S][E];
• S = 2^s
• cache_line //上面说了不需要block offset，所以可以忽略block的内容
  • Valid bit
  • Tag
  • LRU counter
• 通过getopt获取命令行输入
  • 返回-1表示没有输入了
  • 通常在循环里面接收参数
  • 需要包含#include <unistd.h>,#include <getopt.h>
  • 通常使用switch来处理不同的输入
  • 考虑如何处理无效输入
  • 更多信息 man 3 getopt
• fscanf可以指定要读的流(scanf只能读标准输入流)，用来读取trace file
  • 参数
    • 一个流的指针
    • 如何解析文件的信息的格式化字符串
    • 其余部分是指向存储解析数据的变量的指针
  • 通常在循环里使用
  • 当命中EOF或者没有匹配到格式化字符串的时候返回-1
  • 更多信息 man fscanf
• Malloc/free
  • malloc分配数据到heap
  • 记得 free 掉malloc的数据
  • 不要 free 你没有分配的内存

要求我们实现csim.c文件，给了一个示例csim-ref文件。

输入./csim-ref -h可以看到我们要实现的东西。

首先需要接受参数，参数有

• -h 输出帮助信息
• -v 可选详细标志，根据示例程序来，就是输出 L 10,1 miss这些信息
• -s [num] set index bit 数
• -E [num] 每个set的行数
• -b [num] block offset bit数
• -t [file] Trace file文件路径

根据上面的提示可以知道，通过getopt函数来接收参数，并通过switch来处理。读取文件则通过fscanf函数，来读取-t传的文件。

下面是./traces/yi.trace文件的内容

1
2
3
4
5
6
7

L 10,1
M 20,1
L 22,1
S 18,1
L 110,1
L 210,1
M 12,1

• L 代表数据载入
• S 代表数据存储
• M 代表数据修改，需要一次载入 + 一次存储
• 后面的10，20，22这些代表地址
• 最后的1代表操作内存访问的字节数

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214

#include "cachelab.h"
#include <unistd.h>
#include <getopt.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct{
        int valid;
        int tag;
        int time_stamp;
} cache_line;

int timestamp = 0;

// 开始匹配到合适的set 找到命中的cache，如果命中返回1,如果没有命中返回0
int find_hit_cache(cache_line *cache_line,int E,int tag, int*hits) {
    int isHit = 0;
    // 循环set中的cache_line 找到是否有匹配tag && valid
    for(int i = 0; i < E; i++) {
        if (cache_line[i].valid == 1 && cache_line[i].tag == tag ) {
            //hit
            printf("hit \n");
            *hits = *hits + 1;
            isHit = 1;
            //刷新时间
            cache_line[i].time_stamp = timestamp;
            return isHit;
        }
    }
    return isHit;
}

// 找到一个空的cache line放进去，找到了就返回1，没有找到就返回0
int find_empty_cache(cache_line *cache_line,int E,int tag) {
    int have_empty_cache = 0;
    for (int i = 0; i< E; i++) {
        if (cache_line[i].valid == 0) {
            // 空的
            // 把当前内存放入cache
            cache_line[i].valid = 1;
            cache_line[i].tag = tag;
            cache_line[i].time_stamp = timestamp;
            // 找到了就不需要替换了
            have_empty_cache = 1;
            return have_empty_cache;
        }
    }
    return have_empty_cache;
}

// 获取要替换的索引
int get_eviction_index(cache_line *cache_line, int E) {
    int max_time_stamp = timestamp;
    int eviction_index = -1;
    for (int i = 0; i< E; i++) {
        if (cache_line[i].time_stamp < max_time_stamp) {
            //找到time_stamp最小的那个
            max_time_stamp = cache_line[i].time_stamp;
            eviction_index = i;
        }
    }
    return eviction_index;
}

// LRU替换
void LRU(cache_line *cache_line, int E,int tag) {
    // 获取要替换的索引
    int eviction_index = get_eviction_index(cache_line, E);
    
    // 替换
    cache_line[eviction_index].valid = 1;
    cache_line[eviction_index].tag = tag;
    cache_line[eviction_index].time_stamp = timestamp; 
}

// L和S操作，M就调用两次这个
int load_and_store(unsigned address,int b,int s,int u_max,int E,cache_line **cache, int *hits,int *misses,int *evications) {
    // 获取set index block offset tag
    int set_index,tag;
    set_index = (address >> b) & u_max;
    tag = (address >> b) >> s;

    // 开始匹配到合适的set 找到命中的cache，如果命中返回1,如果没有命中返回0
    int isHit = find_hit_cache(cache[set_index], E, tag, hits);
    if (isHit == 0) {
        // miss
        printf("miss \n");
        *misses = *misses + 1;
        // 找到一个空的cache line放进去，找到了就返回1，没有找到就返回0
        int have_empty_cache = find_empty_cache(cache[set_index], E, tag);
        // 如果没有找到空的cache,就需要LRU替换
        if (have_empty_cache == 0) {
            printf("evictions \n");
            *evications = *evications + 1;
            //LRU替换
            LRU(cache[set_index], E, tag);
        }
    }
    // 更新全局时间戳
    timestamp++;
    return 0;
}

int main(int argc, char** argv)
{
    // 接受参数 getopt
    int opt,v,s,E,b,S,B;
    // 文件
    FILE        *       pFile;
    while(-1 != (opt = getopt(argc, argv, "h?v?s:E:b:t:"))){
        // opt is h,v,s,E,b,t的ASCII码值
        // 通过switch对不同的参数进行不同的处理
        switch(opt) {
            case 'h':
                printf("./csim: Missing required command line argument \n Usage: ./csim-ref [-hv] -s <num> -E <num> -b <num> -t <file> \n Options: \n -h         Print this help message. \n -v         Optional verbose flag. \n -s <num>   Number of set index bits. \n -E <num>   Number of lines per set. \n -b <num>   Number of block offset bits. \n -t <file>  Trace file. \n\n Examples: \n ./csim -s 4 -E 1 -b 4 -t traces/yi.trace \n ./csim -v -s 8 -E 2 -b 4 -t traces/yi.trace \n");
                // h参数输出帮助内容
                break;
            case 'v':
                // v参数输出详细信息
                v = 1;
                printf("v:%d \n",v);
                break;
            case 's':
                // S is set 2^s 的数量
                // s is Number of set index bits
                s = atoi(optarg);
                S = 1 << s;
                printf("s:%d, S:%d \n",s,S);
                break;
            case 'E':
                // E is cache line 的数量
                // Number of lines per set
                E = atoi(optarg);
                printf("E:%d \n",E);
                break;
            case 'b':
                // B is block data 的字节
                // b is Number of block offset bits
                b = atoi(optarg);
                B = 1 << b;
                printf("b:%d, B:%d \n",b,B);
                break;
            case 't':
                // t is Trace file
                // 读取文件
                //t = atoi(optarg);
                pFile   =       fopen(optarg,"r");
                printf("t:%s, file:%p \n",optarg,pFile);
                break;
            default:
                printf("非法参数 \n");
            break;
        }
    }
    if(s == 0 || E == 0 || b == 0) {
        return 0;
    }
    // cache存储
    cache_line **cache = (cache_line **)malloc(S * sizeof(cache_line *));
    if (cache == NULL) {
        printf("内存分配失败 \n");
    }
    for(int i = 0; i < S; i++) {
        cache[i] = (cache_line *)malloc(E * sizeof(cache_line));
        if(cache[i] == NULL) {
                printf("内存分配失败，开始回滚 \n");
                // 在这里需要释放已分配的内存，然后退出
            for (int j = 0; j < i; ++j) {
                free(cache[j]);
            }
            free(cache);
        }
    }

    int u_max = 1; 
    for(int i = 0; i < s - 1; i++) {
        u_max = (u_max << 1) | 1;
    }

    // 读取文件
    char        identifier;
    unsigned    address;
    int         size;
    int hits,misses,evictions;
//      Reading lines   like    "       M       20,1"   or      "L      19,3"
    while(fscanf(pFile," %c %x,%d",&identifier,&address,&size)>0)
    {
        //      Do      stuff
        // 开始计算 hits,misses,evictions, hits:0 misses:0 evictions:0
        //printf("identifier %c, addr:%x, size:%d \n",identifier,address,size);
        
        //根据identifier来判断动作L load S store M = 一次L 一次S
        if (identifier == 'L' || identifier == 'S'){
        printf("identifier %c, addr:%x, size:%d \n",identifier,address,size);
            load_and_store(address,b,s,u_max,E,cache,&hits,&misses,&evictions);
        } else if (identifier == 'M') {
            // 一次L 一次S
        printf("identifier %c, addr:%x, size:%d \n",identifier,address,size);
            load_and_store(address,b,s,u_max,E,cache,&hits,&misses,&evictions);
            load_and_store(address,b,s,u_max,E,cache,&hits,&misses,&evictions);
        }
    }
    
    fclose(pFile);  //remember      to      close   file    when    done
    printSummary(hits, misses, evictions);

    // 释放数组内存
    for(int i = 0; i< S; i++) {
        free(cache[i]);
    }
    free(cache);
    return 0;
}

Efficient Matrix Transpose

Shell Lab

shell lab shell实验

代码下载

从CSAPP上面下载对应的lab代码

http://csapp.cs.cmu.edu/3e/labs.html

Data Lab

data lab 数据实验

这个数据实验请在linux机器上面运行，实测mac m1本跑不起来。windows没试过。

centos上需要安装好gcc运行环境。

如果跑不起来记得安装下面这个东西：

yum -y install glibc-devel.i686

运行make btest的时候可能会有warning提示，不用管，这个时候其实已经创建完btest了，可以直接运行btest。

bitXor

第一个函数是实现位的异或。

看一下异或的要求，相同为0，不同为1，这个函数里面只能使用按位与&和按位取反~。

最大操作符号数：14

假设我们有4 = 100, 5 = 101，异或的结果为1 = 001.

先看按位与的结果。100 & 101 = 100 这个时候能得到 0 0 0这个正确的组合

100再取反就是011，就可以得到 1 1 0 这个正确的组合。

先看按位或的结果。100 | 101 = 101 这个时候能得到 0 1 1 和 1 0 1这个正确的组合

可以看到 ~(x & y) & (x | y) 就可以得出结果了，但是我们不能用 | ，所以我们需要通过 &，～来实现 |。

可以通过 (x & ~y) 来实现 ｜ ,4 = 100 取反 = 011， 5 = 101 取反 = 010, 011 & 010 = 010,取反 = 101. 100 | 101 = 101。

所以 异或就是 (x & y) & ((~x & ~y))

代码

1
2
3

int bitXor(int x, int y) {
  return ~(x & y) & ~(~x & ~y);
}

btest 结果：

dlc 结果：

bdd check 结果：

Tmin

Tmin是1000 0000，也就是最小的有符号数，那当然是符号位是1，剩下全0了。

可以使用操作符：! ~ & ^ | + << >>

最大操作符号数量：4

分数：1

返回 1000 0000就可以了。正常的int Tmin就是1后面31个0，也就是1左移动31位

代码：

1
2
3

int tmin(void) {
  return 1 << 31;
}

btest 结果：

dlc 结果：

bdd check 结果：

isTmax

Tmax是0111

可以使用操作符: ! ~ & ^ | +
最大操作符号数量: 10

4位的话，Tmax就是7，看一下7的一些操作结果,可以发现，7+1 = ~7

1
2
3
4

7 = 0111
7 + 1 = 1000 = -8
~7 = 1000 = -8
1000 ^ 0000 = 1000 !1000 = 0000

但是 -1 + 1 也等于 ~-1,所以我们需要排除-1

1
2
3
4

-1 = 1111
-1 + 1 = 0000
~-1 = 0000
0000 ^ 0000 = 0000 !0000 = 0001

可以看到4的话，4 + 1 不等于~4

1
2
3
4

4 = 100
4 + 1 = 0101
~4 = 1011
101 ^ 000 = 101 !101 = 000

怎么排除-1呢，观察发现-1+1 = 0，而0^0 = 0,但是tmax ^ 0 不等于0

所以tmax需要满足两个条件

1. x + 1 == ~x
2. x + 1 != 0

可以用^操作来实现==。如果相等，那么x+1 ^ ~x 就会等于0，!0 == 1，所以第一个条件就是

!((x+1) ^ ~x)

第二个条件同样通过^来实现。

!!((x+1) ^ 0)

只要这两个都满足就是Tmax了，都满足可以通过&来实现，如果都是1，那么&以后就是1，有一个不满足&以后就是0.

代码：

1
2
3
4

int isTmax(int x) {
    int xPlus = x + 1;
    return !(xPlus ^ ~x) & !!(xPlus ^ 0);
}

btest 结果：

dlc 结果：

bdd check 结果：

allOddBits

如果所有的奇数位都是1就返回1，否则返回0

可以使用的操作符: ! ~ & ^ | + << >>
最大数量: 12
分数: 2

比如 1010 1010就是奇数位上全1.

所以只要和 1010 1010 做 & 操作，只要做完以后还是 1010 1010的话，那么就返回1，不然就是0.

因为假设 x 奇数位上有一个是0，比如 1010 1000，那么结果就会是 1010 1000，所以只有奇数位上全1，&以后一定是1010 1010。

所以需要满足条件

1. x & 1010 1010 == 1010 1010

代码：

1
2
3
4
5
6

int allOddBits(int x) {
  int odd = 0xAA; //1010 1010
  int halfOdd = (odd << 8) + odd; // 1010 1010 0000 0000 + 1010 1010 = 1010 1010 1010 1010
  int allOdd = (halfOdd << 16) + halfOdd;
  return !((allOdd & x)  ^ allOdd );
}

btest 结果：

dlc 结果：

bdd check 结果：

negate

返回-x
可以使用的操作符: ! ~ & ^ | + << >>
最大数量: 5
分数: 2

这里要分成三部

• 正数，比如 7 = 0111
• 0， 0 = 0000
• 负数，-1 = 1111

如果使用按位取反

• 7 = 0111，～7 = 1000 = -8
• 0 = 0000， ～0 = 1111 = -1
• -1 = 1111， ～-1 = 0000 = 0
• -8 = 1000， ～-8 = 0111 = 7

取反以后的值 + 1就是对应的负数了，-8 + 1 = -7, -1 + 1 = 0, 0 + 1 = 1, 7 + 1 = 8

代码：

1
2
3

int negate(int x) {
  return ~x + 1;
}

btest 结果：

dlc 结果：

bdd check 结果：

isAsciiDigit

如果 0x30 <= x <= 0x39，返回1，否则0
可以使用的操作符: ! ~ & ^ | + << >>
最大数量: 15
分数: 3

0x30 = 0011 0000, 0x39 = 0011 1001。
根据题目，也就是判断 0011 0000 <= x <= 0011 1001

首先高位要等于 0011，如果不等于0011，那么肯定不在这个范围。可以通过 >> 4位然后 ^ 0011，如果结果为0，那么高位就是满足的。

低位在0000 到 1001之间,当首位是0的时候，后面是啥都行，首位是1，那么后面两位必须是00，也就是前三位是100.

判断首位是0可以通过 & 0x8 然后 ^ 0来判断，如果结果是0首位就是0，不然首位是1

判断低4位的前3位，先 & 0xE来获取前3位，然后 ^ 0x8来判断是不是 100

所以需要满足条件1并且满足条件2或者3

1. x >> 4 ^ 0011 == 0
2. (x & 0x8) ^ 0 == 0
3. (x & 0xE) ^ 0x8 == 0

代码：

1
2
3
4
5
6
7
8

int isAsciiDigit(int x) {
    int xh = x >> 4;
    int a3 = 0x3;
    int xlh = x & 0x8;
    int xorxlh = xlh^0;
    int xorxl = (x & 0xE) ^ 0x8;
    return (!(xh ^ a3 ^ 0)) & (!xorxlh | !xorxl);
}

btest 结果：

dlc 结果：

bdd check 结果：

conditional

实现三元运算 x ? y : z
可以使用的操作符: ! ~ & ^ | + << >>
最大数量: 16
分数: 3

x 为真代表 x & 1 == 1,x 为假代表 x & 1 == 0。
需要满足条件

1. x & 1 == 1时，返回y,所以z需要置为0并且和y一起返回。!(x & 1) & z就可以把z置为0，所以应该返回 (!(x & 1) & z) | y
2. x & 1 == 0时，返回z,所以y需要置为0并且和z一起返回。x & 1 & y就可以把y置为0。所以应该返回 (x & 1 & y) | z

把上面的2个条件合并起来。

(!(x & 1) & z) ｜ (x & 1 & y)

但是发现这样并不行，所以重新思考，发现 x & 1 == 1时候是没错，但是我们应该让 x = 0xFF才行。

所以改进一下子

• 先对x取反。!x = 1,说明x = 0,这个时候应该返回 z,所以需要(0 & y) | z
• !x = 0,说明x = 1，应该返回y,所以需要 (0 & z) | y

这里把 !x 在按位取反 + 1就可以得到当 x = 0时候，condition = 1111 1111。这个时候返回z。

代码：

1
2
3
4
5

int conditional(int x, int y, int z) {
  int xn = !x;
  int condition = ~xn + 1; //x = 0,condition = 1111 1111, x = 1, condition = 0000 0000
  return (condition & z) | (~condition & y);
}

btest 结果：

dlc 结果：

bdd check 结果：

isLessOrEqual

如果x <= y，返回1，否则0
可以使用的操作符: ! ~ & ^ | + << >>
最大数量: 24
分数: 3

等于可以通过异或来做。

!(x ^ y)

在看小于，如果一个正数和一个负数，那么负数一定小于正数，负数的符号位1，正数的符号位0.

取出符号位，通过右移动31位来获取符号位，但是负数会补1，所以在和1与一下，就可以得到符号位了。

(x >> 31) & 1

可以|一下，如果是 1 | 0就返回1了。

((x >> 31) & 1 ) | ((y >> 31) & 1)

如果两个都是正数或者负数，那么符号位相同。

• 对较小的数进行按位取反，在加上大的数的话，会产生溢出。也就是 x < y, ~x + y 会溢出，所以首位是0
• 如果两个数相等或者较大的数取反了在加上小的数，不会溢出。x >= y, ~x + y 不会溢出，所以首位是1
• 所以对于等于的情况还需要处理，如果两个数相等，那么 ~x + y = -1，也就是所有位都是1，让这个值+1就是0了，就和小于保持一致了

如果两个数的符号位不同，那么x是1,y是0的话，就返回1，否则0

• 对x的符号位取反，如果x符号位是1，那么取反0,y的符号位是0，那么就返回1
• 如果x符号位是0，取反1，y是1，那么返回0

代码

1
2
3
4
5
6
7
8
9
10
11
12

int isLessOrEqual(int x, int y) {
  // 取首位
  int signalX = (x >> 31) & 1;
  int signalY = (y >> 31) & 1;
  // !(signalX ^ signalY)是符号位相同的情况
  // !(((~x + y + 1) >> 31) & 1) 是符号位相同时候小于等于的情况
  int lessEq = !(signalX ^ signalY) & !(((~x + y + 1) >> 31) & 1);
  // 如果符号位不同的情况
  int neq = (!signalY) & signalX;
  // 两个情况做|，满足任一个情况则返回1
  return (lessEq | neq);
}

btest 结果：

dlc 结果：

bdd check 结果：

logicalNeg

对x取反，实现!操作
可以使用的操作符: ~ & ^ | + << >>
最大数量: 12
分数: 4

两种情况

• 0，(~0 + 1) | 0 的首位是0
• 其他数， (~x + 1) | x的首位是1

0要返回1，1要返回0，可以异或1

代码

1
2
3

int logicalNeg(int x) {
  return ((((~x + 1) | x) >> 31) & 1) ^ 1;
}

btest 结果：

dlc 结果：

bdd check 结果：

howManyBits

输出最少需要的位数来表示int x
可以使用的操作符: ! ~ & ^ | + << >>
最大数量: 90
分数: 4

例子：

• howManyBits(12) = 5 = 10010
• howManyBits(298) = 10 = 10 1001 1000
• howManyBits(-5) = 4 = 1011
• howManyBits(0) = 1 = 0
• howManyBits(-1) = 1 = 1
• howManyBits(0x80000000) = 32 = 1000….

三种情况

• 正数的首位都是1，遇到1的话，找到1是哪位就可以了
• 负数的首位是符号位都是1，所以需要找到第二个1，如果把负数的符号位变成0，就可以按照正数处理了
• 0，直接返回0，也可以使用正数的方法找1，找不到自然返回0了

有没有1，可以通过!!来判断，如果是!!0，就是0，如果是其他数!!x就是1了。

这道题的代码是从网上抄的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

int howManyBits(int x) {
  int signal = x >> 31;
  int b1,b2,b3,b4,b5,h16,h8,h4,h2,h1;
  x =  (signal & ~x) | (~signal & x);
  // 查看高16位是否有1
  h16 = !!(x >> 16);
  // 如果高16位有1，那么肯定需要16位来表示，记住这16位
  // 因为高 16bit 有1，那么h16就是1，所以1 << 4 就是16，代表最低需要16位表示
  // 如果高 16bit 没有1，那么h16就是0，所以 0<< 4就是0，代表最低需要0位表示
  b1 = h16 << 4;
  // 如果高位有1，那么x >> 16位，这样的原来的高位变成了低位
  // 如果高位没有1，那么x >> 0位，这样低16位还是低16位
  x = x >> b1;

  // 这里分为两种情况，如果高16位有1，需要继续看高8位是否有1，如果高16位没有1，需要看低16位的高8位是否有1
  // 因为上面对于高16位有1的时候，将高16位变成了低16位，所以都只需要看低16位的高8位就可以了
   h8 = !!(x >> 8);
  // 和上面同理，如果现在16位的高8位有1，那么b2代表 1 << 3就是8，如果没有，那么就是0
   b2 = h8 << 3
  // 同样处理，如果有，那么高8位变低8位
  x = x >> b2;

  //处理8位的高4位
   h4 = !!(x >> 4);
   b3 = h4 << 2;
  x = x >> b3;

  // 处理4位的高2位
   h2 = !!(x >> 2);
   b4 = h2 << 1;
  x = x >> b4;

  // 处理最后2位是否有1
   h1 = !!(x >> 1);
   b5 = h1;
  x = x >> b5;

  // 所有结果相加 最后+1，因为高16位有1，那么需要17位表示
  return b1 + b2 + b3 + b4 + b5 + x + 1;
}

btest 结果：

dlc 结果：

bdd check 结果：

float_twice

传入一个无符号数uf,返回uf * 2的小数的bit表示
可以使用的操作符: 任何整数的操作，包||,&&,if,while
最大数量: 30
分数: 4

在复习一下，IEEE浮点标准用V = (-1)的s次方 * M * 2的E次方来表示。
单精度尾数是23位，exp是8位，符号位1位

取符号位
int s = (uf >> 31) & 1;

取exp
int exp = (uf << 1) >> 24

当阶码exp不等于全0或不等于全1的时候，就表示规格化的浮点数。
E的计算方式

• E = 阶码 - Bias
• Bias = 单精度是127
• 单精度下，假设阶码为 0000 0001, 那么E = 1 - 127 = -126
  E = exp - Bias

M的计算方式

• M = 1.XXXXXX
• 尾数就是 XXXXXX
• 假设 尾数为 0000 0000 0000 0000 0000 001，那么M = 1.00000000000000000000001

-1^s * 1.尾数 * 2^E

当阶码等于全0的时候，就表示非规格化的浮点数。
exp ^ 0是0就代表全0，非规格化
E的计算方式，他跟阶码没关系了，因为阶码永远是0

• E = 1 - Bias
• Bias = 单精度是127
• 阶码永远为 0000 0000, E = 1 - 127 = -126
  E = 1 - 127

M的计算方式

• M = 0.XXXXXX
• 尾数就是 XXXXXX
• 假设 尾数为 0000 0000 0000 0000 0000 001，那么M = 0.00000000000000000000001

-1^s * 0.尾数 * 2^E

当阶码等于全1的时候，就表示特殊的浮点数。
~exp ^ 0是0就代表全1，特殊浮点数 当尾数不为全0的时候，就是NaN，返回参数。

小数乘法

• 符号位s1 ^ s2
• M = M1 * M2
• E = E1 + E2

对于规格化的数，2，自然是e+1，因为2的E次方，E+1，那就等于多乘了个2
对于非规格化的数，E是固定的-126，没法改变，所以尾数2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

unsigned float_twice(unsigned uf) {
  // 初始化s符号位，exp阶码，fre尾数
  int s,exp,fre;
  s = (uf >> 31) & 1;
  exp = (uf & 0x7F800000) >> 23;
  fre = uf & 0x7FFFFF;
  // 如果exp == 0，代表非规格化的数
  if (exp == 0) {
    // 非规格化
    // 尾数 * 2
    fre = fre << 1;
    return (s << 31) | (exp << 23) | fre;
  } else if (exp == 0xFF) {
    // 特殊
    return uf;
  } else {
    // 规格化 exp + 1
    exp = exp + 1;
    // +1以后有可能是全1，那么就是无穷大，也就是特殊值，无穷大需要把尾数变成全0
    if (exp == 0xff) {
        fre = 0x0;
    }
    return (s << 31) | (exp << 23) | fre;
  }
}

btest 结果：

dlc 结果：

bdd check 结果：

float_i2f

计算机系统漫游

计算机系统是由硬件和系统软件组成的，它们共同工作来运行应用程序。。虽然系统的 具体实现方式随着时间不断变化，但是系统内在的概念却没有改变。所有计算机系统都有 相似的硬件和软件组件，它们又执行着相似的功能。

第一个c程序

一般第一个程序都是输出hello world，这里我们使用c语言输出一个hello world。后面在来讲这里面都发生了什么。

1
2
3
4
5
6
7

#include <stdio.h>

int main(void)
{
    printf("hello world\n");
    return 0;
}

信息的表示和处理

无符号整型和有符号整型的二进制表示

bit

可以用bit来表示集合，并用位操作来表示集合的操作。

p && *p可以避免空指针

左移1位等于乘2

右移1位等于除2，且向下取整

逻辑右移：右移后补0，java中 -3 >> 1 = -2
算术右移：右移后补符号位,java中 -3 >>> 1 = 2147483646

大端表示和小端表示

• 最高有效字节在最前面的方式，称为大端表示。
• 低有效字节在最前面的方式，称为小端表示。

可以通过下面的代码来测试自己的机器是大端还是小端的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

#include <stdio.h>

typedef unsigned char *pointer;

void show_bytes(pointer start, size_t len) {
	size_t i;
	for (i = 0; i < len; i++)
		printf("%p\t0x%.2x\n", start+i, start[i]);
	printf("\n");
}

int main() {
    int a = 15213;
    printf("int a = 15213;\n");
    show_bytes((pointer) &a, sizeof(int));
    return 0;
}

float

101.11表示5又3/4，也就是23/4。前面的101表示5，小数点后面的11表示3/4,小数点后面第1个1表示1/2，第二个1表示1/4，所以相加就是3/4

浮点数表示由IEEE制定。

IEEE浮点标准用V = (-1)的s次方 * M * 2的E次方来表示。

所以存储就有了3部分

• 符号位，1位，0表示正数，1表示负数，表示s
• 尾数significand，尾数通常是1-2之间或0-1之间。encodes M，但不等于M
• 阶码exponent，encodes E，但不等于E

表示方式

规格化表示(Normalized)

当阶码不等于全0或不等于全1的时候，就表示规格化的浮点数。

E的计算方式

• E = 阶码 - Bias
• Bias = 2的k-1次方 - 1，单精度是127，双精度是1023
• 单精度下，假设阶码为 0000 0001, 那么E = 1 - 127 = -126

M的计算方式

• M = 1.XXXXXX
• 尾数就是 XXXXXX
• 假设 尾数为 0000 0000 0000 0000 0000 001，那么M = 1.00000000000000000000001

假设符号为0表示正数，那么这个浮点数为 V = 1 * M * 2的E次方
= 1 * 1.00000000000000000000001 * 2的-126次方
= 1.00000000000000000000001 * 2的-126次方
= 0.000…00100000000000000000000001 （小数点左移126位）
这等于非常非常小的一个浮点数了

如何表示15213.0呢。首先符号位为0，然后计算尾数和阶码。

• 15213.0 换成二进制表示为 11 1011 0110 1101.0
• 接下里移动小数点为 1.1101 1011 0110 1 * 2的13次方，因为小数点左移动了13位。
• 所以尾数为 1101 1011 0110 1000 0000 000
• E = 13，所以阶码 = E + Bias = 13 + 127 = 140.
• 所以阶码为 140，二进制表示为 1000 1100

15213.0的浮点数表示为：

0 1000 1100 1101 1011 0110 1000 0000 000

非规格化表示(Denormalized)

当阶码等于全0的时候，就表示非规格化的浮点数。

E的计算方式，他跟阶码没关系了，因为阶码永远是0

• E = 1 - Bias
• Bias = 2的k-1次方 - 1，单精度是127，双精度是1023
• 阶码永远为 0000 0000, E = 1 - 127 = -126

M的计算方式

• M = 0.XXXXXX
• 尾数就是 XXXXXX
• 假设 尾数为 0000 0000 0000 0000 0000 001，那么M = 0.00000000000000000000001

假设符号为0表示正数，那么这个浮点数为 V = 1 * M * 2的E次方
= 1 * 0.00000000000000000000001 * 2的-126次方
= 0.00000000000000000000001 * 2的-126次方
= 0.000…00000000000000000000000001 （小数点左移126位）
这等于非常非常小的一个浮点数了，比上一个规格化的更小

如果尾数也等于全0，那么就表示浮点数0

特殊值

当阶码等于全1的时候，就表示特殊的浮点数。

• 当尾数全0，就表示无穷大
• 当尾数为其他值的时候，就表示 NaN(Not a Number)

用数轴表示如下：

练习题

习题2.54 假定变量x,f和d的类型分别是int、float 和cioubile。除了f和d都 不 能 等 于 十∞ 、 、 一 ∞ 或 者 N a N ， 它 们 的 值 是 任 意 的 。 对 于 下 面 每 个 C 表 达 式， 证 明 它 总 是 为 真 ( 也 就 是 求 值 为 1 )， 或 者 给 出 一 个 使 表 达 式 不 为 真 的 值 ( 也 就 是 求 值 为 0 )。

类型中long > double > int > float

1. x == (int) (double) x // true
2. x == (int) (float) x // false
3. d == (double) (float) d // false
4. f == ( float ) ( double ) f // true
5. f == -(-f) //true 只改变了符号位
6. 1.0/2 == 1/2.0 //true
7. d*d >= 0.0 // true
8. ( f + d ) - f == d //false浮点数不满足结合律

程序的机器级表示

历史

从最早的16位处理器8086到现在的64位处理器x86-64

• 8086(1978年 ， 29 K个晶体管 )。 是 第 一代单芯片、16 位微处理器之一。8088是8086的一个变种，在8086上增加了一个8位外部总线，构成最初的IBM个人计算机的心脏。 BM与当时还不强大的微软签订合同，开发MS DOS 操作系统。最初的机器型号有32768 字节的内存和两个软驱 (没有硬盘驱动器)。 从体系结构上来说，这些机器只有655360字节的地址间 – 地址只有20位长(可寻址范围为1048576字节)，而操作系统保留了393216字节自用。1980年 ，Intel提出了8087浮点协处理器 (45 K个晶体管)，它与一个8086或8088处理器一同运行，执行浮点指令。8087 建立了x86 系列的浮点模型，通常被称为 “x87”
• 80286(1982 年，134K个晶体管)。增加了更多的寻址模式(现在已经废弃了)，构成了IBM PC- AT个人计算机的基础，这种计算机是 MS Windows 最初的使用平台。
• i386 (1985 年，275K 个晶体管) 。将体系结构扩展到32位。增加了平坦寻址模式(flat addressingmodel)，Linux 和最近版本的Windows 操作系统都是使用的这种模式。这是 Intel 系列中第 一台全面支持Unix操作系统的机器。
• i486(1989 年，1.2M个晶体管)。改善了性能，同时将浮点单元集成到了处理器芯片上，但是指令集没有明显的改变。
• Pentium(1993 年，3.1M个晶体管)。改善了性能，不过只对指令集进行了小的扩展
• PentiumPro( 1995 年，5.5M个晶体管)。引人全新的处理器设计，在内部被称为P6 微体系结构。指令集中增加了一类“ 条件传送(conditional move)” 指令
• Pentium/ MMX ( 1997年，4.5M个晶体管 )。 在 Pentium处理器中增加了一类新的处理整数向量的指令。每个数据大小可以是1、2或4字节。每个向量总长64位
• Pentium II ( 1997 年 ，7M 个晶体管 )。 P6微体系结构的延伸
• Pentium III (1999年，8.2M个晶体管)。引人了SSE，这是一类处理整数或浮点数向 量的指令。每个数据可以是1、2或4个字节，打包成128位的向量。由于芯片上包括了 二 级高速绥存，这种芯片后来的版本最多使用 了24M 个晶体管
• Pentium4 ( 2000年 ， 42M个晶体管 )。 SSE 扩展到了 SSE2，增加了新的数据类型 (包括双精度浮点数)，以及针对这些格式的 144 条新指令。有了这些扩展，编译器可以使用 SSE 指令(而不是x87 指令)，来编译浮点代码
• Pentium 4E(2004年，125M个晶体管)。增加了超线程(hyperthreading)，这种技术 可以在一个处理器上同时运行两个程序;还增加 了EM64T ，它是 Intel 对 AMD 提出的对 IA32的64 位扩展的实现，我们称之为x86-64。
• Core2( 2006年 ， 291M 个晶体管 )。 回归到类似于 P6 的微体系结构 。Intel的第一个多核微处理器，即多处理器实现在一个芯片上。但不支持超线程。
• Core i7，Nehalem(2008年，781M个晶体管)。既支持超线程，也有多核，最初的版 本支持每个核上执行两个程序，每个芯片上最多四个核
• Core i7, Sandy Bridge(2011年，1.17G 个晶体管)。引入了AVX，这是对SSE 的扩 展，支持把数据封装进 256 位的向量。
• Corei7, Haswel(2013年，1.4G个晶体管)。将AVX扩展至AVX2，增加了更多的指令和指令格式.

机器级代码

程序优化性能

要写出编译器友好的程序来提升程序性能，比如下面两个函数

1
2
3
4

void test1(long *xp, long *yp) {
    *xp += *yp;
    *xp += *yp;
}

1
2
3

void test2(long *xp, long *yp) {
    *xp += 2 * *yp;
}

对于test1来说，要执行读取xp,读取yp,写xp，再次读取xp,读取yp，写xp，总共4次读取，2次写入。

对于test2来说，要执行读取xp,读取yp，写xp，只需要2次读取，1次写入，当然性能更好。

而且考虑一种情况，就是*xp和*yp指向同一个内存，如果这样的话，那么test1就变成了 xp = 4 * xp，test2就变成了 xp = 3 * xp，意思就不一样了，所以编译器没有办法把test1优化成test2的形式，这种叫做内存别名

在看一个指针的问题

1
2
3
4

x = 1000;y = 3000;
*q = y;
*p = x;
t1 = *q; // 1000 or 3000

如果*q和*p是指向两个内存，那么t1就是3000,如果指向同一个内存，那么t1就是1000，因此编译器无法对这种代码进行优化。

消除循环的低效率

可以把循环中的多次计算或者过程调用等重复执行的，结果确定的，提取出来，只执行一次。

比如下面的代码，这个时候strlen这个函数会执行n次，A-a也会执行n次，他们的结果每次都是一样的，可以都提取出来。A-a由于是常数减法，编译器应该会优化，但是strlen是一个函数，函数的结果是不确定的，编译器会保守的保留它不进行优化。

1
2
3
4
5
6
7

void lower(char *s)
{
 size_t i;
 for (i = 0; i < strlen(s); i++)
 if (s[i] >= 'A' && s[i] <= 'Z')
 s[i] -= ('A' - 'a');
} 

优化后的代码

1
2
3
4
5
6
7
8

void lower(char *s)
{
 size_t i;
 size_t len = strlen(s);
 for (i = 0; i < len; i++)
 if (s[i] >= 'A' && s[i] <= 'Z')
 s[i] -= ('A' - 'a');
} 

减少过程调用

有一些函数中会有一些不必要的操作，可以减少他们，比如数组函数，里面也许会有边界检查之类的，防止越界，但是如果我们的外部代码已经很明显的做了检查，或者说肯定不会越界，那么我们就可以省掉调用函数里面的这部分开销。

get_vec_element这个函数获取数组中的值，并且做了边界检查。这样会做n次边界检查，我们可以优化它。

1
2
3
4
5
6
7
8
9
10
11

void combine2(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    *dest = IDENT;
    for (i=0; i<length; i++) {
        data_t val;
        get_vec_element (v, i, &val);
        *dest = *dest OP val;
    }
}

优化之后的代码，省了每次的边界检查。

1
2
3
4
5
6
7
8
9
10

void combine3(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    data_t *data =get_vec_start(v);
    *dest = IDENT;
    for (i=0; i<length; i++) {
        *dest = *dest OP data[i];
    }
}

消除不必要的内存引用

上面的代码还是有些问题，因为对于dest来说，每次都要经历load,计算,store的过程，这个过程要重复n次，可以通过增加局部变量来减少load和store的次数。

1
2
3
4
5
6
7
8
9
10
11

void combine4(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    data_t *data =get_vec_start(v);
    data_t acc = IDENT;
    for (i=0; i<length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

循环展开

for循环每次循环都会进行if条件判断，计算机执行条件判断的时候是比较费时的，现在有了分支预测功能，但是预测失败的话，也会影响性能。可以通过循环展开来优化这里，来减少for循环的消耗。这样改造的程序，已经极为接近线性代码的功耗了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

void combine5(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data =get_vec_start(v);
    data_t acc = IDENT;
    // 循环次数减半
    for (i=0; i<limit; i+=2) {
        acc = acc OP data[i] OP data[i+1];
    }

    // 循环不一定是2的倍数，这里处理剩下的元素
    for(;i<length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

结合律

对于满足结合律的运算，可以通过结合律来优化。对于上面的combine5函数来说，他的执行流程是这样的。因为每次乘的时候都要等上一个的结果，所以是线性的。

使用结合律优化以后，执行路程是下面这样的，为啥它能并行呢，因为在执行左边acc * (i * i+1)结果的时候，就已经可以计算i+2 * i+3的结果了。这两个乘法并行了，所以缩短了执行时间。上面无法并行的原因是先计算了acc * i，当计算下一个acc * i的时候需要依赖上一次acc的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

void combine6(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data =get_vec_start(v);
    data_t acc = IDENT;
    // 循环次数减半
    for (i=0; i<limit; i+=2) {
        // 唯一的区别的就是这里加了括号
        acc = acc OP (data[i] OP data[i+1]);
    }

    // 循环不一定是2的倍数，这里处理剩下的元素
    for(;i<length; i++) {
        acc = acc OP data[i];
    }
    *dest = acc;
}

多个累积变量

还可以通过先求出所有i为偶数的结果，和i为奇数的结果，在把两个结果结合到一起。这样的话先计算奇数和偶数，这两个是互不干涉的，也可以达到上面结合律的效果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

void combine7(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    long limit = length - 1;
    data_t *data =get_vec_start(v);
    data_t acc0 = IDENT;
    data_t acc1 = IDENT;
    // 循环次数减半
    for (i=0; i<limit; i+=2) {
        // 计算偶数和奇数
        acc0 = acc0 OP data[i]；
        acc1 = acc1 OP data[i+1];
    }

    // 循环不一定是2的倍数，这里处理剩下的元素
    for(;i<length; i++) {
        acc0 = acc0 OP data[i];
    }
    *dest = acc0 OP acc1;
}

存储器层次结构

存储技术

存储技术分为易失存储和非易失存储。

• 易失存储：DRAM 也就是一般所说的电脑内存,SRAM 也就是一般的cpu缓存，CPU的L1缓存，L2,L3这些
• 非易失存储：机械硬盘，固态硬盘

机械硬盘

最便宜的存储，存储容量也很大。由下面的部分组成

• 主轴：盘片放在主轴上
• 盘片：一个盘片有两个面可以进行存储
• 磁道：每个盘面上有多个磁道
• 扇区：每个磁道被划分为一组扇区
• 磁头：通过磁头进行读写扇区上的数据

所以在次盘上读写的时候，需要移动磁头，让磁头找到对应的盘面，在找到磁道和扇区，然后才能读写数据，所以顺序读写比随机读写快的多。因为顺序的话磁头只需要移动一点点距离，而随机需要移动很长的距离。

固态硬盘

固态硬盘是基于闪存的存储技术，价格比机械硬盘贵一些。因为是闪存，所以顺序读写和随机读写都比机械硬盘快。虽然固态的顺序读写和随机读写的差距缩小了，但是顺序读写依旧比随机读写快。

• 块：整个闪存分成一个个块,一个块有32-128个页，块的大小为16KB-512KB
• 页：一个块有多个页组成，每次读写都是一个页，页的大小是512字节-4KB
• 闪存翻译层：连接IO总线和闪存数据，将数据放到IO总线里面，也将IO总线的数据放到闪存里面。

固态每次写入需要先擦除一个页里面原来的内容，在写入新的，因此，擦除次数多了以后，这个页就会坏掉。为了提升固态的使用寿命，一般也会控制每次擦除寿命更高的页。

DRAM

DRAM 也就是电脑内存，由下面几部分组成，价格比固态和机械硬盘贵的多，容量也小的多，现在大多数是16G内存。

• n * n的存储单元：真正存储数据的地方
• 行缓冲区：每次先将一行的数据取到缓冲区里面，在取对应的存储单元里面的数据。
• addr引脚：发送行号和列号给DRAM，发送行号以后，将这一行数据取到行缓冲区里面，再发送列号以后，返回对应的数据
• data引脚：传递数据

DRAM的发展历史，RAS:发送行号，CAS:发送列号

• 快页模式DRAM(Fast Page Mode DRAM, FPMDRAM)。传统的DRAM将存储单元的一整行复制到它的内部行缓冲区中， 使用一个 ，然后丢弃剩余的。FPM DRAM允许对同一行连续地访问可以直接从行缓冲区得到服务，从而改进了这一 点。例如，要从一个传统的DRAM的行i中读4个存储单元，内存控制器必须发送4 个RAS/CAS请求，即使是行地址i在每个情况中都是一样的。要从一个FPM DRAM的同一行中读取存储单元，内存控制器发送第一个RAS/CAS请求，后面跟三个CAS请求。初始的RAS/ CAS请求将行i复制到行缓冲区，并返回CAS寻址的那个存储单元。接下来三个存储单元直接从行缓冲区获得，因此返回得更快。
• 扩展数据输出 DRAM( Extended Data Out DRAM, EDO DRAM) . FPM DRAM 的一个增强的形式 ，它允许各个 CAS 信号在时间上靠得更紧密一点。
• 同步DRAM(Synchronous DRAM，SDRAM)。就它们与内存控制器通信使用一组显式的控制信号来说，常规的FPM 和EDO DRAM 都是异步的。SDRAM用与驱动内存控制器相同的外部时钟信号的上升沿来代替许多这样的控制信号。我们不会深人讨论细节， 最终效果就是SDRAM 能够比那些异步的存储器更快地输出它的超单元的内容。
• 双倍数据速率同步DRAM(Double Data-Rate SynchronousDRAM, DDR SDRAM)。 DDR SDRAM 是 对 SDRAM 的一种增强 ，它通过使用两个时钟沿作为控制信号，从而使DRAM的速度翻倍。不同类型的DDR SDRAM 是用提高有效带宽的很小的预取绥冲区的大小来划分的 : DDR (2位)、 DDR2 (4位)和 DDR (8位)。

现在一般的DDR5，DDR4，其实就是DDR DRAM内存。

SRAM

SRAM 也就是电脑CPU的L1,L2,L3三级缓存使用的，价格比DRAM更贵，容量更小。通常是多少KB或MB。

SRAM将每个位存储在一个双稳态的(bistable)存储器单元里。每个单元是用一个六晶体管电路来实现的。这个电路有这样一个属性，它可以无限期地保持在两个不同的电压 配置(configuration )或状态(state) 之一。其他任何状态都是不稳定的一一从不稳定状态开始，电路会迅速地转移到两个稳定状态中的一个。

局部性(locality)

局部性分为空间局部性(spatial locality)和时间局部性(temporal locality)。

从上面也能看出，DRAM一次加载一行到行缓冲区，如果我们要的数据都在这一行，取的时候就会很快。这就是空间局部性。

比如数组的顺序访问。这个时候一个个接着访问的，就具有空间局部性。

1
2
3
4

a[100] = {0,0,0,...} 
for(int i = 0; i < 100; i++) {
    printf("ai:%d",a[i]);
}

二维数组是一样的，需要按照行来访问。而不能按照列。

1
2
3
4
5
6
7
8
9
10
11
12
13

a[100][100] = {{0,0,0,...},{0,0,0,...},...} 
for(int i = 0; i < 100; i++) {
    for(int j = 0; j < 100; j++) {
        printf("aij:%d",a[i][j]);
    }
}

// 按照列访问，不具有局部性，应该使用上面那种方式
for(int i = 0; i < 100; i++) {
    for(int j = 0; j < 100; j++) {
        printf("aij:%d",a[j][i]);
    }
}

三维数组,也应该使用行访问。
{
{
{0,0,0,…}, // 000, 001, 002, 003
{0,0,0,…}, // 010, 011, 012, 013
{0,0,0,…},
{0,0,0,…}
},
{
{0,0,0,…}, // 100, 101, 102, 103
{0,0,0,…}, // 110, 111, 112, 113
{0,0,0,…},
{0,0,0,…}
},
{
{0,0,0,…},
{0,0,0,…},
{0,0,0,…},
{0,0,0,…}
},…
}

1
2
3
4
5
6
7
8

a[100][100] = {{{0,0,0,...},{0,0,0,...},{0,0,0,...},...},{{0,0,0,...},{0,0,0,...},{0,0,0,...},...},...} 
for(int i = 0; i < 100; i++) {
    for(int j = 0; j < 100; j++) {
        for (int k = 0; k < 100; k++) {
            printf("aijk:%d",a[i][j][k]);
        }      
    }
}

使用最近使用过的数据，就是时间局部性。这是因为缓存的原因，比如最近使用过的数据还在L1缓存中，就会比再去DRAM中取数据要快。

sum就有 时间局部性，一直在使用。

1
2
3
4
5
6

a[100] = {0,0,0,...} 
int sum = 0;
for(int i = 0; i < 100; i++) {
    sum += a[i];
    printf("ai:%d",a[i]);
}

存储器层次结构

通常，高层的可以作为低层的缓存，比如L1缓存L2的数据，L2缓存L3的，L3缓存内存的。数据以块为大小传输。

• 缓存命中(cache hit)：要查找的内容就在L1缓存中，就不需要去L2查找了
• 缓存不命中(cache miss): 要查找的内容不在L1中，而在L2中，需要从L2传输到L1中。
  • 强制性不命中(compulsory miss): 在第一次访问缓存的时候，缓存中肯定是空的。这个时候肯定不会命中。
  • 冲突不命中(conflict miss): 缓存已经满了以后需要进行替换，比如LRU算法，比如取余算法，这个时候有可能你需要的缓存被替换出去了，因为这个原因不命中的，就是冲突不命中。
  • 容量不命中(capacity miss): 因为缓存不够大而没有命中的。

高速缓存存储器

像L1,L2这种SRAM，就是高速缓存存储器。

假设每个存储器地址有m位，形成$M = 2^m$个不同的地址。它由 $S = 2^s$ 个set组成。每个set里面有 $E = 2^e $ 个缓存行。每个行有 $B = 2^b$字节的数据块组成。高速缓存的大小$C = S * E * B$(不包括Tag和Valid)

每个数据块有

• Valid: 1bit，0表示无效缓存，1表示有效缓存
• Tag: t个bit，一些标记 t = m - (b + s)
• Data: 真正的数据，有$B = 2^b$字节

m个地址位的组成：

• t个bit:Tag，用来匹配高速缓存中的Tag，如果匹配上了说明缓存命中。
• s个bit:set index,用来找到对应的数据在哪个set里面。
• b个bit:block offset,用来找到具体数据在block的哪个位置里面。

读取

假设 m = 6,s = 2,t = 1, b = 3, e = 1, 则 S = 4个set,E = 2个行，B = 8字节。大小C =4 * 2 * 8 = 64。

假设 当前m = 000001, 那么 tag = 0, bit set = 00, block offset = 001。

缓存命中的情况。总共4个set，找到第0个set，然后找到其中tag是0并且valid是1的一个block，找到以后，找 001位置的数据，然后返回就可以了。

1
2
3
4
5
6
7
8
9
10

    valid   tag     data
00   1       0      ...    // 首先找到set 00 的这个set,有两行，这一行
00   0       0      ...    // 还有这一行
01   0       0      ...
01   0       0      ...
10   1       0      ...
10   1       0      ...
11   0       0      ...
11   0       0      ...

缓存不命中的情况。总共4个set，找到第2个set，然后找到其中tag是0并且valid是1的，这个时候发现没有匹配的，那么触发miss，开始去下一层获取数据，获取到数据以后，通过替换算法替换掉一个行，将tag修改为0并且valid修改为1，然后把数据写入block data。再返回001位置的数据。

1
2
3
4
5
6
7
8
9
10

    valid   tag     data
00   1       0      ...    
00   0       0      ...    
01   0       0      ...    // 首先找到set 01 的这个set,有两行，这一行
01   0       0      ...    // 还有这一行
10   1       0      ...
10   1       0      ...
11   0       0      ...
11   0       0      ...

冲突不命中，比如计算两个数组的点积。这个时候a[0] * b[0],会先把数组a加载到L1缓存，然后再把b加载到L1缓存，这个时候b会把a覆盖，然后a[1] * b[1]的时候，a就会冲突不命中，然后用a把b覆盖，一直重复这个动作。这个时候可以增加E,比如一个set里面有多个block，这样就不会覆盖了。

1
2
3
4
5
6
7
8
9

float dotProd(float a[100], float b[100]) {
    float sum = 0.0;
    int i;
    for (i = 0; i < 100; i++) {
        sum += a[i] * b[i];
    }
    return sum;
}

写入

在写入的时候有两种情况，缓存命中和不命中，通常的搭配是write through + no write allocate和write back + write allocate

• 缓存命中
  • wirte through: 这个时候直接写入缓存。并且修改下一层的数据。相当于同步修改。
  • write back: 直接写入缓存，并且标记dirty, 尽可能的推迟更新下一层的数据，只有当替换算法执行的时候才更新。相当于异步修改。
• 缓存不命中
  • write allocate: 先把数据从下一层加载到缓存，然后更新缓存数据。
  • no write allocate: 直接写入下一层数据。

链接

c文件变成可执行文件的过程

• c预处理器cpp生成ASCII码的.i文件, cpp main.c main.i
• c编译器cc1生成ASCII汇编语言.s文件, cc1 main.i -Og -o main.s
• 汇编器as生成可重定位目标文件.o文件， as -o main.o main.s
• 链接器ld生成可执行文件, ld -o main main.o

为了构造可执行文件，链接器必须完成两个主要任务

1. 符号解析。目标文件定义和引用符号，每个符号对应于一个函数 、一个全局变量或一个静态变量 (即C语言中任何以 static 属性声明的变量)。 符号解析的目的是将每个符号引用正好和一个符号定义关联起来
2. 重定位。编译器和汇编器生成从地址。开始的代码和数据节。链接器通 过把每个符号定义与 一个内存位置关联起来，从而重定位这些节，然后修改所有对 这些符号的引用，使得它们指向这个内存位置。链接器使用汇编器产生的重定位条 目(relocation entry)的详细指令，不加甄别地执行这样的重定位。

目标文件有三种形式

• 可重定位目标文件。包含二进制和代码数据，可与其他重定位目标文件合并起来变成可执行目标文件。
• 可执行目标文件。包含二进制和代码数据，可被直接复制到内存并执行。
• 共享目标文件。一种特殊类型的可重定位目标文件，可在加载或运行时被动态的加载进内存并链接。

ELF(x86-64的Linux系统的文件)可重定位目标文件的格式

• ELF头。
• .text。已编译程序机器代码
• .rodata。只读数据，比如printf语句中的格式串
• .data。已初始化的全局和静态变量。
• .bss。未初始化的全局和静态变量，以及所有初始化为0的全局和静态变量。不占据实际空间，仅仅是一个占位符。
• .symtab。一个符号表，用来存放 在程序中定义和引用的函数和全局变量的信息。
• .rel.text。一个.text节中位置的列表，当链接器把这个目标文件和其他文件组合时，需要修改这些位置。一般而言，任何调用外部函数或者引用全局变量的指令都需要修 改。另 一方面，调用本地函数的指令则不需要修改
• .rel.data。被模块引用或定义的所有全局变量的重定位信息。
• .debug。一个调试符号表，其条目是程序中定义的局部变量和类型定义，程序中定 义和引用的全局变量，以及原始的C源文件。只有以 -g选项调用编译器驱动程序时，才会得到这个表
• .line。原始C源程序中的行号和.text 节中机器指令之间的映射。只有以-g选项调 用编译器驱动程序时，才会得到这张表
• .strtab。一个字符串表，包括.symtab和.debug中的符号表，以及节头 部中的节名字。字符串表就是以nu 11 结尾的字符串的序列。

每个可重定位目标模块m都有一个符号表，它包含m定义和引用的符号的信息。在链接器的上下文中，有三种不同的符号:

• 由模块m定义的并能被其他模块引用的全局符号。对应非静态的C函数和全局变量。
• 由其他模块定义的并被m引用的全局符号。对应其他模块的非静态的C函数和全局变量。
• 由模块m定义和引用的局部符号。对应于静态的C函数和全局变量。

C++ 和Java 都允许重载方法，这些方法在源代码中有相同的名字，却有不同的参数 列表。那么链接器是如何区别这些不同的重载函数之间的差异呢?C++ 和Java 中能使用 重载函数，是因为编译器将每个唯一的方法和参数列表组合编码成一个对链接器来说唯一 的名字。这种编码过程叫做重整(mangling)，而相反的过程叫做恢复(demangling)。 幸运的是，C++ 和Java使用兼容的重整策略。一个被重整的类名字是由名字中字符 的整数数量，后面跟原始名字组成的。比如，类Foo 被编码成3Foo。方法被编码为原始方法名， 后面加上 __ ， 加上被重整的类名， 再加上每个参数的单字母编码。 比如，Foo::bar (int, long)被编码为bar__3Fooil。重整全局变量和模板名字的策略是相似的。

链接器对多个文件中同名变量或函数的处理。编译器会先分强符号和弱符号,强符号指函数和已初始化的全局变量，弱符号指未初始化的全局变量。

1. 不允许有多个同名的强符号
2. 如果有一个强符号和多个弱符号同名，那么选择强符号。
3. 如果有多个弱符号同名，那么从这些弱符号中任意选择一个。

上面说的链接器接受一组可重定位文件，并生成一个可执行文件，所有的编译系统都提供一种机制，将所有相关的目标模块打包成为一个单独的文件，称为静态库。它也可以用作链接器的输入。当构造可执行文件的时候，直接复制静态库里面被应用程序引用的目标模块。静态库是.a文件。

可执行目标文件的格式

• ELF头。
• 段头部表
• .init。定义了一个函_init，程序的初始化代码会调用它
• .text。已编译程序机器代码
• .rodata。只读数据，比如printf语句中的格式串
• .data。已初始化的全局和静态变量。
• .bss。未初始化的全局和静态变量，以及所有初始化为0的全局和静态变量。不占据实际空间，仅仅是一个占位符。
• .symtab。一个符号表，用来存放 在程序中定义和引用的函数和全局变量的信息。
• .debug。一个调试符号表，其条目是程序中定义的局部变量和类型定义，程序中定 义和引用的全局变量，以及原始的C源文件。只有以 -g选项调用编译器驱动程序时，才会得到这个表
• .line。原始C源程序中的行号和.text 节中机器指令之间的映射。只有以-g选项调 用编译器驱动程序时，才会得到这张表
• .strtab。一个字符串表，包括.symtab和.debug中的符号表，以及节头 部中的节名字。字符串表就是以nu 11 结尾的字符串的序列。

动态库也叫共享库是致力于解决静态库缺陷的一个现代创新产物。共享库是一个 目标模块，在运行或加载时，可以加载到任意的内存地址，并和一个在内存中的程序链接起来。在linux中常用.so后缀来表示。 微软的操作系统大量地使用了共享库，它们称为DLL(动态链接库)

共享库是以两种不同的方式来共享的。首先，在任何给定的文件系统中 ，对于一个库只有一个 .so 文件 。 所有引用该库的可执行目标文件共享这个.so文 件中的代码和数据 ，而不是像静态库的内容那样被复制和嵌入到引用它们的可执行的文件中

共享库和Java本地接口 Java定义了一个标准调用规则，叫做Java本地接口(Java Native Interface, JNI)，它允许Java程序调用“本地的” C和C++ 函数。JNI的基本思想是将本地C函数(如Foo)编译 到一个共享库中 (如 Foo.so )。 当一个正在运行的Java 程序试图调用函数 Foo 时 ，Java解释器 利用dlopen 接口 (或者与其类似的接口)动态链接和加载 Foo.so，然后再调用Foo。

在 Linux 系统中有大量可用的工具可以帮助你理解和处理目标文件。特别地，GNU binutils 包尤其有帮助，而且可以运行在每个Linux 平台上。

• AR:创建静态库，插人、删除、列出和提取成员。
• STRINGS:列出一个目标文件中所有可打印的字符串。
• STRIP:从目标文件中删除符号表信息。
• NM:列出一个目标文件的符号表中定义的符号。
• SIZE:列出目标文件中节的名字和大小。
• READELF:显示 一个目标文件的完整结构，包括ELF 头中编码的所有信息。包含 SIZE 和NM的功能。
• OBJDUMP:所有二进制工具之母。能够显示 一个目标文件中所有的信息。它最大的作用是反汇编.text节中的二进制指令。

Linux 系统为操作共享库还提供了LDD程序:

• LDD:列出一个可执行文件在运行时所需要的共享库。

异常控制流

异常控制流（ExceptionalControlFlow, ECF）使程序能进行跳转，正常的程序执行都是PC里面一条条指令顺序执行的。ECF使PC里面的下一条指令变成别的指令，从而完成别的功能。ECF在系统的各个层次，比如进程切换，操作系统调用，网络请求处理，IO请求处理，是计算机中实现并发的基本机制。

异常

异常是异常控制流的一种形式，它 一部分由硬件实现，一部分由操作系统实现。

假设当前程序正在运行，出现了缺页异常，也就是数据在内存中不存在，需要进行IO请求将数据加载到内存中。执行图如下，异常处理程序有很多，每个异常都有对应的处理程序，当异常发生以后，系统切换到异常处理程序中执行。异常处理完成以后返回用户程序继续执行。

根据异常的不同，返回会发生三种情况：

• 异常处理程序将控制返回给当前用户程序正在执行的指令
• 异常处理程序将控制返回给当前用户程序的下一个指令
• 异常处理程序终止当前用户程序

这里说的都是硬件异常，和Java中try catch的软件异常是不一样的。

系统中可能的每种类型的异常都分配了一个唯 一的非负整数的异常号。有的异常号是处理器的设计者分配的，有的是操作系统的设计者分配的。前者包括被零除，缺页，断点，算术运算溢出，后者包括系统调用和外部IO设备的信号。

在系统启动时，操作系统会分配一个异常表。异常表的key就是异常号，value是异常处理程序的地址。当发生异常的时候，通过异常号找到异常处理地址，然后进行处理。异常表的首地址则放在异常表基址寄存器里面。硬件触发异常以后，就由异常处理程序软件进行执行了，执行在内核模式下。

异常可以分为4类，中断(interrupt),陷阱(trap)，故障(fault)和终止(abort)

中断是异步发生的，中断发生的时候拉起中断引脚。处理器发现中断引脚被拉起，就从系统总线读取异常号，然后执行对应的异常处理程序。执行完成以后继续返回执行下一条指令。

陷阱是有意的异常，最重要的作用是触发系统调用，正常用户程序都是运行在用户模式下，可以执行的功能有限，如果需要读取文件，创建进程等操作，就需要切换到内核模式下，由操作系统内核来进行处理。通过系统调用就可以切换到内核执行。

故障由错误情况引起，它可能能够被故障处理程序修正。比如缺页异常就是一个故障。当发生以后，故障处理程序进行处理，从磁盘加载数据，加载以后重新执行当前指令，就会成功了。如果故障没有被修正，那么就会转为abort，终止当前程序。

终止是不可恢复的致命错误造成的结果，通常是一些硬件错误。

x86-64系统定义了多达256种不同的异常类型，0-31号是由Inter架构师定义的，因此所有x86-64系统的电脑都是一样的。32-255对应的是操作系统定义的中断和陷阱。

下面是一些系统调用：

进程

进程的经典定义就是一个执行中程序的实例。系统中的每个程序都运行在某个进程的上下文(context)中。上下文是由程序正确运行所需的状态组成的。这个状态包括存放在内存中的程序的代码和数据，它的栈、通用目的寄存器的内容、程序计数器、环境变量以及打开文件描述符的集合.

进程提供给应用程序的关键抽象

• 一个独立的逻辑控制流，它提供一个假象，好像我们的程序独占处理器
• 一个私有地址空间，它提供一个假象，好像我们的程序独占内存

/proc文件系统将许多内核数据结构的内容输出为 一个用户程序可以读的文 本文件的层次结构。比如，你可以使用/proc 文件系统找出一般的系统属性，比如CPU类型 (/proc/cpuinfo)，或者某个特 的进程使用的内存段(/proc//maps)。2.6 版本的Linux内核引人/sys 文件系统，它输出关于系统总线和设备的额外的低层信息

操作系统内核使用一种称为上下文切换(context switch)的较高层形式的异常控制流来实现多任务。上下文包括通用目的寄存器、浮点寄存器、程序计数器、用户栈、状态寄存器、内核栈和各种内核数据结构，比如描述地址空间的页表、包含有关当前进程信息的进程表，以及包含进程已打开文件的信息的文件表。

在内核调度了一个新的进程运行后，它就抢占当前进程，并使用一种称为上下文切换的机制来将控制转移到新的进程。

上下文切换

• 保存当前进程的上下文
• 恢复要执行的进程的上下文
• 将控制传递给这个新恢复的进程

当Unix 系统级函数遇到错误时，它们通常会返回一1，并设置全局整数变量errno 来表示什么出错了.比如

1
2
3
4
5

if ((pid = fork()) < 0) {
    // strerror函数返回一个文本串，描述了和某个errno值相关联的错误
    fprintf(stderr, "fork error: %s \n", strerror(errno));
    exit(0);
}

一些进程控制的系统调用C函数

• getpid(), 获取当前进程的pid
• getppid(), 获取当前进程的父进程的pid
• waitpid(), 等待子进程终止
• sleep(), 让程序休眠，时间到啦返回0，时间没到被其他信号中断则返回剩余秒数
• pause(), 让程序休眠直到收到信号
• execve(), 在当前进程的上下文中加载并运行一个新程序
• getpgrp(), 返回当前进程的进程组id
• signal(), 设置信号处理函数

从程序员的角度，可以认为进程总是处于下面三个状态之一

• 运行：进程正在CPU上执行
• 阻塞：进程被挂起，比如读取磁盘的时候
• 终止：进程结束了，收到终止信号，主程序执行完，调用exit函数

当一个子进程终止时，内核并不会立即清除它，进程会被保持为一种已终止的状态中，直到被父进程回收。这时候的子进程被称为僵尸进程。当父进程回收子进程后，内核将子进程的退出状态传递给父进程，然后清除子进程，这个时候子进程就不存在了。

如果一个父进程终止。它的子进程就被称为孤儿进程，内核会安排init进程成为它的孤儿进程的养父，init进程的pid为1，是在系统启动时由内核创建的，它是所有进程的祖先进程。如果父进程没有回收僵尸进程就死了，init进程会回收僵尸进程，不过长时间运行的程序比如shell或者服务器，总是应该回收它们的僵尸子进程，即使僵尸子进程没有运行，他们仍然消耗系统的内存资源。

一个进程可以通过waitpid函数来等待它的子进程终止或者停止。如果子进程已经终止，那么立即返回，如果子进程没有终止，挂起当前进程，等待子进程终止后返回，返回值为子进程的pid。此时，子进程已经被回收，内核会删除掉它的所有痕迹。

进程的执行顺序和回收顺序都是由操作系统内核通过异常控制流切换执行的，所以我们不能假设他们的执行顺序和回收顺序。

信号

Linux信号允许进程和内核中断其他进程。一个信号就是一条小消息，它通知进程系统中发生了一个某种类型的事件。每个信号类型都对应一个系统事件，底层的硬件异常由内核异常处理程序处理的，正常情况下，对用户进程是不可见的。

下图是一些信号

传送信号分为两部分

1. 发送信号。内核通过更新进程上下文中的某个状态，发送一个信号，可能有下面的原因
   • 内核检测到一个系统事件，比如除0或者子程序终止
   • 一个进程调用了kill函数，显式的发送一个信号
2. 接收信号。当进程被内核强迫以某种方式对信号作出反应时，就接收了信号。进程可以忽略这个信号，终止或者通过执行信号处理程序来处理信号。
3. 一个发出但没有被接收的信号叫做待处理信号。在任何时刻，一种类型至多只有一个待处理信号。

发送信号的几种方式

• kill程序，kill -9 pid
• kill函数，kill(pid, sig)
• alarm函数，给自己发送SIGALRM信号
• 键盘，ctrl+c会发送SIGINT信号，默认终止前台作业，ctrl+z会发送SIGTSTP信号，默认挂起前台作业。

前台作业和后台作业，系统只能有一个前台作业，但是可以有多个后台作业，前台作业就是通过waitpid等待程序在前台完成的，后台作业是运行在后台的，一般在命令最后面加上&就可以让程序后台运行。

接收信号的几种处理

1. 忽略该信号
2. 进程终止
3. 用户程序捕获信号并处理

可以通过signal函数来捕获信号并处理，第一个参数是信号，第二个参数是处理函数，如果处理函数是SIG_IGN，则忽略该信号，如果是SIG_DFL，则采用信号的默认行为处理，如果是一个函数，则执行他进行处理。

待处理的信号只能有一个。再过来一个同类型的信号就会被丢弃，实际上处理方式是有一个Pending的位，如果有6个信号，Pending就有6位，一个信号对应一位，当有一个待处理信号的时候，相应的位就变成1，所以最多只有一个待处理，剩下的会被丢弃。所以我们不能假设所有的信号都能被接收并且处理。

为了解决上面的问题，就出现了阻塞信号。通过阻塞信号可以暂时阻塞住信号，不接收它，等我们把待处理信号处理了再解除阻塞然后接受它，这样的话就可以接收到每一个信号并处理了，同样的阻塞信号是通过Blocked位来实现的，有6个信号那么Blocked就有6位，阻塞一个信号，对应的位就变成1.

可以通过sigprocmask函数来设置Blocked位，他有三个参数，第一个参数决定了行为，第二个参数是一个set变量用来设置Blocked位，第三个参数是返回一个oldset变量来存储以前的Blocked位，当解除阻塞以后用来恢复Bloked位的。

第一个参数值

• SIG_BLOCK: 把set中的位添加到Bloked中，相当于Blocked = Blokced | set
• SIG_UNBLOCK: 从Blocked中删除set中的位，相当于 Blocked = Blocked & ~set
• SIG_SETMASK: Blocked = set

使用下面的函数可以操作set变量中的位。

• sigemptyset。初始化set为空集合
• sigfillset. 把每个信号都添加到set中
• sigaddset. 添加某个信号到set中
• sigdelset. 从set中删除某个信号
• sigismember. 判断某个信号是否在set中。

信号处理程序的编写很麻烦，因为它和其他信号处理程序以及主程序都是并发执行的。为了保证安全，要尽可能的保守，以下是一些基本原则。

• 处理程序要尽可能简单。避免麻烦的最好方法是保持处理程序尽可能小和简 单。例如，处理程序可能只是简单地设置全局标志并立即返回;所有与接收信号相 关的处理都由主程序执行，它周期性地检查(并重置)这个标志
• 在处理程序中只调用异步信号安全的函数。所谓异步信号安全的函数(或简称安全的函 数)能够被信号处理程序安全地调用，原因有二:要么它是可重入的， 要么它不能被信号处理程序中断.
• 信号处理程序中产生输出唯一安全的方法是使用 write 函数
• 保存和恢复errno。许多Linux异步信号安全的函数都会在出错返回时设置 errno 。
• 阻塞所有的信号，保护对共享全局数据结构的访问
• 用 volatile 声明全局变量 。
• 用 sig_atomic_t 声明标志。在常见的处理程序设计中，处理程序会写全局标 志来记录收到了信号。主程序周期性地读这个标志，响应信号，再清除该标志。对于通过这种方式来共享的标志 ， C 提供一种整型数据类型 sig_atomic_t， 对它的读和写保证会是原子的(不可中断的)，因为可以用一条指令来实现它们

非本地跳转

当程序返回的时候一般都是通过调用栈一层层返回，有的时候会很麻烦，为了避免这种情况，出现了非本地跳转，它通过setjmp和longjmp来进行直接跳转，避免了一层层返回。

setjmp保存当前的运行环境，longjmp可以跳回setjmp的地方。

C++和Java 提供的异常机制是较高层次的，是C语言的setjmp和longjmp 函数的更加结构化的版本。你可以把try语句中的catch 子句看做类似于setjmp函数。相似地，throw语句就类似于longjmp 函数。

系统级IO

在Linux中，所有的一切都是文件。所以文件读取可以控制一切，包括磁盘读写，网络编程都是通过文件IO来控制的。一个Linux文件就是一个m个字节的序列。

Unix IO接口提供了对文件的控制

• 打开文件。返回一个文件描述符
• 读取文件。读操作就是将文件内容复制到内存中。
• 写文件。写操作就是将内存中的内容写入到文件中。
• 改变当前的文件读写指针位置。打开文件的时候，初始为0.
• 关闭文件。关闭这个文件。

Linux shell创建的每个进程开始时都有三个打开的文件:标准输入(描述符为0)、标准输出(描述符为1)和标准错误(描述符为2)

每个文件都有一个类型

• 普通文件：包含任意数据，操作系统并不区分文本文件和二进制文件，在更高层的级别有的会区分
  • 文本文件： 只含有ASCII和 Unicode 字符的普通文件。
  • 二进制文件： 所有其他的普通文件，对于内核来说，二进制和文本文件没有区别。
• 目录：包含一组链接的文件，其中每个链接都将一个文件名映射到一个文件，这个文件也可能是另一个目录，每个目录至少含有两个条目
  • .是该目录自身的链接
  • ..是父目录的链接
• socket：是用来与另一个进程进行跨网络通信的文件

Linux将所有文件都组织成一个目录结构，最上面是/根目录，其他所有目录都是它的子级。

打开文件以后返回的文件描述符总是在进程中当前没有打开的最小描述符。通过系统的limit命令可以看到当前系统可以同时打开的文件数量。

Unix对文件的读取和写入操作可能会遇到不足值(short count)的问题。比如你要读取一个文件的前100个字节，但是这个文件每行50个字节，所以51个字节就是换行符EOL，换行符在Linux/mac里面是LF,在win里面是CRLF。当遇到换行的时候只会读入换行前的50个字节，然后读取换行的时候会读取0个字节，再之后才能读取下一行。下面是几种会遇到不足值的情况。

• 读的时候遇到换行
• 从终端读文本。从终端读取的话，read一次读取一行
• 读写socket

RIO包

RIO包解决了不足值的问题，它提供了两类函数

• 无缓冲输入输出：没有应用级缓冲，对二进制数据读写到网络和从网络读写二进制数据尤其有用
• 有缓冲输入输出：先读取或写入到缓冲区里面，在调用系统的read/write来读写。效率更高，开销小，RIO还是线程安全的。

无缓冲输入输出

• rio_readn(int fd, void * usrbuf, size_t n):从fd文件描述符中读取n个字节到内存usrbuf中
• rio_writen(int fd, void * usrbuf, size_t n):从内存usrbuf中写入n个字节到fd中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

ssize_t rio_readn(int fd, void *usbuf, size_t n) {
    size_t nleft = n;
    ssize_t nread;
    char *bufp =usrbuf;

    // 没读取够需要的n个字节就一直循环读取
    while (nleft > 0) {
        // 从fd中读取nleft个字节到内存bufp中 
        if ((nread = read(fd, bufp, nleft)) ‹ 0)  {
            // 如果读取失败 判断失败类型如果是被信号打断则再次读取，如果是其他失败，则返回失败
            if (errno = EINTR) /* Interrupted by sig handler return */
                nread =0; /*andcall read()again*/
            else
                return -1; /* errno set by read() */
        } else if (nread = 0)
            // 如果是读取到0个，则是读取到换行符，继续读取
            break; /* EOF */
        // 读取的字节数变少，bufp增加
        nleft -= nread;
        bufp += nread;
    }
    // 返回读取到的字节数
    return n - nleft; /* Return >= 0 */
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

ssize_t rio_writen(int fd, void *usrbuf, size_t n)
{
    size_t nleft =n;
    ssize_t nwritten;
    char *bufp =usrbuf;
    while (nleft >0) {

        if ((nwritten =write(fd, bufp, nleft)) « 0) {

            if (errno = EINTR) /* Interrupted by sig handler return */ 
                written = 0; /* and call write() again */
            else
                return -1; /* errno set by write() */
        }
        nleft -= nwritten;
        bufp += nwritten;
    }
    return n;
}

有缓冲输入输出

• rio_readinitb(rio_t *rp, int fd): 初始化一个读取的缓冲区rp，读取的时候会先从fd文件中读取数据到rp缓冲区里面，然后在从缓冲区读取
• rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen): 从缓冲区rp中读取一个文本行到内存usrbuf中，最多maxlen-1个字节，最后以NULL结尾。如果一行不足maxlen-1，则读取一整行，如果超过maxlen-1，就截断他
• rio_readnb(rio_t *rp, void *usrbuf, size_t n): 对于既包含文本行也包含二进制数据的读取可以使用这个函数，它是rio_readn带缓冲区的版本。

下面是缓冲区rio_t结构体

1
2
3
4
5
6

typedef struct {
    int rio_fd; /* 文件描述符fd */ 
    int rio_cnt; /* 缓冲区未读取的字节数 */ 
    char *rio_bufptr; /* 下一个要读取的指针 */ 
    char rio_buf [RIO_BUFSIZE]; /* 缓冲区 */
} rio_t;

1
2
3
4
5

void rio_readinitb(rio_t *rp, int fd) {
    rp->rio_fd =fd;
    rp->rio_cnt = 0;
    rp->rio_bufptr = rp->rio_buf;
}

读取最核心的是rio_read函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

static ssize_t rio_read(rio_t *rp , char *usrbuf, size_t n) {
    int cnt;

    // 开始读取数据到缓冲区rp
    while (rp->rio_cnt <= 0) { /* Refill if buf is empty */
        // 调用 read读取
        rp->rio_cnt = read(rp->rio_fd, rp->rio_buf, sizeof(rp->rio_buf));
        // 判断是否读取失败
        if (rp->rio_cnt < 0) {
            // 如果不是被信号打断，就是真的失败，返回-1 如果是被打断的话回到while继续读取
            if (errno != EINTR)
                return -1;
        } else if (rp->rio_cnt == 0) {
            // 读取到换行符，继续读取
            return 0;
        } else {
            // 读取成功 缓冲区指针指向缓冲区开头
            rp->rio_bufptr = rp->rio_buf; /* Reset buffer ptr */
        }
    }

    // 开始冲缓冲区读取数据到usrbuf
    /* Copy min(n, rp-›rio_cnt) bytes from internal buf to user buf */
    // 默认读取n个字节，如果缓冲区不足n个，就读取整个缓冲区
    cnt = n;
    if (rp->rio_cnt < n) {
        cnt = rp->rio_cnt;
    }
    // 从缓冲区读取到usrbuf
    memcpy(usrbuf, rp->rio_bufptr, cnt);
    // 修改缓冲区指针
    rp->rio_bufptr += cnt;
    // 修改缓冲区未读字节数量
    rp->rio_cnt -= cnt;
    // 返回读取的字节数
    return cnt;
}

rio_readlineb和rio_readnb都是用了rio_read函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

ssize_t rio_readlineb(rio_t *rp, void *usrbuf, size_t maxlen) {
    int n,rc;
    char c, *bufp = usrbuf;

    // 循环从缓冲区读取
    for (n = 1; n < maxlen; n++) {
        // 从缓冲区读取1个字节到c里面 如果rc == 1则读取成功
        if ((rc = rio_read(rp, &c, 1)) == 1) {
            // 读取成功把读取到的字节放到bufp指向的usrbuf位置 然后bufp指向下一个usrbuf字节
            *bufp++ = c;
            // 如果读取到的是换行 n++再次读取
            if (c == '\n') {
                n++;
                break;
            }
        } else if (rc == 0) {
            // 读取EOF
            if (n == 1)
                return 0;
            else
                break;
        } else {
            // 出错，返回-1表示错误
            return -1;
        }
    }
    // 读取结束以后重制bufp指针
    *bufp = 0;
    // 返回 读取字节数
    return n - 1;
}

和上面的rio_readn唯一的区别就是read换成了rio_read，因此里面也不需要在判断是否被信号打断了，因为rio_read已经判断了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

ssize_t rio_readnb(rio_t *rp, void *usrbuf, size_t n) {
    size_t nleft = n;
    ssize_t nread;
    char *bufp =usrbuf;

    // 没读取够需要的n个字节就一直循环读取
    while (nleft > 0) {
        // 从fd中读取nleft个字节到内存bufp中 
        if ((nread = rio_read(fd, bufp, nleft)) ‹ 0)  {
            return -1; /* errno set by read() */
        } else if (nread = 0)
            // 如果是读取到0个，则是读取到换行符，继续读取
            break; /* EOF */
        // 读取的字节数变少，bufp增加
        nleft -= nread;
        bufp += nread;
    }
    // 返回读取到的字节数
    return n - nleft; /* Return >= 0 */
}

文件元数据

有两个函数可以获取文件元数据

• stat(const char *filename, struct stat *buf): 第一个参数是文件名，第二个参数是文件元数据的结构体。
• fstat(int fd, struct stat *buf): 第一个参数是文件描述符，第二个参数是文件元数据的结构体。

文件元数据结构体

共享文件和文件重定向

内核用三个数据结构来表示打开的文件

• 描述符表(descriptor table): 每个进程都有独立的描述符表，里面每个表项是一个指针，指向一个打开文件表，每个进程一开始的描述符表都有三个指针，指向stdin,stdout,stderr
• 打开文件表(open file table): 所有进程共享的打开文件表，记录了所有打开的文件，记录了当前的文件位置，引用计数，指向v-node表的指针。调用close关闭文件会减少引用计数，当达到0,内核才会删除这个表项。
• v-node表(v-node table)：所有进程共享v-node表，记录了stat结构中的大部分信息

1

注意：当fork的时候，子进程会继承父进程的描述符表，打开文件表的引用计数会+1，这个时候想彻底关闭文件，需要两个进程都close才行。

可以使用dup2函数来实现IO重定向，也就是Linux里面的>功能，在linux中，cat a.c > b.c可以把cat a.c的输出内容重定向输入到b.c文件中。

• dup2(int oldfd, int newfd): 复制描述符表oldfd到newfd，覆盖newfd以前的内容，如果newfd已经打开，会先关闭它再复制。

执行dup2(4,1)的意思是复制描述符fd4的内容给fd1,覆盖fd1原来的内容，假设原来fd1指向标准输出，复制以后fd1的输出将不再输出到标准输出，而是输出到fd4指向的打开文件里面。也就是将fd1的输出重定向到了fd4

C程序还提供了标准IO库，和RIO一样对Unix IO进行了封装，不过标准IO不适合网络读写，所以网络读写应该使用RIO，其他情况都应该使用标准IO。

虚拟内存

MMU（Memory Management Unit）来进行虚拟地址到物理地址的转化。

虚拟内存也像磁盘一样，划分为一个个块，虚拟内存里面一个块叫做一页，虚拟页面，物理内存同样分成一个个页面，称为物理页面。

在任意时刻，虚拟页面的集合都分为三个不相交的子集:

• 未分配的：还没有分配出去的虚拟页面，不占用任何磁盘空间和内存
• 缓存的：已经分配出去且加载到物理内存中的页面
• 未缓存的：已经分配出去，但是还在磁盘里面，没有加载到物理内存中的页面

因为主存不命中的话需要到磁盘去加载数据，这样会很慢，所以主页页面通常比较大，在4KB - 2MB，由于大的不命中处罚，所以主存是全相连的。任何虚拟页都可以放在任何物理页中。因为对磁盘的访问时间很长，所以主存总是用写回法，而不是直写法。

页表(page table)存储了虚拟页是否加载到物理页中，以及物理页的地址，页表中的每一项叫做页表条目(Page Table Entry)，简称PTE。

下图展示了虚拟页VP1,VP2,VP4,VP7已经加载到了物理内存中，对应的PTE里面的有效位是1，PTE里面还记录了对应的物理页面地址。VP0和VP5则处于未分配状态。剩下的VP3,VP6则在磁盘里面。

命中，如果通过虚拟页找到对应的PTE，发现valid == 1，就可以直接取出物理地址，去物理内存中获取对应的信息。

不命中,如果通过虚拟页找到对应的PTE,发现valid == 0，那么需要进入缺页异常处理程序，先选择出一个victim page，如果victim page有修改，需要写回磁盘，然后把新的页面装入物理内存。当缺页异常处理完毕以后，返回程序继续处理，进入命中流程。

如果程序有好的局部性的话，虚拟内存将工作的很好，不命中会很少，因为都集中在局部性这几页中，如果程序局部性不好，可能就会发生抖动，虚拟内存不断的换入换出。

你可以利用Linux的getrusage函数监测缺页的数量 (以及许多其他的信息)

页表中还有一些位来表示权限，SUP位为1表示只有内核可以访问这个PTE,用户程序不可以，READ则表示可以读取这个PTE的内容，WRITE表示可以写入这个PTE的内容。如果违反了这些，会触发异常段错误(segmentation fault)

地址翻译

每个进程有自己的页表，当前进程页表的起始地址存放在页表基址寄存器PTBR中，n位的虚拟地址包含两个部分，一个p位的虚拟页面偏移VPO(Virtual Page Offset)和一个n-p位的虚拟页号VPN(Virtual Page Number)。

1. MMU根据虚拟地址的VPN从页表中获取到对应的PTE
2. 如果命中，就把PTE里面存储的PPN和虚拟地址的VPO拼接起来成为物理地址,因为物理页面和虚拟页面都是p字节的，所以VPO等于PPO,可以把VPO直接拿来用。
3. 根据物理地址去cache获取数据

由于每次地址翻译都需要获取PTE,如果PTE不在cache中还需要去主存获取，所以速度会下降，在MMU中添加了一个翻译后备缓冲器TLB(Translation Lookaside Buffer)来加快速度，TLB中缓存了页表的数据，从TLB中获取页表的速度要比cache中获取更快。在虚拟页号VPN中，再次被分为了两部分，如果TLB有T = 2^t个组，两部分分别是t位的TLB索引(TLBI)和n-p-t位的TLB的tag TLBT。

TLB的执行步骤

1. MMU根据虚拟地址中的TLBI从TLB中取到对应的PTE
   • 如果没有命中，则从cache获取PTE
2. 如果命中，就把PTE里面存储的PPN和虚拟地址的VPO拼接起来成为物理地址,因为物理页面和虚拟页面都是p字节的，所以VPO等于PPO,可以把VPO直接拿来用。
3. 根据物理地址去cache获取数据

一个页表装载现在所有的内存地址，可能会很大，甚至比整个内存都要大，因此，可以使用多级页表的方式来组织页表。一级页表里面存放的是对应的二级页表的地址，以此类推。只有最后一个页表中包含的是物理页面号PPN。

• 多级页表可以大大减少一级页表的大小，虚拟地址空间大部分都是未分配的，而未分配的一级页表项则不存在对应的二级页表项。
• 只有一级页表才需要总是在主存中，虚拟内存系统可以在需要时创建，页面调入或调出二级页表，这就减少了主存的压力，只有最经常使用的二级页表才需要缓存在主存中。

动态内存分配

在内存的堆中动态的分配内存，内核维护着一个变量brk，指向堆的顶部。分配器将堆视为一组不同大小大的块的集合，每个块就是连续的虚拟内存片，要么是已分配的，要么是空闲的。

分配器有两种

• 显式：比如C中通过malloc来分配，通过free来释放
• 隐式：比如java中通过垃圾收集器gc来自动释放

显式分配器必须在一些相当严格的约束条件下工作

• 处理任意的malloc和free请求序列。
• 立即响应请求
• 只使用堆
• 对齐块(对齐要求)
• 不修改已分配的块

在这些限制条件下，试图实现吞吐率最大化和内存使用率最大化。

一个实际的分配器要在吞吐率和利用率之间把握好平衡，就必须考虑以下几个问题：

• 空闲块组织：字节数组？链表？双向链表？分离链表？
• 放置：如何选择一个合适的空闲块放置新分配的块，最先适配？最优适配？最坏适配？
• 分割：在将新块放置到某个空闲块之后，如何处理这个空闲块的剩余部分
• 合并：如何处理一个刚别释放的块,在free的时候是立即合并？还是延迟合并？

隐式空闲链表

将空闲块大小信息放入空闲块头部，返回指针的时候返回指向payload的指针。如果是8字节对齐的，那么size的最低3位总是0，可以用来存放其他信息，比如最低位来存放是否分配，1已经分配，0还是空闲块

网络编程

每个网络应用都是基于客户端 - 服务器模型的。采用这个模型，一个应用是由一个服务器进程和一个或者多个客户端进程组成。服务器管理某种资源，并且通过操作这种资源 来为它的客户端提供某种服务。

主机A和LAN1相连，它发送一段数据字节到主机B，主机B和LAN2相连

• 主机A的客户端进行一个系统调用，从客户端的虚拟地址空间复制数据到内核缓冲区
• 主机A上的协议软件通过在数据前附加互联网络包头和LAN1帧头，创建了一个LAN1的帧。网络包头寻址到网络主机B，LAN1帧头寻址到路由器。然后它传送此帧到适配器。
• LAN1适配器复制该帧到网络上
• 此帧到达路由器，路由器的LAN1适配器从电缆上读取它，并把它传送给协议软件
• 路由器提取网络包头，根据路由表确定往哪里转发，确定为LAN2，去掉LAN1帧头，添加LAN2帧头，并把新的帧传送到适配器
• 路由器的LAN2适配器将该帧复制到网络上
• 此帧到达主机B，适配器从电缆上读取此帧并传送给协议软件
• 最后，主机B的协议软件剥落帧头和网络包头，当服务器进行读取这些数据的系统调用时，协议软件将数据复制到服务器的虚拟地址空间。

每个主机都运行TCP/IP协议。因特网的客户端和服务器混合使用套接字接又函数和Unix I/O函数来进行通信。通常将套接字函数实现为系统调用，这些系统调用会陷入内核，并调用各种内核模式的 TCP/IP 函数。

IP协议提供基本的命名方法和递送机制，能从一台网络主机往其他主机发送包，也叫数据报。IP协议是不可靠的，如果数据报

套接字接口(socket interface)是一组函数，它们和Unix I /O函数结合起来，用以创建 网络应用。

从Linux内核的角度来看， 一个套接字就是通信的一个端点。从Linux程序的角度来看，套接字就是一个有相应描述符的打开文件。

并发编程

现代操作系统提供了三种并发编程的方法

• 进程：由内核调度维护，每个进程有独立的虚拟地址空间，想要和其他进程通信，必须使用某种显示的进程间通信机制。需要注意子进程的回收，避免僵尸进程。需要注意子进程会复制父进程的一切，包括文件描述符等，注意关闭不需要的文件描述符。不然内核不会回收它们。
• IO多路复用：应用程序在一个进程的上下文中显示的调度它们自己的逻辑流。逻辑流被模拟成状态机，数据到达文件描述符后，改变文件的状态。因为程序是一个单独的进程，所以所有的流共享同一个虚拟地址空间，缺点是编写麻烦，代码复杂。
• 线程：线程是运行在一个单独进程的上下文中，由内核调度，所有线程共享同一个虚拟地址空间。

进程通过fork和execve来进行开发。

IO多路复用通过select或epoll函数来执行，它们会挂起当前进程，当文件描述符的状态改变的时候会触发对应的操作。

1
2
3
4
5
6
7
8
9

#include <sys/select.h>

// 返回已准备好的描述符的非零的个数，若出错则为-1
int select(int n, fd_set *fdset, NULL, NULL, NULL);

FD_ZERO(fd_set *fdset); //把fdset中的所有位置0
FD_CLR(int fd, fd_set *fdset); //清楚fdset中的fd bit
FD_SET(int fd, fd_set *fdset); //设置fdset中的fd bit
FD_ISSET(int fd, fd_set *fdset); //检查fdset中的fd bit是否设置

IO多路复用的优缺点

• 优点：能对程序的行为进行更好的控制；运行在同一个进程里面，共享同一个虚拟地址空间，能更好的共享数据；由于是单一进程，可以使用GDB进行调试，对调试很友好；执行性能优秀，不需要进程上下文切换这些。
• 缺点：更复杂的编码方式，随着要对程序行为更好的控制，和并发粒度的减小，都会变得更加复杂；由于只有一个进程，只能进行单核的并发，而无法充分发挥多核的并行性能。

除了多进程以外，还可以在一个进程里面运行多个线程，每个线程有线程上下文。它们包括

• 线程id
• 栈
• 栈指针
• 寄存器
• PC
• 条件寄存器

多个线程共享进程的虚拟地址空间，代码，数据，共享库和打开的文件，线程的切换开销更小。

线程的一些函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <pthread.h>

// 创建线程 tid是线程的ID，attr可以改变创建线程的默认属性，f是 线程要执行的函数，arg是传给线程函数的参数
int pthread_create(pthread_t *tid, pthread_attr_t *attr, func *f, void *arg);

// 在线程中通过这个方法获得自己的线程id
pthread_† pthread_self (void);

// 调用这个函数显示的终止线程，主线程调用会等待所有线程终止，然后在终止主线程和整个进程
void pthread_exit (void *thread_return);

// 终止某一个线程tid是线程id 任何线程都可以通过这个方法终止其他线程
int pthread_cancel (pthread_t tid);

// 线程通过调用这个函数等待其他线程终止 该函数会阻塞，直到tid线程终止
int pthread_join(pthread_t tid, void **thread_return);

在任何一个时间点上，线程是可结合的或可分离的。可结合的线程可以被其他线程收回和杀死。在被其他线程回收前，它的内存资源是不被释放的。一个分离的线程是不能被其他线程回收或杀死的。它的内存资源在它终止时由系统自动释放。

默认情况下，线程都是可结合的，可以通过下面的函数变成可分离的。

1
2

// 某个线程变成可分离的
int pthread_detach(pthread_† tid);

初始化线程。once_control 变量是一个全局或者静态变量，总是被初始化为PTHREAD_ONCE_INIT 。当你第一次用参数 once_control 调 用 pthread_.once 时，它调用 init_routine，这是一个没有输入参数、也不返回什么的函数。接下来的以once_control为参数 的pthread_once 调用不做任何事情。无论何时，当你需要动态初始化多个线程共享的全局变量时，Pthread_once 函数是很有用的

1
2

pthread_once_t once_control = PTHREAD_ONCE_INIT;
i n t pthread_once (pthread_once_t *once_control, void (*init_routine) (void));

用信号量同步线程

共享变量很方便，但也引入了同步错误的可能性。

假设两个线程操作同一个变量进行计数。我们预期cnt应该是200，但结果却不一定。

1

for (int i=0; i< 100; i++) cnt++;

cnt++虽然是一条指令，但是查看汇编可以发现，其实被分解成了三个指令，Load将cnt从内存加载到寄存器,Update更新cnt的值，Store将cnt写入内存。

如果按照顺序执行，是没有问题的。比如

• Load cnt=0
• Update cnt += 1
• Store cnt=1
• Load cnt = 1
• Update cnt += 1
• Store cnt = 2

但是多线程是并发执行的，我们不能假设它们的执行顺序，所以有可能是以下顺序执行

• Load cnt = 0
• Load cnt = 0
• Update cnt += 1
• Store cnt = 1
• UPdate cnt+=1
• Store cnt = 1

进度图(progress graphy)可以将n个并发线程的执行模型化为一条n维笛卡尔空间中的轨迹线。每条轴k对应线程k的进度。每个点代表已经完成了Ik这个状态。

将两个线程的执行化成进度图，如下：从左下角开始，任意一条可以到达右上角的链接线都是可能的执行顺序。

对于这两个线程来说，Load,Update,Store这三个指令构成了一个临界区。只要确保每次只有一个线程在执行临界区的代码，就可以保证顺序。也就是对共享变量的互斥访问。

两个临界区的交集形成的空间叫做不安全区(unsafe region)。没有经过不安全区的路线叫做安全路线，经过不安全区的叫做不安全路线。所有的安全路线都可以得到正确的结果，而不安全路线将得到错误的结果。

通过信号量(semaphore)可以阻止代码走到不安全路线上面。信号量s是具有非负整数值的全局变量。只能由两种特殊的操作来处理：

• P(s): 如果s非0，那么将s减去1，并且立即返回。
  • 如果s是0，那么挂起这个线程，直到s非0为止
  • V操作会重启这个线程，重启后，将s减1，并将控制返回给调用者。
• V(s): 将s加1。如果有任何线程阻塞在P操作中，V会重启其中的一个。

P操作和V操作都是不可分割的，不会被中断。

下面是操作信号量的函数

1
2
3
4
5
6
7

#include <semaphore.h>

// 使用信号量前需要通过sem_init初始化，初始化sem为value值
int sem_init (sem_t *sem, 0, unsigned int value);
int sem_wait (sem_t *s); /* P(s) */
int sem_post (sem_t *s); /* V(s) */