2.2  操作系统

　　操作系统是用户和计算机的接口。笔试当中，操作系统方面的试题也占很大比例。进程与线程、虚拟内存和Shell命令是操作系统中的三大考查热点。

　　2.2.1  进程与线程

　　考点：

　　·线程与进程的概念、通信方式

　　·进程同步机制、死锁

　　·多线程优缺点

　　进程是一个程序在其自身的地址空间中的一次运行活动，是资源申请、调度和独立运行的单位。

　　线程是进程中单一的连续控制流程，一个进程可以拥有多个线程。线程调度有两种方式—抢占式（如Windows NT、UNIX、OS/2中）和非抢占式（如DOS、Windows 3.x中）。

　　进程和线程的区别在于，线程没有独立的存储空间，而和所属进程中的其他线程共享一个存储空间。

　　线程有5个状态—新建、就绪、运行、阻塞、死亡。各个状态之间的转换如图2.11所示。

图2.11  各个状态之间的转换

　　线程间的通信一般用wait()方法、notify()方法和notifyAll()方法，它们都是Object类的方法，每个类都默认拥有。

　　wait()方法可以使调用其线程释放共享资源的锁，然后从运行状态中退出，进入等待队列，直到被再次唤醒。

　　notify()方法可以唤醒等待队列中第一个等待同一共享资源的线程，并使该线程退出等待队列，进入就绪状态。

　　notifyAll()方法可以使所有正在等待队列中等待同一共享资源的线程从等待状态退出，进入就绪状态。此时，优先级最高的那个线程最先运行。

　　Windows系统用文件映射、内存共享、匿名管道、命名管道、邮件槽、剪贴板、动态数据交换、对象连接与嵌入、动态链接库、远程过程调用、NetBIOS通信、套接字通信来进行进程之间的通信。

　　进程互斥是进程之间发生的一种间接性作用，一般是程序不希望发生的，通常的情况是两个或两个以上的进程需要同时访问某个共享变量。我们一般将能够访问共享变量的程序段称为临界区。若两个进程同时进入临界区，就会导致数据的不一致，产生与时间有关的错误。因此，两个进程不能同时进入临界区。解决互斥问题应该遵守互斥和公平两个原则，即任意时刻只允许一个进程处于同一共享变量的临界区，而且不能让任意进程无限期地等待。

　　进程同步是进程之间直接的相互作用，是进程间有意识的行为。

　　进程之间的同步互斥通过信号量、管程、汇合和分布式系统来实现。

　　由于进程之间抢占资源，因此容易形成死锁。死锁是由于两个或多个进程都无法得到相应的锁而造成的所有进程处于等待状态的现象。死锁有如下4个必要条件。

　　（1）互斥使用（资源独占）。一个资源每次只能供一个进程使用。

　　（2）不可强占（不可剥夺）。资源申请者不能强行从资源占有者手中夺取资源，资源只能由占有者自愿释放。

　　（3）请求和保持（部分分配，占有申请）。一个进程在申请新的资源的同时保持对原有资源的占有（只有这样才是动态申请，动态分配）。

　　（4）循环等待。

　　假如存在如下一个进程等待队列。

　　其中P1等待P2占有的资源，P2等待P3占有的资源……Pn等待P1占有的资源，形成一个进程等待环路。

　　死锁的处理策略如下。

　　（1）忽略该问题。

　　（2）检测死锁并且恢复。

　　（3）仔细地对资源进行动态分配，以避免死锁。

　　（4）通过解除死锁的4个必要条件之一来防止死锁产生。

　　多线程有两种实现方法，分别是继承Thread类与实现Runnable接口。通过继承Thread类创建的多个线程虽然运行的是相同的代码，但彼此相互独立，且各自拥有自己的资源，互不干扰。而通过实现Runnable接口可以使多个线程拥有同一资源，所以一般在定义资源对象时实现Runnable接口。相对于扩展Thread类来说，实现Runnable接口具有无可比拟的优势。这种方式不但有利于提高程序的健壮性，使代码能够被多个线程共享，而且代码和数据资源相对独立，从而特别适合多个具有相同代码的线程处理同一资源的情况。这样，线程、代码和数据资源三者有效分离，很好地体现了面向对象程序设计的思想。

　　多线程的优点是提高并发性，提高效率；缺点是数据同步困难，开发调试困难，随意使用多线程会降低效率（过犹不及），不能随意使用多线程。

　　2.2.2  虚拟内存

　　考点：

　　·逻辑地址、物理地址的计算方法

　　·虚拟内存的概念、优点

　　·换页算法

　　当运行一个程序时，程序中有许多东西需要存储，因此需要用到堆、栈及各种功能库。在你写程序时可能都不需要自己控制，因为Linux内核会帮你完成存储的调度，你只需要告诉它你想做什么，内核就会在合适的地方为你分配空间。

　　Linux内核对整个系统中物理内存的管理是通过类型为struct page的数组mem_map进行的。系统中的伙伴系统分配算法最终通过操作这个数组来记录物理内存的分配、回收等操作。

　　本节有如下几个概念需要理解。

　　逻辑地址（logical address）是指由程序产生的与段相关的偏移地址。例如，在C语言中，可以读取指针变量本身的值（&操作），实际上该值就是逻辑地址，它是相对于当前进程中数据段的地址，与绝对物理地址无关。程序员仅需与逻辑地址打交道，而分段和分页机制对于程序员来说是完全“透明”的，仅由系统编程人员涉及。程序员虽然自己可以直接操作内存，但只能在操作系统为其分配的内存段进行操作。

　　线性地址（linear address）是指逻辑地址到物理地址变换之间的中间层。程序代码会产生逻辑地址（或者称为段中的偏移地址），加上相应段的基地址就生成了线性地址。若没有启用分页机制，那么线性地址就是物理地址。

　　物理地址（physical address）是指出现在CPU外部地址总线上的寻址物理内存的地址，是地址变换的最终结果。如果启用了分页机制，那么线性地址会使用页目录和页表中的项变换成物理地址；如果没有启用分页机制，线性地址就直接成为物理地址。

　　虚拟内存（virtual memory）是指计算机呈现出要比实际拥有的内存大得多的内存，因此它允许程序员编译并运行需要的内存比实际系统拥有的内存大得多的程序。这使得许多大型项目能够在具有有限内存资源的系统上实现。

　　虚拟地址到物理地址的转化方法是与体系结构相关的，一般来说有分段、分页两种方式。以现在的x86 CPU为例，它对于分段和分页都是支持的。内存管理单元（Memory Mangement Unit，MMU）负责从虚拟地址到物理地址的转化。逻辑地址是段标识+段内偏移量的形式，MMU通过查询段表，可以把逻辑地址转化为线性地址。如果CPU没有开启分页功能，那么线性地址就是物理地址；如果CPU开启了分页功能，MMU还需要查询页表来将线性地址转化为物理地址，具体过程如下。

　　逻辑地址→段表→线性地址→页表→物理地址

　　不同的逻辑地址可以映射到同一个线性地址，不同的线性地址也可以映射到同一个物理地址，所以它们之间均是多对一的关系。另外，在发生换页以后，同一个线性地址也可能被重新装载到另外一个物理地址上，所以这种多对一的映射关系也会随时间发生变化。

　　在进程运行过程中，如果它访问的页面不在内存中而需要将页面调入内存，但内存没有空闲空间，就从内存中调出一页程序或者数据并放到磁盘的对换区中。应该调用哪个根据换页算法决定。页面的更换频率越低越好。换页算法的类型如下。

　　先进先出（First In First Out，FIFO）：最直观，性能最差，总是淘汰最先进入内存的页面（选择在内存中驻留时间最久的页面予以淘汰）。

　　最近最少使用（Least Recently Used，LRU），给每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当淘汰一个页面时，选择现有页面中t值最大的予以淘汰。其页面访问图与最少使用（Least Frequently Used，LFU）算法完全相同。

　　最佳置换（Optimal Replacement，OPT），性能最好，所选择的被淘汰页在以后永不使用，或者在未来一段时间内不再访问。