引言

之所以有这个疑问,是上次阅读Java基础书时碰到讲解char类型没有看明白,并且在代码验证过程中错误的理解了代码的意思,导致我对这么个简单问题产生疑惑并且“恶意揣测”Java内部的黑魔法,这里就把我如何走上歪路,并且最终找到“正确”的道路的故事讲出来

问题的产生

我们知道Java是采用Unicode进行内部编码,但是使用UTF-16作为外部编码。

怎么来理解这个东西呢。首先你要知道Unicode是在我们熟悉的GB 18030BIG-5ISO8859-1之后出现的,它的出现就是为了统一全世界的编码,因为前面这些编码都太片面了,只包含自己国家或者少数几个国家的字符。

Unicode的目的就是包括全世界的编码,并且给未来可能出现的编码留下位置,你可以理解为它是一张大“表”,一般我们使用16进制来表达它,并且在前面加上U+。例如U+0041代表字母A,但是这里有个历史问题

一开始我们知道Unicode为了包含全世界的字符从ASCII的一个字节扩展到两个字节,就能包含65536个字符了,但是随着字符包含越来越多,我们逐渐需要更多字符了,最后扩展到U+0000 -> U+10FFFF去了,为了表示这些我们必须使用三个字符,假设我们不考虑内存成本,每个字符都使用四个字符来表示(不使用三个是为了内存对齐),那么问题就解决了,大家都用Unicode来表示,这样我传给你一串字符你就能秒懂了。

但是学过信息论就知道,单字符越长信息熵也就是信息量就少,其实在日常通信中我们并不是每个字符都会用到,为了提高效率,我们可以使用霍夫曼、香农编码技术对信息重新编码,这个就是UTF-8UTF-16等现代编码的理论基础。

这就好比特种部队手势,我们把作战命令(Unicode)需要的指令放到手势(如UTF-8)里面,这样几个手势就能表达复杂的作战计划(假如用嘴巴说的话)。

接下来我们就从JAVA和Python来看,编码与其关系

表面兄弟:JAVA

Unicode对于JAVA来说,只能算是表面兄弟,虽然内部支持Unicode编码,但是其本质还是基于UTF-16编码,为什么要这么说呢。

我们来回顾一下,我们知道Unicode的范围是U+0000-U+10ffff,这意味着我们没法用两个字节来表示,但是在Java里面char类型字节为2字节,而对于字符串类String来说,其组成就是一个char字组,对于小于U+10000Unicode码来说,String对象最小组成单位就是char,但是对于大于U+10000Unicode码来说却是char数组,我们用代码来展示一下两者之间的关系。

char[] chars = Character.toChars(0x1f121);
String s = new String(chars);

而且我们将s输出的话,会发现它是一个字符,但是它的length却为二,而且我们将s每个字符转换成二进制你会发现他们的值依次为0xd83c0xdd21,他们存贮的值全部以UTF-16的格式存贮,具体编码详细我就不细说了,下面资料介绍的很详细(需要翻墙)。在Unicode里面占一个字符的值,却以两个基本类型存贮,当然为了维持这种“表面兄弟”的关系,Java也使用了“码点”来支持一下兄弟,只要使用codePointAt代替charAt,用codePointCount代替length,我们也能处理超过U+10000Unicode编码(对于不超过U+10000的字符那就是“真兄弟”)

当我不知道一个char只能放两个字节的时候,我强行使用char c = (char)0x1f121来“存”一个超过U+10000Unicode码,结果被Java无情的溢出掉,只取到了部分值,但是我却误以为Java有黑魔法能用两个字节存贮了三个字节才能存下的值,乃至我闹了个笑话。

总结一下Java是一个非常严谨的语言,规定死的东西就不会变,表面上看Java能够支持Unicode编码,但是实际上他只是编译器支持,比如你写一个🄡(0x1f122)的值来赋给String如下面:

String ns = "🄡"

表面上看,Java完全支持Unicode码,但在实际的上面他内部还是用UTF-16进行编码,只是在编译的时候帮我们将0x1f122转换成为两个
0xd83c0xdd21存贮在char字符组里面。

其实这个表面兄弟是相对的,从Python3``Unicode支持来比较一下就能发现不同。

亲兄弟:Python

Python3Unicode是非常友好的,它在明面上完全按照Unicode的编码表使用来存贮Unicode码,对应它的Unicode字符串,最小单元都是Unicode码,多说无意,上代码。

  c = chr(0x1f122)
print(len(c))  # = 1
print(type(c)) # str

我们可以看到我们得到的最小的码元是字符串str类型,无论这个Unicode码是否大于U+10000Python都把它视为一个基本单位,这样避免了你对其进行一些误操作,插句话来讲讲怎么得到这个大小呢,我们使用sys.getsizeof方法就能计算出来

sys.getsizeof(chr(0x1f122))  # 80
sys.getsizeof(chr(0x1f122) * 2) # 84

由于Python使用一些字段来标注类型,所以直接使用sys.getsizeof得不得一个Unicode码需要的字节,所以我们计算两个的差,很清楚的就能得到一个Unicode码使用四个字节,你可以依次乘下去,而且你发现一个有趣的现象,对于小于U+007FUnicode码,其大小为一字节,而对于U+0080-U+07FF其大小为两字节。具体可以看参考资料Python内部是使用UTF-8来存贮Unicode码的,但是Python将这一切都隐藏起来,你从表面上看好像一个Unicode就是一个最小单元,对于其底层我们不得而知,我们可以从侧面来验证一下

 timeit.timeit("'中国人'.encode('gbk')")
>> 0.6366317819999949
timeit.timeit("'中国人'.encode('utf-8')")
>> 0.2109854949999317

我们可以看到将Unicode编译成其他编码方式,其中utf-8速度是最快的,因为基本上是复制一下就行了,而其他的差距到了三倍

总结

通过前面我们知道,Python之所以 Unicode如此“亲兄弟”是因为做了一层封装得来的,相比JavaUnicode码(使用UTF-16作为底层编码)暴露给出来,Java在底层上却是非常“坦诚”,你想直接使用Unicode码值也可以,Java编译器会帮你把Unicode码值转换成UTF-16,你也可以从UTF-16码生成String字符串,这样底层在实现查找的时候也是使用统一的编码进行。但是也正是由于这么“底层”,代码看起来总不是那么“亲”,相比于Python的“一视同仁”,我们也可以理解这就是这两种语言的各自特点所在。

总的来说如果你想直接接触代码底层,推荐使用Java,假如你只想研究其本质,推荐使用Python来进行自然语言处理,他的封装能让你不需要了解其内部组成。

引用

https://zh.wikipedia.org/wiki/UTF-16

https://en.wikipedia.org/wiki/UTF-8

Spring的IOC理解

什么是IOC

在这里我们不谈Spring的基础知识,我们知道谈到Spring就会谈到IOC,这个IOC是什么呢,中文名叫控制反转,这个东西是伴随着一些编程思想出现,其实同Java的本身也有关

就好比我熟悉的Python就是一个鸭子语言,你可以随便把一个值丢掉函数里面去,只要他满足一些特性就能正常运行,但是Java是一种强类型语言,你函数给什么参数,必须传什么参数

这里就不讨论两张语言的设计优劣呢,Java这种特性也做了一些妥协,我们肯定得为语言的扩展性做点事,谁也不知道未来会发生什么,Java里面使用多态来实现这种扩展,只要他是函数参数的家族成员,他就能上去运行

这个多态是实现IOC的基础,但是造成他出现的原因是因为设计模式里面的单一职责原则,这个要求我们类功能要单一,我们这里给一个例子来说明这个问题

class Car {
    void run() {
        System.out.println("Car running...");
    }
}

首先我们有一个Car的类,一开始我们只让他有run这个属性,很好,接下来我们想知道是谁驾驶这辆车,于是我们便给这个类加一个字段driver

public class Car {
    String driver;
    public Car(String driver) {
        this.driver = driver;
    }
    void run() {
        System.out.println("Driver :" + driver);
        System.out.println("Car running...");
    }
}

很好我们知道驾驶这辆车的人,接着我们又想知道这个驾驶人的驾龄,如果我们继续给Car加入字段,这样我们就违背了单一职责原则,Car类不但承担了车的功能还承担了人的功能

于是我们就把驾驶人隔离出来

class Driver{
    String name;
    String age;
    public Driver(String name, String age) {
        this.name = name;
        this.age = age;
    }
}


class Car {
    Driver driver;
    public Car(Driver driver) {
        this.driver = driver;
    }
    void run() {
        System.out.println("Driver age:" + driver.age + "name: " + driver.name);
        System.out.println("Car running...");
    }
}

我们重新将类分成两个类来实现了这个问题,但是这个时候又来了一个问题,我们有一个飞行员的也想驾驶这辆车,但是这辆车只能司机来驾驶,但是飞行员和司机开车的动作步骤是一样的,为了复用run这个函数,你开始揪起了你的头发.

你想呀想突然想到,Java的多态,假如我们声明一个IDriver的接口,让飞行员和司机都继承这个类这样我们只要给车一个IDriver对象就能复用run函数

//IDriver.java
public interface IDriver{
    String getName();
    void setName(String name);
    int getAge();
    void setAge(int age);
}

// Driver.java
public class Driver implements IDriver{
    String name;
    int age;


    @Override
    public String getName() {
        return this.name;
    }

    @Override
    public void setName(String name) {
        this.name = name;
    }

    @Override
    public int getAge() {
        return this.age;
    }

    @Override
    public void setAge(int age) {
        this.age = age;
    }
}



// Aviator.java
public class Aviator implements IDriver{
    String name;
    int age;


    @Override
    public String getName() {
        return null;
    }

    @Override
    public void setName(String name) {

    }

    @Override
    public int getAge() {
        return 0;
    }

    @Override
    public void setAge(int age) {

    }
}


//Car.java
public class Car {
    private IDriver driver;

    public void setDriver(IDriver driver) {
        this.driver = driver;
    }

    void run() {
        System.out.println("Driver age: " + driver.getAge() + " name: " + driver.getName());
        System.out.println("Car running...");
    }
}

我们重构代码把Driver抽象为接口,然后让司机和飞行员都继承它,这样不管我们再添加什么其他的人就能适配这辆车.这个就是依赖倒置(DI)的思想

网上大部分教程就停留到这里了,这里我们继续探索下去,看看Spring是如何让这个DI更加简单的

首先我们反思一下,我们使用接口参数让我们的代码符合了设计模式,但是也带来了一些繁琐,我们来用代码”开”这辆车

IDriver driver = new Driver();
driver.setName("allen");
driver.setAge(18);
Car car = new Car();
car.setDriver(driver);
car.run();

PS:当然可以把赋值放到构造器中减少代码,但是由于Bean依赖方法接口来赋值,所以为了后面讲解Bean这里就不采用构造器来减少代码

代码有2行变成了6行,而且我们发现这个代码现在带来两个问题:

  1. 每次运行都得创建一个实现IDriver的对象
  2. 每次我们想换人开车的时候都得修改源代码

而且这些工作都很繁琐,作为一个偷懒的程序员,我可不想给每个用户都重新写一套代码,我们的想法很简单,我们希望这个Car能够开箱即用,其实前面我们已经实现了控制反转了,现在就是要解决控制反转带来的“负面影响”

而且我们发现了一个问题,假如我们把上面函数放到一个代码里面,每次我们“开车”都得创建一个司机,然而我们还是相信“老司机”的手艺,所以我们也希望是否能够”记住“司机,只让一个老司机开车

接下来就是隆重介绍SpringBean的用法了,前面我们知道我们需要某种机制来去除”IOC“的弊端,我们把每个Car当做一个对象,其实我们需要一个配置文件来记录IDriver这些依赖对象,对象的其实在Java里面表现就是一棵树,所以通俗来讲我们需一个”树结构“数据来存贮依赖关系

我们程序在运行的时候解析这个树结构,然后依次给对象注入你想给他实例话的对象(比如你把”IDriver“设置为飞行员),这样的话,我们把依赖关系成功放到了配置文件中

这样带来两个好处:

  1. 想给不同用户使用软件时候,源代码不需要改变,只要给他们不同的配置文件就行
  2. 我们可以保存依赖实现”老司机“的复用

所以现在我们理理思路,我们需要的有两个东西

  1. 配置文件
  2. 一个加载配置文件并保存依赖的对象

SpringBean中这两个分别对应xml文件和实现ResourceLoader接口对象(有多种实现)

为了更好的理解Bean,接下来我们就从代码出发来测试这个Bean

最简单的实现

首先我们新建一个Spring项目,无论你是用IntelliJ还是Eslipse都没关系,只能你能引用到Spring库就行,我们复用前面的代码,看看使用Spring Bean来如何解决掉IOC的”副作用“

我们把前面的类分别放到同一路径不同的文件夹中,接下来我们先创建一个xml文件,什么名字不重要,我们这里先命名为driver.xml

<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xsi:schemaLocation="http://www.springframework.org/schema/beans
    http://www.springframework.org/schema/beans/spring-beans.xsd">


    <bean id="car" class="Car">
        <property name="driver">
            <bean class="Driver">
                <property name="name" value="Allen"></property>
                <property name="age" value="18"></property>
            </bean>
        </property>

    </bean>
</beans>

写入这些东西,接下来我们看看是否能够通过这个xml文件来直接得到一个配置好司机Allen的车

随便新建一个类在上面的路径中,我们这里就新建一个Main

import org.springframework.context.ApplicationContext;
import org.springframework.context.support.ClassPathXmlApplicationContext;


public class Main {
    public static void main(String[] args) {
        ApplicationContext context = new ClassPathXmlApplicationContext("driver.xml");
        Car car  = context.getBean("car", Car.class);
        car.run();

    }
}

输出为

Driver age:18 name: Allen
Car running...

我们成功通过一个xml配置文件和一个ApplicationContext对象实现了一个即开即走的车,而且假如我们想换个司机,我们可以修改配置文件把class换成“飞行员”,而且我们可以发现我们得到的司机都是一样的,验证方法很简单,我就不写代码了,假如我们想换司机怎么办,简单在bean里面加上scope=“prototype”就行(默认值为singleton

接下来我们又有一个疑问,假如我们有一辆特别宝马车,我们希望只有某一种加上员能能开(假设只有飞行员),也就是是说,我们其实即不想放弃IOC,但是又不想将这个配置写到Bean里面去,有办法能够解决吗?

当然有,Spring2.5就支持注解来写Bean配置,对于一些固定的类,我们可以把依赖关系用代码写到类中,这样一方面能够保证IOC,一方面又能实现Bean xml文件瘦身

由于Spring默认不会去扫描注解,所以有三种方式,第一种是在xml里面用加上一个

<context:component-scan base-package="...."></context:component-scan>

第二种是使用AnnotationConfigApplicationContext来对象来进行扫描,第三种就是SpringApplication来运行Spring程序自动扫描

这三种方式假如你最后要做一个web程序的话,第三种是非常方便的,这里我们就不谈怎么使用注解来代替xml文件了,本质上是一样的,其实在我没有理解Bean的强大之前,我比较推崇使用注解来写Bean,但是随着对Bean的探索,我发现xml文件才是最佳选择,他将程序依赖与代码分离开来,假如我们还想用程序依赖写在代码里面,那就违背了Bean的设计初衷

如果你想了解怎么使用注解可以阅读这篇博客

总结

至此,我们从问题的出现到问题的解决探索了IOC背后的故事,但是你可能会有一个疑问,为什么Spring里面会有IOC问题。

其实这个也跟Web的发展有关,我们知道从Web的发展,一开始是没有前端的,只有后端,慢慢的后端分离出来前端,Web端页面也被分离出视图层和数据层,随着逐渐分离,也就出现我们前面举到的例子,类越来越多,比如视图层依赖数据层,数据层依赖控制层…..

这种层层依赖的问题延生出来的IOC的提出,也就慢慢的促进了Bean这个库的开发,也正是因为Bean我们才能享受静态强类型语言的低耦合的酸爽。

引言

本文是学习Tensorflow官方文档的过程中的一点感悟,本文假设你对矩阵运算有一定的了解,具体可以看看下面资料

加载数据

首先我们得先把数据下载下来,Tensorflow给我们提供了一个函数来进行下载,这个函数read_data_sets

这个函数read_data_sets函数很简单,查看在目录下面有没有文件没有就去下载,有就解析加载,一方面方便我们获取数据,一方面方便我们直接开箱即食,但是由于这个默认下载地址是需要翻墙,所以我这里提供一个不需要翻墙的地址,你只需要加载下面的函数

from tensorflow.examples.tutorials.mnist import input_data
mnist = input_data.read_data_sets("input/", one_hot=True, source_url="http://yann.lecun.com/exdb/mnist/")

等几分钟,数据就会下载到当前目录的input文件夹中,这样你下次运行就能直接本地文件夹中加载图片数据了

观察数据

首先我们看看下载了什么数据,打开input文件夹,我们可以看到,Tensorflow给我下载好了四个文件,分为两组,一组训练集一组测试集,每组里面2个文件,一个是手写图片文件,一个标签文件(每张手写的图片代表的数字)

加载图片数据对于新手来说挺麻烦的,为了让我们专注于模型而不是编程,Tensorflow直接帮我们做好了加载数据的事情,我们上面得到的mnist变量里面就存贮了我们这个项目所需要的数据,我们来看看这个mnist有什么

我们最关心的就是mnist里面训练数据,这里推荐使用notebook来操作这个数据集,我们首先mnist的训练数据是什么

mnist数据来源网络

mnist数据就是上面这些图片,我们把图片把每个像素的二值化,然后把他们放到一个数组中,每张图片对应一个数组

mnist训练数据存贮在这两个变量中

mnist.train.labels
mnist.train.images

其中mnist.train.images是一个(55000, 784)的二维数组,其中mnist.train.labels.shape是一个(55000, 10)的二维数组,现在摆在我们面前的其实很简单,通过55000个图片像素值来训练我们模型,以便能让模型能给一张图片像素值来预测图片代表的数字

这些数字在人看来非常容易辨认,但是怎么能让电脑也能辨别他呢,这就要用到卷积神经网络的力量,通过卷积神经网络,电脑的准确率能到99%,这就非常恐怖了,我们人有时候也会看走眼呢。

在谈卷积之前我们先谈谈我们以前的做法,这样通过对比就能知道卷积到底做了什么优化

传统做法

其实从传统的角度来看,其实图像识别也就是通过图片的特征值来判断图片代表的含义,但是图片这个东西又很特殊,相比于其他机器学习问题,他的特征值很多,这里我们使用28X28的图片就有784个特征,如果我们图片尺寸再大,这个特征值会变得非常巨大,而且我们知道机器学习需要大量数据才能大展身手,然而每个图片如此巨大,训练巨大的数据集电脑也吃不消

所以我们必须要将数据进行降维,机器学习里面有很多降维的方法,比如PCA,LDA这些,但是这些方法都有一个问题他们必须把一个图片看做一个整体输入,也就是前面的将28X28转换成一个784的数组,这个数组我们知道,他丧失了一个非常重要的东西维度,我们仔细观察上面的图片

mnist数据来源网络

每个图片其实我们关注的都是数字的二维分布,我们通过闭合的圆的个数来区分8和0,我们通过中间的空白部分来区分0和1,所以我们希望能使用一种新的方法来确定图片特征,一方面能够保存图片的空间信息,一方面能最终数据一维的结果(图片代表的数字),这个就是卷积的引入了,卷积从二维的角度来提取图片的特征,相比于传统的一维提取,它能最大程度保留图片的信息,并且进行深度降维

从项目了解卷积

一开始学习深度学习卷积神经网络,看了很多资料,但是总是感觉并没有很深的理解,至到接触这个项目,从代码的层次上再去理解卷积才给我恍然大悟的感觉

首先先谈一谈Tensorflow这个库的基础知识,由于Python速度有点慢,所以Tensorflow的后端全部由C++写的,你可以这样理解Tensorflow,Python相当于一个客户端,你可以使用一个session(回话)与服务器(C++)进行交互,这样的话,我们在客户端可以享受Python的方便快捷,也可以享受C++运行的高效性,但是这个也带来一个麻烦,原来Python是一个所见即所得的,现在运行一些东西必须使用session来通知服务器来运行,我们很多中间过程就没法知道,只能通过返回的结果来进行推断了。在官方教程并没有讲太多中间过程,只是一笔带过,所以为了更好的理解卷积神经网络,我们将会以一种很难看的方法运行Tensorflow,但是我们能从这个过程中对卷积的理解更加深刻

所以接下来我们基本上每个操作都会让后端运行并且分析返回结果,为了方便叙述,我们假设你在运行session.run之前都会运行这个session.run(tf.global_variables_initializer())来初始化所以的变量

PS:之所以要运行这个,因为我们使用session与C++进行交互,如果我们“不声明”变量,c++会报错的

下面我们就从这个项目一行一行讲起

准备数据

前面我们知道,卷积就是要从二维空间中来提取我们想要的特征,首先我们把数据还原成二维的

x_image = tf.reshape(x, [-1,28,28,1])

x是上面我们输入的数据,来我们来检测一下,首先我们声明一个session

session = tf.Session()

再从数据集中掏出50张图

data = mnist.train.next_batch(50)[0]

接下来我们看看这个x_image变成了什么

session.run(tf.global_variables_initializer())

x_image_data = session.run(x_image, feed_dict={x: data})

我们输入两者的shape

data.shape, x_image_data.shape
(50, 784) (50, 28, 28, 1)

我们很清楚的看到,我们成功将一维的数组图像(784)变成了二维的数组图像(28X28),其实我们生成了三维(28 X 28 X 1),但是由于我们只有有些图片还会有多个色道(RGB),所以我们为了兼容,声明成28 X 28 X 1

好的,现在我们成功将一维图片还原成二维的,接下来就是将他们卷起来的时候了

第一层

如果你学过一些信号处理你会发现,深度学习使用的卷积其实并不是原始意义上的卷积,他没有“旋转180”的操作,但是他的形式其实是类似的。这个“积”的操作主要是通过矩阵运算来实现的,为了更好的理解卷这个操作,我从网上找了前辈们辛苦做的动图

卷积操作-来源网络

PS: 这个图与我们数据有点不同,我们每张只有一个色道,这个有三个色道,这张图有两个卷积核,但是我们这个第一层会使用32个,但是其实原理都一样,如果你实在理解不过来,你可以先值看最上面那一排

我们回到这种图,最左边就是图像输入,中间是卷积核,最后右边是输出,我们可以从图中可以很清楚的看到卷积的与我们平常操作不同,首先输入上我们是二维数据,通过二维的卷积核进行矩阵运算,最后我们输出二维结果,这就是卷积的强大之处,不但保留了原来的二维信息而且能够使用高效的矩阵运算来加速提取特征

现在我们回到代码

首先是要声明卷积核,我们可以使用简单的方法,将卷积核全部声明为全0矩阵,但是这个有可能造成0梯度,所以我们加入一点噪音,我们看看加入噪音的卷积核是什么值

initial = tf.truncated_normal([5, 5, 1, 32], stddev=0.1)
W_conv1 = tf.Variable(initial)
session.run(tf.global_variables_initializer())

W_conv1_value = session.run(W_conv1)

W_conv1_value.mean(), W_conv1_value.std()
(0.001365028, 0.08744488)

我们使用tf.truncated_normal函数声明了32个5X5X1的随机卷积核,看起来随机性还挺不错哦

PS:前面(5,5,1)代表输入长、宽、色道,后面代表输出输出数量当然我说它是32个它不一点为32个矩阵,应该是(色道X输出数量)个卷积核,但是我们这里只有一个色道,所以只有32个,我们可以通过W_conv1_value.shape查看真实的维度(当前的维度为(5, 5, 1, 32))

这个卷积核就对应上面图中间的小矩阵,他的长宽都为5,图中长宽都为3,当然我们可以把这个长宽修改,使用5是我们的经验值,通过这个大小的卷积核能够在模型表现能力更好。

接下来我们就进行最重要的卷积操作了,由上面图可知,要进行卷积必须要有三维的数据与对应的卷积核进行相卷,其实我们在图中还可以看到一个重要的东西,卷积的步长也就是每个框移动的位置(图中的步长为2)

还有一个较隐秘的知识,你有没有注意到图中的数据原来是7X7的数据,通过卷积核转换之后就变成了3X3了,影响卷积后图像尺寸不但有步长还有框子的大小,假如你的框是7,那图中只剩下一个值了,所以我们避免尺寸减少,我们使用周围填充0来使最边缘的位置卷积也成为到框子的中心,一方面避免边缘数据流失,一方面也能突出边缘数据(周边全为0)

Tensorflow为我们封装好了上面所以的方法,我们只要通过传参过去就能改变部长,改变填充方式,好了现在就开始来正式“卷”了

session.run(tf.global_variables_initializer())

v = session.run(tf.nn.conv2d(x_image, W_conv1, strides=[1, 1, 1, 1], padding='SAME'), feed_dict={x: data})

现在我们来看看卷完后vshape

   v.shape
(50, 28, 28, 32)

50代表50个数据,(28、28)代表图片维度,这个32就是卷积核数,50和32这两个应该是固定的,不难理解,我们现在来看看为什么通过卷积核的“卷”,图片还是保持28X28的,这个也是在知乎上涉及到的一个问题,现在我们从实验上来解决一下

首先我们看tf.nn.conv2d函数,他接受四个参数,第一个图片、第二个卷积核、第三个步长,第四个卷积方式

首先问题是觉得,卷完之后应该是变成24 X 24,这个理解是没错的,我们将pading的值改成VALID再次运行

session.run(tf.global_variables_initializer())

v = session.run(tf.nn.conv2d(x_image, W_conv1, strides=[1, 1, 1, 1], padding='VALID'), feed_dict={x: data})

v.shape
(50, 24, 24, 32)

我们得到了24 X 24的图片,这个SAME和VALID有什么区别呢,这个区别就是填充0没有填充0的原因,SAME在图像周边填0这样就能得到28 X 28

我们也发现,这个还有一个参数strides,这个就是前面填的步长,步长的长宽就是中间两位设置的(最边上两位跟输入有关,第一个是输入图片数量,最后一个是图片的色道),我们在这里使用使用1步长,我们来试试2步长试试

v = session.run(tf.nn.conv2d(x_image, W_conv1, strides=[1, 2, 2, 1], padding='SAME'), feed_dict={x: data})

v.shape
(50, 14, 14, 32)

果然输出的图像变成28的1/2了

接下来我们就要把卷积的值丢到神经元函数里面去了,为了符合实际,我们加入一个偏置量b_conv1

def bias_variable(shape):
  initial = tf.constant(0.1, shape=shape)
  return tf.Variable(initial)
b_conv1 = bias_variable([32])

这里我们使用0.1来初始化偏置量,接下来就是丢到神经元函数,这里我们使用numpy 的array的传播性,将b_conv1传递给所有的28X28的维度

h_conv1 = tf.nn.relu(tf.nn.conv2d(x_image, W_conv1, strides=[1, 1, 1, 1], padding='SAME') + b_conv1)

v = session.run(h_conv1,  feed_dict={x: data})

v.shape
(50, 28, 28, 32)

我们可以看到卷积完后从神经元函数生成的数据是(50X28X28X32)的,最后维度由1变成32,所有我们得使用点方法来缩减数据维度,这里我们使用卷积池的方法

卷积池

由上面可以看到,其实很简单就是把最大的挑出来

h_pool1 = tf.nn.max_pool(h_conv1, ksize=[1, 2, 2, 1],
                    strides=[1, 2, 2, 1], padding='SAME')

这里的参数很简单我就不介绍,这样“瘦身”之后,数据的维度由(50, 28, 28, 32)变成(50, 14, 14, 32),减少4倍

到这里我们的第一层卷积就结束了,接下来就是第二层卷积,为什么要多卷一次呢,因为前一层学到的还是太少了,要加强学习,这层和第一层没什么差别,所以我们就跳过这层

直接贴代码(函数就不复制了,文档里面有)

W_conv2 = weight_variable([5, 5, 32, 64])
b_conv2 = bias_variable([64])

h_conv2 = tf.nn.relu(conv2d(h_pool1, W_conv2) + b_conv2)
h_pool2 = max_pool_2x2(h_conv2)

全连接层

当我们完成两层卷积之后,我们的数据变成了(50,7,7,64)的四维数组了,我们知道我们传统的机器学习其实最后都是采用二维数组来当做训练数据(X代表特征,Y代表样本),所以全连接层就是把卷积给“反卷”过来,这样后面你方便对接传统机器学习,而且最后我们需要的数据也是输出的也是二维的(对一堆数据统一进行预测,所以这里称二维),但是这里要注意全连接层不是输出层,所以我们可以随意设置输出的维度,最后输出层对接再进行一次全连接层类似操作就能输出我们想输出的维度,这里我们看看全连接层权值变量

W_fc1 = weight_variable([7 * 7 * 64, 1024])
b_fc1 = bias_variable([1024])

这里我们声明全连接层的权值变量W_fc1和偏置量b_fc1,我们可以看看W_fc1shape是多少

session.run(tf.global_variables_initializer())

session.run(W_fc1).shape
(3136, 1024)

我们可以看到其实就是一个二维数组维度为(3136,1024),第一个维度跟输入有关,第二个维度影响输出维度,前面我们使用tf.nn.conv2d卷积操作来转换图片,在全连接层我们要使用矩阵运算来转换我们的维度

矩阵运算非常有趣,我们在前面其实也提到过一点,就是降维的实现PCA就是使用矩阵运算来进行降维,我们把数据分为X(特征),Y(数量),经过一次矩阵运算我们可以实现数量不变,而特征改变,这个就非常强大了,我们可以随便修改矩阵参数来动态修改我们特征数量

但是矩阵运算也有一定局限性,就是两个运算的矩阵必须是前者长与后者的宽想同,这个跟矩阵运算特性有关,具体可以看看矩阵运算相关资料

所以为了进行矩阵运算我们第一件事就是改变输入的shape,让它由四维变成二维,以便能够与我们权值矩阵W_fc1进行运算

h_pool2_flat = tf.reshape(h_pool2, [-1, 7*7*64])

我们简单的使用tf.reshape就能把第二层卷积后的输出变量转换成(50,7764)的维度,这样我们就能直接与权值矩阵W_fc1进行运算

h_fc1 = tf.nn.relu(tf.matmul(h_pool2_flat, W_fc1) + b_fc1)

我们这里直接将运算后的值放到激活函数里面去完成全连接层的功能

输出层

其实输出层同全连接层很类似,我们就是把前面的变量转换成我们想输出的维度,在进行这个输出层之前,我们得先搞一层Dropout层,这个能有效的避免神经网络的过拟合问题,具体可以看看这篇论文

keep_prob = tf.placeholder("float")
h_fc1_drop = tf.nn.dropout(h_fc1, keep_prob)

因为同全连接层原理类似,输出层我就不就不详细介绍了

W_fc2 = weight_variable([1024, 10])
b_fc2 = bias_variable([10])

y_conv=tf.nn.softmax(tf.matmul(h_fc1_drop, W_fc2) + b_fc2)

我们可以看看最后我们输出是什么

session.run(tf.global_variables_initializer())

session.run(y_conv, feed_dict={x:data, keep_prob:0.5}).shape
(50, 10)

ok,我们最后得到一个二维数组,50个预测结果(输出采用OneHot方法)

反向传播

在前面我们得到了在初始话随机权值下得到输出结果,但是这个结果肯定是错误的,我们必须通过修改每层的权值来修正模型,使模型越来越聪明,所以第一步,我们必须“自我反省”,了解自己与真实结果差距多少

y_ = tf.placeholder("float", [None, 10])
cross_entropy = -tf.reduce_sum(y_*tf.log(y_conv))

我们引入y_作为实际值(我们模型预测值为y),我们这里使用交叉熵来评判预测准确性,但是单单知道“自己错了”没有什么卵用,我们必须要“改正”,这里我们使用AdamOptimizer优化算法来反向传播我们误差,让模型好好“反省改正”

train_step = tf.train.AdamOptimizer(1e-4).minimize(cross_entropy)

到这里基本上差不多了,我们已经形成了一个闭环,预测->评估->改正->预测->……,只有让它不断的训练下去直到我们能接受他的误差我们的模型就训练好了

correct_prediction = tf.equal(tf.argmax(y_conv,1), tf.argmax(y_,1))
accuracy = tf.reduce_mean(tf.cast(correct_prediction, "float"))
session.run(tf.initialize_all_variables())
for i in range(18000):
  batch = mnist.train.next_batch(50)
  if i%100 == 0:
    train_accuracy = accuracy.eval(feed_dict={
        x:batch[0], y_: batch[1], keep_prob: 1.0}, session=session)
    print("step %d, training accuracy %g"%(i, train_accuracy))
    if abs(train_accuracy - 1) < 0.01:
        break
  train_step.run(feed_dict={x: batch[0], y_: batch[1], keep_prob: 0.5}, session=session)

由于我们使用OneHot方法来输出预测变量,所以我们要使用tf.argmax来得到我们想要的真实数字,经过20000轮训练我们正确率可以达到99%,至此卷积神经网络发挥他的威力。

总结

卷积神经网络是深度学习的一个很重要的组成部分,了解卷积必须要知道为什么要用卷积,用了有什么好处。总而言之,卷积并不是一个很新奇的东西,很早在信号处理中就有应用,但是在图像处理上由于他能保留图像维度信息从而在深度学习领域大放异彩,这也可以看做“是金子总会发光吧”

引用

http://www.tensorfly.cn/tfdoc/tutorials/mnist_pros.html
矩阵运算
通俗理解卷积神经网络
Dropout

由于我的笔记本是农卡,没法安装CUDA加速,而且我的显卡只有2G显存,安装OpenCL费力不讨好,而且由于我有一个Google云的300美元的体验,所以可以在Google云上使用TPU来进行加速,所以我就干脆不安装显卡加速,但是Tensorflow提供了指令集优化,由于默认使用pip安装没有提供这个功能,所以只能手动编译安装

假如你是用pip安装的Tensorflow你可以会得到下面警告

the tensorflow library wasn't compiled to use sse4.1 instructions

安装步骤

  1. 首先你得先看看你CPU支持什么指令集

    cat /proc/cpuinfo|grep flags
    

执行这个指令就能看到你所支持的指令集

  1. 然后安装bazel

    sudo add-apt-repository ppa:webupd8team/java
    sudo apt-get update && sudo apt-get install oracle-java8-installer
    echo "deb [arch=amd64] http://storage.googleapis.com/bazel-apt stable jdk1.8" | sudo tee /etc/apt/sources.list.d/bazel.list  
    curl https://bazel.build/bazel-release.pub.gpg | sudo apt-key add -  
    sudo apt-get update && sudo apt-get install bazel  
    sudo apt-get upgrade bazel  
    
  1. 安装完之后下载tensorflow源码

    mkdir github && cd github
    git clone –recurse-submodules https://github.com/tensorflow/tensorflow
    cd tensorflow
    ./configure

接下来一路选择N就行

  1. 生成whl文件

    bazel build -c opt --copt=-msse3 --copt=-msse4.1 --copt=-msse4.2 --copt=-mavx --copt=-mavx2 --copt=-mfma //tensorflow/tools/pip_package:build_pip_package
    

在源码处开始编译,注意copt命令主要是添加指令集支持,这里你要看看上面的指令集(去掉m就是你的指令集,如-msse3指令集为sse3)你的CPU是否支持(一般都支持我的I5 4200U都支持),如果不支持删掉那个就行

这里你安装的时间比较长,要看你的CPU了

  1. 验证

退出安装目录运行python

执行下面两句

import tensorflow as tf;sess = tf.Session(config=tf.ConfigProto(log_device_placement=True))

总结

如果没有报上面的不支持指令集的warning,那么你的CPU指令集优化版就安装好了,当然这个加速效果因CPU而异,对于Xeon SP系列(100核心以上)已经能加速到50倍,同GPU差距也就2倍了(原来可是100倍),但是对于我的笔记本来说,加速效果可能就在30%左右(核心少),所以当前加速性价比最高的还是GPU加速,骚年还是买个好一点的GPU吧,没事还可以吃吃鸡。


引言

这篇博客其实写于2016年,最近在重新学了一下正则表达之后,觉得有必要重新整理一下正则的用法

Python对正则匹配的库是re,re是基于Perl所用的正则表达式,并有
一定的改进.

正则本质就是搜索所需的文本,正则里面有三种搜索方式

  1. 第一种是知道文本内容直接使用普通字符搜索出来,比如要从abcdefg中搜到cd
  2. 第二种就是模糊查询,比如我想从英文中找一个数字,一般借助特殊符号(.+*?)或者转义符号(\w\d等)
  3. 第三种就是结合前两种,比如我记得一个单词的前两个字母想把那个单词搜出来.

这里不介绍正则基本知识,你想知道可以点这里

ps: 由于在python里面也是用反斜杠做转义字符,所以比如\\\b这两个特殊字符必须用\\\\\\b来代替.但是python提供了一个元字符支持re模块,只要字符前面加上r比如r' regex '就能不关闭python的转义.

正则里面我觉得很重要的一个概念就是组概念,当我们的文本比较复杂的时候将其分成多个小组是利于我们正则的后期维护和改进

正则里面使用一个括号来表示组比如(a)(b)就分成了两个组

re函数里面searchfinall都支持组查询,而且findall方法假如里面有组分布会只显示组成员.

re库支持搜索选项,这几个选项对于正则有时候非常有用

DOTALL [简S]-------------允许点字符匹配换行符
IGNORECASE [简I] --------忽悠大小写
LOCALE  [简L]  ----------支持本地化字符
MULTILINE [简M] ---------多行,每行都支持锚点
UNICODE [简U]  ----------支持Unicode,\w也可以是Unicode了
VERBOSE  [简X]  --------------神器,会无视代码中的注释空格和换行

我们也可以在正则的组里面使用这些搜索选项,只要用上面的简称的小写比如(?is)就可以在组里面使用这些规则.


正则里面还有一些比较有趣的函数,同string里面的translate函数,sub函数可以替换找到的变量
bold = re.compile(r’*{2}(.?)\{2}’)
bold.sub(r’\1‘, ‘this foo and ok‘)

\1代表第一组变量也就是foo和ok
输出为'this <b>foo</b> and <b>ok</b>'我们使用成功用加粗了foo和ok,同translate不同这个方法不需要知道要替换的是什么.


正则的断言

我们可以使用一些特殊的符号来执行一些程序判断选择,比如说判断是否特殊字符,如果有
的话就不匹配,这就是断言

断言有两种一种是前向,一种是后向

前向是指判断语句在前面,这种就相当于一个if语句,而后向是匹配后判断,由于已经匹配好了文字所以
匹配的字符必须是固定长度的(不能使用*.?).

前向就是在判断后面匹配的表达式必须与规定相同,比如一个邮箱地址我们要匹配可以用<>包起来的,但是不匹配只要一个的我们就可以在前面加上这个^(?=(<.*>$)|([^<].*[^>]$))通过使用?=来断言后面必须是用<>包起来或者没有<>,我们使用前向断言可以通过正则直接过滤掉不符合的(当然你可以用多个简单正则来做但是效率没有这个高),还有否定前向就是通过?!来声明.
相对应后向断言就是很简单了,直接在匹配后面使用一个?<=(肯定后向)或?<!(否定后向),不过要注意这个是判断前面匹配是否满足的.

断言只是限定我们想选的文本的范围,他并不会被选择.
断言的一个有趣的应用就是选择字符间的空格,我们知道python其实假设每个字符间都一个空格(这就是我们有时候会选出一些空字符出来的原因),这个空格不是我们自己打上去的.

举个例子

两个字符串a1a 1,第一个我们称为A,第二个我们称他为B,假如我们想把数字和字母分出来,对于B来说,很简单因为数字和字母之间有一个空格,我们可以直接使用字符自带的split就行,但是对于A来说,就不那么简单了.

字母a和数字1中间没有字符,我们必须把字母和数字之间的”空格”给选择出来,这时候就可以用到断言了.

r = re.compile(r'(?<=[a-z])(?=\d)') 

这个r就可以字母和数字直接的隐形空格给选择出来了

遗憾的是由于python的正则并不把隐形的空格当做字符,所以我们不能简单的使用正则的re.split方法(选择字符分割)直接将字符串分解开.

我们就得写几步

第一先把空格换成 $$$(或其他)

>>> s = r.sub('$$$', 'a1')
>>> print(s)
'a$$$1'

然后在分割

>>> s.split('$$$')
>>> ['a', '1']

成功分割好了,当然这个只能处理字母在前数字在后的”隐形空格”,只要加一个"|"在把前向改成后向,后向改成前向就可以选择任意字母和数字直接的”隐形空格”了.


正则的变量

我们可以使用?P来声明一个组(用括号,当然其实我们每使用一个括号re自动帮我们将组取一个
名,依次从1-n

有时候我们可以要求上面的匹配组,下面也要相应匹配组,我们就可以通过两种方法来引用这个变量,假如你没有使用<?P<name>来声明组你只能通过\n来引用,n是这个变量的序号,第二种是通过(?P=name)
来引用这个变量,name为你自己定义的组的名字

re还提供了一种机制来让你修正你的正则,简单来说就是能判断一个组存不存在来约束匹配,语法为

(?(id)yes-expression|no-expression)

id为组的编号或者name.

正则的起源

正则这个东西其实很简单,我们

通过前面的学习我们知道,在前两个实验中最主要的程序就是kern/init.c文件中i386_init函数,但是我们看到最后却是一个while循环结束。

while (1)
    monitor(NULL);

这个monitor就是简单读取用户输入然后通过字符串调用给定的几个函数。我们可以把这个函数看做i386_init的子函数,也就是程序一直在i386_init中运行,也就是一直以内核形式运行。实验三就开始完成一个正常的操作系统的用户模式的建立,以及两者直接转换。

引言

什么是用户呢,我们把内核当做一个大程序,用户就是小程序,两者基本上没有差别,但是为了让众多用户和内核平稳运行,我们必须要区别对待用户和内核

首先我们要相信内核,内核是我们精心设计的,相反用户我们不能相信它,任何人都可以犯错误,我们知道计算机程序其实非常精巧,当他们完整的时候,他们可以完成你无法想象的工作,但他们有时候少掉一行指令时,他们就会瞬间崩溃,所以我们必须要保证就算用户怎么折腾都不会把内核搞垮

所以我们来考虑一下怎么来限制用户不影响整个系统,第一用户不能动内核在内存上的程序,甚至连查看的资格都没有,这就是为什么前面我们已经绞尽脑汁把内核放到高地址上确保其“高高在上”;第二个用户不能在CPU一直跑,假如它有权限一直在CPU上跑,那么内核就废了,没有CPU可以用相当于“断了胳膊”;第三用户必须要有一些内核的权限,比如说申请一些内存啥的。

接下来我们就从这几个问题出发来探索一下xv6为什么要这样设计用户空间。

用户是个程序?

在完成用户设计之前,首先我们先做个实验,来验证一下用户是个程序。首先我们在kern/init.c文件中i386_init 的头部加上#include <inc/elf.h>然后在#if defined(TEST)代码前加入几行代码

extern uint8_t _binary_obj_user_hello_start[];
struct Elf* header = ((struct Elf *) _binary_obj_user_hello_start);
assert(header->e_magic == ELF_MAGIC);
((void (*)(void)) (header->e_entry))();

这段代码你如果仔细观察过前面操作系统载入的源码(boot/main.c中)你会发现基本上差不多。首先我们声明了_binary_obj_user_hello_start外部变量,这个变量是通过ld编译器将内核中用户程序hello.c的起始地址定义来的,由于我们现在没有文件系统,内核就把用户程序一股脑链接到自己身上,在以后有了文件系统就不需要了。但是它给了我们一个便利,我们现在可以直接在内存上运行它

当然虽然它的确是个程序(assert那不会出错),但是它还是跑不起来,因为它的虚拟地址不在内核内存上,必须要像前面映射内存物理空间才能运行,但是他的确是一个程序,从这里我们得到一个结论,用户其实也就是一段程序,接下来我们就看看如何用软件与硬件的结合的设计解决上面的问题。

权限

首先我们来看看权限问题,x86系统硬件给我们提供了一个分段式权限功能,在开启内存分页后,CS寄存器16位里面拿出两位来当做权限管理,分为四级(0b00、0b01、0b10、0b11),最小的权限最大,当然xv6只用了两级,如下图所示

系统环来源网络

PS:当然CS寄存器拿出来三位来当权限管理,但是xv6将第三位用户和内核都设置为1,所以我们也不介绍这一位

我们在CS寄存器的这两位称为CPL,用来区分权限。在引导和操作系统的交互这篇博客我们知道,在x86系统中,这个CS寄存器是标志段选择子,在GDT表中每个表项也有两位用来标志权限,我们称他们为DPL,他们的意义也就是CS寄存器选择这个段时他们最低拥有的权限。

当然在GDT表中的段选择子也有一个表示权限的称作RPL,这三者的关系在这里面介绍的很详细,RPL是历史遗留问题但是操作系统基本上没有使用这个功能,所以这里我们也不解释,感兴趣可以看一下前面的介绍。

kern/env.c结构体gdt我们声明了一个GDT表,并且声明了一个系统段和用户段。

这两个段就是我们权限的基础我们接下来通过实验来验证权限位对操作系统的保护

我们首先在user/badsegment.c中加入一句汇编

asm volatile("ljmp %0,$1f\n 1:\n" :: "i" (0x08)); // 将CS设置为0x08

我们尝试将CS设置为0x08(内核段)结果直接引发一个General Protection的异常,但是当我们尝试执行这句

asm volatile("ljmp %0,$1f\n 1:\n" :: "i" (0x18));  // 将CS设置为0x18

我们发现程序没有引发异常(这段的含义是跳转到用户段,由于已经在用户段,所以没有触发异常),这说明x86通过CS寄存器很好的实现了内核和用户的保护(用户不能直接跳到内核去执行代码)

user/faultwritekernl.cuser/faultreadkernl中我们发现尝试写入或者读取内核也失败了,这是通过前面章节的内存分页权限实现的,这里就不介绍了。

现在我们知道,通过我们不懈努力内核和用户直接存在一个鸿沟,但是这时候摆在我们面前很大的问题,内核拥有一些非常重要的权限比如申请内存,如果用户没有这个权限那么功能非常受限,所以我们就要提到一个内核和用户交互的手段:Trap。

Trap

其实这个Trap包括内部中断、软中断、异常。但是xv6统一将他们叫做陷阱(Trap),这个Trap主要完成从用户到内核的一种跳转,我们就不介绍内部中断和异常,因为这些都是系统完成,我们来介绍了一下软中断,这个我们人为可以操作,而且我们可以把其他中断、异常当做系统去帮我们调用这个指令

int $n

很简单x86共定义了256个中断向量,存在物理内存0x000-0x3ff之间,每个存贮一个cs值一个eip的值,这个n只要是在256直接就行,当调用这个的时候我们直接调到那里读取cseip的值。

在正式介绍Trap之前我们要简单的介绍一下两个知识点

IRET

这是iret是一个机器码,我们前面介绍了无论是操作系统还是用户没有办法直接跳段(会引发General Protection fault),而且我们知道前面只是测试了跳代码段,我们知道两个不同的程序,不仅仅是代码段不同,堆栈段也要不同,才能保证各个程序的独立。所以系统为了解决这个问题,直接提供一个iret指令,这个全名应该叫中断返回,它的功能其实很简单,就是实现上面的跳代码段和堆栈段还有恢复EFLAGS寄存器值,这个主要应用在从系统跳转到用户上面。

感兴趣的可以看看这个详细资料,接下来我们看看在xv6里面如何使用iret来实现跳段

kern/env.cenv_pop_tf函数实现了切换程序段的功能

asm volatile(
        "\tmovl %0,%%esp\n"
        "\tpopal\n"
        "\tpopl %%es\n"
        "\tpopl %%ds\n"
        "\taddl $0x8,%%esp\n" 
        "\tiret"
        : : "g" (tf) : "memory");

首先第一个就是把tf指针指向的值赋给esp寄存器,要想知道这个操作的意思就必须知道,一个结构体其实在程序里面就是一块连续的内存值,所以这里就是把esp的值指向tf代表的Trapframe结构体的开始位置,所以我们得看看这个Trapframe组成是什么

struct Trapframe {
    struct PushRegs tf_regs;
    uint16_t tf_es;
    uint16_t tf_padding1;
    uint16_t tf_ds;
    uint16_t tf_padding2;
    uint32_t tf_trapno;
    /* below here defined by x86 hardware */
    uint32_t tf_err;
    uintptr_t tf_eip;
    uint16_t tf_cs;
    uint16_t tf_padding3;
    uint32_t tf_eflags;
    /* below here only when crossing rings, such as from user to kernel */
    uintptr_t tf_esp;
    uint16_t tf_ss;
    uint16_t tf_padding4;
} __attribute__((packed));

第一个是PushRegs结构体,这个对应我们第一个操作popal,将PushRegs所有值全部从堆栈中取出,我们发现当到iret操作时,正好对应取出代码段还有堆栈段和EFLAGS寄存器,所以其实iret的操作非常简单,只是将三个取出指令和成了一个。

TSS

前面我们捋了捋从系统跳转到用户,因为我们给用户的都是刚新建的值,所以这个并没有什么问题,但是你要想一想,当用户想跳转到系统的时候,这个时候它也必须要切换堆栈,因为用户可以还没有准备好(有时候可以是因为堆栈内存不够,如果把寄存器值强行插值到用户堆栈会引发二次异常)。但是假如使用操作系统的堆栈,在我们切换之前系统必须要知道内核堆栈在哪

所以x86提供了一个tr寄存器给我们使用,这个寄存器的位数为16位,专门存贮一个选择子(类似前面段选择子),这个选择子base地址必须指向一块空余空间。前面知道我们要想从用户跳操作系统,必须知道操作系统的堆栈(中断向量表提供了代码段cs:ip),所以x86干脆规定了这个空间名字为TSS,并声明了一大串寄存器的值备用,当然这些是硬件规定的,软件用不用无所谓,但是硬件会在跳转的时候,读取里面固定位置的值,也就是我们需要的堆栈段ss:esp,在inc/mmu.hTaskstate结构体中声明了这段内存规定的字段

所以我们在kern/trap.c中声明了(ss:esp)

   ts.ts_esp0 = KSTACKTOP;
ts.ts_ss0 = GD_KD;

这样我们在跳转的时候就能获取到内核的堆栈段,从而进入内核模式,当然硬件设定TSS的作用一开始为了考虑任务切换,它也提供了相应的指令,但是需要200左右时钟周期来完成,所以我们xv6嫌弃其速度太慢,只是使用了其保存内核堆栈地址的作用,所以在xv6TSS只是一个“数据库”而已。


介绍完前面的基础知识之后,接下来的就是这个Trap,前面我们知道在得到int这个指令时候这个时候就开始一个Trap开始。

这个时候硬件接管程序控制,你也可以认为跳转到硬件代码去了。在给的资料第三章的X86 Protection里面介绍了这个过程,我们将前面几个步骤很我们前面给的资料联系起来

后面推寄存器值就不解释了,同Trapframe的反向结构相同,之所以会这样,是因为堆栈地址是向下生长,而程序地址是向上生长的

硬件这部分操作为

  • 获取中断向量表第n个的地址(n为int后面整数)

然后开始权限检查,这个也是为什么程序不能随意调用系统资源的原因

  • 检测DPL与CPL的大小关系

这个DPL不是前面GDT里面的,这个是存贮在中断向量表中CS里面的值,这个设置可以让我们给每个中断向量设置一个权限,看它允许是用户调用还是系统调用,如果只允许系统调用,那么用户调用直接引发General Protection Fault(13号中断),在我们的xv6中,我们只允许用户调用DebugSystem Call中断,其他只能由系统调用

  • 判断保留espss,检测目标的段与当前段

当我们在操作系统中出现中断的时候,如果硬件还傻乎乎的将操作系统的堆栈归位那么就进入死循环了,所以这个目的就是避免同属一个段的时候不会切换堆栈

  • 当跳段的时候,从TSS中取到espss切换堆栈段

这个就是前面弹到的TSS的功能,接下来我们所以推出去的值全部存贮在要跳的段的堆栈上面了。

推完Trap程序的寄存器值,保留好“犯罪现场”后,就可以进入内核进行处理这个异常了。

至此我们介绍完了严格有序的处理从用户到内核的跳转,当我们处理完后就可以通过iret回到用户程序,这样就完成了用户拥有内核权限的设计。


用户时间控制

接下来的用户使用CPU时间设置也是通过这个这个Trap的中断实现,你可以理解为硬件在每个CPU上在每隔个10ms的时候就触发一个中断。这样到内核的时候,内核发现是时间中断,就保留用户的寄存器值到用户自己空间(Env里面有一个env_tf变量可以存贮这些信息),然后调用其他或者这个程序,这样的话,我们就实现了一个时间控制。

PS:这里我们提一下这个Env结构体,内核初始化了1024个这个结构体,这说明我们可以同时拥有1024个用户程序运行,这个结构体就是用户环境,也就是我们在Unix系统上输入ps中的pid(每个pid代表一个程序)

总结

至今我们介绍了通过一个简简单单的Trap操作就实现了复杂的权限管理和空间隔离,虽然操作系统看起来非常复杂,但其实都是由简单干练的概念搭建起来的,因为Unix的哲学就是简单至上

引用

https://stackoverflow.com/questions/6892421/switching-to-user-mode-using-iret

https://stackoverflow.com/questions/36617718/difference-between-dpl-and-rpl-in-x86

https://en.wikipedia.org/wiki/Task_state_segment

概括

这个问题主要在这本xv6-ref的第一章的练习题2中提出来

问题如下

KERNBASE limits the amount of memory a single process can use, which might be irritating on a machine with a full 4 GB of RAM. Would raising KERNBASE allow a process to use more memory?

根据前面的知识可知这个问题翻译过来就是:在32位处理器下,当KERNBASE0x80000000时用户最多可以用2GB内存,我们是否能够增加KERNBASE让用户使用超过2GB内存呢?

ps: 下面KERNBASE简写为KE

引言

要想解答这个问题,我们必须要知道xv6是如何分配内存的,以及如何区分用户和内核,以及KE的作用。

xv6使用内存分页技术,如果你对这个不了解可以看这篇引导中的静态表和这篇内存分页设计细节,了解完这个我们谈谈用户和内核的内存分页应用。

注意我们所以计算的前提是在32位处理器的条件下

用户和内核应用内存分页

其实用户和内核都是程序,对于用户来说内核只有一个,对于内核来说,用户可以有无数个。为了隔离内核和用户我们必须在内存上就进行隔离,所以单一内核和每个用户都拥有一个内存目录。

内存分页的意义

其实我们可以把内存的目录对应的所有内存表看做一张大的内存映射表,我们使用1024 × 1024个表单项代表4GB内存地址,每个代表4K连续的内存空间,当然大部分程序不会使用全部表单(一般就是内存目录一个,一到三个内存表)

当然好处有很多,比如任何程序都可以使用相同的虚拟地址但是在实际运行的时候不会相互影响,这个好处就是通过映射来实现的。

  • 映射就是虚拟地址到物理地址的一种转换,这是一种多对一的映射,也就是一个虚拟地址只能对应一个物理地址,然而物理地址可以对应多个虚拟地址

这个转换带来了一个问题,给你一个虚拟地址,你可以查表然后得到物理地址,但是如果给你一个物理地址,你除了遍历没有很好的办法获取虚拟地址(而且有可能你会得到多个虚拟地址)。

这个问题非常重要,因为它影响了我们后面内核与用户切换的时候地址的搜索,接下来我们看看内核初始化后内存是一种什么样的存在。

内核内存利用

看xv6源码我们知道,内核这个程序将程序虚拟地址起点定在KE上,我们知道一个程序由三部分组成指令、数据、堆栈。堆栈是向下生长,而数据、指令向上生长。而xv6把堆栈固定为32KB,所以内存只能向上生长,所以理论上内核最大占用空间只有2^32(4G) - KE

  • KE0xf0000000时,只有256M
  • KE0x80000000,有2G。

由于用户内存空间不能超过KE(实际系统中为UTOP,值为KE减去一些为系统功能预留的空间,这里我们忽略他们),所以用户所能得到的内存空间最大为KE,也就是

  • KE0xf0000000时,为 3840M(4G-256M)
  • KE0x80000000,有2G。

通过上面简单的理论值我们推断出答案是:

  • 增大KE可以增大用户内存

这个结果看起来是正确的,但是我们知道作为一个操作系统不能固定用户的内存,我们接下来就看看在不同的内存下的实际应用以及xv6自身设计问题,由此来探索这个问题的本质

我们就分两种情况来考虑

物理内存小于(4G-KERNBASE)

这种情况在很早的时候经常出现,我们计算机的内存可能就几M,这个时候内核假如真的占了4G-KE那连内核都跑不起来何况用户程序。

我们接下来进入源码来看xv6将实际占用的空间体现在内存表中,我们看到kern/kernld.ld配置文件,其中最主要的一行

PROVIDE(end = .);

这行位置出现在最后一行,它的作用是提供了一个变量end,我们在C中就可以用这个变量代表机器码的最后一行的虚拟地址,有了这个地址之后,我们就获取了一个重要信息内核程序总长度,假如没有这个变量,我们只能人工设定一个操作系统的占用空间,假如定大了就是浪费,定小了程序就可能崩溃(内存溢出)。分配的细节可以看这篇文章,通过这个变量,我们把内核占用的物理空间给腾出来了。接下来的剩余的物理空间就留给用户了,所以用户能用到的内存最大为实际内存 - 操作系统占用的内存

而且我们能够知道操作系统还将内核的内存映射直接固定了,将KE:4G的地址映射到0:4G-KE,公式为虚拟内存=物理内存+KERNBASE,这个映射存在于kern/pmap.cmem_init函数中,这个带来了一个便利,就是程序变得很简单,假如我们得到一个物理内存地址,我们就能知道虚拟内存地址,但是这个也引来一个巨大的问题,就是当内存大于4G - KE的时候。

PS:关于知道物理内存能知道虚拟地址在源码的好处主要体现在用户内存空间创建的时候,这个时候处于内核态,当我们得到一个空的物理空间页,我们只要简单的使用上面公式就能获取到虚拟地址,然后内核就能在直接通过指针修改程序。假如没有这个映射,我们就后面动态建立,但是这里涉及到一个非常棘手的成本的问题,我们其实只需要一个值映射,然而我们却要浪费4K的连续内存空间,而且给程序带来了很大的复杂性。

我们接下来考虑系统内存大于那段映射最大值(4G-KE)时候会造成什么情况

物理内存大于 (4G-KERNBASE)

在现在大家内存愈来愈大,这种情况比较常见,由于xv6在程序设计中是动态创建用户空间,当用户比较少占用空间比较小的时候,程序不会用到物理地址比较大的空间,但是当物理内存超过这个阀值(4G-E),在这里我们考虑KE=0xf0000000,也就是物理内存地址大于256M的时候,由于内核没有映射到这么高的地址,所以我们用上面那个物理地址转虚拟地址公式就失效了。

由于xv6只是一个教学系统,所以为了简化系统,降低程序复杂性所以使用了最简单的直接映射的方法来处理内存,也正是由于这个原因提高KE并不能增加用户最大内存,当然解决的方法也有,我想了两种。

  • 在内核空间中分配用户内存目录空间,这种最为简单,但是会浪费一定的内存空间(必须在内核一开始运行就占用空间)
  • 在内核空间中映射一段固定的地址来存放用户内存目录地址,这个程序设计比较复杂,但是只需要初始化一个内存表单就行

总结

通过上面的分析,我们得到一个结论:

由于xv6设计的局限性,增大KERNBASE并不能增大用户最大可用空间,反而会减少。但是如果修改xv6设计可以实现增大KERNBASE增大用户最大可用空间。

引用

引言

前面已经通过lab1的这篇博文了解了内存分页的实现细节,接下来就谈谈如何具体实现内存分页

物理载体

通过了解KERNBASE对操作系统的影响这篇博文我们知道,其实内存分页就是完成对物理存在的一种分割和隔离,所以我们在完成内存分页系统设计之前必须要构建一个载体,完成对物理存在的一种表示。

在xv6中声明一个动态数组来代表物理内存,每一个值代表一块4k的内存页。我们主要通过offset - base得到偏移倍数,每个偏移量为4K,也就是通过(offset - base ) << 12得到物理地址,我们看一下这个数组成员:PageInfo结构体

struct PageInfo {
    struct PageInfo *pp_link;
    uint16_t pp_ref;
};

主要存在两个值:一个为下一个可用的地址指针,一个为引用次数。

引用次数比较好理解,但是这个pp_link有什么用呢。其实你可用把这个结构体看做成一个由链表组成的堆栈,我们只需要保留栈顶值(page_free_list),由于它保存下一个值地址,这样通过不断的push、pop,就能维持一个可用物理内存栈。

二级指针的妙用

由于前面的博客原理已经介绍的很详细了,我就不再累赘了,在这里我提一下源码中二级指针的妙用,虽然它只有短短几行,但是运行的结果却是让人大开眼界,体会到指针的神奇威力。

这段代码出现在kern/pmap.ccheck_page_free_list函数中

if (only_low_memory) {
    // Move pages with lower addresses first in the free
    // list, since entry_pgdir does not map all pages.
    struct PageInfo *pp1, *pp2;
    struct PageInfo **tp[2] = { &pp1, &pp2 };
    for (pp = page_free_list; pp; pp = pp->pp_link) {
        int pagetype = PDX(page2pa(pp)) >= pdx_limit;
        *tp[pagetype] = pp;
        tp[pagetype] = &pp->pp_link;
    }
    *tp[1] = 0;
    *tp[0] = pp2;
    page_free_list = pp1;
}

主要的作用是将“栈底”的元素移到“栈顶”,首先它使用了两个一级指针(pp1、pp2),还有两个二级指针分别指向(pp1、pp2)

首先int pagetype = PDX(page2pa(pp)) >= pdx_limit;判断物理地址是否为大于4M还是小于4M,我们把物理内存页分成两组

  • 小于4M A组
  • 大于4M B组

对于小于4M的组,分两种情况

  1. 第一个小于4M的内存页(page1)
  1. *tp[0] (也就是pp1) 存贮了pp的值,也就是pp1 = page1
  2. tp[0] 存贮了pp -> link 的地址(这个没有什么用)
  1. A组第二个以及以后的内存页(page2)
  1. 上一个地址的值等于pp(没什么用)
  2. tp[0] 存贮了下一个空闲地址的值

对于B组来说也是一样的,最重要的是for循环结束后实现的交换

*tp[1] = 0; 

B组最后一个的pp_link地址地址设置为NULL,也就相当于把他放到栈底

*tp[0] = pp2;

A组最后一个变成pp_link地址设置pp2,也就是B组的第一个接到了A组的最后面去了

page_free_list = pp1;

栈顶变成A组第一个,通过这样的“乾坤大挪移”术就将A组部分移到B组前面去了,也就实现了先使用低地址的物理内存的作用

总结

理解内存分页必须要了解背后的原理,了解了原理看具体实现的时候才能事半功倍。

引用

引言

本来自己查了很多资料,想自己写出来,结果下笔的时候发现别人已经把我想写的部分全部写出来了,而且比我想的还要具体,所以我就不写了,把链接放出了,顺便我补充一些

http://leenjewel.github.io/blog/2014/07/29/%5B%28xue-xi-xv6%29%5D-cong-shi-mo-shi-dao-bao-hu-mo-shi/

http://leenjewel.github.io/blog/2015/05/26/%5B%28xue-xi-xv6%29%5D-jia-zai-bing-yun-xing-nei-he/

ELF文件

首先你要知道什么是ELF,可以看一下这篇博客,简单来说就是编译完C后的机器码,前面加了一些数据表记录程序的分布情况

为了帮助我们逆向分析这些代码有什么,我们必须要借助两个工具

  • objdump
  • readelf

我们接下来就用实际例子解读mit6.828里面的引导和核心

引导

首先我们查看一下引导文件,在boot/目录下有两个文件

  • boot.S
  • main.c

两者是通过gcc编译器将汇编和C编译成为一个elf文件,具体在Makefile文件中(boot/Makefrag),我将它简单翻译一下

gcc -N -e start -Ttext 0x7C00 -o boot.out boot.o main.o

boot.omain.o就是boot.Smain.c编译后的文件,-e start意思程序从boot.Sstart中开始运行(这样就能从汇编开始执行),-Ttexttext代表代码段,也就是说直接指定代码入口地址为0x7C00,我们可以用readelf验证一下

mit-6.828-2014 ➤ readelf -h obj/boot/boot.out                         git:lab1*
ELF Header:
  Magic:   7f 45 4c 46 01 01 01 00 00 00 00 00 00 00 00 00 
  Class:                             ELF32
  Data:                              2's complement, little endian
  Version:                           1 (current)
  OS/ABI:                            UNIX - System V
  ABI Version:                       0
  Type:                              EXEC (Executable file)
  Machine:                           Intel 80386
  Version:                           0x1
  Entry point address:               0x7c00
  Start of program headers:          52 (bytes into file)
  Start of section headers:          4868 (bytes into file)
  Flags:                             0x0
  Size of this header:               52 (bytes)
  Size of program headers:           32 (bytes)
  Number of program headers:         2
  Size of section headers:           40 (bytes)
  Number of section headers:         9
  Section header string table index: 6

我们读取了一下生成的elf文件头部,我们可以看到Entry point address这个字段,就是我们设定的0x7c00,要了解这个地址的含义我们必须知道虚拟地址和物理地址的区别,可以看一下这篇博客,接着我们看一下反汇编的汇编代码obj/boot/boot.asm中,我们知道现在0x7c00代表程序把自己当做在内存上的真实内存上面,但是不一定会真的存在这块上,所以我们称它为虚拟的

首先我们了解一个系统知识,因为电脑启动后会按照启动盘顺序,把每个盘第一个扇形区512B取出来,如果最后两个字节为0xAA55的话就把它放到内存上面的0x7c00上去,我们看一下我们生成的obj/boot/boot

使用hexdump obj/boot/boo可以看到(我把最后一行复制出来)

00001f0 0000 0000 0000 0000 0000 0000 0000 aa55

最后连个字节为0xaa55,且文件大小刚刚好512B,这时候你可以有一个疑惑了,我们知道gcc我们生成的boot.out的elf文件,但是这个文件还有头部存贮数据,我们如果把整个文件放到磁盘上,当程序在内存0x7c00处执行时,那么文件头部碰到的就是elf头了,所以
为了把机器码提取出来并生成合适文件(512B尾部为0xaa55),程序干了两件事

  • 用objcopy将elf文件中执行代码提取出来(相当于去掉elf头部)
  • 用脚本修改尾部两字节(在boot/sign.pl用了perl程序来将生成512B且尾部为0xaa55boot文件)

总结

后面将核心加载到内存,上面的给出资料写的很详细,我就不多说,只不过由于当前2014的版本同资料有点不同,这里我提一下

当前版本是将内核头加载在0x10000上,然后在把内核代码加载到0x100000上(前面4个0,后面5个0,我当初看错了,百思不得其解),并将内核地址映射到f0100000上。

由于资料给的操作系统与2016的操作系统实现细节有点不同,其中最主要的就是一个很重要的KERNBASE常量值由0x80000000变成0xf0000000,这个变量牵扯到了在给出的book-rev8.pdf资料中第一章的最后一个问题,我就把我对这个问题的思考放到这篇文章中。

引用

http://leenjewel.github.io/blog/2014/07/29/%5B%28xue-xi-xv6%29%5D-cong-shi-mo-shi-dao-bao-hu-mo-shi/

https://my.oschina.net/u/864891/blog/87965

端口信息

引言

本来自己查了很多资料,想自己写出来,结果下笔的时候发现别人已经把我想写的部分全部写出来了,而且比我想的还要具体,所以我就不写了,把链接放出了,顺便我补充一些

http://leenjewel.github.io/blog/2015/11/11/%5B%28xue-xi-xv6%29%5D-nei-he-gai-lan/

总结

由于内存分页在后面的lab2中也会设计,而且给出的资料写的非常详细,所以我就不多提了。这里提一下为了更好的理解什么内存分页的段选择子与CS的关系,我写了一篇关于CS寄存器的发展史

最后我提一下kern/entrypgdir.c手写的内存分页表

第一个entry_pgdir是页目录,第二个entry_pgtable页表,而且注意entry_pgtable是代表0-4M物理内存可写可读的真实内存地址

前面知道了目录和页表的作用,在现实系统中,一个目录下有1024个页表,但是这只有一个页表,而且它代表从0-4M连续的内存空间

PS:后面12位是权限位,只看前三位,可以知道是从(000-3ff)的高20位物理地址,由于我们声明了__attribute__((__aligned__(PGSIZE)))(地址4K对齐,其实意思是它真实物理地址后12位一定全部为0),所以直接取(uintptr_t)entry_pgtable地址就是页表地址,虽然后面加上权限位PTE_P + PTE_W,但是在寻找真实地址时都会屏蔽(只取前20位如),当初想了很久感觉取不到页表的真实地址,还以为有什么神奇的编译设定,后面查了很久资料才明白,所以这里提个醒后面我们会在lab2中正式接触内存分页技术,这里只是相当于设定了一个“常数”,后面会将器扩展变成“函数”。

引用