Tonychow's Blog

CSAPP 读书笔记-计算机系统中的抽象-操作系统

Posted on 五 05 四月 2013 in readings • Tagged with csapp, abstract • 1 min read

初言

我们使用着计算机系统提供的种种功能,安装不同的操作系统,使用不同的软件,听歌,上网,看视频,似乎理所当然.我们也知道,信息时代是建立在0和1的基础之上的,我们的计算机系统也是遵循着0和1的二进制.但是这两者是如何关联到一起的?当我们启动一个软件的时候,计算机系统底层是怎样的?我们打开一个网页如此的简单,但是这背后,计算机系统又发生了什么事情?

程序的执行

如果是计算机系的学生,或者对计算机技术有着兴趣的人,都会知道计算机操作系统的一些概念,也知道一个程序的执行其实到底是怎么一回事.无非就是将一段在硬盘上的二进制代码加载到内存中,然后由CPU执行相关的指令.程序的执行简单来说就是这么一回事,所以一个软件的启动和执行,也就是在这个简单的基础上再加上一些复杂的操作. 更深入点,我们知道操作系统也是软件,计算机关闭的时候操作系统的编译后的可执行对象也是保存在硬盘上.在计算机启动的时候,将操作系统加载到内存上,之后,操作系统就会一直运行直至计算机重新关闭.一般来说,我们将程序运行分为两种状态,用户的应用程序运行在用户态,而操作系统则是运行在内核态.

操作系统的抽象

计算机系统中的抽象其实应该是涉及两个方面.一个是处理器方面的,处理器的指令集对于硬件的抽象;而另一方面则是操作系统方面的抽象.

正如上面提及到的,程序运行于两种状态,这是为了安全的考虑,用户态的用户程序是无法直接进行一些直接操作硬件的指令的.比如创建保存一个文件的操作,涉及到了IO操作,而保存在硬盘上也涉及到磁盘的寻道.这些操作完全交由用户来进行一方面是非常的不安全,另一方面,每个人都有自己的实现方式,那将会导致各种混乱的代码.所以,操作系统一般会通过提供一些系统调用函数给用户程序,用户程序通过系统API从而实现对系统代码的调用.而这些系统代码将会进行相关的底层操作.通过系统API,操作系统作为硬件和用户应用程序的中间层,对用户应用程序隐藏了对硬件的操作,将硬件的操作细节抽象为一个个系统调用.

操作系统的抽象是计算机系统中非常重要的一个概念,总结来说大概有三个方面的抽象:

文件对于 IO 设备的抽象

IO 设备包括硬盘等设备,操作系统将这些设备都抽象为文件.比如硬盘上的数据保存是以0和1的方式保存在不同的磁道或者区域中的,操作系统将这些数据抽象成一个个文件.相关的IO操作也抽象成了文件的操作,复杂具体的底层操作隐藏在一个个简单的系统调用函数在之下.

虚拟内存对于内存和硬盘的抽象
进程对于处理器,内存和IO设备的抽象

-EOF-

Python 内置函数 reduce

Posted on 一 18 三月 2013 in python • Tagged with python • 1 min read

原型

reduce 函数原型是 reduce(function, iterable[, initializer]),返回值是一个单值.使用例子如下:

>>> print reduce(lambda x, y: x + y, [1, 2, 3, 4, 5])
15

可以看到通过传入一个函数和一个 list , reduce 函数返回的是这个 list 的元素的相加值.注意 lambda 函数是有两个参数的,如果我们改成一个参数会怎么样?如下:

>>> print reduce(lambda x: x, [1, 2, 3, 4, 5])
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: <lambda>() takes exactly 1 argument (2 given)

结果是抛出了错误,提示 () 函数只接受一个参数缺给了两个参数.所以在 reduce 内部中,我们可以知道对于作为参数的 function ,接受了两个值作为参数的.

深入

第一个例子中, reduce 函数返回的是 list 变量元素的和,那 reduce 函数是如何实现将这个 list 变量元素相加起来呢?考虑到定义的匿名函数体中将 x 的值和 y 的值加起来了,所以应该和这个函数是相关的,那 reduce 函数给赋给这个 lambda 函数的两个参数分别是什么呢?

>>> l = []
>>> def fun(x, y):
...     l.append((x, y))
...     return x + y
... 
>>> result = reduce(fun, [1, 2, 3, 4, 5])
>>> result
15
>>> l
[(1, 2), (3, 3), (6, 4), (10, 5)]

通过这个例子,可以看出答案已经很明显了.在 reduce 函数内部,对 lambda 函数的调用一共有四次:

fun(1, 2)     #x = 1, y = 2,x 是列表的第一个元素,y是第二个元素
fun(3, 3)     #x = 3, y = 3,x 是上一次调用返回值 1+2 , y 是第三个元素
fun(6, 4)     #x = 6, y = 4,同上, y 是第四个元素
fun(10, 5)    #x = 10, y = 5,同上, y 是第五个元素

最后得到 reduce 函数的返回值 15,也就是 fun 函数的第四次调用的返回值.所以现在我们知道了,reduce 函数对作为参数的函数是有要求的,要求这个函数接受两个参数.第一个参数的值是累积的值,而第二个参数的值是 reduce 函数参数中的序列的下一个元素.其实 reduce 函数中还有第三个可选的参数初始值,如果这个参数为空则初始值默认为序列的第一个元素,所以上面可以看到第一次调用这个函数是以序列的第一个和第二个元素作为参数的.最终,最后一次调用返回的值作为 reduce 函数的返回值.

定义

reduce 函数可以参考下面的定义(来自官网):

def reduce(function, iterable, initializer=None):
    it = iter(iterable)
    if initializer is None:
        try:
            initializer = next(it)
        except StopIteration:
            raise TypeError('reduce() of empty sequence with no initial value')
    accum_value = initializer
    for x in it:
        accum_value = function(accum_value, x)
    return accum_value

reduce 函数对 function 的调用次数为 iterable 参数的长度n减1.

参考资料:

SQL 反模式读书笔记-AS

Posted on 五 11 一月 2013 in readings • Tagged with antipattern, sql • 1 min read

P16

SELECT c.product_id, COUNT(*) AS products_per_account
FROM Contacts
GROUP BY account_id

其中 Contacts 表是 Products 表和 Accounts 表的中间表，这个 SQL 查询语句的作用是查询每个账号相关的产品数量。

SELECT c.product_id, c.accounts_per_product
FROM (
    SELECT product_id, COUNT(*) AS accounts_per_product
    FROM Contacts
    GROUP BY product_id
) AS c
HAVING c.accounts_per_product = MAX(c.accounts_per_product)

这个 SQL 查询语句的作用是查询相关账号最多的产品。在这两个查询语句中我注意到的是 accounts_per_product 和 products_per_account 这两个本来不存在的字段。很明显这两个是通过 AS 得到的字段。AS 也就是 Alias (别名)，通过 Alias 可以方便组织多表查询特别是在涉及到自身对应自身表的时候，比如评论表如果想要父级和子级的结果查询，同时也可以用 Alias 给表的字段起一个别名，便于输出，比如上面的两个 SQL 查询。

第一个 SQL 查询语句中，通过将 c.product_id，COUNT(*) 这个要查询的字段 alias 成 products_per_account，这样输出的结果类似于：

products_per_account
7

就很容易阅读了。

第二个 SQL 查询语句中

SELECT product_id, COUNT(*) AS accounts_per_product
FROM Contacts
GROUP BY product_id

这样一段查询得到结果集合被 alias 成了 c ，此外其中也将根据 product_id 查询得到的 products 数量 alias 成了 accounts_per_product，所以 c 这个集合中也多了一个字段 accounts_per_product，通过这样的处理，想要得到关联账号最多的产品的 product_id 就简单得好像以下：

SELECT product_id, accounts_per_product
FROM c 
HAVING accounts_per_product = MAX(accounts_per_product)

这个查询语句通过 AS，写得相当优雅，易懂。

CSAPP读书笔记- 一个C程序的编译

Posted on 二 09 十月 2012 in readings • Tagged with csapp, reading-notes • 2 min read

CSAPP中，1.2节讲到了程序的编译:

Programs Are Translated By Other Programs into Different Forms.

程序由其他程序翻译成不同的形式，其实看下面这张图应该可以很清晰地了解上面这一句：

c程序编译

上图是一个 hello 的 C 程序由 GCC 编译器从源码文件 hello.c 中读取内容并将其翻译成为一个可执行的对象文件 hello 的过程。这个过程包含了几个阶段：

首先是源文件，此时是处于文本类型：

1 // C 代码
2 #include <stdio.h>
3 int main(int argc, char** argvs)
4 {
5     printf("hello, world\n");
6 }

然后是预处理阶段，将对以#开始的指令进行修改，比如对于#include <stdio.h>指令，预处理器将会读取系统头文件 stdio.h 内容，然后将其内容直接插入到程序源码文本中，经过预处理之后源码文件被翻译成 hello.i 文件，此时得到的仍然是一个文本类型的 C 源码文件：

......
844
845 extern void funlockfile (FILE *__stream) __attribute__ ((__nothrow__));
846 # 938 "/usr/include/stdio.h" 3 4
847
848 # 2 "hello.c" 2
849
850 int main(int argc, char** argvs)
851 {
852     printf("hello, world\n");
853 }

以上部分代码可以看出除了#include <stdio.h>指令之外其他指令并未被改变。

接下来的是编译阶段。在这个阶段中，前一阶段得到的c程序代码将会被编译器翻译成汇编语言的形式，每个汇编语言声明都对应一个机器语言指令。这个阶段得到的是一个文本类型的汇编语言源码文件 hello.s ：

 1     .file   "hello.c"
 2     .section    .rodata
 3 .LC0:
 4     .string "hello, world"
 5     .text
 6 .globl main
 7     .type   main, @function
 8 main:
 9 .LFB0:
10     .cfi_startproc
11     pushq   %rbp
12     .cfi_def_cfa_offset 16
13     movq    %rsp, %rbp
14     .cfi_offset 6, -16
15     .cfi_def_cfa_register 6
16     subq    $16, %rsp
17     movl    %edi, -4(%rbp)
18     movq    %rsi, -16(%rbp)
19     movl    $.LC0, %edi
20     call    puts
21     leave
22     .cfi_def_cfa 7, 8
23     ret
24     .cfi_endproc
25 .LFE0:
26     .size   main, .-main
27     .ident  "GCC: (GNU) 4.4.4 20100726 (Red Hat 4.4.4-13)"
28     .section    .note.GNU-stack,"",@progbits

之后是汇编器将上个阶段得到的汇编程序源码中的每条指令都翻译成机器代码，也就是 01 的形式，生成一个对象类型的文件 hello.o ，在这里用objdump查看下这个文件的内容：

hello.o:     file format elf64-x86-64

Contents of section .text:
 0000 554889e5 4883ec10 897dfc48 8975f0bf  UH..H....}.H.u..
 0010 00000000 e8000000 00c9c3             ...........
Contents of section .rodata:
 0000 68656c6c 6f2c2077 6f726c64 00        hello, world.
Contents of section .comment:
 0000 00474343 3a202847 4e552920 342e342e  .GCC: (GNU) 4.4.
 0010 34203230 31303037 32362028 52656420  4 20100726 (Red
 0020 48617420 342e342e 342d3133 2900      Hat 4.4.4-13).
Contents of section .eh_frame:
 0000 14000000 00000000 017a5200 01781001  .........zR..x..
 0010 1b0c0708 90010000 1c000000 1c000000  ................
 0020 00000000 1b000000 00410e10 4386020d  .........A..C...
 0030 06560c07 08000000                    .V......

最后一个阶段是链接阶段，链接程序将上一个步骤产生的hello.o文件与 C 编译器提供的 printf.o 文件合并到一起，因为 hello 代码中调用了标准 C 库中的 printf 函数。这两个对象文件将会被合并成为一个可执行的对象文件，这个文件可以加载到内存中执行。下面继续用objdump查看下这个 hello 对象文件的内容:

hello:     file format elf64-x86-64

Contents of section .interp:
 400200 2f6c6962 36342f6c 642d6c69 6e75782d  /lib64/ld-linux-
 400210 7838362d 36342e73 6f2e3200           x86-64.so.2.
Contents of section .note.ABI-tag:
 40021c 04000000 10000000 01000000 474e5500  ............GNU.
 40022c 00000000 02000000 06000000 12000000  ................
Contents of section .note.gnu.build-id:
 40023c 04000000 14000000 03000000 474e5500  ............GNU.
 40024c 20b51099 4bd53844 69dcba88 4bf11585   ...K.8Di...K...
 40025c 599dda4e                             Y..N
Contents of section .gnu.hash:
 400260 01000000 01000000 01000000 00000000  ................
 400270 00000000 00000000 00000000           ............
......
......
 600788 07000000 00000000 48034000 00000000  ........H.@.....
 600798 08000000 00000000 18000000 00000000  ................
 6007a8 09000000 00000000 18000000 00000000  ................
 6007b8 feffff6f 00000000 28034000 00000000  ...o....(.@.....
 6007c8 ffffff6f 00000000 01000000 00000000  ...o............
 6007d8 f0ffff6f 00000000 1e034000 00000000  ...o......@.....
 6007e8 00000000 00000000 00000000 00000000  ................
 6007f8 00000000 00000000 00000000 00000000  ................
 600808 00000000 00000000 00000000 00000000  ................
 600818 00000000 00000000 00000000 00000000  ................
 600828 00000000 00000000 00000000 00000000  ................
 600838 00000000 00000000 00000000 00000000  ................
Contents of section .got:
 600848 00000000 00000000                    ........
Contents of section .got.plt:
 600850 b8066000 00000000 00000000 00000000  ..`.............
 600860 00000000 00000000 be034000 00000000  ..........@.....
 600870 ce034000 00000000                    ..@.....
Contents of section .data:
 600878 00000000                             ....
Contents of section .comment:
 0000 4743433a 2028474e 55292034 2e342e34  GCC: (GNU) 4.4.4
 0010 20323031 30303732 36202852 65642048   20100726 (Red H
 0020 61742034 2e342e34 2d313329 00        at 4.4.4-13).

以上就是一个简单 C 语言 hello 程序的编译过程，已夜，晚安。

Newer Posts