操作系统笔记

进程间通信方法🔗

• 匿名管道通信
  • 半双工，具有固定的读端和写端
  • 父子进程间和兄弟进程间通信
  • 匿名管道可试做一种特殊的文件，可用普通的read，write函数读写
  • 跟随进程，进程结束后杀死该匿名通道
  • 仅存在于内存中
  • 父子进程之间通信方式，父进程创建管道与两个首尾文件描述符。父子进程分别使用写端和读端，父进程写数据，子进程读数据，整个结构由一个循环队列维护，这样实现进程间通信
• 有名管道
  • 支持非父子关系进程间通信
  • 有名管道有路径名与其关联，以一种特殊设备文件形式存在于文件系统中
• 消息队列通信
  • 消息队列一般为一种消息链表，发送进程/线程向队列中放置消息，接受进程/线程根据一个事先约定的key从队列中取走消息
  • 发送端写入信息时，并不需要一个接收端在该队列等待
  • 消息队列不随进程的结束被杀死
  • 消息队列为内存中的数据结构
• 信号量通信
  • 为一个计数器，用于实现进程间的互斥与同步，并不储存和传输通信数据
  • 信号量基于PV操作，信号量的增减都是原子操作
• 信号通信
• 共享内存通信
  • 两个及以上进程共享一个给定的内存区域
• 套节字通信*

进程调度的时机🔗

• 当前进程结束
• 当前进程阻塞
• 系统调用结束后返回用户进程
• 抢占调度系统中，更高优先级的进程就绪时
• 分时系统中，当前进程的时间片用完

不能进行进程调度的情况🔗

• 中断处理程序执行时
• 在操作系统的内核临界区内
• 在需要屏蔽中断的原子操作中

临界区🔗

• 就是访问和操作共享数据的代码段
• 为了避免在临界区中发生并发访问，临界区代码都是原子地执行
• 若两个线程在同一临界区中同时执行，称之为竞争条件
• 避免并发和防止竞争条件称为：同步

进程的调度算法🔗

• 先来先服务调度算法
  • 选择最先进入队列的进程，一直运行直至结束或者阻塞
  • 若运行长作业，则会使短作业长时间等待
  • 不利于短作业
• 最短作业有限调度算法
  • 有限选择运行时间最短的进程
  • 不利于长作业
• 高响应比优先调度算法
  • 进程调度时计算响应比，高响应比进程先运行
  • 响应比 = (等待时间 + 要求服务时间) / 要求服务时间
• 时间片轮转调度算法
  • 每个进程分配一个时间片，在时间片结束若未结束后阻塞进程
• 高优先级调度算法
  • 分为动态优先级与静态优先级
    • 静态优先级：创建进程时则决定优先级
    • 动态优先级：优先级随着等待时间变长而变高
  • 缺点是低优先级的进程可能永远不会运行
• 多级反馈队列调度算法
  • 配置多个就绪队列，优先级由高到低
  • 每个就绪队列内按先到先服务调度算法调度，并设置时间片
  • 一个进程首先放入高优先级进程，若时间片内未完成，则放入低一级就绪队列中
  • 若高优先级队列中有就绪进程，则先执行高优先级队列中的进程

进程调度策略的基本设计指标🔗

• CPU利用率
• 系统吞吐率
• 响应时间
• 周转时间
  • 作业从提交到完成的时间间隔

孤儿进程/僵尸进程🔗

• 孤儿进程：父进程退出但子进程仍在运行的进程
  • 孤儿进程将被交付给1号进程(initial进程)，由其进行状态收集
• 僵尸进程：
  • 僵尸进程即一个子进程已经结束，但其程序控制块仍存在于进程表中，需要父进程调用wait去读取其退出状态后才删除
  • 父进程或者调用SIG_IGN，表面不需要读取退出信息，交由initial进程进行处理

线程🔗

• 线程使得多个程序能够并发执行，提高资源利用率与系统吞吐率
  • 进程同一时刻只能执行一个任务，不能充分利用CPU资源
  • 进程若发生阻塞就会被全部挂起，尽管有些任务不需要依赖等待的资源
• 线程相对进程的优点
  • 开辟线程的资源开销远小于进程
  • 线程间相互切换的效率也会更好
  • 线程间共享同一块内存空间，可以直接通过共享内存进行通信

进程与线程的区别🔗

• 同一进程的线程共享该进程地址空间，而不同进程直接的地址空间相互独立
• 进程是资源分配的最小单位，线程是CPU调度的最小单位
• 同一进程的线程共享该进程的资源，不同进程间相互独立
  • 线程共享进程的代码段（代码和常量），数据段（全局变量和静态变量），附加段（堆空间），但拥有独立的运行时栈空间
• 进程崩溃后不会对其他进程产生影响，而线程崩溃后整个进程崩溃，所以多进程比多线程健壮
• 进程切换消耗资源大于线程切换，设计频繁切换时线程优于进程
• 进程拥有独立的程序入口与出口，但线程必须依赖于进程存在

函数的可重入性🔗

• 一个函数可能同时被多个线程调用，若多个线程调用函数时会修改其他线程调用时的数据，造成结果的不确定性，那么则认为该函数不具备可重入性
• 一般来说，一个函数若想实现可重入，至少需要满足以下条件
  • 只使用函数中的局部变量
  • 或在使用全局变量中使用手段保证同步（比如信号量，互斥量等）
  • 函数中不存在内存的分配与释放
  • 函数中不存在I/O等操作
  • 函数中不存在静态的变量与结构
  • 不会调用其他不可重入的函数

进程与线程Linux API🔗

• fork
  • 创建新的进程
• exit
  • 从当前进程退出
• waitpid
  • 等待某进程结束后，获取其退出状态
• atexit
  • 在退出进程时调用的函数
• getpid
  • 获取进程ID
• abort
  • 请求进程非正常退出

多线程模型🔗

• 多对一模型
  • 多个用户级线程映射到一个内核级线程上，该模型效率较高，但若一个线程阻塞，该进程所有线程都会阻塞，已基本没有操作系统使用该模型
• 一对一模型
  • 一个用户级线程映射到一个内核级线程上，具有更好的并发性；但一般来说内核线程有上限，会限制用户线程的数量；Windows与Linux使用该模型
• 多对多模型
  • 多个用户级线程映射到多个内核级线程上

进程同步的方法🔗

• 互斥锁
• 信号量
• 读写锁
• 记录锁
• 条件变量
  • 当不满足条件变量时，阻塞进程
• 屏障

线程同步的方法🔗

• 互斥锁
• 信号量
• 读写锁
• 自旋锁
• 条件变量

死锁的产生条件🔗

• 互斥条件
  • 进程不允许其他进程访问分配的资源
• 占有并等待条件
  • 进程在占有当前资源的情况下又请求另外的资源，并不会放弃当前占有的资源
• 非抢占条件
  • 进程已获得的资源在使用完之前不会被剥夺
• 循环等待条件
  • 存在一个进程-资源的环形链

解决死锁🔗

• 方法即破坏四个必要条件
• 方法
  • 一次性分配所有资源
• 若一个资源得不到分配，就不分配给他其他的资源
• 若进程新的资源未满足，则释放该进程占用的资源
• 有序分配资源，进程按编号分配资源

虚拟地址与物理地址🔗

• 对主存在2^N(32位N=32,64位N=64)上对物理地址进行的一个映射

虚拟内存🔗

• 在硬盘上划分的一块区域作为内存空间
• 操作系统为每个进程提供独立的页表，也就是独立的虚拟内存空间；多个虚拟页面可以映射到同意物理页面上
• 共享内存：即多个进程的虚拟页面映射到同一物理页面上
• 简化内存分配：用户可以分配一段连续虚拟内存，而物理内存则不连续；

虚拟内存管理的优点🔗

• 读写内存的安全性，由于物理地址访问不受限，如果直接使用物理地址则恶意代码或错误代码可以访问重要内存区域而导致问题；虚拟地址则可以控制内存访问，实现读写内存的安全性
• 可以为每个进程都分配独立的地址空间，防止踩踏或非法访问等问题产生，同时进程认为独立占有整个地址空间也可以简化管理，不需要程序员考虑内存地址冲突等问题
• 可以在物理地址难以保证足够大的连续空间时，仍然为进程分配足够大的连续虚拟内存空间
• 可以实现为所有进程分配大于实际物理空间的虚拟内存空间，进程只将目前需要的内容存入内存中，当内存中缺失需要的代码时，则触发缺页中断，并通过页面置换来替换得到需要的内容；linux中表现为swap交换区

伙伴算法🔗

• 一种实现内存管理的方法，用于在分配连续内存空间的同时，减少碎片的产生
• 基本思路
  • 将一块连续的内存空间划分为1、2、4、8...1024个连续页框的块，提前预留
  • 分配时，将大于等于的内存块划出分配；若不存在对应的内存块，则将更大的一块内存块分成两半，一半分配，一半储存
  • 释放时，递归执行；若释放后内存相邻空闲内存为伙伴，则组合并向上递归，最后储存
• 伙伴定义：
  • 两个块大小相同
  • 两个块地址连续
  • 两个块从同一个大块中分离而来

页面置换算法🔗

• 先入先出算法（FIFO）
  • 思路：置换最先调入内存的页面，即在内存中驻留最久的页面
  • 特点：
    • 性能较差，因为调出的页面可能被经常访问
    • 但实现非常简单
• 最近最少使用(LRU)
  • 思路：
    • 置换最久未被访问的页面
    • 基于程序局部性原理，刚刚被调用的页面再被调用的可能性更高
• 最不常用算法(LFU)
  • 思路：缺页时，置换访问次数最少的页面
  • 特点：
    • 开销较大
    • 对于一开始频繁使用但后来不再使用的页面，不容易被置换出去

写时复制🔗

• 多个进程共享同一资源时，若仅仅是读取资源，则没必要对资源进行复制，直接读取即可
• 若某个进程需要修改该资源时，才对资源进行复制并修改
• 一种惰性思想，即直到必要的时候再去执行操作
• 对于父子进程，当fork调用结束后，子进程和父进程虽然拥有独立的内存地址，但其实是共享同一内存空间的

协程🔗

• 协程是一种函数对象，可以设置锚点暂停，然后再在该锚点恢复运行

#include <iostream>
#include <boost/coroutine2/all.hpp>

void coroutine_function(boost::coroutines2::coroutine<void>::pull_type & coro_back)
{
    std::cout << "a ";
    coro_back(); // 锚点，返回
    std::cout << "b ";
    coro_back(); //锚点 返回
    std::cout << "c ";
}

int main()
{
    boost::coroutines2::coroutine<void>::push_type coroutine_object(coroutine_function); 	// 创建协程
    std::cout << "1 ";
    coroutine_object(); // 运行协程
    std::cout << "2 ";
    coroutine_object(); // 返回锚点，继续运行协程
    std::cout << "3 ";
    coroutine_object(); // 返回锚点，继续运行协程
    return 0;
}

• 类似用户态线程，轻量级线程
• 天然同步，因为调用协程后当前线程阻塞，并运行协程，直至遇到锚点或运行结束才返回结果