2019年9月

https://www.cnblogs.com/xiami-xm/articles/8417526.html

由于GEM5需要从原始的Linux内核可执行文件启动,不能使用压缩过的vmlinuz,所以一开始的想法是从当前发行版的软件包管理器下载压缩过的内核,然后从里面解压出完整版本的来。在Stackoverflow上看到了两种方法:

  1. 二进制暴力解法 https://superuser.com/questions/298826/how-do-i-uncompress-vmlinuz-to-vmlinux 分析vmlinuz的构成原理,可以得知其拆解方式。在此仅引用结论,原理学习还请暂时移步其他博客。 zImagebzImage都是指的使用gzip压缩的内核,有无b的主要区别在于内核文件的大小,实际上b就代表big。作为第一个在裸处理器上运行的程序,内核显然不能指望有其他程序能够替自己解压缩,因而vmlinuz是包含有gzip自解压的代码的。也就是说,vmlinuz文件至少由压缩的内核和预操作(比如解压)代码组成。在承认这些部分的数据是各自连续的情况下,可以通过在其中寻找gzip的文件头,来寻找压缩内核的位置,然后解压即可获得原始内核。

借用原文中的例子:

> od -A d -t x1 vmlinuz | grep '1f 8b 08 00'
0024576 24 26 27 00 ae 21 16 00 1f 8b 08 00 7f 2f 6b 45

其中1f 8b 08 00是gzip文件的文件头,标识一个合法的gzip文件开头。 很幸运,在当前的vmlinuz中似乎还是只含有一个gzip文件,而这个文件正是我们所需要的,经过gzip压缩的vmlinux。

> dd if=vmlinuz bs=1 skip=24584 | zcat > vmlinux
1450414+0 records in
1450414+0 records out
1450414 bytes (1.5 MB) copied, 6.78127 s, 214 kB/s

使用dd命令,从指定位置复制数据出来,bs=1表示每次的数据操作量为1字节,使用这个值能够较为简便地确定开始位置(od命令所提供的偏移量就是以字节为单位的)。比如上文中的0024576表示十六进制数据“24”相对文件首部的偏移量为24576 * 1字节 = 24576字节。将偏移量定位到gzip文件首部的“1f”,相对“24”向后偏移了8字节,故dd中的命令偏移量设置为24576 + 8 = 24584。使用管道将二进制内容直接发送到zcat,在命令行内完成文件的解压,得到预期中的vmlinux文件。

  1. 使用Linux内核包提供的解压工具(天知道原理和1是不是一样的) https://stackoverflow.com/questions/12002315/extract-vmlinux-from-vmlinuz-or-bzimage 简单说就是使用scripts目录下的extract-vmlinux脚本来完成操作。不过这个我没试过。

几乎完全参考自:https://blog.csdn.net/u012822903/article/details/64506037

  1. 下载所需系统的Minimal(最小版本),或者Cloud Image(云镜像),不用安装的那种

  2. 使用util目录下的gem5img.py生成镜像:python2 util/gem5img.py init /path/to/your/img <size> 其中size表示镜像大小,一般单位为MB。根据原文,使用了root权限建立镜像。

  3. 挂载镜像: 先用losetup将文件挂载为系统可识别的设备,然后再用mount命令挂载为磁盘分区。 gem5img.py可以自动完成这一系列工作:sudo util/gem5img.py mount /path/to/your/img /mount/folder

  4. 把Linux系统上的文件树复制过去,如果是压缩文件的话直接解压到根目录即可

  5. 设置串口作为GEM5与虚拟系统的默认通信方式: 建立etc/init/tty-gem5.conf

    # ttyS0 - getty
    #
    #This service maintains a getty on ttyS0 from the point the system is
    # started until it is shut down again, unless there is a script passed to gem5.
    # If there is a script, the script is executed then simulation is stopped.
    
    start on stopped rc RUNLEVEL=[12345]
    stop on runlevel [!12345]
    
    console owner
    respawn
    script
       # Create the serial tty if it doesn't already exist
       if [ ! -c /dev/ttyS0  ]
       then
         mknod /dev/ttyS0 -m 660 /dev/ttyS0 c 4 64
       fi
    
       # Try to read in the script from the host system
       /sbin/m5 readfile > /tmp/script
       chmod 755 /tmp/script
       if [ -s /tmp/script  ]
       then
         # If there is a script, execute the script and then exit the simulation
         exec su root -c '/tmp/script' # gives script full privileges as root user in multi-user mode
         /sbin/m5 exit
       else
         # If there is no script, login the root user and drop to a console
         # Use m5term to connect to this console
         exec /sbin/getty --autologin root -8 38400 ttyS0
       fi
    
    end script
  6. 按照目标架构,编译好m5文件放到sbin目录下: 由于不同架构下的编译方式可能不一样,make的时候要用-f选项指定目标平台所对应的Makefile。

  7. 系统内安装应用 不知道为啥要链接三个目录,但是这里不是用ln,因为非系统底层的文件系统映射,并不是所有软件都能较好支持。 这里用mount的bind选项:

    sudo /bin/mount -o bind /dev dev
    sudo /bin/mount -o bind /sys sys
    sudo /bin/mount -o bind /proc proc

    然后用chroot来模拟对另一套文件系统的操作:sudo chroot /path/to/mounted/root /bin/bash 这时的bash就会按照新的伪根目录进行操作了,有root权限。内核还是宿主系统的,显然。 操作完成之后要卸载镜像,在此之前需要先把上面的三个目录umount一下。

  8. 关于启动 最小版本的Ubuntu内部是不含有启动内核的。一般来说,内核文件是放在/boot目录下的。Ubuntu的最小版本可以通过apt下载对应的内核,但是这个方法并不适用于GEM5。GEM5的启动方式是直接执行内核,因而内核必须是一个完整的文件,静态编译且保留符号才可运行,所以在镜像外部准备一个未经压缩的完整Linux内核,在启动时指定为参数即可。现在发行版提供的大多是vmlinuz,是将原始版本vmlinux脱去符号、再经gzip压缩后的版本,还原后由于没有符号不能用于GEM5,还原方法打算另开一文简述(已经写好了->参见这里)。所以考虑一下自己编译吧。

一个单文件的C语言源程序也是一个C项目。


在之前用C语言编程的时候,往往都是随意地新建一个.c.cpp文件,把代码往里面一写,gcc命令一敲,然后就在命令行里运行自己的程序,开始快乐苦B的debug之旅了。直到最近学习编译原理,了解了一些程序解析的原理之后,才开始把这个曾经思考过,却又未曾放在心上的问题拿出来解决。

在看了这篇文章之后,有了一定的新认识,决定也自己写点东西来加深一下理解。(看起来是位高中物竞,大学计科的dalao啊)

首先提出一个问题:C语言中的.c.h读者有见到过吗?在使用时,有注意到自己是在何种情况下使用两者的吗?

显然,一个接触过C语言的人,是一定见到过这两者的。因为,即使是一个编程界最基础的程序Hello World,在使用C语言编写时也必须同时用到这两种类型的文件。

回忆一下,步骤如下:

  1. 建立helloworld.c
  2. 使用任意文本编辑器(如记事本)打开,在内部输入如下内容:

    #include <stdio.h>
    int main()
    {
    printf("Hello world!\n");
    return 0;
    }
  3. Ctrl+S,关闭;
  4. 使用编译器编译(如GCC):gcc -o helloworld.exe helloworld.c
  5. 运行:helloworld.exe,或者./helloworld.exe

于是我们就见到了helloworld.cstdio.h两个文件。至少到这里,一般人都会有的想法:编写自己的程序用.c后缀,使用系统预定义的函数用.h后缀。为什么不能反过来呢?理论上可以。不过由于这已经形成了约定俗成的习惯,随意地违反规则,可能造成意料之外的结果。

接下来,按照大众称呼,将.c文件称呼为源文件source file.h文件称呼为头文件header file。何为源文件呢?程序是由代码编译生成的,代码是程序之源,因而代码又叫做程序的源代码;源代码中的文件自然而然地便可以称为源文件了。那何为头文件呢?浅显易懂的理解方法是,.h文件作为include预处理指令的操作对象,一般都是随预处理指令放在文件头部位置的。(C语言中代码功能与书写位置是有关的;作用域为定义位置开始向后,所以需要的功能最好在一开始就引用。

在上文所提到的文章中,作者表示,由于include预编译指令的实际作用是将目标文件直接复制到当前文件的同一位置,所以文件到底叫啥,有什么后缀名都无关紧要,因为文件名在include预编译指令中必须明确指定。一开始我还在这踩了个坑,以为头文件中函数的实现只能在名称对应的源文件中查找,直到我试了一下。。。发现实际上至少在Visual Studio中,只要是在解决方案资源管理器中添加了的文件,都算是源文件,即使名字不对应,后缀奇怪,也不会影响函数实现的搜索,平时常见的头文件和源文件命名对应的目的只是为了方便开发人员寻找函数的实现代码。换个说法,就是MSVC会在编译时把添加到项目资源管理器的文件都扫描一遍,生成对应的目标文件(符号表)。即使后缀改成exe,只要没从解决方案中排除,照样编译给你看

寻找的两种不同的库文件(Windows下的.dll,Linux下的.so;Windows下的.lib,Linux下的.a),依次对应的是动态编译和静态编译两种各有优劣的编译方法。在此不做展开,关于这个内容的博客在搜索引擎上还是很好找的。由于了解尚不够深入,目前还不清楚源文件的有无是否影响动态编译——反正静态是肯定不影响的:编译器往往提供了其C标准实现(有多种,如GCC的glibc,BSD的BSD libc,Windows平台下的MSVC Runtime等等)的静态编译库,而不提供其实现源码。(从某种程度上来讲实现了对源码的保护)

但是在最简单的Hello World例子中,我们是无法找到stdio.c这个文件的。因为往往编译器都提供的是静态库,如上一段所说,原因为何我也不清楚。。

由于Windows下的MinGW采用的C标准实现是MSVC的,因而在编译程序时,所需要的函数实现都是从MSVC对应的静态库里提取的。这个静态库一般是libmsvcrt.a,使用strings工具可以看出其中存在printf字符串,可以间接地表明其中含有printf的实现。顺便了解到Windows下与grep对应的命令是findstr

由include的原理所牵扯到的是,“所include的文件一定要是头文件,而不能是源文件吗?”这样一个问题。这个想法很好:把源文件复制到待引用文件的头部的话,相当于是只是把函数的定义换了个位置写,然后用编译器命令复制过去,在理论上是行得通的。然而若是亲自实践的话,会发现编译器报出符号多重定义的错误,即实际上并不可行。

这个思考方式忽视了一个问题:打开任何一个现有项目的的头文件查看,里面都是只有函数的原型声明的,没有任何实现代码。上面也有提到,编译器会自动到所有指定为源文件的文件中寻找函数的实现,来试图在链接过程使这个函数具体化。那么如何实现寻找呢?在对源码直接进行搜索的基础上进行改进,把对源文件的词法和语法分析的中间结果记录下来,也就是可能会听说过的.obj文件,里面就有编译器可以识别格式的文件信息,包括定义的变量、函数等。再把函数名字相同的函数寻找出来(由于C语言是面向过程型的语言,没有重载特性,故没有函数签名一说),作为函数声明的实现。也就是说,可以理解为,编译期先将源文件解析为一一对应的一系列“符号集合”,然后在“符号集合”的并集里寻找匹配的函数实现。那么,上面的问题就好解决了:如果include了一个源文件的话,声明引用的文件中会出现被引用文件的代码,这些函数被定义了一遍,放进该文件的符号表里;同时由于被引用的文件被视为了源文件,该文件自身也会有一个对应的符号表,把文件里的函数定义一遍。由于这个“并集”并不会、且出于严谨的目的也不能自动合并命名重复的函数实现,因而在链接阶段,链接器将不知道该采用哪个实现,直接报出多重定义的错误。

如果我不把被include的文件添加至项目呢?

这个更好回答,你告诉编译器这个不是源代码文件,编译器就会直接在词法分析预处理的阶段报错。需要的文件“不存在”(因为你告诉编译器不是这个文件,而它又找不到其他满足条件的文件),词法分析无法进行。

而函数的声明和定义就不一样了,声明是针对编译的过程而言的,为的是向语法分析器确认该函数的用法。至于该函数到底有啥用,语法分析器不管,因为它不需要关心自己所处理的句子的内在含义的问题,只要句子“读得通”(符合文法)就行。所以,函数的声明是不需要写入到符号表的,相同的声明可以在不同的源文件中同时出现。这个时候,头文件的作用就显现出来了:能够规范简洁而统一地对需要引用的同一(批)函数进行声明。这个功能还可以扩展至所有声明性的工作,包括宏定义#define、C++的类定义、结构体以及枚举类型的定义,等等。但凡涉及到实体化的工作,即使是变量声明,也不能放在头文件中,因为只要有实体的对象都会被添加至符号表,造成重定义的错误。

总结如下: .c文件里写代码(放实体),.h文件里放声明(说空话)。因为口说无凭,立字为据嘛

  1. 优先级去除文法的二义性 优先级在于确定无二义的文法时有重大作用,它可以确定在具有多个可选右侧的产生式中,到底选择哪个的顺序。显然这个顺序在产生式本身是无法定义的,所以需要通过多级的产生式来强行确立一个顺序:必须先完成这个表达式的匹配,才能进行下一级匹配。 由于个人的逻辑水平实在有限,发现可以作为一个规律记忆的是,最先匹配的产生式右侧,在运算时的优先级是最低的(出现多个优先级相同的运算符的话,就需要规定推导方式了,比如最左?)。也就是说,需要最先计算的表达式,是需要最后匹配的。至于为什么是这样。。暂时不知道

  2. 不连续的模式句型 比如1n0m1m0n,两侧的1和0出现次数一致,中间的次数也一致。这个时候中间部分照常处理,用0A1替换即可,外侧的不连续0和1则可以视作附在A两侧的对称句型,与A不同的是对称中心不为空而是A。也就是说,外侧句型B中间不是10而是1A0,这样就解决了中间夹了一个A的问题,即B ::= 1B0 | A。实际上A就是B中对称中心为空的特殊情况。之前被老师坑了,以为产生式右侧不能放ε,所以就对右侧有了奇怪的理解,比如A ::= 0A1 | 01。。。

写在草稿纸上,之前的工作早晚会被埋没了。


之前看了一下SSD的I/O调度算法,发现里面大有文章。 看的还是Stan Park的论文:https://dblp.org/rec/html/conf/fast/ParkS12 该论文有15页。该论文的中心内容为作者自行研发的一套SSD I/O调度器,为了体现出其性能的优越性,作者将其与一些常见的Linux I/O调度器进行了性能比较,包括应用程序综合性能和读写公平程度两大方面。毕竟,这个I/O调度器的目的是为了解决由SSD基本结构造成的读写不公平性。(读写操作共用相同队列,但是写入时间要远远长于读取时间,按照最短任务,最先执行Shortest Job First, SJF的理论来看,让大量耗时较短的读取操作等待耗时较长的写入操作完成,会对性能有相当大的负面影响;当然也不能一味地优先读取,这样对写入也不公平,让一定时间内的读取任务优先执行即可)

  1. NOOP 仿佛是No Operation的缩写。(= =)正如其名字一样,一个队列,先来先走,不做任何操作。在实际情况下根据算法实现者的考虑,可能会对任务按照地址进行一定的顺序重排,这样能够减少一定的I/O时间(最明显的是机械硬盘,连续读取省去了磁头机械臂移动带来的额外等待耗时),但整体思路就是按先来后到发送I/O请求。

  2. CFQ Linux下经常使用的一个I/O调度器,全名为Completely Fair Queueing,即完全公平队列。采用类似模拟的方法计算任务的发送顺序,给每个任务建立一个单独的请求队列,然后分配相同的时间片给每个队列用以执行请求。由于公平性问题在网络(不是社交网络,理解成设备之间通信的网络比较好)上也有需求,可以借鉴一下CFQ在网络上的解决方法:由于网络层传输数据是按照包来的,显然在包头定义完长度之后整个包的大小就确定了,包的传输中断的话会被对方主机认为包损坏,因而在网络层包不可拆。所以采用这么一个办法:用计算机模拟包的预计传输时间,每次发送预计完成最早的包,在宏观上就有着近似的效果。但是由于我没有深入研究Linux上的具体实现方法,在磁盘I/O上的具体规则如何有待考证。

  3. WFQ Weighted Fair Queueing,加权公平队列,是CFQ的一种改版,可以为不同优先级的队列分配对应合适的时间片长度。

  4. Deadline https://blog.csdn.net/hs794502825/article/details/24664259 照着链接看了一下源码,没看完,说的太具体了,讲的是在Linux系统中的实现,而不是算法本身的思路。

  5. Anticipation 翻译为中文是预测。该算法主要针对在HDD上运行、需要连续读取数据的应用。如上文NOOP中略微提到过的请求重排序一样,该算法会在单次I/O请求结束后较短的时间内,强制空闲I/O设备,等待可能出现的连续地址的请求。这样对于某些加载-处理类型的任务较为友好。解决的问题是“假空闲”:一个任务的I/O请求执行完毕后,可能还没有发送下一请求;此时系统认为该程序程序暂时不需要I/O,开始处理其他程序的I/O请求。而可能恰恰在1-2ms后,该任务发出了下一I/O请求,可是却需要等到其他任务的请求执行完成后才能得到处理。(个人举例是MD5校验码的计算:MD5计算可以使用当前已计算的部分,即已经获得的部分内容的MD5码,追加需要计算部分的数据进行计算。这样做的目的是节约内存,不然一次加载整个文件的话,有的设备内存会吃不消。则程序的运行流程可视为:读取数据-合并至已有的部分数据MD5-读取数据-继续合并MD5,直至整个文件加载完成,完成整个文件的MD5计算)似乎Anticipation的等待时间典型值为6ms。但是由于该方法使用场景过于狭窄(尤其是现在多任务系统,而且不会都是连续读取型请求,所以强制空闲反而可能降低整体I/O效率),所以现在的Linux内核基本上都是不用这个的,仅作为替选方案存在于<=4.x版本的Linux内核中。

  6. Deficit Round Robin 毛。。咳咳,俄罗斯友人的一项传统游戏,一把左轮,一发子弹,一人一枪,看谁先中。这里的Round Robin有着类似的规则,所有程序轮流使用相同时间的稀缺资源(如磁盘或网络I/O),直到任务执行完成。而这里的Deficit一词直译为赤字,引申为赊欠,表示在一个Round Robin轮回中没有使用完的时间可以加到下一轮回。没有用完分配时间的原因是,原子性的任务耗时若是小于可用的剩余时间,将不能执行,因而有很大概率会剩下零散的时间片。若是忽略每个程序可能剩下的不等资源片,又会在整体上表现出资源分配的不公平性。因而,采取占用一点资源的方式,记录下每个任务所剩下的未使用资源,在下一个周期补上,能够有效地弥补其公平性。 A:你们玩吧,今天我不参加了 BC等:行,我们先玩,明天多给他来两枪 与上面的冷笑话相反的是,在系统中程序是不会嫌资源多的。