>

第七章

去年今日此门中,人面桃花相映红。人面不知何处去,桃花依旧笑春风。

《现代操作系统》

非常棒的一本书,可以把很多知识点给串起来,对于操作系统的历史发展和基本运行规则有比较清晰的描述。对非计算机科班的孩纸特别友好。个人认为第二章进程和线程,第三章存储管理,第六章死锁,第十章Linux实例研究都是非常值得读的章节,对实际理解操作系统也非常有用。当然如果涉及到视频,第七章的多媒体也不错。

存储管理这一章有一个小节介绍了很多种页面置换算法,在实际应用中,iOS很多第三方的框架有用到,比如YYCache用的LRU算法。

名词解释

BIOS:Basic Input Output System 基本输入输出系统;

BSD:Berkeley SoftWare Distribution 伯克利软件发布版本;

POSIX:Portable Operating System Interface of UNIX,可移植操作系统接口,前三个字母代表可移植操作系统,后缀IX用来使这个名字与Unix的构词相似;

MMU:Memory management Unit 内存管理单元

IDE:Integrated Drive Electronics 集成驱动电子设备

ADSL:非对称数字用户环线

JPEG:Joint Photographic Experts Group 联合摄影专家组

MPEG:Motion Picture Experts Group 运动图像专家组

VCR:Video Cassette Recorder 录像机

RPC:Remote Procedure Call 远程过程调用

TCP:Transmission Control Protocol 传输控制协议

DNS:Domain Name System 域名系统

URL:Uniform Resource Locator 统一资源定位符

HTTP:Hypertext Transfer Protocol 超文本传输协议

shell:命令行界面

PID:Process Identifer 进程标识符

PAE:物理地址扩展

NFS:Network File System 网路文件系统

LPC:Local Procedure Call 本地过程调用

APC:Asynchronous Procedure Calls 异步过程调用

ACL:访问权限控制列表

ALPC:Advanced Local Procedure Call 高级本地过程调用

VAD:Vritual Address Descriptor 虚拟地址描述符

第二章 进程与线程

1.进程间通信的几种方式:管道pipe,信号量,互斥量(信号量的简化版本),管程,消息传递。其中信号量和互斥量是属于共享内存的方式,比如信号量可以存放在内核中,只能通过系统调用来访问。如果没有共享的途径,则可以使用共享文件。

——似乎kill(pid,signal)这个系统调用,可以发送信号给别的进程,算进程间通信方式的一种嘛?——是的

——信号(signal):信号是一种比较复杂的通信方式,用于通知接收进程某一事件已经发生。

——套接字socket也算一种进程间的通信机制?——对,只不过一般是两台不同机器上的进程之间的通信。

管道pipe是一种虚文件,它可连接两个进程。当进程A想对进程B发送数据时,它把数据写到管道上,仿佛管道就是输出文件一样。进程B可以通过读该管道而得到数据,仿佛该管道就是一个输入文件一样。

一个例子: git log grep xyz

把进程git 的输出 作为进程grep的输入。

进程间通信方式的扩展阅读:https://www.jianshu.com/p/c1015f5ffa74

2.对于单核处理器来说,如果某个进程需要从内存中读出一个字(需要花费多个时钟周期),多线程CPU则可以切换至另一个线程。多线程不提供真正的并行处理。在任一时刻只有一个进程在运行,但是线程的切换时间则减少到纳秒数量级。

在Unix系统中,使用fork 系统调用来创建新的进程。在调用了fork后,这两个进程(父进程和子进程)拥有相同的存储映像、同样的环境字符串和同样的打开文件。通常,子进程接着执行一个execve或一个类似的系统调用,以修改其存储映像并运行一个新的程序。

在Unix中,进程和它的所有子女和后裔共同组成一个进程组;相反,Windows则没有进程层次的概念,所有的进程地位都是相同的。

3.一个进程是某种类型的一个活动,它有程序,输入,输出以及状态;如果一个程序运行了两遍,则算作两个进程。 ——这是微信可以多开的基本原理。

4.停留在后台处理诸如电子邮件,web页面,新闻,打印之类活动的进程称为守护进程;在Unix中可以用ps指令列出正在运行的进程。

5.不同的进程有不同的地址空间,父进程和子进程也有不同的地址空间。

6.进程有三种状态:运行态(此时占用CPU),就绪态(可运行,但是没有CPU分配给它)和阻塞态(除非外部事件发生,否则不能运行)。

Unix中,当一个进程从管道或设备文件(例如终端)读取数据时,如果没有有效的输入存在,则进程会被自动阻塞。

7.为了实现进程模型,操作系统维护着一张表格——进程表(数组或链表结构);每个进程占用一个表项,该表项包含了进程状态的重要信息,包括程序计数器,堆栈指针,内存分配情况,所打开文件的状态,账号和调度信息,以及其他在进程由运行态转换到就绪态或阻塞态时必须保存的信息。

每个计算都有一个被保存的状态,存在一个会发生且使得相关状态发生改变的事件集合,我们把这类设计称为有限状态机。

多线程使得顺序进程的思想得以保留下来,这种顺序进程阻塞了系统调用(如磁盘IO),但是仍旧实现了并行性。

8.进程模型基于两种独立的概念:资源分组与执行。

9.进程用于把资源集中到一起,而线程则是在CPU上被调度执行的实体。资源管理的单位是进程而不是线程。

10.所有的线程都有完全一样的地址空间,这意味着他们也共享同样的全局变量。线程可以在用户空间或内核中实现。

线程概念试图实现的是,共享一组资源的多个线程的执行能力,以便这些线程可以为完成某一任务而共同工作。

每个线程的堆栈有一帧,供各个被调用但是还没有从中返回的过程使用。在该帧中存放了相应过程的局部变量以及过程调用完成之后使用的返回地址。

11.用户级线程切换,保存该线程状态的过程和调度程序都只是本地过程,所以其要比内核级线程切换快很多,同时它允许每个进程有自己定制的调度算法。

12.在内核中创建或撤销线程的代价比较大。系统调用的代价比较大。

13.信号是发给进程的而不是线程的。

一个消息的到达导致系统创建一个处理该消息的线程,这种线程称为弹出式线程。因为线程相当新,没有历史包袱,这类线程可以快速创建。使用弹出式线程的结果是,消息到达与处理之间的时间非常短。

在内核空间中运行弹出式线程通常比在用户空间中容易且快捷,而且内核空间中的弹出式线程可以很容易访问所有的表格和IO设备。不过出错的内核线程会比出错的用户线程造成更大的损害。

14.把对共享内存进行访问的程序片段称作临界区域。

15.只有在有理由认为等待时间是非常短的情形下,才使用忙等待。用于忙等待的锁,称为自旋锁。

使用TSL或XCHG指令来防止几个CPU同时访问一个信号量,这与生产者或消费者使用忙等待来等待对方腾出或填充缓冲区是完全不同的。信号量操作仅需几个毫秒,而生产者或消费者则可能需要任意长的时间。

供两个或多个进程使用的信号量,初始值为1,保证同时只有一个进程可以进入临界区,称为二元信号量。

信号量mutex用于互斥,它用于保证任一时刻只有一个进程读写缓冲区和相关的变量。

信号量的另一种用途是用于实现同步。信号量full和empty用来保证某种时间的顺序发生或不发生。在本例中,他们保证当缓冲区满的时候生产者停止运行,以及当缓冲区空的时候消费者停止运行,这种用法与互斥是不同的。

如果不需要信号量的计数能力,又是可以使用信号量的一个简化版本,称为互斥量。

如果多个线程被阻塞在同一个互斥量上,当互斥量被解锁时,将随机选择一个线程运行并允许它获得锁。

如果两个或多个进程共享其全部或大部分的地址空间,进程和线程之间的差别就变得模糊起来。当然,共享一个公共地址空间的两个进程仍旧有各自的打开文件,报警定时器以及其他一些单个进程的特性个,而在单个进程中的线程,则共享进程的全部的特性。另外,共享一个公共地址空间的多个进程决不会拥有用户级线程的效率。

16.管程是一种高级同步原语,一个管程是一个由过程、变量及数据结构等组成的一个集合,他们组成一个特殊的模块或软件包。

17.任一时刻管程中只能有一个活跃进程。

18.进入管程时的互斥由编译器负责,但通常的做法是用一个互斥量或者二元信号量。

19.消息传递是系统调用。

20.进程切换的代价是比较高的。首先用户态必须切换到内核态;然后保存当前进程的状态,然后通过运行调度算法选定一个新进程,之后将新进程的内存映像重新装入MMU,之后进程开始运行。进程切换还要使整个内存告诉缓存失效,强迫缓存从内存中动态装入两次(进入内核一次,离开内核一次)。

21.尽管有一些不同,但许多适用于进程调度的处理方法也同样适用于线程调度。当内核管理线程的时候,调度经常是按线程的,与线程所属的进程基本或根本没有关联。

22.批处理系统中的调度算法:FIFO先来先服务,最短作业优先(耗时短),最短剩余时间优先。

23.交互式系统的调度算法:轮转调度,优先级调度,多级队列,公平分享等等。

24.进程切换的消耗:保存和装入寄存器值及内存映像,更新各种表格和列表,清除和重新调入内存高速缓存等。

25.用户级线程和内核级线程之间的差别在于性能。用户级线程的线程切换需要少量的机器指令,而内核级线程需要完整的上下文切换,修改内存映像,使告诉缓存失效,这导致了若干数量级的延迟。

26.内核级线程中,内核从来不了解每个线程的作用(虽然它们被赋予了不同的优先级)。一般而言,应用定制的线程调度程序能够比内核更好的满足应用的需要。

27.几乎所有的操作系统都把一个进程视为一个容器,该容器用以聚集相关的资源,如地址空间、线程、打开的文件、保护许可等。

第三章 存储管理

1.操作系统中管理分层存储器体系的部分称为存储管理器。它的任务是有效的管理内存,即记录哪些内存是正在使用的,哪些内存是空闲的;在进程需要时为其分配内存,在进程使用完后释放内存。

——所有APP内部的内存泄漏,在APP被杀掉后,都会不复存在,因为APP所在的地址空间里的内存page会悉数被操作系统回收标记为空闲内存。安卓越用越卡是因为很多APP开了很多的后台服务service,或者干脆后台重启。

2.最底层的高速缓存方案由硬件来完成。

3.地址空间为程序创造了一种抽象的内存。地址空间是一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间,并且这个地址空间独立于其他进程的地址空间(除了在一些特殊情况下进程需要共享它们的地址空间外)。

——动态库的地址空间是独立的,是在App加载动态库的时候动态分配的(这也是可以被多个APP进程共享的基础)。而静态库是在链接的时候就已经确定了地址。比如有一个单例 [Preference sharedInstance],Preference是静态库P提供的,你的App在使用这个,然后你开发了一个动态库B,B也在使用Preference这个静态库P。那么你以为你们的单例是同一个实例么,遗憾的告诉你,不是。因为静态库P既会链接到App中,也会编译链接到动态库B中,也就是这两个模块中分别存在一份P的完整代码编译结果,单例 [Preference sharedInstance]会在各自模块的地址空间分配一个实例。

4.地址空间可以不是数字的。一套“.com”的互联网域名也是地址空间。

5.基址寄存器和界限寄存器的机制,是简单的把每个进程的地址空间映射到物理内存的不同部分。程序的起始物理地址装载到基址寄存器中,程序的长度装载到界限寄存器中。每次一个进程访问内存,取一条指令,读或写一个数据字,CPU硬件会把地址发送到内存总线前,自动把基址值加到进程发出的地址值上。

6.有两种处理内存超载的通用方法。最简单的策略是交换技术,即把一个进程完整调入内存,使该进程运行一段时间,然后把它存回磁盘。空闲进程主要存储在磁盘上。另一种策略是虚拟内存,该策略甚至能使程序在只有一部分被调入内存的情况下运行。(缺页会产生中断,从而读取缺失的页面)

7.交换技术在内存中产生了多个空闲区,通过把所有的进程尽可能向下移动,有可能将这些小的空闲区合成一大块。该技术称为内存紧缩。这个操作通常不进行,因为它要耗费大量的CPU时间。

8.若一个进程在内存中不能增长,而且磁盘上的交换区也满了,那么这个进程只有挂起直到一些空间空闲,或者可以结束该进程。

9.为了减少因内存区域不够而引起的进程交换和移动所产生的开销,可以当换入或移动进程时为它分配一些额外的内存。然而,当进程被换出到磁盘上时,应该只交换进程实际上使用的内存中的内容,将额外的内存交换出去是一种浪费。

10.空闲内存管理的两种方式:位图和链表。

11.在决定把一个占k个分配单元的进程调入内存时,存储管理器必须搜索位图,在位图中找出有k个连续为0的串,查找位图中指定长度的连续0串是耗时的操作(因为在位图中该串可能跨越字的边界),这是位图的缺点。

12.另一种记录内存使用情况的方法是,维护一个记录已分配内存段和空闲内存段的链表。链表中的每一个结点都包含以下域:空闲区或进程的指示标志,起始地址,长度和指向下一结点的指针。

13.段链表使用双向链表比单向链表更方便,更容易找到上一个结点,并检查是否可以合并。

14.首次适配算法:存储管理器沿着段链表进行搜索,直到找到一个足够大的空闲区,除非空闲区大小和要分配的空间大小正好一样,否则将该空闲区分为两部分,一部分供进程使用,另一部分形成新的空闲区。它速度很快,因为它尽可能少的搜索链表结点。

15.最佳适配算法:搜索整个链表,找出能够容纳进程的最小的空闲区。因为每次调用都要搜索整个链表,所以它要比首次适配算法慢。让人感到意外的是它比首次适配算法或下次适配算法浪费更多的内存,因为它会产生大量无用的小空闲区。

16.快速适配算法:它为哪些常用大小的空闲区维护单独的链表。快速适配算法寻找一个指定大小的空闲区是十分快速的,但当一个进程终止或者被换出时,寻找它的相邻块,查看是否可以合并的过程是非常耗时的。

17.虚拟内存:每个程序拥有自己的地址空间,这个空间被分割成多个块,每一块称作一页page。每一页有连续的地址范围。这些页被映射到物理内存,但并不是所有的页都必须在内存中才能运行程序。当程序引用到一部分在物理内存中的地址空间时,由硬件立刻执行必要的映射。当程序引用到一部分不在物理内存中的地址空间时,由操作系统负责将缺失的部分装入物理内存并重新执行失败的指令。

18.从某个角度来讲,虚拟内存是对基址寄存器和界限寄存器的一种综合。

19.虚拟地址空间按照固定大小划分称为页面page的若干单元。在物理内存中对应的单元称为页框page frame。页面和页框的大小通常是一样的。现有操作系统常用的页大小一般从512字节到64kb。目前一般4kb或8kb的比较多。

20.当程序访问了一个未映射的页面,MMU注意到该页面没有被映射,就会产生一个缺页中断。操作系统找到一个很少使用的页框且把它的内容写入磁盘(如果它不在磁盘上)。随后把需要访问的页面读到刚才回收的页框中,修改映射关系,然后重新启动引起陷阱的指令。

21.虚拟地址到物理地址的映射可以概括如下:虚拟地址被分成虚拟页号(高位部分)和偏移量(低位部分)两部分。

22.页表的目的是把虚拟页面映射为页框。

23.不论是读还是写,系统都会在该页面被访问时设置访问位。它的值被用来帮助操作系统在发生缺页中断时选择要被淘汰的页面。不再使用的页面要比正在使用的页面更适合淘汰。

24.虚拟内存本质上是用来创造一个新的抽象概念——地址空间。这个概念是对物理内存的抽象,类似于进程是对物理机器(CPU)的抽象。虚拟内存的实现,是将虚拟地址空间分解成页,并将每一页映射到物理内存的某个页框或者(暂时)解除映射。

25.当发生缺页中断时,操作系统必须在内存中选择一个页面将其换出内存,以便为即将调入的页面腾出空间。如果要换出的页面在内存驻留期间已经被修改过,就必须把它写回磁盘以更新该页面在磁盘上的副本;如果该页面没有被修改过,那么它再磁盘上的副本就已经是最新的,不需要回写。

26.页面置换算法对比

27.一个进程正在使用的页面的集合称为它的工作集。

28.不少分页系统都会设法跟踪进程的工作集,以确保让进程运行以前,它的工作集就已经在内存中了。该方法称为工作集模型,其目的在于大大减少缺页中断率。在让进程运行前预先装入其工作集页面也称为预先调页。预先调页就是在程序继续运行之前预先装入推测出的工作集的页面。请注意工作集是随着时间变化的。

29.基于工作集的页面置换算法,基本思路就是找出一个不在工作集中的页面并淘汰它。

30.管理内存动态分配的一种方法是使用PFF(page fault frequency,缺页中断率)算法。它指出了何时增加或减少分配给一个进程的页面,但却完全没有说明在发生缺页中断时应该替换掉哪一个页面,它仅仅控制分配集的大小。

31.减少竞争内存的进程数的一个好方法是将一部分进程交换到磁盘,并释放他们所占有的所有页面。即使是使用分页,交换也是需要的,只是现在交换的是用来减少对内存潜在的需求,而不是收回它的页面。一些进程被周期性的从磁盘调入,而其他一些则被周期性的交换到磁盘。

32.当内存中的进程数过低的时候,CPU可能很长的时间都处于空闲状态。考虑到该因素,在决定交换出哪个进程时不光要考虑进程大小和分页率,还要考虑它的特性(CPU密集型还是IO密集型)以及其他进程的特性。

33.几个不同的用户同时运行一个程序是很常见的。那些只读的页面(诸如程序文本)可以共享,但是数据页面则不能共享。

34.共享数据要比共享代码麻烦,但也不是不可能。特别是在Unix中个,在进行fork系统调用后,父进程和子进程要共享程序文本和数据。但只要有一个进程更新了一点数据,就会触发只读保护,并引发操作系统陷阱。然后会生成一个该页的副本,这样每个进程都有自己的专用副本。两个复制都是可以读写的,随后对任何一个副本的写操作都不会再引发陷阱。这就是写时复制,它通过减少复制而提高的性能。

35.一个更加通用的技术是共享库,在Windows中称为DLL或动态链接库。

36.当一个程序和共享库链接时,链接器没有加载被调用的函数,而是加载了一小段能够在运行时绑定被调用函数的存根例程。依赖于系统和配置信息,共享库和程序一起被装载,或者在其所包含函数第一次被调用时被装载。当一个共享库被装载和使用时,整个库并不是被一次性的读入内存。而是根本需要,以页面为单位装载的,因此没有被调用到的函数是不会被装载到内存中的。

37.除了可以使可执行文件更小,节省内存空间之外,共享库还有一个优点:如果共享库中的一个函数因为修正一个bug被更新了,那么并不需要重新编译调用了这个函数的程序。

38.库被装载到的物理地址与这个库是否为共享库是没有任何关系的。因为所有的页面都被MMU硬件从虚拟地址映射到了物理地址。

39.在编译共享库时,用一个特殊的编译选项告知编译器,不要产生使用绝对地址的指令,相反,只产生使用相对地址的指令。只使用相对偏移量的代码被称作位置无关代码。

40.共享库实际上是一种更为通用的机制——内存映射文件的一个特例。这个机制的思想是:进程可以通过发起一个系统调用,将一个文件映射到其虚拟地址空间的一部分。在多数实现中,在映射共享的页面时不会实际读入页面的内容,而是在访问页面时才会被每次一页的读入。

41.如果两个或两个以上的进程同时映射了一个文件,它们就可以通过共享内存来通信。这个机制提供了一个进程之间的高带宽通道。如果内存映射文件可用,共享库就可以使用这个机制。

42.为保证有足够的空闲页框,很多分页系统有一个称为分页守护进程的后台进程,它在大多数时候睡眠,但定期被唤醒以检查内存的状态。如果空闲叶框过少,分页守护进程通过预定的页面置换算法选择页面换出内存。如果这些页面装入内存后被修改过,则将它们写回磁盘。

43.在任何情况下,页面中原先的内容都被记录下来。当需要使用一个已被淘汰的页面时,如果该叶框还没有被覆盖,将其从空闲叶框缓冲池中移出即可恢复该页面。

44.允许程序员对内存映射进行控制的一个原因就是为了允许两个或者多个进程共享同一部分内存。如果程序员可以对内存区域进行命名,那么就有可能实现共享内存。通过让一个进程把一片内存区域的名称通知另一个进程,而使得第二个进程可以把这片区域映射到它的虚拟地址空间中去。

45.页面共享也可以用来是吸纳高性能的消息传递系统。一般传递消息的时候,数据被从一个地址空间复制到另一个地址空间,开销很大。如果进程可以控制他们的页面映射,就可以这样来发送一条消息:发送进程清除那些包含消息的页面的映射,而接收进程把它们映射进来。这里只需要复制页面的名字,而不需要复制所有数据。

46.分布式共享内存:该方法允许网络上的多个进程共享一个页面集合,这些页面可能(而不是必要的)作为单个的线性共享地址空间。

47.当调度一个进程执行时,必须为新进程重置MMU,刷新TLB,以清除以前的进程遗留的痕迹。

48.当进程退出的时候,操作系统必须释放进程的页表、页面和页面在硬盘上所占用的空间。如果某些页面是与其他进程共享的,当最后一个使用它们的进程终止的时候,才可以释放内存和磁盘上的页面。

49.锁定内存中的页面:一种解决方法是锁住正在做IO操作的内存中的页面以保证它不会被移出内存。锁住一个页面通常称为在内存中钉住页面。另一种方法是在内核缓冲区完成所有的IO操作,然后再将数据复制到用户页面。

50.在磁盘上分配页面空间的最简单的算法是在磁盘上设置特殊的交换区,甚至从文件系统划分一块独立的磁盘(以平衡IO负载)。大多数Unix是这样处理的。在这个分区里没有普通的文件系统,这样就消除了将文件偏移转换成块地址的开销。取而代之的是,始终使用相应分区的起始块号。

51.由于程序正文通常是只读的,当内存资源紧张、程序页不得不移出内存时,尽管丢弃它们,在需要的时候再从可执行文件读入即可。共享库也可以用这个方式工作。

52.编译器编译过程中会创建的表:

53.分段也有助于在几个进程之间共享过程和数据。这方面的一个常见的例子就是共享库。在分段系统中,可以把图形库放到一个单独的段中由各个进程共享,从而不再需要每个进程的地址空间都保存一份(比如iOS的UIKit和Foundation)。

54.每个段只包含了一种类型的对象,所以这个段就可以设置针对这种特定类型的合适的保护。

55.分段和分页的实现本质上不同的:页面是定长的而段不是。(比如page一页一般4kb)

56.分段和分页的结合:MULTICS。一个段描述符包含了一个段是否在内存中的标志,只要一个段的任何一部分在内存中这个段就被认为是在内存中,并且它的页表也会在内存中。MULTICS中的一个地址由两部分构成:段和段内地址。段内地址又进一步分为页号和页内的字。

57.另一个分段和分页结合例子是Intel Pentium处理器。Pentium处理器中虚拟内存的核心是两张表,即LDT(局部描述符表)和GDT(全局描述符表)。每个程序都有自己的LDT,但是同一台计算机上的所有程序共享一个GDT。LDT描述局部于每个程序的段,包括其代码、数据、堆栈等;GDT描述系统段,包括操作系统本身。

58.系统通过交换技术可以同时运行总内存占用超过物理内存大小的多个进程,如果一个进程没有内存空间可用,它将会被换到磁盘上。内存和磁盘上的空闲空间可以使用位图或空闲区链表来记录。

59.虚拟内存在最简单的形式中,每一个进程的地址空间被划分为同等大小的块,称为页面page,页面可以被放入内存中任何可用的页框内。有多重页面置换算法,其中两个比较好的算法是老化算法和工作集时钟算法。

60.为了使分页系统工作良好,仅选择算法还是不够的,还要关注诸如工作集的确定、存储器分配策略以及所需要的页面大小等问题。

61.分段可以帮助处理在执行过程中大小有变化的数据结构,并能简化连接和共享。分段还有利于为不同的段提供不同的保护。有时可以把分段和分页结合起来,以提供一种二维的虚拟内存。

第四章 文件系统

1.长期存储信息的三个基本要求:①能够存储大量的信息。②使用信息的进程终止时,信息仍旧存在。③必须能使多个进程并发存取有关信息。

2.进程与线程,地址空间和文件,这些抽象概念均是操作系统中最重要的概念。

3.文件是进程创建的信息逻辑单元。如果能把每个文件看成一种地址空间,那么读者就离理解文件的本质不远了。

4.文件是受操作系统管理的。有关文件的构造、命名、存取、使用、保护、实现和管理方法都是操作系统设计的主要内容。操作系统中处理文件的部分称为文件系统file system。

5.在Unix里,如果有文件扩展名,则扩展名长度完全由用户决定,一个文件甚至可以包含两个或更多的扩展名。当然Unix中文件扩展名只是一种约定,操作系统并不强迫采用它。相反,Windows对扩展名赋予含义。

6.普通文件中包含有用户信息,一般分为ASCII文件和二进制文件。Unix系统还有字符特殊文件和块特殊文件。字符特殊文件和输入/输出有关,用于串行IO类设备,如终端、打印机、网络等。块特殊文件用于磁盘类设备。

7.ASCII文件的最大优势是可以显示和打印,还可以用任何文本编辑器进行编辑。如果以ASCII文件作为输入输出,就很容易把一个程序的输出作为另一个程序的输入,如shell管道。

8.文件头以所谓的魔数(magic number)开始,表明该文件是一个可执行的文件(防止非这种格式的文件偶然运行)。

9.能够以任何次序读取其中字节或记录的文件称作随机存取文件。有两种方法来指示从何处开始读取文件,一种是每次read操作都给出开始读文件的位置;另一种是用一个特殊的seek操作设置当前位置,在seek操作后,从这个当前位置顺序的开始读文件。

10.文件都有文件名和数据。操作系统还会保存其他与文件相关的信息,如文件的创建日期和时间、文件大小等。这些附加的信息称为文件属性,有些人称之为元数据。

11.文件的临时标志表明当创建该文件的进程终止时,文件会被自动删除。

12.很多系统限制进程打开文件的个数,以鼓励用户关闭不再使用的文件。磁盘以块为单位写入,关闭文件时,写入该文件的最后一块,即使这个块还没有满。

13.增量编译:编译时检查目标文件的修改时间,以实现最小编译。

14.在很多系统中,目录本身也是文件。

15.如果路径名的第一个字符是分隔符,则这个路径就是绝对路径。Unix中分隔符是“/”,Windows中是“\”,MULTICS中则是”>”。

16.每个进程都有自己的工作目录,这样在进程改变工作目录并退出后,其他进程不会受到影响,文件系统也不会有改变的痕迹。

17.link连接技术允许在多个目录中出现同一个文件。有时称为硬连接。

18.文件系统存放在磁盘上。多数磁盘划分为一个或多个分区,每个分区中有一个独立的文件系统。磁盘的0号扇区称为主引导记录(MBR),用来引导计算机。在MBR的结尾是分区表。该表给出了每个分区的起始和结束地址。表中的一个分区被标记为活动分区。在计算机被引导时,BIOS读入并执行之。引导块中的程序将装载该分区的操作系统。

19.超级快中的典型信息包括:确定文件系统类型用的魔数,文件系统中数据块的数量以及其他重要的管理信息。

20.文件存储的实现的关键问题是记录各个文件分别用到哪些磁盘块。

21.每个文件都从一个新的块开始,这样如果文件A实际上只有1/3块,那么最后一块的结尾会浪费一些空间。

22.文件分配表:File Allocation Table,FAT。

23.目录系统的主要功能是把ASCII文件名映射成定位文件数据所需的信息。

24.在需要查找文件名时,加快查找速度的一个方法是在每个目录中使用散列表。

25.文件系统本身是一个有向无环图,而不是一棵树。

26.符号连接的问题是需要额外的开销。必须读取包含路径的文件,然后要一个部分一个部分的扫描路径,直到找到 i 节点。符号连接有一个优势,即只要简单的提供一个机器的网络地址以及文件在该机器上驻留的路径,就可以连接全球任何地方的机器上的文件。

27.每隔一段时间,或者是有特殊需要时,被缓冲在内存中的所有未决的写操作都被放到一个单独的段中,作为在日志末尾的一个邻接段写入磁盘。总而言之,所有的写操作最初都被缓冲在内存中,然后周期性的把所有已缓冲的写作为一个单独的段,在日志的末尾处写入磁盘。

28.LFS(日志结构文件系统)有一个清理线程,该清理线程周期的扫描日志进行磁盘压缩。整个磁盘成为一个大的环形缓冲区,写线程将新的段写到前面,而清理线程则将旧的段从后面移走。

29.日志文件系统的基本想法是保存一个用于记录系统下一步将要做什么的日志。这样当系统在完成它们即将完成的任务前崩溃时,重新启动后,可以通过查看日志,获取崩溃前计划完成的任务,并完成它们。微软的NTFS文件系统就是此类。

30.为了让日志文件系统工作,被写入日志的操作必须是 幂等 的,它意味着只要有必要,它们就可以重复执行很多次,并不会带来破坏。

31.为了增加可信性,一个文件系统可以引入数据库中 原子事务 的概念。NTFS有一个扩展的日志文件系统,并且它的结构几乎不会因系统崩溃而受到破坏。

32.Windows通过制定不同的盘符来处理这些不同的文件系统。比如“C:”、“D:”等。当一个进程打开一个文件,盘符是显式或隐式存在的,所以Windows知道向哪个文件系统传递请求,不需要尝试将不同类型文件系统整合为统一模式。

33.绝大多数Unix操作系统都使用虚拟文件系统(VFS)概念尝试将多种文件系统统一成一个有序的框架。关键的思想就是抽象出所有文件系统都共有的部分,并且将这部分代码放在单独的一层,该层调用底层的实际文件系统来具体管理数据。

34.虚拟文件系统对用户进程有一个更高层的接口,它就是著名的 POSIX 接口。

35.NFS:network file system网络文件系统。

36.几乎所有文件系统都把文件分割成固定大小的块来存储,各块之间不一定相邻。拥有大的块尺寸则意味着小文件浪费了大量的磁盘空间,小的块尺寸意味着大多数文件会跨越多个块,需要多次寻道和旋转延迟才能读出,降低了性能。(现在一般4kb-64kb一个块)

37.跟踪空闲块的两种方法:链表和位图。位图方法所需要的空间较少,只有在磁盘快满时,链表方案需要的块才比位图少。位图是一种固定大小的数据结构。

38.转存储磁盘到磁带上有两种方案:物理转储和逻辑转储。物理转储简单快速,但是不能跳过目录也不能增量转储,还不能恢复个人文件。逻辑转储可以实现增量恢复。

39.最常用的减少磁盘访问次数技术的是 块高速缓存 或者缓冲区高速缓存。它们在逻辑上属于磁盘,但实际上基于性能的考虑被保存在内存中。

40.可以使用散列表来查找某个快是否在高速缓存中。如果告诉缓存已满,则需要调入新的块,因此,要把原来的某一块调出高速缓存(如果修改过则需要写回磁盘)。这个情况跟页面置换非常相似。

41.在Unix系统中有一个系统调用sync,它强制性的把全部修改过的块立即写回磁盘。系统启动时,在后台运行一个通常名为update的程序,它在无限循环中不断的执行sync调用,每两次调用之间休眠30秒。

第五章 输入输出

1.IO设备大致可以分为两类:块设备和字符设备。块设备的特征是每个块都能独立于其他块而读写,比如硬盘,U盘等。字符设备以字符为单位发送或接收一个字符流,而不考虑任何块结构。比如打印机,鼠标等。

2.无论一个CPU是否具有内存映射IO,它都需要寻址设备控制器以便与它们交换数据。但是这样做浪费CPU的时间,所以经常用到一种称为直接存储器存取(Direct Memory Access,DMA)的不同方案。

3.无论DMA控制器在物理上处于什么地方,它都能够独立于CPU而访问系统总线。大多数DMA控制器使用物理内存地址进行传送。

4.中断信号导致CPU停止当前正在做的工作并且开始做其他的事情。通过让CPU延迟对中断的应答,直到它准备好处理下一个中断,就可以避免与多个几乎同时发生的中断相牵涉的竞争状态。

5.程序控制IO十分简单但是有缺点,即直到全部IO完成之前要占用CPU的全部时间。

6.允许CPU在等待打印机变为就绪的同时做某些其他事情的方式就是使用中断。当打印机讲字符打印完毕并且准备好接收下一个字符时,它将产生一个中断。

7.中断驱动IO的一个明显缺点是中断发生在每个字符上。DMA重大的成功是将中断的次数从打印每个字符一次减少到打印每个缓冲区一次。

8.中断最终的结果是使先前被阻塞的驱动程序现在能够继续运行。

9.每个连接到计算机上的IO设备都需要某些设备特定的代码来对其进行控制。这样的代码称为 设备驱动程序 。设备驱动程序通常是操作系统黑盒的一部分。实际上,有可能构造运行在用户空间的驱动程序,这一设计使得内核与驱动程序相隔离,并且使驱动程序之间相互隔离,这样做可以消除系统崩溃的一个主要源头。然而,大多数操作系统都要求驱动程序运行在内核中。

10.两个缓冲区轮流使用,当一个缓冲区正在被复制到用户空间的时候,另一个缓冲区正在收集新的输入。像这样的缓冲模式称为双缓冲。

11.磁盘被组织成柱面,每一个柱面包含若干磁道,磁道数与垂直堆叠的磁头个数相同。磁道又被分成若干扇区。

12.高层建筑中的电梯调度问题和磁盘臂调度很相似。

13.磁盘控制器的高速缓存完全独立于操作系统的高速缓存。

14.一个磁盘子系统具有如下特性:当一个写命令发给它时,磁盘要么就正确的写数据,要么什么也不做,让现有的数据完整无缺的留下。这样的系统称为稳定存储器。

15.时钟负责维护时间,并且防止一个进程垄断CPU。

16.时钟由三个部件构成:晶体振荡器,计数器和存储寄存器。它给计算机的各种电路提供同步信号。该信号被送到计算器,使其递减计数至0。当计数器变为0时,产生一个CPU中断。

17.在方波模式中,当计数器变为0并且产生中断之后,存储寄存器的值自动复制到计数器中,并且整个过程无限期的再次重复下去。这些周期性的中断称为时钟滴答。

18.每当一个进程启动时,便启动一个不同于主系统定时器的辅助定时器。当进程终止时,读出这个定时器的值就可以知道该进程运行了多长时间。当中断法神时应该讲辅助定时器保存起来,中断结束后再将其恢复。

19.用户输入主要来自键盘和鼠标,键盘包含一个嵌入式微处理器,该微处理器通过一个特殊的串行端口与主板上的空值芯片通信。每当一个键被按下的时候都会产生一个中断,并且每当一个键被释放的时候还会产生第二个中断。

20.在Unix中,enter键被转换成一个换行用于内部存储;而在Windows上,它被转换成一个回车跟随一个换行。

21.EOF字符被解释为文件结尾。

22.Windows是面向消息的,每一个程序都有一个消息队列,与程序的所有窗口相关的消息都被发送到该队列中。程序的主循环包括提取下一条消息,并且通过调用针对该消息类型的内部过程对其进行处理。

23.通过在图像上覆盖一层网格扫描输入,每一个网格方块的平均红,绿,蓝取值被采样并且保存为一个像素的值。这样的文件称为位图(bitmap)。

24.一个停止的磁盘是休眠而不是睡眠,因为要花费相当多的时间将磁盘再次旋转起来,导致用户感到明显的延迟。重新启动磁盘将消耗相当多额外的能量。

25.节省磁盘能量的另一种方法是在RAM中拥有一个大容量的磁盘高速缓存。

26.由于电能消耗与电压的平方成正比,将电压降低一半会使CPU的速度减慢一半,而电能消耗降低到只有1/4。

27.关闭高速缓存是进入睡眠状态,将主内存的内容写到磁盘并关闭主内存则是休眠。

28.当移动计算机将要关闭无线电设备时,让移动计算机发送一条消息到基站。从那时起,基站在其磁盘上缓冲到来的消息。当移动计算机再次打开无线电设备时,它会通知基站。此刻,所有积累的消息可以发送给移动计算机。

第六章 死锁

1.操作系统都具有授权一个进程(临时)排他性访问某一种资源的能力。

2.软硬件资源都可能出现死锁。大部分死锁都和资源有关。我们把需要排他性使用的对象称为资源。简单来说,资源就是随着时间的推移,必须能够获得,使用以及释放的任何东西。

3.资源分为两类:可抢占的和不可抢占的。存储器就是一类可抢占的资源。不可抢占资源是指在不引起相关的计算失败的情况下,无法把它从占有它的进程处抢占过来。有关可抢占资源的潜在死锁问题通常可以通过在进程之间重新分配资源而化解。

4.若请求时资源不可用,则请求进程被迫等待。在一些操作系统中,资源请求失败时进程会自动被阻塞,在资源可用时再唤醒它。在其他的系统中,资源请求失败会返回一个错误码,请求的进程会等待一段时间,然后重试。

5.当一个进程请求资源失败时,它通常会处于这样一个小循环中:请求资源,休眠,再请求。

6.如果一个进程集合中的每个进程都在等待只能由该进程集合中的其他进程才能引发的事件,那么,该进程就是死锁的。无中断条件使死锁的进程不能被时钟中断等唤醒,从而不能引发释放该集合中的其他进程的事件。

7.资源死锁的四个必要条件:

①互斥条件。每个资源要么已经分配给了一个进程,要么就是可用的。

②占有和等待条件。已经得到了某个资源的进程可以再请求新的资源。

③不可抢占条件。已经分配给一个进程的资源不能强制性的被抢占,它只能被占有它的进程显示的释放。

④环路等待条件。死锁发生时,系统中一定有由两个或两个以上的进程组成一条环路,该环路中的每个进程都在等待下一个进程所占的资源。

死锁发生时,以上四个条件一定是同时满足的。如果其中任何一个条件不成立,死锁就不会发生。

8.有四种处理死锁的策略:

①忽略该问题。也许如果你忽略它,它也会忽略你。

②检测死锁并恢复。让死锁发生,检测它们是否发生,一旦发生死锁,采取行动解决问题。

③仔细对资源进行分配,动态的避免死锁。

④通过破坏引起死锁的四个必要条件之一,防止死锁的发生。

9.检测有向图环路的方法:依次将每一个节点作为一棵树的根节点,并进行深度优先搜索。如果再次碰到已经遇到过的节点,那么就算找到了一个环。

10.如果死锁进程数达到一定数量,就没有多少进程可运行了,所以CPU会经常空闲。

11.从死锁中恢复:

①利用抢占恢复,在不通知原进程的情况下,将某一资源从一个进程强行取走给另一个进程使用,接着又送回,这种做法是否可行主要取决于该资源本身的特性;

②利用回滚恢复:将该进程复位到一个更早的状态,那时它还没有取得所需的资源,接着就把这个资源分配给一个死锁进程。如果复位后的进程试图重新获得对该资源的控制,它就必须一直等到该资源可用时为止;

③通过杀死进程恢复:杀掉环中的一个进程。如果这样做行不通的话,就需要继续杀死别的进程知道打破死锁。另一种方法是选一个环外的进程作为牺牲品以释放该进程的资源。有可能的话,最好杀死可以从头开始重新运行而且不会带来副作用的进程。

12.一种能够避免死锁的的调度算法,称为银行家算法。银行家算法就是对每一个请求进行检查,检查如果满足这一请求是否会达到安全状态。若是,那么久满足该请求;若否,那么就推迟对这一请求的满足。

13.银行家算法虽然很有意义但缺乏实用价值,因为很少有进程能够在运行前就知道其所需资源的最大值。实际中,如果有,也只有极少的系统使用银行家算法来避免死锁。

14.可以通过破坏死锁发生时的四个条件,四个条件中只要有一个不成立,死锁将不会产生。

①破坏互斥使用条件。如果资源不被一个进程所独占,那么死锁肯定不会产生。避免分配哪些不是绝对必需的资源,尽量做到尽可能少的进程可以真正请求资源。

②破坏占有和等待条件。只要禁止已持有资源的进程再等待其他资源便可以消除死锁。

一种方法是规定所有进程在开始执行前请求所需的全部资源。如果所需的全部资源可用,那么就将它们分配给这个进程,于是该进程能够运行结束。如果有一个或多个资源正被使用,那么就不进行分配,进程等待。

另一种方法是,要求当一个进程请求资源时,先暂时释放其当前占用的所有资源,然后再尝试一次获得所需的全部资源。

③破坏不可抢占条件。一些资源可以通过虚拟化的方式来避免发生这样的情况。不过并不是所有的资源都可以进行类似的虚拟化。

④破坏环路等待条件。

一种是保证每一个进程在任何时刻只能占用一个资源,如果要请求另一个资源,它必须先释放第一个资源。

另一种方法是将所有的资源统一编号,进程可以在任何时刻提出资源请求,但是所有请求必须按照资源编号的顺序(升序)提出。

15.两阶段加锁:第一阶段,进程试图对所有所需的记录进行加锁,一次锁一个记录。如果第一阶段加锁成功,就开始第二阶段,完成更新然后释放锁。如果在第一阶段某个进程需要的记录已经被加锁,那么该进程释放它所有加锁的记录,然后重新开始第一阶段。

16.通信死锁:两个以上的进程利用发送信息来通信时,进程A向进程B发送请求信息,然后阻塞直至B回复。假设请求信息丢失,A将阻塞以等待回复,而B会阻塞等待一个向其发送命令的请求,因此发生死锁。

17.根据标准的定义,在一系列进程中,每个今晨因为等待另外一个进程引发的事件而产生阻塞,这是一种死锁。

18.通信死锁不能通过对资源排序或者通过仔细的安排调度来避免。但是通常可以用超时来中断通信死锁。

19.并非所有在通信系统或者网络发生的死锁都是通信死锁,资源死锁也会发生。

20.活锁:两个进程总是一再的消耗分配给它们的CPU配额,但是没有进展也没有阻塞,看起来就像是死锁发生了。

21.与死锁和活锁非常相似的一个问题是 饥饿 。饥饿可以通过先来先服务资源分配策略来避免,等待最久的进程会是下一个被调度的进程。

22.死锁检测是一个经典的图论问题。

23.在一组进程中,每个进程都因等待由改组进程中的另一个进程占有的资源而导致阻塞,死锁就发生了。这种情况会使所有的进程都处于无限等待的状态。

24.死锁的另外一种可能的情况是一组通信进程都在等待一个消息,而通信信道却是空的,并且也没有采用超时机制。

第七章 多媒体操作系统

1.机顶盒实际上就是普通的计算机,只不过其中包含特殊的芯片用于食品解码和解压缩。

2.NTSC制式每秒包含30帧,PAL和SECAM制式美妙包含25帧。

3.传输率的变动称为 颤动 。

4.让人可以接受的回放多媒体所要求的实时性通常通过服务质量参数来描述,这些参数包括可用平均带宽,可用峰值带宽,最小和最大延迟(两者一起限制了颤动)以及位丢失概率。

5.必须要有保持子文件同步的某种方法,这样才能保证当选中的音频轨迹回放与视频保持同步。

6.隔行扫描:首先显示所有的奇数扫描线,接着再显示所有的偶数扫描线。非隔行扫描则称为逐行扫描。

7.人的眼睛对亮度信号比对色度信号敏感的多,所以色度信号不需要非常精确的进行传输。理解亮度和色度对于理解视频压缩的工作原理是十分必要的。

8.数字视频最简单的标识方法是帧的序列,每一帧由呈矩形栅格的图像要素即像素组成。数字视频隔行扫描是不必要的,因此所有计算机显示器都采用逐行扫描,仅仅连续刷新相同的帧三次就足以消除闪烁。

9.运动的平滑性是由每秒不同的图像数决定的,而闪烁则是由每秒刷新屏幕的次数决定的。

10.奈奎斯特采样定理:如果存在最高频率的成分为f,那么以2f 的评率进行采样就足够了。

11.所有的压缩系统都需要两个算法:编码算法和解码算法。这些算法具有某些不对称性,这一不对称性对于理解数据压缩是十分重要的。

①一个多媒体文档只需要编码一次,但是需要解码数千次;②编码解码的过程不必是100%可逆的。

12.视频信号经过编码和解码之后与原始信号只存在轻微的差异通常就是可以接受的。被称为有损的,所有用于多媒体的压缩系统都是有损的,因为这样可以获得更好的压缩效果。

13.用于压缩运动图像的标准MPEG不过是分别对每一帧进行JPEG编码,再加上某些帧间压缩和运动补偿等额外的特征。

14.JPEG大体上是对称的:解码一幅图像花费的时间与编码基本相同。

15.MPEG的两个版本均利用了在电影中存在的两类冗余:空间冗余和时间冗余。

16.互相连续的帧常常几乎是完全相同的,这就是时间冗余,利用这一事实可以达到额外的压缩效果。DV数字视频只使用类JPEG的方案,这是因为只单独对每一帧进行编码可以达到更快的速度,从而使编码可以实时完成。

17.对于摄像机和背景绝对静止,而又一两个演员在四周缓慢移动的场景而言,帧与帧之间几乎所有的像素都是相同的。此时,仅仅将每一帧减去前一帧并且在差值图像上运行JPEG就相当不错。然而,对于运动的镜头场景而言,就需要某种方法对这一运动进行补偿,这正是MPEG要做的事情,实际上,这就是MPEG和JPEG之间的主要差别。

18.MPEG-2输出由三种不同的帧组成:

①I帧:自包含的JPEG编码静止图像。

②P帧:与上一帧逐块的差。

③B帧:与上一帧和下一帧的差。

19.在输出流中使I帧周期性的出现是十分必要的。有了I帧,就可以向前或向后跳过若干帧直到找到一个 I 帧并从那里开始观看。由于上述原因,MPEG每秒将 I 帧插入到输出流中一次或两次。

20.MP3是功能最强大也是最出名的音频压缩算法。MP3属于MPEG视频压缩标准里的音频部分。

21.音频压缩可以用两种方法完成:①波形编码技术中,信号通过傅里叶变换变换成频率分量。②感知编码是基于心理声学的——人们如何感知声音的科学。MP3正式基于感知编码。

22.感知编码的关键特性在于一些声音可以掩盖住其他声音。在一个频段里响亮的声音掩盖住另一频段中较柔和声音的能力,这种较柔和声音只有在没有响亮声音时才可以听到——频段屏蔽。

23.通过跟踪那些被附近频段能量更强的信号所屏蔽的信号,可以省略越来越多的编码信号中的频率,以此来节约二进制位。MP3编码的实质就是对声音做傅里叶变换从而得到每个频率的能量,之后只传递那些不被屏蔽掉的频率,并且用尽可能少的二进制位数来编码这些频率。

24.大部分的二进制位分配给拥有多数频谱能量的未屏蔽波段,小部分二进制位分配给拥有较少频谱能量的未屏蔽波段,已屏蔽的波段不分配二进制位。

25.多个相互竞争的进程,其中若干进程或全部进程具有必须满足的最终时限的调度称为实时调度。

26.在多媒体系统中,进程通常是可抢占的,这意味着允许有危险错过其最终时限的进程在正在运行的进程完成工作以前将其中断,然后当它完成工作以后,被中断的前一个进程再继续运行。

27.进程要访问一个文件时,首先要发出open系统调用。如果该调用成功,则调用者被给予某种令牌以便在未来的调用中使用,该令牌在Unix中倍称为文件描述符,在Windows中被称为句柄。

28.为了读取一个多媒体文件,用户进程发出start系统调用,指定要读的文件和各种其他参数,接着视频服务器开始以必要的速率送出帧,然后用户进程以帧进来的速率对它们进行处理。具有这种数据流模型的文件服务器被称为 推送型服务器。与此相对照的是拉取型服务器,用户可以通过重复的调用read一块接一块的取得数据,每调用一次可以拉取出一块数据。

29.音频压缩是独立于视频压缩的,所以对于在高速模式中显示的每一视频帧,还必须找到正确的音频帧(除非在高于正常速度播放时将声音关闭)。因此,对一个DV文件进行快进操作需要有一个索引,该索引可以使帧的查找快速的实现。MPEG要求按顺序播放文件。

30.多媒体文件非常庞大,通常只写一次而读许多次,并且倾向于被顺序访问。

31.诸如出租的电影,从图书馆借出的图书,访问的web网页,甚至一部小说中使用的英文单词或者特大城市居住的人口,相对流行性的一个合理的近似遵循着一种令人惊奇的可预测模式——zipf定律。(其实可以看一下泊松分布)

32.在传统的LRU缓冲区高速缓存背后的思想是,当一个块被使用之后,应该将其保存在高速缓存中,以防很快再次需要访问它。

33.为了保持输出给客户的数据流运行流畅,在服务器中采用双缓冲是必要的。

34.多媒体文件包含多重平行的轨迹,通常有一个视频轨迹和至少一个音频轨迹,有时还有一些字母轨迹。在回放期间,这些轨迹都必须保持同步。

35.视频压缩可以使用帧内压缩(JPEG),也可以使用帧间压缩(MPEG)。后者将P帧表示为与前一帧的差,而B帧则既可以基于前面的帧,也可以基于后面的帧。

36.多媒体文件系统通常使用推送型模型而不是拉取型模型。

补充:

1.直播的四大指标:画质、卡顿率、延时、秒开。画质和卡顿率要看传说的码率,码率高画质高,卡顿率也可能增大。秒开则主要是减少GOP,即减少 I 帧在视频流的间隔。

第八章 多处理机系统

1.按照爱因斯坦相对论,电子信号的速度不可能超过光速。光速=波长*频率。光速真空中大约是30cm/ns,在光纤中大概是20cm/ns。这在计算机中意味着10GHz的时钟,信号的传送距离总共不会超过2cm。——这个可能是计算机始终频率没有继续上升的原因

2.获取更高速度的一种处理方式是大规模使用并行计算机。在高强度的数据处理中经常采用高度并行计算机。

3.虚拟化技术:一种通过软件创造出更多虚拟CPU的方法。

4.共享存储器多处理机(简称为多处理机)是这样一种计算机系统,其两个或更多的CPU全部共享访问一个公用的RAM。运行在任何一个CPU上的任何程序都看到一个普通(通常是分页)的虚拟地址空间。这个系统唯一的性质是,CPU可对存储器字写入某个值,然后读回该字,并得到一个不同的值(因为另一个CPU改写了它)。这种性质构成了处理器间通信的基础:一个CPU向存储器写入某些数据而另一个读取这些数据。

5.所有的多处理机都具有每个CPU可以访问全部存储器的性质。

6.如果CPU试图在一个或多个远程高速缓存中写入一个字,总线硬件检测到写,并把一个信号放到总线上通知所有其他的高速缓存。如果其他高速缓存有个干净的副本,也就是同存储器内容完全一样的副本,那么它们可以丢弃该副本 并让写者在修改之前从存储器取出高速缓存块(进行写操作)。如果某些其他高速缓存有 脏 的副本,它必须在处理写之前把数据写回存储器或者把它通过总线直接传送到写者。——高速缓存一致性协议。

7.多核芯片:将两个或多个完整的CPU,通常称为核,放到一个芯片上。

8.特殊的硬件电路可以确保在一个字同时出现在两个或者多个的高速缓存中的情况下,当其中某个CPU修改了该字,所有其他高速缓存中的该字都会被自动的并且原子性的删除来确保一致性,这个过程称为 窥探。

9.除了所有核都是对等的多核芯片之外,还有一类多核芯片被称为片上系统(SOC)。这些芯片含有一个或多个主CPU,但是同时还包含若干个专用核,例如视频与音频解码器,加密芯片,网络接口等。

10.对称多处理机:在存储器中有操作系统的一个副本,且任何CPU都可以运行它。任何CPU都可以运行操作系统,但是任一时刻只有一个CPU可运行操作系统。——大多数现代多处理机都采用这种安排。

11.使用多个锁进行同步:给一个未能获得锁的CPU分配一个锁变量并且把它附在等待该锁的CPU链表的末端。在当前锁的持有者退出临界时,它释放链表中的首个CPU正在测试的私有锁(在自己的高速缓存中)。然后该CPU进入临界区。操作完成后,该CPU释放锁。其后继者接着使用,以此类推。

12.不论是连续轮询方式,间歇轮询方式,还是把自己附在进行等候CPU链表中的方式,我们都假定需要加锁的互斥信号量的CPU只是保持等待。

13.多数研究工作使用了这样一个模型:一个未能获得互斥信号量的线程自旋一段时间。如果时间超过某个阈值,则进行切换。在某些情形下,该阈值是一个定值,典型值是切换至另一个线程再切换回来的开销。在另一些情形下,该阈值是动态变化的,它取决于所观察到的等待互斥信号量的历史信息。

14.亲和调度:尽量使一个线程在它前一次运行过的同一个CPU上运行。(方便复用高速缓存的内容)

15.两级调度算法有三个优点:

①它把负载大致平均的分配在可用的CPU上;

②它尽可能发挥了高速缓存亲和力的优势;

③通过为每个CPU提供一个私有的就绪线程链表,使得对就绪线程链表的竞争减到了最小,因为试图使用另一个CPU的就绪线程链表的机会相对较小。

16.群调度:既可以调度时间又可以调度空间的算法,特别是对于要创建多个线程而这些线程通常需要彼此通信的线程。

群调度由三个部分组成:

①把一组相关线程作为一个单位,即一个群,一起调度。

②一个群中的所有成员在不同的分时CPU上同时运行。

③群中的所有成员共同开始和结束其时间片。

17.群调度的思想是,让一个进程的所有线程一起运行,这样,如果其中一个线程向另一个线程发送请求,接受方几乎会立即得到消息,并且几乎能够立即应答。

18.多计算机是紧耦合CPU,不共享存储器。每台计算机有自己的存储器。

19.很多接口板上有一个完整的CPU,可能另外还有一个或多个DMA通道。他们被称为网络处理器。这种设计意味着主CPU将一些工作分给了网卡,诸如处理可靠的传送(如果底层硬件会丢包),多播(将包发送到多于一个目的地),压缩/解压缩,加密/解密以及在多进程系统中处理安全事务等。

20.在多计算机系统中高性能通信的敌人是对包的过度复制。最简单的设计是使用两块网络接口板,一块映射到用户空间供应用程序使用,另一块映射到内核空间供操作系统使用。许多计算机就正是这样做的。

21.DMA使用武力地址而不是虚拟地址,并且独立于CPU运行。

22.远程过程调用RPC:允许程序调用位于其他CPU中的过程。当机器1的进程调用机器2的过程时,在机器1中的调用进程被挂起,在机器2中的被调用的过程执行。可以在参数中传递从调用者到被调用者的信息,并且可在过程的处理结果中返回信息。

23.虚拟化技术允许一台机器中存在多台虚拟机,每一台虚拟机可能运行不同的操作系统。好处是一台虚拟机上的错误不会自动的使其他虚拟机崩溃。

24.即使在不可虚拟化的硬件上,II 型管理程序也能正常工作的原因:所有的敏感指令被仿真这些指令的过程调用所替代。客户操作系统发射的敏感指令不会被真正的硬件执行。它们转换了对管理程序的调用,而这些调用仿真了那些敏感指令。

25.几乎全部的现代操作系统都支持虚拟内存,即从虚拟地址空间到物理地址空间的页面映射。这个映射由(多级)页表所定义。

26.多核芯片上的所有核共享内存。

27.分布式系统面对不同硬件和操作系统实现某种统一性的途径是,在操作系统的顶部添加一层软件。这层软件称为中间件。这层软件提供了一些特定的数据结构和操作,从而允许散布的机器上的进程和用户用一致的方式来操作。

28.用于特定计算机通信的这些规则的集合,称为协议。

29.所有的现代网络都使用所谓的协议栈把不同的协议一层一层叠加起来。每一层解决不同的问题。

30.浏览器访问网页的步骤:

31.采用多个CPU可以把计算机系统建造得更快更可靠。CPU的四种组织形式是多处理器,多计算机,虚拟机和分布式系统。

第九章 安全

1.安全领域中基本但却重要的工具:现代密码学。

2.计算机系统的四个主要安全目标:数据保密,数据完整性,系统可用性(指没有人可以扰乱系统使之瘫痪),数据隐私。

3.病毒就是一种能够自我复制并通常会产生危害的程序代码。

4.加密的目的是将明文——也就是原始信息或文件,通过某种手段变为密文,通过这种手段,只有经过授权的人才知道如何将密文恢复为明文。

5.在算法中使用的加密参数叫做密钥。加密算法本身应该完全公开,而加密的安全性由独立于加密算法之外的密钥决定。

6.公钥机制的主要问题在于运算速度要比对称密钥机制慢数千倍。

7.最常用的散列函数(哈希函数)有MD5,SHA-1,SHA-256,SHA-512。

8.所有的浏览器都预加载了大约40个著名的CA的公钥。

9.域(domain)是一对(对象,权限)组合。每一对组合指定一个对象和一些可在其上运行的操作子集。这里权限是指对某个操作的执行许可。

10.每个Unix的进程有两个部分:用户部分和核心部分。当执行系统调用时,进程从用户部分切换到核心部分。核心部分可以访问与用户部分不同的对象集。系统调用就引发了域切换。

11.大多数操作系统允许个人用户来决定谁可以读写他们的文件和其他对象。这一策略称为可自由支配的访问控制。

12.将每一个口令同一个叫做 盐 的n位随机数相关联。无论何时只要口令改变,随机数就改变。随机数以未加密的方式存放在口令文件中。对口令文件采用 加盐 的方法以及使之不可读(除非间接和缓慢的读)可以抵挡大多数的外部攻击。

13.更换口令更极端的方式是每次登陆换一次口令,即使用一次性口令。——现在大多数的账号系统都采用

14.汉明距离:两个比特字串之间的汉明距离指从一个比特串变换为另一个比特串最少需要变化的比特数。

15.利用代码漏洞进行攻击的几种方式:

①缓冲区溢出攻击:C语言函数库的gets函数可以把(未知大小)的串变量读入定长的缓冲区里,但并不校验是否溢出,这样就很容易遭受攻击。

②格式化字符串攻击:某个变量的值在函数printf中可能以一种不显眼的方式被修改。它意味着打印一个格式化字符串可能导致一个或多个单词被存储在内存中。由于程序员的不严禁的修改,可能导致用户有了输入格式化字符串的机会,而打印一个格式化字符串可能会导致内存被重写,这就为覆盖栈中pringtf函数的返回值提供了一种方法,通过重写这个返回地址,可以使得函数在printf函数函数时跳到任何位置。

③返回 libc 攻击:通过修改当前函数的返回地址到指定位置来实施攻击。

④整数溢出攻击:计算机进行长整形数的运算,如果结果超过了整形数可以表示的最大值,就称溢出发生了。

⑤代码注入攻击:将一段代码用另一种形式注入到一个函数的参数里,当参数被取出,传递给别的函数执行时,可能会有预料之外的代码被执行。

⑥权限提升攻击:攻击者欺骗系统为其赋予比正常情况更高的权限。

16.绝对多数系统安全问题都与缓冲区溢出漏洞相关,而这类漏洞很难被修复。对付这类攻击的办法是修改代码,显示的检查用户输入的所有变量的长度。从而避免把长字符串放入定长缓冲里。

17.之所以有如此多的攻击是因为操作系统和其他应用程序都是用C语言写的,但遗憾的是,没有一个C编译器可以做到数组边界检查。

18.几乎所有的C程序都连接了libc库,这个库包括了C程序几乎所有的关键函数,其中的一个就是strcpy。该函数将一个任意长度的字符串从任意地址复制到另一地址。这种攻击的本质是欺骗strcpy函数降恶意程序复制到数据段并在那里执行。

19.作为安装免费软件的代价,他们同时也安装了恶意软件。这种方式叫做木马攻击。——木马是受害者自己安装的。

20.病毒是一种特殊的程序,它可以通过把自己植入到其他程序中来进行繁殖,就像生物界中真正的病毒那样。

21.共事者病毒并不真正感染程序,但当程序执行的时候它也执行。

22.更复杂的一类病毒是感染可执行程序的病毒。它们中最简单的一类会覆盖可执行程序,这叫做覆盖病毒。

23.病毒把自己附在正常程序里,在病毒发作时可以让原来的程序正常工作。这类病毒叫做寄生病毒。

24.最具移植性的病毒是源代码病毒。

25.能够自我复制的程序叫做蠕虫,蠕虫包含了两部分程序,引导程序和蠕虫本身。由于蠕虫能够自我复制,因此扩散趋势比病毒要快。

26.间谍软件是一种迅速扩散的恶意软件,粗略的讲,间谍软件是在用户不知情的情况下加载到PC上的,并在后台做一些超出用户意愿的事情。它隐藏自身,收集用户数据,将收集到的资料传给远程的监控者,卸载它时,它还会试图进行防御。

27.防火墙有两种基本的类型:硬件防火墙和软件防火墙。

28.最简单的一种防护墙是 无状态防护墙 :只会检查通过的包的头部,然后根据包头部的信息和防火墙的规则作出传送还是丢弃这个包的决定。

29.每次复制时都发生变异的病毒叫做多形态病毒。能够交换机器码指令而不影响程序功能的代码叫做变异引擎。

30.代码签名:我们只运行哪些来自可靠软件厂商的没有被修改过的软件。代码签名基于公钥密码体系。

iOS APP代码签名的流程(见这里http://blog.cnbang.net/tech/3386/):

31.即使一个软件已经被签名了,一个好的态度是去核实它是否都能正常运行。做这件事情的一种技术是 囚禁。

32.封装移动代码的两种方式:

①沙盒法:这种方法将每个运行的Applet(或APP)限制在一定范围的有效地址中。保证每个Applet不能跳转到或引用其他的代码沙盒或数据沙盒。

②解释法:解释运行并阻止它们获得对硬件的控制。web浏览器使用的就是这种方法。

第十章 实例研究:Linux

1.微内核背后的思想是在内核中只提供最少的功能,从而使其可靠和高校。

2.由于一个用户态进程崩溃后造成的损害要远小于一个内核组件崩溃后造成的损害,因此将功能代码从内核移到用户态后,系统会更加可靠。微内核的主要缺点是用户态与内核态的额外切换会带来较大的性能损失。

3.一直以来,Unix都被设计成一种能够同时处理多进程和多用户的交互式系统。

4.设计Linux的一个基本指导方针就是每个程序应该只做一件事并且把它做好。

5.Linux具有三种不同的接口:真正的系统调用接口,库函数接口和由标准应用程序构成的接口。

6.make 的作用是跟踪哪些文件依赖于哪些头文件等,然后安排所有需要进行的编译自动进行。几乎所有的Linux程序,除了最小的那些,都是依靠make进行编译的。

7.Linux把进程和线程简单的看作可运行的实体,并使用统一的调度策略对它们进行调度。

8.Linux系统中主要的活动实体就是进程。每个进程执行一段独立的程序并且在进程初始化的时候拥有一个独立的控制线程。每一个进程都拥有一个独立的程序计数器,用这个程序计数器可以追踪下一个将要被执行的指令。

9.在大多数单用户的工作站里,即使用户已经退出登录,仍然会有很多后台进程,即守护进程,在运行。在系统启动的时候,这些守护进程就已经被shell脚本开启。

10.系统中还存在其他的守护进程,他们接收或发送电子邮件,管理打印队列,检测内存中是否有足够的空闲页等。在Linux系统中,守护进程可以直接实现,因为它不过是与其他进程无关的另一个独立的进程而已。

11.系统调用fork将会创建一个与原始进程完全相同的进程副本。调用fork函数的进程称为父进程,新的进程称为子进程。父进程和子进程都拥有自己的私有内存映像。

12.Linux系统中的进哼可以通过一种消息传递的方式进行通信。在两个进程之间,可以建立一个通道,一个进程向这个通道里写入字节流,另一个进程从这个通道里读取字节流。这些通道称为 管道(pipe)。使用管道也可以实现同步,因为如果一个进程试图从一个空的管道中读取数据,这个进程就会被挂起直到管道中有可用的数据为止。shell中的管线就是用管道技术实现的(比如git log | grep xxx)。

13.进程还可以通过另一种方式通信:软件中断。一个进程可以给另一个进程发送信号(signal)。

一个进程只可以给它所在进程组中的其他进程发送信号,这个进程组包括它的父进程(以及远祖进程),兄弟进程和子进程(以及后裔进程)。同时,一个进程可以利用系统调用给它所在的进程组中所有的成员发送信号。

14.一个进程在某一个特定的时刻只能有唯一一个未处理的警报。第一次alarm系统调用设置的信号被第二次alarm系统调用取消了。

15.pause系统调用,它会通知Linux系统将本进程挂起知道下一个信号到来。

16.每一个进程都有一个运行用户程序的用户模式。但是当它的某一个线程调用系统调用之后,进程会陷入内核模式并且运行在内核上下文中,它将使用不同的内存映射并且拥有对所有机器资源的访问权。它还是同一个线程,但是现在拥有更高的权限,同时拥有自己的内核堆栈以及内核程序计数器。

17.Linux系统内核中,进程通过数据结构task_struct被表示成任务。一个多线程的进程将为每一个用户级线程分配一个任务数据结构。Linux是多线程的,并且它所拥有的是与任何用户进程无关的内核级线程。

18.内核将所有进程的任务数据结构组织成一个双向链表。不需要遍历这个链表来访问进程描述符,PID可以直接被映射成进程的任务数据结构所在的地址,从而立即访问进程的信息。

19.关于信号的信息必须永远保存在内存里,即使这个进程已经不在内存当中了。换句话说,关于文件描述符的信息可以被保存在用户级的数据结构里,当进程存在于内存当中并且可以执行的时候,这些信息才需要被调入内存。

20.写时复制所带来的额外好处是,不需要在内存中维护同一个程序的两个副本,从而节省了RAM。

21.从历史观点上说,进程是资源容器,而线程是执行单元。一个进程包含一个或多个线程,线程之间共享地址空间,已打开的文件,信号处理函数,警报信号和其他。

22.传统观念上,当一个新线程被创建的是偶,之前的线程和新线程除了寄存器内容之外共享所有的信息。特别是,已打开文件的文件描述符、信号处理函数、警报信号和其他每个进程(不是每个线程)都具有的全局属性。

23.Unix系统为每一个进程分配一个独立的PID,不论它是单线程的进程还是多线程的进程。Linux对进程标识符(PID)和任务标识符(TID)进行了区分。当调用clone函数创建一个新进程而不需要和旧进程共享任何信息时,PID被设置成一个新值;否则,任务得到一个新的任务标识符,但是PID不变。这样一来,一个进程中所有的线程都会拥有与该进程中第一个线程相同的PID。

24.Linux系统的线程是内核线程,所以Linux系统的调度是基于线程的。

25.Linux调度算法使用一个重要的数据结构——调度队列。在系统中,一个CPU有一个调度队列,调度队列有两个数组,一个是正在活动的,一个是过期失效的。这两个分量都是指向数组的指针,每个数组都包含了140个链表头,每个链表具有不同的优先级。链表头指向给定优先级的双向进程链表。

26.当正在活动数组中没有其他的任务了,调度器交换指针,使得正在活动的数组变为过期失效数组,过期失效数组变为正在活动数组。

27.不同的优先级被赋予不同的时间片长度。Linux系统会赋予高优先级的进程较长的时间片。

28.Linux系统区分静态优先级和动态优先级。线程的动态优先级不断的被重新计算。

29.调度器只考虑可以运行的任务,这些任务被放在适当的调度队列当中。不可运行的任务和正在等待各种IO操作或内核事件的任务被放入另一个数据结构当中,即等待队列。等待队列的头包含一个指向任务链表的指针及一枚自旋锁。为了保证等待队列可以在主内核代码、中断处理函数或其他异步处理请求代码中进行并发操作,自旋锁是非常必要的。

30.每个Linux进程都有一个地址空间,逻辑上有三个段组成:代码、数据和堆栈段。通常代码段是只读的,不会发生改变。数据段包含了所有程序变量、字符串、数字和其他数据的存储。它有两部分,初始化数据段和未初始化数据(BSS)。所有BSS部分中的变量在加载后被初始化为0。

31.未初始化数据的存在实际上仅仅是个优化,大部分全局变量并没有初始化,因此都是0。

32.为了避免分配一个全是0的物理页框,在初始化的时候,Linux就分配了一个静态零页面,即一个全0的写保护页面。当加载程序的时候,未初始化数据区域被设置为指向该零页面。

33.Linux允许数据段随着内存的分配和回收而增长和缩减,通过这种机制来解决动态分配的问题。

34.第三段是栈段,在多数机器里,它从虚拟地址空间的顶部或者附近开始,并且向下生长。当一个程序启动的时候,它的栈并不是空的,它包含了所有的环境变量以及为了调用它而向shell输入的命令行。

35.大多数Linux系统支持共享代码段(进程多开的原理)。

36.数据段和栈端从来不共享,除非是在一个fork之后,并且仅仅是哪些没有被修改过的页面。

37.除了动态分配更多的内存,Linux中的进程可以通过内存映射文件来访问文件数据。这个特性使我们可以把一个文件映射到进程空间的一部分而该文件就可以像位于内存中的字节数组一样被读写。把一个文件映射进来使得随机读写比使用read和write之类的IO系统调用要容易得多。共享库的访问就是用这种机制映射进来后运行的。

38.把一个文件映射进来的一个附加好处是两个或更多的进程可以同时映射相同的文件,其中一个进程对文件的写可以被其他进程马上看到。

39.mmap的第一个参数,addr决定文件被映射的地址,第二个参数len指示要映射的字节数。最后一个参数offset告诉从文件中的什么位置开始映射,并不一定要从0字节开始映射,任何页面边界都是可以的。

mmap(addr,len,prot,flags,fd,offset);

40.32位机器上的每个Linux进程通常有3GB的虚拟地址空间,还有1GB留给其页表和其他内核数据。在用户态下运行时,内核的1GB是不可见的,但是当进程陷入到内核时是可以访问的。内核内存通常驻留在低端物理内存中,但是被映射到每个进程虚拟地址空间顶部的1GB中。

41.内核维护内存的一个映射,该映射包含了所有系统物理内存使用情况的信息,比如区域,空闲页框等。

42.首先,Linux维护一个页描述符数组,称为mem_map,其中页描述符是page类型的,而且系统当中的每个物理页框都有一个页描述符。每个页描述符都有个指针,在页面非空闲时指向它所属的地址空间,另有一对指针可以使得它跟其他描述符形成双向链表,来记录所有的空闲页框和一些其他的域。

43.区域描述符包含了每个区域中内存利用情况的信息,例如活动和非活动页的数组,页面置换算法所使用的高低水位,还有许多其他的域。此外,区域描述符包含一个空闲区数组。

44.每个节点描述符包含了内存使用的信息和该节点上的区域。

45.分页缓存并不是一个独立的缓存,而是那些不再需要的或者等待换出的用户页面集合。如果分页缓存当中的一个页面在被换出内存之前复用,它可以被快速收回。

46.Linux支持动态加载模块,最常见的是设备驱动。

47.虚拟地址空间被分割成同构连续页面对齐的区域。每个区域由一系列连续的具有相同保护和分页属性的页面组成。代码段和映射文件就是区的例子。

48.在内核中,每个区是用vm_area_struct项来描述的。一个进程所有vm_area_struct用一个链表链接在一起,并且按照虚拟地址排序以便可以找到所有的页面。当这个链表太长时(多余32项),就创建一个树来加速搜索。——通常被组织成一个二叉红黑树。

49.内存管理单元是一个页,并且几乎所有的内存管理部件以页为操作粒度。交换子系统也是以页为操作粒度,并且跟页框回收算法紧耦合在一起。

50.代码、数据和栈段的页面是动态载入的,仅仅是在它们被引用的时候。如果用户表和页面不在内存中,知道交换器把它们载入内存进程才能运行。

51.分页是一部分由内核是实现而一部分由一个新的进程,页面守护进程,实现的。跟所有守护进程一样,页面守护进程周期性的运行。如果它发现空闲页面数量太少,就开始释放更多的页面。

52.分页文件被动态的添加或删除。一个页总是被连续的写到磁盘,用一个分页文件,也许是或者也许不是这样的。

53.页面只有在需要的时候才在分页设备或者分区上被分配。

54.Linux区分其中不同的页面:不可回收的,可交换的,可同步的,可丢弃的。不可回收页面包括保留或者锁定页面,内核态栈等,不会被换出页面。可交换页面必须在回收之前写回到交换区或者分页磁盘区。可同步的页面如果被标记为dirty就必须要写回到磁盘。最后,可丢弃的页面可以被立即回收。

55.在启动的时候,init开启一个页面守护进程kswapd(每个内存节点都有一个),并且配置它们能周期性的运行。如果有足够的空闲页面,它就继续睡眠。当然它也可以在需要更多页面时被提前唤醒。如果任何内存区域的可用空间低于一个阈值,kswapd初始化页框回收算法。

56.每次PFRA(页框回收算法)执行,它首先回收容易的页面,然后处理难的。可丢弃页面和未被引用的页面都是可以被立即回收的,同时把它们添加到区域的空闲链表中。共享页面带来的挑战是,如果一个页面被回收,那么所有共享了该页面的所有地址空间的页表都要同步更新。Linux维护高效的类似树的数据结构来方便的找到一个共享页面的所有使用者。

57.PFRA用一个类似时钟的算法来选择旧页面换出。这个算法的核心是一个循环。

58.内存管理系统的一个方面是另一个守护进程pdflush,实际上就是一组后台守护线程。pdflush要么周期性醒来(通常是500ms),把非常旧的脏页面写回到磁盘;或者当可用的内存水平下降到一个阈值时由内核显示唤醒,把压面缓存的脏页面写回到磁盘。脏页面也可以通过显示的同步请求写出到磁盘,比如通过系统调用sync,fsync等。

59.Linux系统中,所有的IO设备都被当做文件来处理,并且通过与访问所有文件同样的read和write系统调用来访问。

60.Linux把设备当做一种特殊文件整合到文件系统中,每个IO设备都被分配了一条路径。

61.特殊文件(设备)分为两类,块特殊文件和字符特殊文件。块特殊文件的主要特性是:每一个块都能够被独立的寻址和访问。也就是说,一个程序能够打开一个快特殊文件,并且不用读第0块到第123块就能读第124块。磁盘就是块特殊文件的典型应用。字符特殊文件通常用于表示输入和输出字符流的设备(比如键盘,打印机,鼠标等)。

62.IO的另外一个例子是网络,关键概念是套接字。套接字可以被动态创建和销毁。创建一个套接字成功后,系统返回一个文件描述符。创建连接、读数据、写数据、解除连接时要用到这个文件描述符。

63.每个套接字支持一种特定的网络类型,这在套接字创建时指定。最常用的类型是:

①可靠的面向连接的字节流;

②可靠的面向连接的数据包流;

③不可靠的数据包传输。

第一种套接字类型允许在不同机器上的两个进程之间建立一个等同于管道的连接。第三种方式的优点是有更高的性能,而有时候它比可靠性更加重要(比如在传输多媒体时,快速比正确性更有用——及时视频聊天)。

64.在创建套接字时,有一个参数指定使用的协议。对于可靠字节流通信来说,使用最广泛的协议是TCP。对于不可靠数据包传输来说,UDP是最常用的协议。

65.一方在本地套接字上使用一个listen系统调用,它创建一个缓冲区并且阻塞,直到数据到来。另一方使用connect系统调用,并且把本地套接字的文件描述符和远程套接字的地址作为参数传递进去。如果远程一方接受了此次调用,则系统在两个套接字之间建立起一个链接。一旦连接建立成功,它的功能就类似于一个管道。

66.Linux中IO是通过一系列的设备驱动来实现的,每个设备类型对应一个设备驱动。设备驱动的功能是对系统的其他部分隔离硬件的细节

67.IO系统被划分为两大部分:处理块特殊文件的部分和处理字符特殊文件的部分。

68.Linux系统在磁盘驱动程序和文件系统之间放置了一个高速缓存(cache),在2.2版本内核之前,Linux系统完整的维护着两个单独的缓存:页面缓存和缓冲器缓存。2.2版本以后的Linux内核版本只有一个统一的缓存。

69.cache高速缓存是内核里面用来保存数以千计的最近使用的数据块的表。不管本着什么样的目的而需要一个磁盘快,系统首先检查这个块是否在cache里边。一个程序要回写一个块时,它被写到cache里,而不是直接写到磁盘上。当cache增长到超过一个指定值时,pdflush守护进程会把这个块写回到磁盘上。另外为了防止数据块被写回到磁盘之前在cache里存留太长时间,每隔30秒系统会把所有的“赃块”都写回到磁盘上。

70.可加载模块是在系统运行时可以加载到内核的代码块。

71.Linux使用虚拟文件系统(VFS)层支持很多类型的文件系统。在Linux链接时,用户可以选择要构造到内核中的文件系统。如果需要其他文件系统,可以在运行时作为模块动态加载。

72.Linux提供了一种指向已存在文件的目录项,称作链接。

73.系统提供了两种锁,共享锁和互斥锁。如果文件的一部分已经被加了共享锁,那么在上面尝试加共享锁是允许的,但是加互斥锁是不会成功的;如果文件的一部分已经被加了互斥锁,那么在互斥锁解除之前加任何锁都不会成功。

74.creat系统调用不仅创建了一个新文件,还以写的方式打开了这个文件。create成功时返回一个非负整数,这个非负整数叫做文件描述符。

75.最常使用的文件系统调用是read和write。它们每个都有三个参数:文件描述符(表明要读写的文件)、缓冲区地址(给出数据存放的位置或者读取数据的位置),长度(给出要传输的数据的字节数)。

76.虽然几乎所有程序都是顺序读写文件的,但是一些程序需要能够从文件的任何位置随机的读写文件。每个文件都有一个指针指向文件当前的读写位置。lseek系统调用可以改变位置指针的值,所以之后的read和write可以从文件的任何位置开始读写。

77.lseek有三个参数:第一个是文件描述符,第二个是文件读写位置,第三个表明读写位置是相对于文件开头、当前位置还是文件尾。lseek的返回值是当读写位置改变后的绝对位置。lseek是唯一一个从不会引起实际的磁盘寻道的文件系统调用,因为他所做的只是修改了内存中的一个值(文件读写位置)。

78.pipe系统调用用来创建一个shell管线。它创建了一种伪文件,用于缓冲管线通信的数据,并给缓冲区的读写都返回文件描述符。

79.大多数Unix文件系统不使用位图,而使用空闲列表。

80.打开文件描述表的重点是允许父进程和子进程共享一个文件读写位置,而给不相关的进程提供各自私有的值。

81.NFS网络文件系统的基本思想是允许任意选定的一些客户端和服务器共享一个公共文件系统。NFS允许一台机器同时既是客户端又是服务器。

82.NFS的目标之一是支持异构系统,客户端和服务器可能在不同硬件上运行不同操作系统。

83.NFS支持大多数的Linux系统调用,但是也许很让人惊讶的是,open和close不被支持。

84.当一个文件句柄发送过来要求访问文件时,它检查该句柄。如果是有效的句柄,就使用它。如果安全策略被启用,验证包含对RPC头中的认证密钥的检验。

85.UID为0的用户是一个特殊用户,称为超级用户(或者根用户)。超级用户能够读和写系统中的任何文件,不论这个文件为谁所有,也不论这个文件的保护模式如何。

86.目录也是一种文件,并且具有普通文件一样的保护模式。不同的是,目录的x比特位表示查找权限而不是执行权限。

87.最常用到的安全相关的系统调用是chmod。它用来改变保护模式。

88.当一个文件的保护模式在它被打开后修改,新模式将无法影响已经打开该文件的进程。

89.Linux有三种主要接口:shell、C函数和系统调用。

90.一个进程,或者称为一个任务,通过两个关键的部分来表示,即任务结构和描述用户地址空间的附加信息。前者常驻内存,后者可能被换出内存。

91.每个进程的内存模型由三个部分组成:代码、数据和堆栈。页面守护进程采用一种修改过的双指针时钟算法保证系统有足够多的空闲页。

92.文件系统内部主要使用三种表:文件描述符表、打开文件描述表和 i 节点表。其中 i 节点表是最重要的表,包含了文件管理所需要的所有信息和文件位置信息。

第十一章 实例研究:Windows Vista

1.Windows平台的动态链接库叫做DLL,可执行文件为EXE。

2.桩程序是进行不同的使用子系统的进程间通信的。对子系统进程的调用通常是利用内核态的本地过程调用(LPC)所提供的功能。LPC实现了跨进程的进程调用。

3.本地系统调用包括管理虚拟地址的跨进程功能、线程、句柄和为了运行运用来使用特定子系统的程序而创建的进程中的异常。

4.每次创建和打开对象的调用都返回一个结构叫句柄(类似Unix的文件描述符)给调用者。句柄在接下来用于执行对象的操作。句柄是特定于创建它们的具体的进程的。通常句柄不可以直接交给其他进程,也不能用于同一个对象。

5.一个进程能够复制一个可读写的句柄,并在目标进程中把它改变为只读的版本。

6.Windows有内核对象。Unix系统也同样支持内核态对象,例如文件、网络数据包、管道、进程、共享内存的IPC设备、消息端口、信号和IO设备。

7.Windows会挂载一种特殊的文件系统(为小文件做了优化)到名字空间。这个文件系统称作注册表。

8.内核线程调度程序负责决定哪些线程执行在系统的每一个CPU上。

9.如果下一个运行的线程是在一个不同的地址空间(例如进程),调度程序也必须改变地址空间。

10.在其他类型的操作系统中被编译进内核的功能是被Windows内核动态装载和链接的,包括网络协议栈和文件系统。

11.进程管理管理着进程和线程的创建和终止,包括建立规则和参数指导它们。但是线程运行方案由核心层决定,它控制着线程的调度和同步,以及它们之间相互控制的对象,如APC。进程包含线程、地址空间和一个可以用来处理进程指定内核态对象的句柄表。

12.在大多数PC机中,最初的初始化程序是BIOS,它知道如何在一台PC机上找到设备的标准类型。引导程序知道如何在根目录的文件系统卷之外阅读足够的信息去发现独立的Windows BootMgr程序。

13.为了避免由于竞争条件而过早的释放对象,对象管理器实现了一个引用计数机制,以及引用指针的概念。

14.对象管理器保持一个单独的句柄为每个对象计数。

15.信号量、互斥体和事件,都可以处理进程间的同步。事件可以在两种状态之一:已标记信号或未标记信号。如果一个线程等待事件处于已标记信号状态,线程被立即释放。如果该事件是未标记信号状态,它会一直阻塞知道一些其他线程信号释放所有被阻止的线程(通知事件)的活动或只是第一个被阻止的线程(同步事件)。

16.端口是进程之间交换LPC消息的通道。

17.动态链接库DLL,即代码是在程序运行的时候完成的链接,而非编译时。共享的库不是一个新的概念,最现代化的操作系统使用它们。

DLL通过允许在进程之间共享通用代码来提供系统效率,保持常用代码在内存中,处理减少从程序磁盘到内存中的加载时间。并允许操作系统的库代码进行更新时无需重新编译或重新链接所有使用它的应用程序,从而提供系统的使用能力。

18.Windows Vista中的进程是程序的容器。它们持有的虚拟地址空间,以及指向内核态的对象的线程的句柄。作为线程的容器,它们提供线程执行所需要的公共资源。

19.线程是在Windows中调度CPU的内核抽象。每个线程都有两个单独调用堆栈,一个在用户态运行,一个在内核态执行。

20.内核态与每个进程共享的,即用户共享数据。这个是可以由内核写的页,但是每个用户态进程只能读。

21.在创建一个过程时创建的进程将接收一个句柄,这个句柄允许它通过映射段、分配虚拟内存、写参数和环境变量数据、复制文件描述符到它的句柄表、创建线程来修改新的进程。

22.进程是持有资源的容器,线程是内核调度的实体。

23.线程是CPU调度的基本单位,因为操作系统总是选择一个线程而不是进程来运行。因此,每一个线程有一个调度状态(就绪态、运行态、阻塞态),而进程没有调度状态。

24.线程通常在用户态运行,但是当它进行一个系统调用时,就切换到内核态,并以其在用户态下相同的属性以及限制继续运行。每个线程有两个堆栈,一个在用户态使用,一个在内核态使用。

25.需要注意的是线程是一个调度的概念,而不是一个资源所有权的概念。任何线程可以访问其所属进程的所有对象,只需要使用句柄值,并进行核实的win32调用。

26.线程间可以通过多种方式进行通信,包括管道、命名管道、邮件槽、套接字、远程过程调用RPC、共享文件等。

管道有两种模式:字节管道和消息管道。

邮件槽跟管道类似,但不完全相同,它们是单向的,而管道是双向的。而且允许发送进程将消息广播给多个接收者而不仅仅是一个接收者。

套接字也与管道类似,只不过它们通常连接的是不同机器上的两个进程。例如,一个进程往一个套接字里面写入内容,远程机器上的另外一个进程从这个套接字中读出来。套接字同样也可以被用在同一台机器上的进程通信,但是因为它们比管道带来了更大的开销,所以一般来说它们只被用于网络环境下的通信。

远程过程调用RPC时一种进程A命令进程B调用进程B地址空间中的一个函数。实现RPC的时候,通常是把它作为传输层之上的抽象层来实现。例如对于Windows来说,可以通过TCP/IP套接字、命名管道、ALPC来进行传输。ALPC的全程是高级本地过程调用,他是内核态下的一种消息传递机制。ALPC的实现是通过拷贝参数以及基于消息大小的临时共享内存分配。

进程间可以共享对象,通过这个机制,在生产者消费者问题中用到的共享缓冲区就可以轻松的实现。

27.进程间也可以使用多种形式的同步对象。包括信号量、互斥量、临界区和事件。所有的这些机制只在线程上工作,而非进程。所以当一个线程由于一个信号量而阻塞时,同一个进程的其他线程会继续运行而并不会被影响。

信号量是一个内核态对象。

互斥量也是用于同步的内核态对象,但是比信号量简单,因为互斥量不需要计数器。他们其实是锁。临界区不是内核态的对象,也不能在进程间传递。

事件有两类:通知事件和同步事件。一个事件的状态有两种:收到信号和没收到信号。对于通知事件来说,所有等待的线程都会被释放;对于同步事件来说,如果有一个或多个线程在等待,那么有且仅有一个线程被唤醒并且事件被清除。

28.在下面这些情况下,当前正在执行的线程会执行调度程序代码:

①当前执行的线程发生了信号量、互斥、事件、IO等类型的阻塞。

②线程向一个对象发信号(如发一个信号或者唤醒一个事件)时。

③配额过期(时间)。

因为Windows完全是可抢占式的,在另外两种情况下,调度程序也会被调度:

①一个输入输出操作完成时。

②等待时间结束时。

29.当在最高的优先级有多条线程处于就绪状态,它们就按时间片轮转法来调度。如果没有就绪的线程,那么处理器空闲,并设置成低功耗状态来等待中断的发生。

值得注意的是,调度取决于线程而不是取决于新城所属的进程。因此调度程序并不是首先查看进程然后再是进程中的线程。它直接找到线程。调度程序并不考虑哪个线程属于哪个进程,除非进行线程切换时需要做地址空间的转换。

30.每个线程都有一个基于进程优先级的基本优先级和一个线程自己ID相对优先级。

31.线程获得互斥量却长时间得不到调度的时候会发生一个类似的问题,致使更重要的系统线程由于等待互斥量而不能运行发生饥饿。——spin自旋锁

32.在Windows Vista系统中,每个用户进程都有它自己的虚拟地址空间。对于x86机器,虚拟地址是32位的;因此每个进程拥有4GB大小的虚拟地址空间。其中用户态进程的虚拟地址大小为2GB(在服务器系统中,用户态进程的虚拟地址大小可以配置成3GB)。另外的2GB(或1GB)空间为内核进程所用。对于x86和x64机器,虚拟地址空间需要分页,并且页的大小一般都是固定在4kb。

33.虚拟地址的每页处于三种状态之一:无效、保留或提交。

无效页面是指一个页面没有被映射到一个内存区对象,对它的访问会引发一个相应的页面失效。

保留页面的功效是:可以保证栈不会太长而覆盖其他进程的数据。

34.对于失效页面的一个可能的优化是:在进行一次IO操作时预调入一些额外的页面。修改过的页面被集中到一起,统一进行写入操作。

35.Windows Vista操作系统为每个进程都单独提供了一个4GB大小的按需分页的线性地址空间,不支持任何形式的分段。

36.调度器选择单个线程来运行而不太关心进程。存储管理器在不同,它完全是在处理进程而不太关心线程。毕竟,是进程而非线程拥有地址空间,而地址空间正是存储管理器所关心的。

37.超级预读取技术尝试预先读入很多需要的页面到内存中,尽管进程尚未在这些页面上发生页面失效。这一技术通过重叠从磁盘上读入页面和执行映像中的初始化代码,减少了启动应用程序所需的延时。同时,它改进了磁盘的吞吐量。

38.如果内存管理器能够从内存中找到需要的页而不是去磁盘查找从而响应页面失效,则称为软异常。如果需要从磁盘进行复制,则称为赢异常。

39.当一个物理页面不再映射到任何进程的页表,将进入以下三种状态之一:空闲、修改或后备。

40.物理页面有三种不同的链表:空闲链表,后备链表和已修改链表。除此以外还有第四种链表,即全部被填零的空闲页面。系统会频繁的请求全零的页面。当为进程提供新的页面,或者读取一个文件的最后部分不足一个页面时,需要全零页面。还有第五种链表存放有硬件错误的页面(即通过硬件错误检测)。

41.两个系统线程——映射页面写入器和已修改页面写入器,周期性的被唤醒来检查是否系统中有足够的干净页面。如果没有,这两个线程从已修改链表的顶部取出页面,写回到磁盘,然后将这些页面插入后备链表。当一个页面被写入时没有足够的内存,就会导致死锁。

42.另一个称为零页面线程的低优先级线程将空闲链表中的页面写全零并将页面放入全零页链表。全零页面很可能比空闲页面更加有用。

43.Windows高速缓存通过把最近和经常使用的文件片段保存在内存中的方式来提升文件系统的性能。

44.在文件系统、高速缓存管理器和内存管理器之间管理文件最困难的方面在于文件中最后一个字节的偏移。

45.在Windows中,所有与硬件无关的程序,如文件系统、反病毒过滤器、卷管理器、网络协议栈,甚至内核服务,都是用IO驱动程序来实现的。

46.在多处理器中,可以通过关闭不需要的CPU和降低正在运行的CPU的频率来减少功耗。

47.休眠——该模式将物理内存复制到磁盘,然后把电力消耗降低到很低的水平。待机模式——电源管理器将整个系统降到最低的功率状态,仅使用足够RAM刷新的功率。因为不需要将内存复制到磁盘,进入待机状态比进入休眠状态的速度更快。

48.NTFS限制每个独立的文件名最多由255个字符组成,全路径最多有32767个字符。文件名采用Unicode编码。大多数NTFS磁盘使用4kb的快。

49.安全描述符描述了谁可以对对象执行何种操作。安全描述符还包括一个系统访问控制列表,不过它表示的并不是谁可以使用对象,而是哪些对象访问操作会被记录在系统范围内的安全事件日志中。

50.进程拥有虚拟地址空间并且是资源的容器。线程是执行的单元并被内核层使用优先级算法调度执行,该优先级算法使优先级最高的就绪线程总在运行,并且如有必要可抢占低优先级线程。

51.Windows支持按需分页虚拟内存。分页算法基于工作集的概念。

52.Windows在最近的发行版本中增加了大量的安全特性,包括用Bitlocker来加密整个卷,采用地址空间随机化(ASLR),不可执行的堆栈以及其他措施使得缓冲区溢出攻击更加困难。

第十二章 实例研究:Symbian

1.一个对象提供了具体的数据以及功能,但隐藏了具体实现。一个合理实现的对象可以被移除并被另外一个不同的对象代替,只要系统其他部分对这个对象的使用(也即其接口)保持不变。

2.使用内核端对象通常意味着一个应用程序具有一个对象的句柄,也就是对对象的一个引用,然后通过这个句柄来获得对该对象接口的访问。

3.Symbian操作系统采用了面向对象的设计。系统功能的实现是隐藏的,系统数据的使用通过系统对象已定义的接口完成。

4.Symbian操作系统是一个多任务多线程的操作系统。许多进程可以同时运行,相互间可以进行通信,也可以在各进程内运行多个线程。

5.尽管Symbian操作系统不使用虚拟内存映射,但它通过按页管理实现对内存访问,并支持页的置换,也就是说支持页面换入,但不支持页面换出。

6.许多应用程序具有类似的执行模式:它们向一个通信套接字写数据或者通过管道发送信息,然后在等待接收者的响应时阻塞。这样设计活动对象,是为了当它们从这种阻塞状态返回时,具有进入被调用代码的单一入口点,这简化了它们的实现。

7.套接字是Symbian操作系统使用的基本通信模型。它是两个端点之间抽象的通信管道。Symbian使用套接字的概念在客户端和服务器端之间,线程到设备之间以及线程之间进行通信。

8.Symbian操作系统中广泛使用了信号量和互斥量的一些形式。这些为进程和线程提供同步能力。

9.Symbian签名系统代替用户来对软件进行完整性验证,并且该验证必须被执行。Symbian操作系统识别开发人员的特殊签名。一个开发人员必须获得一个有时效限制的证书和一个特殊的智能手机,即可使用自己的数字证书来创建安装包。

第十三章 操作系统设计

1.对于通用的操作系统而言,需要留心4个基本的要素:

①定义抽象概念;

②提供基本操作;

③确保隔离;

④管理硬件。

2.一个操作系统最重要但可能最困难的任务是定义正确的抽象概念。

3.确保每个用户只能在授权的数据上执行授权的操作是系统设计的关键目标。然而,用户还希望共享数据和资源,因此隔离必须是选择性的并且要在用户的控制之下。

4.指导接口设计的原则:简单、完备和能够有效的实现。

5.对精炼的定义是以机制的最少化和清晰度的最大化实现指定的功能。换言之,每一个特性,功能和系统调用都应该尽自己的本分。它应该做意见事情并且把它做好。

6.Unix有一个系统调用exec,用来覆盖一个进程的虚拟地址空间。

7.抽象的目的是隐藏不合需要的特性,而不是隐藏值得需要的特性。

8.任何面相连接的机制与无连接的机制之间的权衡在于建立连接的机制要求的额外开销,以及在后续调用中避免进行连接所带来的好处。

9.除了在后台运行的内核线程以外,大多数操作系统还要启动许多守护进程。虽然这些守护进程不是操作系统的组成部分,但它们通常执行“系统”类型的活动。这些活动包括接收和发送电子邮件,并且对远程用户各种各样的请求进行服务,例如FTP和Web网页。

10.另一个有助于体系结构一致性的原理是机制与策略的分离。

11.独立的组合单独概念的能力称为正交性,它是简单性和完整性原理的直接结果。

12.在Unix中,进程的创建分为两步完成:fork和exec。创建新的地址空间与用新的内存映像装载该地址空间是分开的,这就为在两者之间做一些事情提供了可能。

13.对于用户线程,栈可以初始化成从虚拟地址空间的顶部向下生长,所以大小不需要预先设定。对于内核线程,大小必须预先设定,因为栈占据了某些内核虚拟地址空间并且可能存在许多栈。

14.重入指的是代码同时被执行两次或多次的能力。最好操作系统的大部分为可重入的,关键的数据结构用互斥量来保护,并且在中断不被允许的时刻禁用中断。

15.性能一旦达到一个合理的水平,榨出最后一点百分比的努力和复杂性或许并不值得。避免灾难比获得优化的性能要重要的多。

16.改进性能的一种一般性的方法是权衡时间与空间。

17.双向链表比单向链表占据更多的内存,但是经常使得访问表项速度更快。散列表甚至更浪费空间,但是要更快。

18.用于改进性能的一种众所周知的技术是高速缓存。

19.进程正在有效的使用的页面可以被标记为它的工作集,并且操作系统能够确保党进程被允许运行时,它的工作集在内存中,这样就减少了缺页的次数。

20.对于一个延期的软件项目,增加人力降使它更为延期。

21.顶尖的程序员比拙劣的程序员生产效率要高出10倍。

22.大多数错误不是在代码中,而是在设计中。

23.两三个人编写一个系统与300个人生产一个大型系统是不同的。在后一种情况下,团队结构和项目管理对于项目的成败起着至关重要的作用。

#