操作系统.md

计算机操作系统

一、操作系统

基本特征

1. 并发与并行

并发是指宏观上在一段时间内能同时运行多个程序； 并行则指同一时刻能运行多个指令，并行需要硬件支持，如多流水线、多核处理器或者分布式计算系统。 操作系统通过引入进程和线程，使得程序能够并发运行。

2. 共享

共享是指系统中的资源可以被多个并发进程共同使用。 有两种共享方式：互斥共享和同时共享。 互斥共享的资源称为临界资源，例如打印机等，在同一时刻只允许一个进程访问，需要用同步机制来实现互斥访问。

3. 虚拟

虚拟技术把一个物理实体转换为多个逻辑实体。主要有两种虚拟技术：时分复用技术和空分复用技术。

多个进程能在同一个处理器上并发执行使用了时分复用技术，让每个进程轮流占用处理器，每次只执行一小个时间片并快速切换。 虚拟内存使用了空分复用技术，它将物理内存抽象为地址空间，每个进程都有各自的地址空间。地址空间的页被映射到物理内存，地址空间的页并不需要全部在物理内存中，当使用到一个没有在物理内存的页时，执行页面置换算法，将该页置换到内存中。

4. 异步

异步指进程不是一次性执行完毕，而是走走停停，以不可知的速度向前推进。

进程与线程

1. 进程与线程

进程是资源分配的基本单位。进程控制块 (Process Control Block, PCB) 描述进程的基本信息和运行状态，所谓的创建进程和撤销进程，都是指对 PCB 的操作。

线程是独立调度的基本单位。一个进程中可以有多个线程，它们共享进程资源。

• 进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。

• 线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。

• 系统开销，由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。

• 通信，线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。

2. 进程的状态转换

就绪状态（ready，等待被调度），运行状态（running），阻塞状态（waiting，等待资源）

• 只有就绪态和运行态可以相互转换，其它的都是单向转换。就绪状态的进程通过调度算法从而获得 CPU 时间，转为运行状态；而运行状态的进程，在分配给它的 CPU 时间片用完之后就会转为就绪状态，等待下一次调度。
• 阻塞状态是缺少需要的资源从而由运行状态转换而来，但是该资源不包括 CPU 时间，缺少 CPU 时间会从运行态转换为就绪态。

3. 进程通信

• 共享内存：两个进程同时共享一块内存，然后在这块内存上的数据可以共同修改和读取，达到通信的目的；共享内存是最快的IPC方式；共享内存常与信号量进行配合使用，信号量是一个控制资源访问的标识符，简单来说就是一个计数器，通过信号量能实现锁以及著名的P V操作等，主要是用来实现进程间同步。

• 无名管道：无名管道是半双工的通信方式；并且只能在具有亲缘关系的进程之间使用（亲缘关系是指进程间的父子关系，兄弟关系等），具有亲缘关系的进程在创建时同时拥有一个无名管道的句柄，可以进行读写；无名管道不存在磁盘节点，只存在与内存中用完即销毁。

• 命名管道：命名管道也是半双工的通信方式；可以在不具有亲缘关系的进程间通信；有名管道存在磁盘节点，有对应的FIFO文件，凡是可以访问该路径的文件的进程均可以进行通信。

• 消息队列：消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。

• 套接字：套接字是网络编程的API，通过套接字可以不同的机器间的进程进行通信，常用于客户端进程和服务器进程的通信。

• 信号：信号是Unix系统中使用的最古老的进程间通信的方法之一。操作系统通过信号来通知进程系统中发生了某种预先规定好的事件（一组事件中的一个），它也是用户进程之间通信和同步的一种原始机制。一个键盘中断或者一个错误条件（比如进程试图访问它的虚拟内存中不存在的位置等）都有可能产生一个信号。Shell也使用信号向它的子进程发送作业控制信号。

3. 进程管理

3.1 调度算法

• 批处理系统
• 先来先服务 first-come first-serverd（FCFS）
• 短作业优先 shortest job first（SJF）
• 最短剩余时间优先 shortest remaining time next（SRTN）
• 交互式系统
  • 时间片轮转（FCFS 原则，每个进程分配一个相同长度时间片）
  • 优先级调度
  • 多级反馈队列（多个队列，队列内FCFS，队列间先服务优先级高的队列）
• 实时系统： 要求一个请求在一个确定时间内得到响应

3.2 进程同步

• 临界区

• 同步&互斥

• 信号量（Semaphore）

  信号量是一个整型变量，可以对其执行 down 和 up 操作，也就是常见的 P 和 V 操作。

  • down : 如果信号量大于 0 ，执行 -1 操作；如果信号量等于 0，进程睡眠，等待信号量大于 0；
  • up ：对信号量执行 +1 操作，唤醒睡眠的进程让其完成 down 操作。

  down 和 up 操作需要被设计成原语，不可分割，通常的做法是在执行这些操作的时候屏蔽中断。

  如果信号量的取值只能为 0 或者 1，那么就成为了 互斥量（Mutex） ，0 表示临界区已经加锁，1 表示临界区解锁。

• 管程

  使用信号量机制实现的生产者消费者问题需要客户端代码做很多控制，而管程把控制的代码独立出来，不仅不容易出错，也使得客户端代码调用更容易。

  管程有一个重要特性：在一个时刻只能有一个进程使用管程。进程在无法继续执行的时候不能一直占用管程，否则其它进程永远不能使用管程。管程引入了 条件变量 以及相关的操作：wait() 和 signal() 来实现同步操作。对条件变量执行 wait() 操作会导致调用进程阻塞，把管程让出来给另一个进程持有。signal() 操作用于唤醒被阻塞的进程。

死锁

处理死锁的几种方法

• 鸵鸟策略：不管它，Unix，Linux，Windows都是这么处理的
• 死锁检测与死锁恢复：通过有向图检测是否存在环等方式检测死锁；通过抢占恢复、回滚恢复、杀死进程恢复来解决死锁
• 死锁预防：破坏互斥条件、破坏占有和等待条件、破坏不可抢占条件、破坏环路等待
• 死锁避免：安全状态、银行家算法

内存管理

1. 虚拟内存

操作系统将内存抽象成地址空间。每个程序拥有自己的地址空间，这个地址空间被分割成多个块，每一块称为一页。这些页被映射到物理内存，但不需要映射到连续的物理内存，也不需要所有页都必须在物理内存中。

虚拟内存允许程序不用将地址空间中的每一页都映射到物理内存，也就是说一个程序不需要全部调入内存就可以运行，这使得有限的内存运行大程序成为可能。例如有一台计算机可以产生 16 位地址，那么一个程序的地址空间范围是 0~64K。该计算机只有 32KB 的物理内存，虚拟内存技术允许该计算机运行一个 64K 大小的程序。

2. 分页系统地址映射

内存管理单元（MMU）管理着地址空间和物理内存的转换，其中的页表（Page table）存储着页（程序地址空间）和页框（物理内存空间）的映射表。

一个虚拟地址分成两个部分，一部分存储页面号，一部分存储偏移量。

3. 页面置换算法

在程序运行过程中，如果要访问的页面不在内存中，就发生缺页中断从而将该页调入内存中。此时如果内存已无空闲空间，系统必须从内存中调出一个页面到磁盘对换区中来腾出空间。

页面置换算法和缓存淘汰策略类似，可以将内存看成磁盘的缓存。在缓存系统中，缓存的大小有限，当有新的缓存到达时，需要淘汰一部分已经存在的缓存，这样才有空间存放新的缓存数据。

页面置换算法的主要目标是使页面置换频率最低（也可以说缺页率最低）。

3.1 最佳（OPT）

所选择的被换出的页面将是最长时间内不再被访问，通常可以保证获得最低的缺页率。

3.2 最近最久未被使用（LRU）

LRU 将最近最久未使用的页面换出。

为了实现 LRU，需要在内存中维护一个所有页面的链表。当一个页面被访问时，将这个页面移到链表表头。这样就能保证链表表尾的页面是最近最久未访问的。因为每次访问都需要更新链表，因此这种方式实现的 LRU 代价很高。

3.3 最近未被使用（NRU）

每个页面都有两个状态位：R 与 M，当页面被访问时设置页面的 R=1，当页面被修改时设置 M=1。其中 R 位会定时被清零。

当发生缺页中断时，NRU 算法随机地从类编号最小的非空类中挑选一个页面将它换出。 NRU 优先换出已经被修改的脏页面（R=0，M=1），而不是被频繁使用的干净页面（R=1，M=0）。

3.4 先进先出（FIFO）

3.5 第二次机会算法

基于FIFO进行的修改，当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查最老页面的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。

3.6 时钟

第二次机会算法需要在链表中移动页面，降低了效率。时钟算法使用环形链表将页面连接起来，再使用一个指针指向最老的页面。

4. 分段

分段的做法是把每个表分成段，一个段构成一个独立的地址空间。每个段的长度可以不同，并且可以动态增长。

5. 段页式

程序的地址空间划分成多个拥有独立地址空间的段，每个段上的地址空间划分成大小相同的页。这样既拥有分段系统的共享和保护，又拥有分页系统的虚拟内存功能。

分段与分页的比较：

• 对程序员的透明性：分页透明，但是分段需要程序员显式划分每个段。
• 地址空间的维度：分页是一维地址空间，分段是二维的。
• 大小是否可以改变：页的大小不可变，段的大小可以动态改变。
• 出现的原因：分页主要用于实现虚拟内存，从而获得更大的地址空间；分段主要是为了使程序和数据可以被划分为逻辑上独立的地址空间并且有助于共享和保护。

fork到底复制了父进程的哪些资源？

这个时候要牵扯到两个概念，一个是逻辑地址(虚拟地址)，一个是物理地址。

逻辑地址： cpu所生成的地址。cpu产生的逻辑地址分为:p（页号）它包含在每个页在物理内存中的基址，用来做页表的索引；d（页偏移），同基址相结合，用来确定送入内存设备的物理内存地址。

物理地址：内存单元所看到的地址。 用户程序看不到物理地址。用户只生成逻辑地址。逻辑地址与物理地址呈现一一映射的关系。

fork()会产生一个和父进程完全相同的子进程，一般情况下，子进程会调用exec函数族去执行新的程序，这个时候子进程就会有新的栈，堆，数据段，和代码段。linux系统经过不断发展，从效率的角度出发，创造了一个写时复制技术。linux中引入了“写时复制“技术，也就是只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程。

写时复制

在fork之后exec之前两个进程用的是相同的物理空间（内存区），子进程的代码段、数据段、堆栈都是指向父进程的物理空间，也就是说，两者的虚拟空间不同，但其对应的物理空间是同一个。当父子进程中有更改相应段的行为发生时，再为子进程相应的段分配物理空间，如果不是因为exec，内核会给子进程的数据段、堆栈段分配相应的物理空间（至此两者有各自的进程空间，互不影响），而代码段继续共享父进程的物理空间（两者的代码完全相同）。而如果是因为exec，由于两者执行的代码不同，子进程的代码段也会分配单独的物理空间。

就以上面两个例子分析一下： 第一个例子，子进程访问了num的值而却没有改变num的值，只是相当于读取了一下，这个时候内核不会给子进程分配新的资源，而是接着共享父进程的资源，这个时候num的值还是5，这样就节省了系统调用时候的资源。 第二个例子，子进程在执行过程中改变了num的值，这个时候系统发现了这个操作，就会给子进程分配新（新指物理地址上的新）的栈，堆和数据段，并且将父进程中fork之前的变量拷贝一份（拷贝的值和父进程中的值就没有任何关系了），然后子进程再对这些值进行操作，所以二者虽然用的是相同的变量名，但是在物理地址上已经完全不相同了。

写时复制技术大大降低了进程对资源的浪费。

再看fork函数 当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct结构，区域结构和页表的原本副样。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有写时复制。 当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新的页面，因此，也就为每个进程保持了私有地址的概念。

二、Linux

• 能简单使用 cat，grep，cut 等命令进行一些操作；
• 文件系统相关的原理，inode 和 block 等概念，数据恢复；
• 硬链接与软链接；
• 进程管理相关，僵尸进程与孤儿进程，SIGCHLD 。

包管理工具

RPM 和 DPKG 为最常见的两类软件包管理工具：

• RPM 全称为 Redhat Package Manager，最早由 Red Hat 公司制定实施，随后被 GNU 开源操作系统接受并成为许多 Linux 系统的既定软件标准。YUM 基于 RPM，具有依赖管理和软件升级功能。
• 与 RPM 竞争的是基于 Debian 操作系统的 DEB 软件包管理工具 DPKG，全称为 Debian Package，功能方面与 RPM 相似。

权限

可以将一组权限用数字来表示，此时一组权限的 3 个位当做二进制数字的位，从左到右每个位的权值为 4、2、1，即每个权限对应的数字权值为 r : 4、w : 2、x : 1。

 chmod [-R] xyz dirname/filename 
 chmod [ugoa]  [+-=] [rwx] dirname/filename
- u：拥有者
- g：所属群组
- o：其他人
- a：所有人
- +：添加权限
- -：移除权限
- =：设定权限

默认权限

• 文件默认权限：文件默认没有可执行权限，因此为 666，也就是 -rw-rw-rw- 。
• 目录默认权限：目录必须要能够进入，也就是必须拥有可执行权限，因此为 777 ，也就是 drwxrwxrwx。

链接

ln [-sf] source_filename dist_filename
-s ：默认是实体链接，加 -s 为符号链接
-f ：如果目标文件存在时，先删除目标文件

实体链接

在目录下创建一个条目，记录着文件名与 inode 编号，这个 inode 就是源文件的 inode。删除任意一个条目，文件还是存在，只要引用数量不为 0。 有以下限制：不能跨越文件系统、不能对目录进行链接。

符号链接

符号链接文件保存着源文件所在的绝对路径，在读取时会定位到源文件上，可以理解为 Windows 的快捷方式。当源文件被删除了，链接文件就打不开了。 因为记录的是路径，所以可以为目录建立符号链接。

进程管理

ps

查看某个时间点的进程信息。

# ps -l
# ps aux 查看系统所有进程
# ps aux | grep threadx  查看特定进程
# ps -ef | grep name

pstree

查看进程树。

示例：查看所有进程树

# pstree -A

top

实时显示进程信息。

示例：两秒钟刷新一次

# top -d 2

netstat

查看占用端口的进程

# netstat -anp | grep port

状态	说明
R	running or runnable (on run queue) 正在执行或者可执行，此时进程位于执行队列中。
D	uninterruptible sleep (usually I/O) 不可中断阻塞，通常为 IO 阻塞。
S	interruptible sleep (waiting for an event to complete) 可中断阻塞，此时进程正在等待某个事件完成。
Z	zombie (terminated but not reaped by its parent) 僵死，进程已经终止但是尚未被其父进程获取信息。
T	stopped (either by a job control signal or because it is being traced) 结束，进程既可以被作业控制信号结束，也可能是正在被追踪。

孤儿进程

一个父进程退出，而它的一个或多个子进程还在运行，那么这些子进程将成为孤儿进程。

孤儿进程将被 init 进程（进程号为 1）所收养，并由 init 进程对它们完成状态收集工作。

由于孤儿进程会被 init 进程收养，所以孤儿进程不会对系统造成危害。

僵尸进程

一个子进程的进程描述符在子进程退出时不会释放，只有当父进程通过 wait() 或 waitpid() 获取了子进程信息后才会释放。如果子进程退出，而父进程并没有调用 wait() 或 waitpid()，那么子进程的进程描述符仍然保存在系统中，这种进程称之为僵尸进程。

僵尸进程通过 ps 命令显示出来的状态为 Z（zombie）。

系统所能使用的进程号是有限的，如果产生大量僵尸进程，将因为没有可用的进程号而导致系统不能产生新的进程。

要消灭系统中大量的僵尸进程，只需要将其父进程杀死，此时僵尸进程就会变成孤儿进程，从而被 init 进程所收养，这样 init 进程就会释放所有的僵尸进程所占有的资源，从而结束僵尸进程。

三、计算机组成原理

寻址方式

立即寻址

指令直接获得操作数，无需访问存储器。

直接寻址

给出操作数在主存的地址，寻找操作数简单，无需计算操作数地址。

间接寻址

指令地址码给出的是操作数地址的地址，需要访问一次或多次主存来获取操作数。

计算机的控制器

指令寄存器、主存地址寄存器、主存数据寄存器、通用寄存器

计算机的运算器

数据缓冲器：输入缓冲、输出缓冲

ALU：算术逻辑单元

状态字寄存器

通用寄存器