Linux_OS.md

Linux、OS 知识

常用命令

系统

• uname -a # 查看内核/操作系统/CPU信息
• hostname # 查看计算机名
• env # 查看环境变量
• uptime # 查看系统运行时间、用户数、负载

资源

• free # 查看内存使用量和交换区使用量
• df -h # 查看各分区使用情况
• top # 实时显示进程状态
• ps # 系统中当前运行的那些进程
• ipcs # 进程间通信

网络

• ifconfig # 查看所有网络接口的属性
• iptables -L # 查看防火墙设置
• route -n # 查看路由表
• netstat -s # 查看网络统计信息
• ss # netstat 的替代
• tcpdump # 用来抓包

任务

• ctrl + z # 可以将一个正在前台执行的命令放到后台，并且暂停
• jobs # 查看当前有多少在后台运行的命令
• fg %jobnumber # 将后台中的命令调至前台继续运行（%jobnumber是通过jobs命令查到的后台正在执行的命令的序号(不是pid)）
• bg %jobnumber # 将一个在后台暂停的命令，变成继续执行。

netstat：用来显示相关的网络信息，如接口/网卡状态(-i)，路由表(-r)，网络连接(-a)，tcp相关选项(-t)，udp相关选项(-u)，按各个协议统计(-s)。

top：在系统维护的过程中，随时可能有需要查看 CPU 使用率，并根据相应信息分析系统状况的需要。运行 top 命令后，CPU 使用状态会以全屏的方式显示，并且会处在对话的模式，此时用基于 top 的命令，可以控制显示方式。退出 top 的命令为 q。

ipcs：Linux下显示进程间通信设施状态的工具。可以显示消息队列、共享内存和信号量的信息。

参考
工具参考篇

进程与线程

并发和并行的区别就是一个处理器同时处理多个任务和多个处理器或者是多核的处理器同时处理多个不同的任务。前者是逻辑上的同时发生，而后者是物理上的同时发生．

• 并发(concurrent)：指能处理多个同时性活动的能力，并发事件之间不一定要同一时刻发生。
• 并行(parallel)：指同时发生的两个并发事件，具有并发的含义，而并发则不一定并行。

［fork 输出个数］
［进程和线程描述］
［线程共享的资源］
［线程并发脏数据］
［进程轮询调度周转时间］

守护进程

守护进程，也即通常所说的 Daemon 进程，是 Linux 下一种特殊的后台服务进程，它独立于控制终端并且周期性的执行某种任务或者等待处理某些发生的事件。守护进程通常在系统引导装入时启动，在系统关闭时终止。Linux 系统下大多数服务都是通过守护进程实现的，守护进程的名称通常以 d 结尾，如 httpd、crond、mysqld等。

守护进程首要的特性是后台运行；其次，要与从启动它的父进程的运行环境隔离开来，需要处理的内容大致包括会话、控制终端、进程组、文件描述符、文件权限掩码以及工作目录等。

守护进程可以在 Linux 启动时从脚本 /etc/rc.d 启动，也可以由作业规划进程 crond 启动，还可以通过用户终端（一般是 Shell）启动。实现一个守护进程，其实就是将普通进程按照上述特性改造为守护进程的过程。

从终端 Shell 启动守护进程的步骤如下：

1. 创建子进程，父进程退出
2. 子进程创建新会话
3. 改变当前工作目录
4. 重设文件权限掩码
5. 关闭文件描述符

守护进程的详细内容参见 Linux_OS_Daemon.md.

僵尸、孤儿进程

子进程先于父进程结束，而且父进程没有函数调用 wait() 或 waitpid() 等待子进程结束，也没有注册 SIGCHLD 信号处理函数，结果使得子进程的进程列表信息无法回收，这样子进程就变成了僵尸进程（Zombie）。

所以简单来说一个已经终止，但是其父进程尚未对其进行善后处理（终止子进程的有关信息）的进程被称为僵尸进程。

UNIX 提供了一种机制可以保证只要父进程想知道子进程结束时的状态信息，就可以得到。这种机制就是: 在每个进程(init除外)退出的时候，内核释放该进程所有的资源，包括打开的文件，占用的内存等。但是仍然为其保留一定的信息（包括进程号PID，退出状态，运行时间等)，直到父进程通过wait/waitpid 来取时才释放。

如果父进程不调用wait/waitpid的话，那么保留的那段信息就不会释放，其进程号就会一直被占用（这时用ps命令就能看到子进程的状态是“Z”），但是系统所能使用的进程号是有限的，如果大量的产生僵死进程，将因为没有可用的进程号而导致系统不能产生新的进程。此即为僵尸进程的危害，应当避免。

注意如果父进程先于子进程结束，这时的子进程应该称作孤儿进程（Orphan）。每当出现一个孤儿进程的时候，内核就把孤儿进程的父进程设置为init，而init进程会循环地调用wait()。这样，当一个孤儿进程结束其生命周期后，init进程就会进行善后工作。因此孤儿进程并不会有什么危害。

参考： 孤儿进程与僵尸进程

死锁以及避免死锁的策略

死锁的规范定义如下：如果一个进程集合中的每个进程都在等待只能由该进程集合中其他进程才能引发的事件，那么该进程集合就是死锁的。

产生死锁的原因主要是：

• 因为系统资源不足。
• 进程运行推进的顺序不合适。
• 资源分配不当等。

产生死锁的四个必要条件：

1. 互斥条件：每个资源要么已经分配给了一个进程，要么就是可用的。
2. 占有和等待条件：已经得到了某个资源的进程可以再请求新的资源。
3. 不可抢占条件：已经分配给一个进程的资源不能强制性地被抢占，只能被占有它的进程显式地释放；
4. 环路等待条件：死锁发生时，系统中一定有两个或者两个以上的进程组成的一条环路，该环路中的每个进程都在等待着下一个进程所占有的资源。

这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之一不满足，就不会发生死锁。

四种处理死锁的策略：

1. 鸵鸟策略（忽略死锁）；
2. 检测死锁并恢复；
3. 仔细对资源进行分配，动态地避免死锁；
4. 通过破坏引起死锁的四个必要条件之一，防止死锁的产生。

避免死锁的主要算法是基于一个安全状态的概念。在任何时刻，如果没有死锁发生，并且即使所有进程忽然请求对资源的最大请求，也仍然存在某种调度次序能够使得每一个进程运行完毕，则称该状态是安全的。从安全状态出发，系统能够保证所有进程都能完成，而从不安全状态出发，就没有这样的保证。

银行家算法：判断对请求的满足是否会进入不安全状态，如果是，就拒绝请求，如果满足请求后系统仍然是安全的，就予以分配。不安全状态不一定引起死锁，因为客户不一定需要其最大贷款额度。

［死锁产生必要条件］
［资源一定，进程最多申请多少资源］

存储管理

对任何一个普通进程来讲，它都会涉及到5种不同的数据段。

1. 代码段：代码段是用来存放可执行文件的操作指令，也就是说是它是可执行程序在内存中的镜像。代码段需要防止在运行时被非法修改，所以只准许读取操作，而不允许写入（修改）操作——它是不可写的。
2. 数据段：数据段用来存放可执行文件中已初始化全局变量，换句话说就是存放程序静态分配的变量和全局变量。
3. BSS段：BSS段包含了程序中未初始化的全局变量，在内存中 bss段全部置零。
4. 堆（heap）：堆是用于存放进程运行中被动态分配的内存段，它的大小并不固定，可动态扩张或缩减。当进程调用malloc等函数分配内存时，新分配的内存就被动态添加到堆上（堆被扩张）；当利用free等函数释放内存时，被释放的内存从堆中被剔除（堆被缩减）
5. 栈：栈是用户存放程序临时创建的局部变量，也就是说我们函数括弧“{}”中定义的变量（但不包括static声明的变量，static意味着在数据段中存放变量）。除此以外，在函数被调用时，其参数也会被压入发起调用的进程栈中，并且待到调用结束后，函数的返回值也会被存放回栈中。由于栈的先进先出特点，所以栈特别方便用来保存/恢复调用现场。从这个意义上讲，我们可以把堆栈看成一个寄存、交换临时数据的内存区。

参考：Linux内存管理

页面置换算法

常见的页面调度算法：

1. 随机算法rand（Random Algorithm）

   利用软件或硬件的随机数发生器来确定主存储器中被替换的页面。这种算法最简单，而且容易实现。但是，这种算法完全没用利用主存储器中页面调度情况的历史信息，也没有反映程序的局部性，所以命中率较低。

2. 先进先出调度算法（FIFO）

   先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。它的优点是比较容易实现，能够利用主存储器中页面调度情况的历史信息，但是，它没有反映程序的局部性，因为最先调入主存的页面，很可能也是经常要使用的页面。

3. 最近最少使用算法LRU（Least Recently Used Algorithm）

   根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少使用在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。

4. 最近最不频繁使用算法 LFU（Least Frequently Used Algorithm ）

   由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。

［LRU 缺页次数］
［缺页率计算］
［缺页替换影响效率］

主存、辅存、虚拟存储

概括的说，CPU对所需要的数据进行计算时，要求很高的存储速度，且不需要能永久保存这些数据，高速存储设备的成本很高。但其他设备对存储速度的要求不像CPU这么高，一般要求永久保存数据。一般低速的存储设备就可以满足，且低速的存储成本也低。

所以有主存和辅存之分：

• 内存（主存）直接给CPU提供存储，高速，低容量，价格贵，不能永久保存数据，断电消失，需要从辅存中重新调入数据。
• 外存（辅存）给主存提供数据，低速，大容量，价格低，能永久保存数据。

所以更高缓存的CPU和更大的内存能够大大提升系统的性能。

• 常见主存有：CPU的高速缓存，电脑的内存条。
• 常见辅存有：硬盘、光盘、U盘、磁盘、移动硬盘等等。

虚拟存储：根据程序执行的互斥性和局部性两个特点，允许作业装入的时候只装入一部分，另一部分放在磁盘上，当需要的时候再装入到主存，这样以来，在一个小的主存空间就可以运行一个比它大的作业。同时，用户编程的时候也摆脱了一定要编写小于主存容量的作业的限制。也就是说，用户的逻辑地址空间可以比主存的绝对地址空间要大。对用户来说，好像计算机系统具有一个容量很大的主存储器，称为“虚拟存储器”。

虚拟存储（Storage Virtualization）是指将多个不同类型、独立存在的物理存储体，通过软、硬件技术，集成转化为一个逻辑上的虚拟的存储单元，集中管理供用户统一使用。这个虚拟逻辑存储单元的存储容量是它所集中管理的各物理存储体的存储量的总和，而它具有的访问带宽则在一定程度上接近各个物理存储体的访问带宽之和。

［虚拟存储的目的］

内存存储模式

存储模型可以分为六种方式：

1. 单一连续区：一段时间内只能有一个进程在内存中，因此内存利用率低；
2. 固定分区：把内存空间分割成若干区域，成为分区，每个分区装载一个且只能有进程；
3. 可变分区：根据进程的需要，把内存空间分割出一个分区，分配给进程，剩余的部分成为新的空闲区。缺点：产生外部碎片，内存利用率低。
4. 页式存储：用户程序的地址空间被划分成若干固定大小的区域，称为“页”；相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。分页方式的优点是页长固定，因而便于构造页表、易于管理，且不存在外碎片。但分页方式的缺点是页长与程序的逻辑大小不相关。
5. 段式存储：将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。
6. 段页式存储：段页式存储组织是分段式和分页式结合的存储组织方法，这样可充分利用分段管理和分页管理的优点。用分段方法来分配和管理虚拟存储器。程序的地址空间按逻辑单位分成基本独立的段，而每一段有自己的段名，再把每段分成固定大小的若干页。用分页方法来分配和管理实存。即把整个主存分成与上述页大小相等的存储块，可装入作业的任何一页。程序对内存的调入或调出是按页进行的。

更多内容参见 Linux_OS_MemoryManage.md

［页表辅存始地址］

Linux 的任务调度机制是什么？

作业调度设备利用率

系统如何将信号通知到进程？

标准库函数与系统调用的区别

共享内存的实现原理（共享内存段被映射进进程空间之后，存在于进程空间的什么位置？共享内存段最大限制是多少？）

经典布局 和 灵活布局

可执行的链接格式 ELF

内存泄露检测

内存泄漏指由于疏忽或错误造成程序未能释放已经不再使用的内存的情况。内存泄漏并非指内存在物理上的消失，而是应用程序分配某段内存后，由于设计错误，导致在释放该段内存之前就失去了对该段内存的控制，从而造成了内存的浪费。

最难捉摸也最难检测到的错误之一是内存泄漏，即未能正确释放以前分配的内存的 bug。只发生一次的小的内存泄漏可能不会被注意，但泄漏大量内存的程序或泄漏日益增多的程序可能会表现出各种征兆：从性能不良（并且逐渐降低）到内存完全用尽。更糟的是，泄漏的程序可能会用掉太多内存，以致另一个程序失败，而使用户无从查找问题的真正根源。

内存泄漏的原因可以概括为：调用了malloc/new等内存申请的操作，但缺少了对应的free/delete，总之就是，malloc/new比free/delete的数量多。实际项目中检测内存泄漏通常会十分繁琐，所以有许多工具帮助我们检测内存泄漏，比如 mtrace，valgrind。

详细内容参见 Linux_OS_MemoryLeaks.md

参考：
C/C++内存泄漏及检测

Linux IO 模式

select，poll，epoll都是IO多路复用的机制。I/O多路复用就通过一种机制，实现单进程可以监视多个描述符，一旦某个描述符就绪（一般是读就绪或者写就绪），能够通知程序进行相应的读写操作。select，poll，epoll本质上都是同步I/O，因为他们都需要在读写事件就绪后自己负责进行读写，也就是说这个读写过程是阻塞的（异步I/O则无需自己负责进行读写，异步I/O的实现会负责把数据从内核拷贝到用户空间）。

［epoll和select］

更多内容参见： Linux_OS_IO_Multiplexing.md

文件系统

更多内容参见 Linux_OS_FileSystem.md

［文件软链接描述］
［磁盘存储优化］

两级缓存机制

为了兼顾速度和容量的问题，一般采用两级Cache结构，第一级Cache小而快，第二辑Cache容量大。

平均的访问时间=命中时间(L1)+失效率(L1)*失效开销(L1)
            =命中时间(L1)+失效率(L1)*((命中时间(L2)+失效率(L2)*失效开销(L2))

［两级缓存访问开销］            

RAID 工作模式

1. RAID 0：无差错控制的带区组

   要实现RAID0必须要有两个以上硬盘驱动器，RAID0实现了带区组，数据并不是保存在一个硬盘上，而是分成数据块保存在不同驱动器上。在所有的级别中，RAID 0的速度是最快的。但是RAID 0没有冗余功能的，如果一个磁盘(物理)损坏，则所有的数据都无法使用。

2. RAID 1：镜像结构

   当主硬盘损坏时，镜像硬盘就可以代替主硬盘工作。镜像硬盘相当于一个备份盘，可想而知，这种硬盘模式的安全性是非常高的，RAID 1的数据安全性在所有的RAID级别上来说是最好的。但是其磁盘的利用率却只有50%，是所有RAID级别中最低的。

3. RAID5：分布式奇偶校验的独立磁盘结构

   RAID5最大的好处是在一块盘掉线的情况下，RAID照常工作，相对于RAID0必须每一块盘都正常才可以正常工作的状况容错性能好多了。因此 RAID5是RAID级别中最常见的一个类型。RAID5校验位即P位是通过其它条带数据做异或(xor)求得的。计算公式为 P=D0xorD1xorD2…xorDn，其中p代表校验块，Dn代表相应的数据块，xor是数学运算符号异或。

4. RAID10：高可靠性与高效磁盘结构

   RAID 10是先镜像再分区数据。是将所有硬盘分为两组，视为是RAID 0的最低组合，然后将这两组各自视为RAID 1运作。RAID 10有着不错的读取速度，而且拥有比RAID 0更高的数据保护性。

参考： RAID 工作模式

linux core文件

在一个程序崩溃时，它一般会在当前工作目录（或者指定目录）下生成一个core文件。core文件仅仅是一个内存映象(同时加上调试信息)，主要是用来调试的。

下面的命令可以检查生成core文件的选项是否打开:

$ ulimit -a
-c: core file size (blocks)         0

注意core file size是0，程序出错时不会产生core文件。可以用以下命令来允许系统生成core文件，并设定core文件最大大小:

$ulimit -c 1024

使用gdb来查看core文件，可以指示出导致程序出错的代码所在文件和行数。

参考： Linux生成core文件、core文件路径设置

［对应题目］

一个由C/C++编译的程序占用的内存分为以下几个部分：

• 栈区（stack）：由编译器自动分配释放，存放函数的参数值，局部变变量的值等，其操作方式类似于数据结构中的栈，可静态亦可动态分配。栈从高地址到低地址分配
• 堆区（heap）：一般由程序员分配释放（new/delete, malloc/free），若程序员不释放，可能造成内存泄漏，程序结束时可能由OS回收。只可动态分配，分配方式类似于链表。堆从低地址到高地址分配
• 全局区（静态区）：存放全局变量、静态数据，程序结束后由系统释放。
• 常量存储区：特殊的存储区，存放常量，不允许修改。
• 程序代码区：存放函数体（类成员函数和全局函数）的二进制代码。

C++ 线程安全

线程安全就是多线程访问时，采用了加锁机制，当一个线程访问某个数据时，进行保护，其他线程不能进行访问直到该线程访问完毕，其他线程才可使用。不会出现数据不一致或者数据污染。线程不安全就是不提供数据访问保护，有可能出现多个线程先后更改数据造成所得到的数据是脏数据

线程安全问题都是由全局变量或者静态变量引起的。若每个线程中对全局变量、静态变量只有读操作，而无写操作，一般来说是线程安全的；若有多个线程同时执行写操作，一般都需要考虑线程同步，否则的话就可能影响线程安全。

C++ 中 volatile 关键字不能保证全局变量多线程安全，因为 volatile 仅仅是告诫compiler 不要对这个变量作优化，每次都要从 memory 取数值，而不是从register。

POSIX线程标准要求C标准库中的大多数函数具备线程安全性。C++标准库里面的string保证不是线程安全的。

［对应题目］

参考：
线程安全和线程不安全理解

Linux 用户权限管理

［新建管理员用户］

awk 与 sed

计算机组成原理

Linux 启动流程

每个平台的启动细节不同，但整体来说启动过程如下。

首先 BIOS 加电自检，对硬件（内存，CPU，主板等）进行检测（POST: Power-On Self-Test）和初始化，因为操作系统的启动过程中可能会依赖于磁盘访问、屏幕、键盘等。（上个世纪70年代初，"只读内存"（read-only memory，缩写为ROM）发明，开机程序被刷入ROM芯片，计算机通电后，第一件事就是读取它。这块芯片里的程序叫做"基本输入输出系统"（Basic Input/Output System），简称为BIOS）

接下来BIOS按照"启动顺序"，把控制权转交给排在第一位的储存设备，读取该设备的第一个扇区（最前面的512个字节），即主引导记录（MBR）。主引导记录的主要作用是，告诉计算机到硬盘的哪一个位置去找操作系统。

主引导记录由三个部分组成：

1. 第1-446字节：调用操作系统的机器码（boot）。
2. 第447-510字节：分区表（Partition table）。
3. 第511-512字节：主引导记录签名（0x55和0xAA）。

MBR 中的 Boot Loader 程序被读入内存（0x7C00）后，首先将自身复制到高地址的内存（0x9000）当中从而为操作系统释放低地址的内存。Boot Loader 读取启动设备的根目录（这个工作通常由引导程序，如GRUB完成），读入操作系统，并把控制权交给内核。

内核的开始代码是用汇编语言写的，具有较高的机器依赖性。系统首先进行自动配置，一旦所有硬件配置完毕，就运行进程0，建立它的堆栈，运行它。进程0继续进行初始化：配置实时时钟，挂载根文件系统，创建 init 进程（进程1）和页面守护进程（进程2）。

然后，init线程加载系统的各个模块，比如窗口程序和网络程序，直至执行/bin/login程序，跳出登录界面，等待用户输入用户名和密码。

参考
计算机是如何启动的？
Linux 的启动流程

数值的存储

正数的原码、反码、补码形式一致，负数的反码为原码的数值位取反，补码为反码+1也即是原码的数值位取反再+1，计算机中以补码表示数据和运算，而32位最小负整数的补码为 1000 0000 0000 0000 0000 0000 0000 0000。

对一个数值执行单目运算符 - 表示的是对该数取反然后再+1，也即是我们常说的求补运算，注意这里取反+1与原码求补码的区别！也就是求补运算与求补码是不一样的！

例子（4位有符号整数）：x=-4 1100（补码） -x=~x+1 也即是 0011+0001=0100（4），而1100再求补码应是先数值位取反，即1011，然后+1，变成1100！注意这两者（求补与求补码）之间的区别。

［－2^31 -1 的各种计算］
［unsigned 取值］

参考：
你不知道的按位运算

分布式系统

分布式领域CAP理论：

• Consistency(一致性)，数据一致更新，所有数据变动都是同步的
• Availability(可用性)，好的响应性能
• Partition tolerance(分区容错性)：可靠性

定理：任何分布式系统只可同时满足二点，没法三者兼顾。 忠告：架构师不要将精力浪费在如何设计能满足三者的完美分布式 系统，而是应该进行取舍。

［分布式系统三个指标］

用户态，内核态

用户态切换到内核态的 3 种方式

• 系统调用
• 异常
• 外围设备的中断

作业调度

周转时间 = 作业完成时间-作业提交时间 响应比 =（作业等待时间+作业执行时间）/作业执行时间

响应比高者优先调度