zztttt
0%

operating system

发表于 更新于 分类于 ，

进程（process）

  • 进程空间分布：
    一个进程内存分为五个segment，从高到低分别为（stack、heap、bss、data、text）segment
  • 进程通信方式:
    • 管道：父子与兄弟进程之间的通信，不是文件系统，存在于内存
    • FIFO：与进程类型无关的通信方式，以特殊的文件形式存在于文件系统中
    • 消息队列：消息的链列表
    • 信号量： 信号量+共享内存通常结合在一起使用，信号量用来同步对共享内存的访问。
      即bitmap，与IPC结构不同，它是一个计数器，用于进程间的互斥与同步，需要结合共享内存。
      它基于operating system的PV操作，对信号量的操作都是原子操作，并且支持信号量组
    • 共享内存：
      指两个或多个进程共享一个给定的存储区。
      共享内存是最快的一种 IPC，因为进程是直接对内存进行存取。因为多个进程可以同时操作，所以需要进行同步。解除映射时才写回文件。
      优点：效率高。缺点：没有同步机制，需要信号量
  • 进程资源的分配方式：
    由PCB(process control block)管理，在32bit系统下，会分配4G内存，3G给用户，1G给内核。
    内核态有一个task_struct，里面保存以下这些信息：
类型 内容
标识 pid ppid
file 打开的文件信息，file descriptor
memory 内存指针，指向虚拟地址空间的信息
context 寄存器的值、进程状态、堆栈的内容
signal 是否还有待处理的信号
I/O 记录进程和各种I/O设备的交互
  • 生命周期：
    • 僵尸态： 子进程退出后，所有资源都消失了，只剩下 task_struct，父进程在 wait 函数中可以得到子进程的死亡原因。在 wait 之前子进程的状态就是僵尸态。
    • 深度睡眠： 等待资源到位后才醒过来
    • 浅度睡眠： 等待资源到位或收到信号后都会醒过来
    • 暂停： stop状态是被外部命令作业控制等强制进程进入的状态。
    • 就绪： 未占有 CPU，等待调度算法调度到运行态的进程
    • 运行：占有 CPU，正在运行的线程。
  • 进程调度算法
    • FIFO
    • SJF
    • 优先权
    • 轮转时间片
    • 多层队列：Linux默认调度算法
  • 守护进程（daemon）：
    是一类在后台运行的特殊进程，用于执行特定的系统任务。很多守护进程在系统引导的时候启动，并且一直运行直到系统关闭。另一些只在需要的时候才启动，完成任务后就自动结束。

线程

  • 线程的使用：

    • C++-Linux：
      pthread_join: 需要父线程调用，等待子线程执行完，回收资源。不然资源没法回收
      pthread_detach: 在该线程运行结束后会自动释放所有资源。
      pthread_cond_t: 必须在互斥锁的保护下使用相应的条件变量
      阻塞在条件变量

      1
      2
      3
      4
      5
      pthread_mutex_lock(pthread_mutex_t *mutex);
      while(condition_is_false){
          pthread_cond_wait(pthread_cond_t *cv, pthread_mutex_t *mutex);
      }
      pthread_mutex_unlock(pthread_mutex_t *mutex);

      唤醒阻塞在某条件变量上的线程：

      1
      2
      3
      pthread_cond_signal(pthread_cond_t *cv); //唤醒至少一个阻塞在该cond上的线程
      pthread_cond_broadcast(pthread_cond_t *cv); // 唤醒所有阻塞在该cond上的线程
      //前者单播，后者广播

    • Java：
      TODO

  • 线程池
    事先将线程放到一个容器中，当使用线程的时候，不用再去new出一个线程，直接从线程池取出来
    优点：
    • 降低资源消耗：即重复利用线程池中的线程可以节省线程创建和销毁带来的消耗
    • 提高性能：当任务需求时，可以不用创建线程直接执行，主要是直接从线程池中取出线程去执行
    • 提高线程的可管理性：线程是稀缺资源，而且也是任务中不可少的资源，如果频繁的且无限制的创建会消耗系统资源，降低系统稳定性导致系统崩溃，内存溢出等等问题
  • 线程安全
    多线程访问同一代码，不会产生不确定的结果。编写线程安全的代码是低依靠线程同步。
    线程安全的类：StringBuffer， HashTable， Vector
    线程不安全的类：StringBuilder（速度更快），HashMap
  • 控制线程执行顺序：
    • 信号量：signal，就上述关于pthread相关的函数
    • sem_post:
      sem_t为一个变量，post是给她+1，wait如果它是0则阻塞，非0则-1
      例：初始化为0，线程1 wait直接阻塞，线程2 执行结束post给它加一，线程1则开始执行

进程（process）与线程（thread）

线程是进程的一个执行流，一个进程可以由很多个线程组成

进程 线程
资源分配的最小单位 程序执行的最小单位
数据分开，需要IPC。共享复杂，同步简单 共享简单，同步复杂
占用内存多，切换复杂，CPU利用低 占用内存少，切换简单，CPU利用率高
编程简单调试简单 难
进程之间不会相互影响 一个线程挂掉将导致整个进程挂掉
分布式扩展到多台电脑比较简单 适用于多核分布
创建/销毁代价高 低
有独立的地址空间 多个线程共享同一个进程的地址空间

Linux系统

  • ELF文件：是一种文件格式。可执行文件、目标文件、共享库和核心转储。由四部分组成
    • ELF header
    • Program header table
    • Section
    • Section header table
      ELF
      TODO: 其大小与程序中全局变量是否初始化有什么关系（注意未初始化的数据放在bss段）bss在一开始全部清零
  • 系统调用和库函数
系统调用 库函数
操作系统为用户提供的一系列操作的接口 对系统调用的一层封装
线程安全 非线程安全
  • 临界区：
    在任意时刻只允许一个线程对共享资源进行访问。
    如果有多个线程试图同时访问临界区，那么在有一个线程进入后其他所有试图访问此临界区的线程将被挂起，并一直持续到进入临界区的线程离开。
    临界区在被释放后，其他线程可以继续抢占，并以此达到用原子方式操作共享资源的目的。
  • 内存管理机制：
    虚拟地址、物理地址、逻辑地址。虚拟地址和物理地址之间采用多级页表映射
  • 页面置换算法：
    • FIFO：只是在按线性顺序访问地址空间时才是理想的，否则效率不高
    • LRU：
      • 优点：命中率,当存在热点数据时,LRU的效率很好；实现相对简单
      • 缺点：偶发性的,周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重；命中时需要遍历链表,找到命中的数据块索引,然后需要将数据移到头部
    • LFU
    • CLOCK：LRU算法的近似实现
    • OPT：最佳置换算法，实际上不可能实现。每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。
  • 同步机制：
    • 每个cpu一个变量
    • 原子操作：PV
    • 自旋锁：锁住一块临界区，进入时需要获取自旋锁。
      读写自旋锁：允许多个进程同时对同一数据结构进行读，但不允许多个进程同时修改同一数据结构，因此在实现上必须分为读锁和写锁。
    • 顺序锁：写锁不会因为读锁而锁住
    • 信号量：存在一个进程等待队列，未获取锁的进程将挂到该队列中，然后主动调用schedule()切换进程，让出cpu
    • 禁止本地中断
读锁 写锁
实现多个进程能同时读同一数据结构，但是读的过程中不允许写 实现仅能有一个进程获取写锁进入临界区，获取写锁时同时保证没有进程已经获取读锁
  • 链接：
    分为动态链接和静态链接。
    动态链接生成可执行文件时不将所需函数链接到一个文件，而是要用的时候从系统ddl里面找。静态链接就是把所有文件都放入exe里面
  • 文件系统：ext2 ext3 ext4。。。

锁

  • 可重入锁（递归锁）：
    • 在同一个线程在外层方法获取锁的时候，再进入该线程的内层方法会自动获取锁（前提锁对象的是同一个对象或者class），不会因为之前已经获取过还没释放而阻塞
    • 可重入锁可以让当前进程再次获取锁，不可重入锁会直接获取失败导致阻塞。可以一定程度避免死锁。
    • 加锁：先尝试获取并更新status的值，如果为0表示没有其他的线程占用，将其置为1；若不为0，则判断是否是当前线程在占有锁，如果是，status++，并再次获取锁，不是则导致获取锁失败，阻塞
    • 解锁：先获取status值，如果是当前线程战有锁，如果status == 1，则置为0并释放，否则status–，不释放。
  • 乐观锁/悲观锁：
乐观锁 悲观锁
每次拿数据的时候认为别人不会改，所以不会锁 每次拿数据都会锁
适用于多读（在拿数据时会判断是否有人改数据）
java.util.concurrent.atomic synchronized、ReentrantLock
  • 生产者消费者模型：
    生产者：生产消费者需要的资料。消费者：把资料做成产品
    • 生产者生产数据到缓冲区中，消费者从缓冲区中取数据
    • 如果缓冲区已经满了，则生产者线程阻塞
    • 如果缓冲区为空，那么消费者线程阻塞