操作系统知识点总结

1.进程与线程

• 对于有线程系统：
  • 进程是资源分配的独立单位
  • 线程是资源调度的独立单位
• 对无无线程系统：
  • 进程是资源调度、分配的独立单位

2.进程间的通信方式及优缺点

• 管道
  • 有名管道：一种半双工的通信方式，它允许无亲缘关系进程间的通信。
    • 优点：可以实现任意关系的进程间的通信
    • 缺点：
      • a.长期存于系统中，使用不当容易出错
      • b.缓冲区有限
  • 无名管道：一种半双工的通信方式，只能在具有亲缘关系的进程间使用（父子进程）
    • 优点：简单方便
    • 缺点：
      • a.局限于单向通信
      • b.只能创建在它的进程以及其有亲缘关系的进程之间
      • c.缓冲区有限
• 信号量：一个计数器，可以用来控制多个线程对共享资源的访问
  • 优点：可以同步进程
  • 缺点：信号量有限
• 信号: 一种比较复杂的通信方式，用于通知接收进程某个事件已经发生
• 消息队列: 是消息的链表，存放在内核中并由消息队列标识符标识
  • 优点： 可以实现任意进程间的通信，并通过系统调用函数来实现消息发送和接收之间的同步，无需考虑同步问题，方便
  • 缺点：信息的复制需要额外消耗 CPU 的时间，不适宜于信息量大或操作频繁的场合
• 共享内存：映射一段能被其他进程所访问的内存，这段共享内存由一个进程创建，但多个进程都可以访问
  • 优点：无须复制，快捷，信息量大
  • 缺点：
    • a.通信是通过将共享空间缓冲区直接附加到进程的虚拟地址空间中来实现的，因此进程间的读写操作的同步问题
    • b.利用内存缓冲区直接交换信息，内存的实体存在于计算机中，只能同一个计算机系统中的诸多进程共享，不方便网络通信
• 套接字：可用于不同及其间的进程通信
  • 优点：
    • a.传输数据为字节级，传输数据可自定义，数据量小效率高
    • b.传输数据时间短，性能高
    • c.适合于客户端和服务器端之间信息实时交互
    • d.可以加密,数据安全性强
  • 缺点：需对传输的数据进行解析，转化成应用级的数据。

3.线程之间的通信方式

• 锁机制：包括互斥锁/量（mutex）、读写锁（reader-writer lock）、自旋锁（spin lock）、条件变量（condition）
  • 互斥锁/量（mutex）：提供了以排他方式防止数据结构被并发修改的方法。
  • 读写锁（reader-writer lock）：允许多个线程同时读共享数据，而对写操作是互斥的。
  • 自旋锁（spin lock）：与互斥锁类似，都是为了保护共享资源。互斥锁是当资源被占用，申请者进入睡眠状态；而自旋锁则循环检测保持者是否已经释放锁。
  • 条件变量（condition）：可以以原子的方式阻塞进程，直到某个特定条件为真为止。对条件的测试是在互斥锁的保护下进行的。条件变量始终与互斥锁一起使用。
• 信号量机制
  • 无名线程信号量
  • 有名线程信号量
• 信号机制(Signal)：类似进程间的信号处理
• 屏障：屏障允许每个线程等待，直到所有的合作线程都达到某一点，然后从该点继续执行。

4.进程之间私有和共享的资源

• 私有：地址空间、堆、全局变量、栈、寄存器
• 共享：代码段，公共数据，进程目录，进程 ID

5.线程之间私有和共享的资源

• 私有：线程栈，寄存器，程序寄存器
• 共享：堆，地址空间，全局变量，静态变量

6.多进程与多线程间的对比、优劣与选择

• 线程与进程选用规则：
  • 需要频繁创建销毁的优先用线程
  • 需要进行大量计算的优先使用线程
  • 强相关的处理用线程，弱相关的处理用进程
  • 可能要扩展到多机分布的用进程，多核分布的用线程
  • 都满足需求的情况下，用你最熟悉、最拿手的方式

7.Linux的内核同步方式

• 为什么需要内核同步？：在现代操作系统里，同一时间可能有多个内核执行流在执行，因此内核其实像多进程、多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问。尤其是在多处理器系统上，更需要一些同步机制来同步不同处理器上的执行单元对共享的数据的访问。
• 内核同步方式:
  • 原子操作
  • 信号量（semaphore）
  • 读写信号量（rw_semaphore）
  • 自旋锁（spinlock）
  • 大内核锁（BKL，Big Kernel Lock）
  • 读写锁（rwlock）
  • 大读者锁（brlock-Big Reader Lock）
  • 读-拷贝修改(RCU，Read-Copy Update)
  • 顺序锁（seqlock）

8.死锁

• 定义：是指两个或两个以上进程在执行过程中，因争夺资源而造成的下相互等待的现象。
• 死锁产生的条件：
  • 互斥
  • 请求和保持
  • 不可剥夺
  • 环路等待
• 预防死锁：
  • 打破互斥条件：改造独占性资源为虚拟资源，大部分资源已无法改造。
  • 打破不可抢占条件：当一进程占有一独占性资源后又申请一独占性资源而无法满足，则退出原占有的资源。
  • 打破占有且申请条件：采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然就等待，这样就不会占有且申请。
  • 打破循环等待条件：实现资源有序分配策略，对所有设备实现分类编号，所有进程只能采用按序号递增的形式申请资源。
  • 有序资源分配法
  • 银行家算法

9.页面置换算法

• 页面置换：在地址映射过程中，如果在页面中发现所要访问的页面不存在于内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

• 分类：

  • 全局置换：在整个内存空间置换
    • 工作集算法
    • 缺失率置换算法

  • 局部置换：在本进程中进行置换

    • 最佳置换算法(OPT)
      • 原理：从主存中移出永远不再需要的页面；如无这样的页面存在，则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。 详见原理

    • 先进先出置换算法(FIFO)

      • 原理：该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。详见原理

    • 最近最久未使用算法(LRU)

      • 原理：根据页面调入内存后的使用情况做出决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t。当需要淘汰一个页面时，选择现有也面中t值最大的，即最近最久未使用的页面予以淘汰。详见原理
    • 时钟置换算法(Clock)
      • 原理：淘汰访问位为0的页框中的页面，被访问过的页面将其页框的访问位数值置1。详见原理
  • 局部置换的三种算法C++代码

    #include<iostream>
    using namespace std;
    int page[] = { 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1,-1 };
    
    void FIFO();
    void OPT();
    void RLU();
    bool inArray(int* a, int n, int p);
    int main(void) {
        FIFO();
        OPT();
        RLU();
        system("pause");
    }
    // FIFO算法
    void FIFO() {
        int temp[3] = { -1,-1,-1 };
        int time[3] = { 0,0,0 };
        int num = 0;
        int error = 0;
        cout << "FIFO:" << endl;
        while (page[num] != -1) {
            if (inArray(temp, 3, page[num])) {
                std::cout << page[num] << ',';
                std::cout << endl;
            }
            else {
                error++;
                bool hasChanged = false;
                for (int i = 0; i < 3; i++) {
                    if (time[i] == 0 && hasChanged == false) {
                        time[i] = 2;
                        temp[i] = page[num];
                        hasChanged = true;
                    }
                    if (time[i] != 0) {
                        time[i]--;
                    }
                }
                std::cout << page[num] << ',' << ' ';
                for (size_t i = 0; i < 3; i++) {
                    if (temp[i] == -1) {
                        std::cout << '*' << ' ';
                    }
                    else {
                        std::cout << temp[i] << ' ';
                    }
                }
                std::cout << endl;
            }
            num++;
        }
        cout << "错误率:" << error << endl;
    }
    bool inArray(int* a, int n, int p) {
        for (int i = 0; i < n; i++) {
            if (p == a[i]) {
                return true;
            }
        }
        return false;
    }
    // OPT算法
    void OPT() {
        int temp[3] = { -1,-1,-1 };
        int num = 0;
        int error = 0;
        //OPT已知未来的页数为20
        cout << "OPT:" << endl;
        while (page[num] != -1) {
            int a = page[num];
            if (inArray(temp, 3, page[num])) {
                std::cout << page[num] << ',';
                std::cout << endl;
            }
            else {
                error++;
                bool fuck = false;
                for (size_t i = 0; i < 3; i++){
                    if (temp[i] == -1) {
                        temp[i] = page[num];
                        fuck = true;
                        break;
                    }
                }
    
                if (fuck == false) {
                    int distance[3] = { 20,20,20 };
                    for (int i = 19; i >= num; i--) {
                        for (int j = 0; j < 3; j++) {
                            if (temp[j] == page[i] && (i - num) < distance[j]) {
                                distance[j] = i - num;
                            }
                        }
                    }
                    int k = 0;
                        int max = -1;
                    for (size_t i = 0; i < 3; i++) {
                        if (max < distance[i]) {
                            max = distance[i];
                            k = i;
                        }
                    }
                    temp[k] = page[num];
                }
                std::cout << page[num] << ',' << ' ';
                for (size_t i = 0; i < 3; i++) {
                    if (temp[i] == -1) {
                        std::cout << '*' << ' ';
                    }
                    else {
                        std::cout << temp[i] << ' ';
                    }
                }
                std::cout << endl;
            }
            num++;
        }
        cout << "错误率:" << error << endl;
    }
    // RLU算法
    void RLU(){
        int temp[3] = { -1,-1,-1 };
        int time[3] = { -1,-1,-1 };
        int num = 0;
        int error = 0;
        cout << "RLU:" << endl;
        while (page[num] != -1) {
            int a = page[num];
            if (inArray(temp, 3, page[num])) {
                std::cout << page[num] << ',';
                std::cout << endl;
                //bool Changed = false;
                for (int i = 0; i < 3; i++) {
                    if (temp[i] == page[num]) {
                        time[i] = 2;
                        //Changed = true;
                    }
                    if (temp[i] != page[num]&&time[i]!=0) {
                        time[i]--;
                    }
                }
            }
            else {
                error++;
                //bool hasChange = false;
                for (size_t i = 0; i < 3; i++){
                    if (temp[i] == -1) {
                        temp[i] = page[num];
                        time[i] = 2;
                        break;
                    }
                    if(time[i] == 0) {
                        temp[i] = page[num];
                        time[i] = 2;
                    }
                    else {
                        time[i]--;
                    }
                }
                std::cout << page[num] << ',' << ' ';
                for (size_t i = 0; i < 3; i++) {
                    if (temp[i] == -1) {
                        std::cout << '*' << ' ';
                    }
                    else {
                        std::cout << temp[i] << ' ';
                    }
                }
                std::cout << endl;
            }
            num++;
        }
        cout << "错误率:" << error << endl;
    }

10.进程状态转换图

• 进程的五种基本状态：
  • 创建状态：进程正在被创建
  • 就绪状态：进程被加入到就绪队列中等待CPU调度运行
  • 执行状态：进程正在被运行
  • 等待阻塞状态：进程因为某种原因，比如等待I/O，等待设备，而暂时不能运行
  • 终止状态：进程运行完毕

11.软链接和硬链接的区别

• 软链接也叫符号链接，软链接文件有类似于Windows的快捷方式。它实际上是一个特殊的文件。在符号连接中，文件实际上是一个文本文件，其中包含的有另一文件的位置信息。
• 硬链接：通过索引节点来进行连接。在Linux的文件系统中，保存在磁盘分区中的文件不管是什么类型都给它分配一个编号，称为索引节点号(Inode Index)。在Linux中，多个文件名指向同一索引节点是存在的。一般这种连接就是硬连接。硬连接的作用是允许一个文件拥有多个有效路径名，这样用户就可以建立硬连接到重要文件，以防止“误删”的功能。其原因如上所述，因为对应该目录的索引节点有一个以上的连接。只删除一个连接并不影响索引节点本身和其它的连接，只有当最后一个连接被删除后，文件的数据块及目录的连接才会被释放。也就是说，文件真正删除的条件是与之相关的所有硬连接文件均被删除。

12.协程

• 定义：又称微线程，纤程，英文名Coroutine。协程看上去也是子程序，但执行过程中，在子程序内部可中断，然后转而执行别的子程序，在适当的时候再返回来接着执行。例如：

  def A() :
      print '1'
      print '2'
      print '3'
  def B() :
      print 'x'
      print 'y'
      print 'z'

• 上面协程运行结果可能是12x3yz。在执行A的过程中，可以随时中断，去执行B，B也可能在执行过程中中断再去执行A。但协程的特点在于是一个线程执行。

13.协程与线程的区别

• 协程最大的优势就是协程极高的执行效率。因为子程序切换不是线程切换，而是由程序自身控制。因此，没有线程切换的开销。协程和多线程相比，线程数量越多，协程的性能优势就越明显。
• 不需要多线程的锁机制，因为只有一个线程，也不存在同时写变量冲突。在协程中控制共享资源不加锁，只需要判断状态就好了，所以执行效率比多线程高很多。

14.进程同步的几种方式

• 信号量：用于进程间传递信号的一个整数值。
• 在信号量上只有三种操作可以进行：初始化、P操作、V操作，这三种操作都是原子操作。P操作(递减操作)可以用于阻塞一个进程，V操作(增加操作)可以用于解除阻塞一个进程。
• 原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。该信号即为信号量s。为通过信号量s传送信号，进程可执行原语semSignal(s);为通过信号量s接收信号，进程可执行原语semWait(s);如果相应的信号仍然没有发送，则进程被阻塞，直到发送完为止。可把信号量视为一个具有整数值的变量，在它之上定义三个操作：
  • 一个信号量可以初始化为非负数；
  • semWait操作使信号量s减1.若值为负数，则执行semWait的进程被阻塞。否则进程继续执行；
  • semSignal操作使信号量加1，若值大于或等于零，则被semWait操作阻塞的进程被解除阻塞
• 管程：由一个或多个过程、一个初始化序列和局部数据组成的软件模块，其主要特点如下：
  • 局部数据变量只能被管程的过程访问，任何外部过程都不能访问；
  • 一个进程通过调用管程的一个过程进入管程；
  • 在任何时候，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程可用；
• 消息传递：是进程间进程消息传递所需要的最小操作集。一个进程以消息的形式给另一个指定的目标进程发送消息；进程通过执行receive原语接收消息，receive原语中指明发送消息的源进程和消息。

15.线程同步的几种方式

• 临界区:通过对多线程的串行化来访问公共资源或一段代码，速度快，适合控制数据访问。在任意时刻只允许一个线程对共享资源进行访问，如果有多个线程试图访问公共资源，那么在有一个线程进入后，其他试图访问公共资源的线程将被挂起，并一直等到进入临界区的线程离开，临界区在被释放后，其他线程才可以抢占。
• 互斥量:采用互斥对象机制。 只有拥有互斥对象的线程才有访问公共资源的权限，因为互斥对象只有一个，所以能保证公共资源不会同时被多个线程访问。互斥不仅能实现同一应用程序的公共资源安全共享，还能实现不同应用程序的公共资源安全共享。
• 信号量:它允许多个线程在同一时刻访问同一资源，但是需要限制在同一时刻访问此资源的最大线程数目。
• 事件:通过通知操作的方式来保持线程的同步，还可以方便实现对多个线程的优先级比较的操作。

  16.操作系统中程序的内存结构

  
• 一个程序本质上都是由BSS段、数据段(data段)、text段(代码段)三个组成的。可以看到一个可执行程序在存储（没有调入内存）时分为代码段、数据区和未初始化数据区三部分。
• BSS段（未初始化数据区）：通常用来存放程序中未初始化的全局变量和静态变量的一块内存区域。BSS段属于静态分配，程序结束后静态变量资源由系统自动释放。
• 数据段：存放程序中已初始化的全局变量的一块内存区域。数据段也属于静态内存分配
• 代码段：存放程序执行代码的一块内存区域。这部分区域的大小在程序运行前就已经确定，并且内存区域属于只读。在代码段中，也有可能包含一些只读的常数变量text段和data段在编译时已经分配了空间，而BSS段并不占用可执行文件的大小，它是由链接器来获取内存的。
  • BSS段（未进行初始化的数据）的内容并不存放在磁盘上的程序文件中，其原因是内核在程序开始运行前将它们设置为0。需要存放在程序文件中的只有正文段和初始化数据段。
  • data段（已经初始化的数据）则为数据分配空间，数据保存到目标文件中。数据段包含经过初始化的全局变量以及它们的值。BSS段的大小从可执行文件中得到，然后链接器得到这个大小的内存块，紧跟在数据段的后面。当这个内存进入程序的地址空间后全部清零。包含数据段和BSS段的整个区段此时通常称为数据区。
• 可执行程序在运行时又多出两个区域：栈区和堆区。
  • 栈区：由编译器自动释放，存放函数的参数值、局部变量等。每当一个函数被调用时，该函数的返回类型和一些调用的信息被存放到栈中。然后这个被调用的函数再为他的自动变量和临时变量在栈上分配空间。每调用一个函数一个新的栈就会被使用。栈区是从高地址位向低地址位增长的，是一块连续的内存区域，最大容量是由系统预先定义好的，申请的栈空间超过这个界限时会提示溢出，用户能从栈中获取的空间较小。
  • 堆区：用于动态分配内存，位于BSS和栈中间的地址区域。由程序员申请分配和释放。堆是从低地址位向高地址位增长，采用链式存储结构。频繁的malloc/free造成内存空间的不连续，产生碎片。当申请堆空间时库函数是按照一定的算法搜索可用的足够大的空间。因此堆的效率比栈要低的多。