操作系统

锁

死锁必要条件

  • 互斥条件：一个资源每次只能被一个进程使用。
  • 占有且等待：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
  • 不可强行占有:进程已获得的资源，在末使用完之前，不能强行剥夺。
  • 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。

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

处理死锁

  • 死锁预防：通过设置某些限制条件，去破坏死锁的四个条件中的一个或几个条件，来预防发生死锁。但由于所施加的限制条件往往太严格，因而导致系统资源利用率和系统吞吐量降低。
  • 死锁避免：允许前三个必要条件，但通过明智的选择，确保永远不会到达死锁点，因此死锁避免比死锁预防允许更多的并发。
  • 死锁检测：不须实现采取任何限制性措施，而是允许系统在运行过程发生死锁，但可通过系统设置的检测机构及时检测出死锁的发生，并精确地确定于死锁相关的进程和资源，然后采取适当的措施，从系统中将已发生的死锁清除掉。
  • 死锁解除：与死锁检测相配套的一种措施。当检测到系统中已发生死锁，需将进程从死锁状态中解脱出来。常用方法：撤销或挂起一些进程，以便回收一些资源，再将这些资源分配给已处于阻塞状态的进程。死锁检测盒解除有可能使系统获得较好的资源利用率和吞吐量，但在实现上难度也最大。

类型

«««< HEAD 互斥锁
读写锁
自旋锁: 停留在用户空间，减少系统调用，但浪费CPU资源
条件锁
=======

  • 互斥锁
  • 条件锁
  • 读写锁:
    读优先 写优先
  • 自旋锁: 在单处理机器上，如果禁止内核抢占，那么在编译时自旋锁就会被剔除出内核。 若系统支持抢占，加锁是禁止内核抢占，解锁是开启。

    291ad1e8d93b4a5b66d9f5dd52712d88a986e015

进程

  • 执行 阻塞 就绪
  • 孤儿进程: 一个父进程退出，而它的一个或多个子进程还在运行，那么那些子进程将成为孤儿进程。孤儿进程将被init进程(进程号为1)所收养，并由init进程对它们完成状态收集工作。
  • 僵尸进程: 如果子进程退出，而父进程并没有调用wait或waitpid获取子进程的状态信息，那么子进程的进程描述符仍然保存在系统中。

实时进程（rt）和普通进程(CFS) 优先级分别是0～99, 100～139

CFS

  • 先在一个调度周期sched_latency_ns内轮流执行一遍，然后根据nice（-20～19）分配分割周期。
  • 每个进程的vruntime计录其虚拟运行时间（nice加权，正相关）
  • vruntime小的优先，但每个cpu都有个min_vruntime以保证每个进程最小的运行时间
  • 新进程或刚醒来的runtime约等于min_vruntime
  • 从其他CPU切换来的进程的vruntime要加上两个CPU的min_vruntime差

rt

FIFO

IPC

  • 管道( pipe )：半双工，数据只能单向流动,父子进程间。
  • 命名管道 (FIFO) ： 半双工，允许无亲缘关系进程间的通信。
  • 信号量：主要有posix信号量和System V信号量，posix一般用在线程上，System V一般用在进程上，posix信号量的函数一般都在下划线。
  • 消息队列( message queue ) ： 消息队列是由消息的链表，存放在内核中并由消息队列标识符标识。消息队列克服了信号传递信息少、管道只能承载无格式字节流以及缓冲区大小受限等缺点。(优先级，大小)
  • 共享内存( shared memory ) ：最快
  • 信号 ( sinal ) ： SIGINT，SIGKILL(不能被捕获)，SIGSTOP(不能被捕获)、SIGTERM(可以被捕获)，SIGSEGV，SIGCHLD，SIGALRM
  • 套接字( socket ) ： 用于不同机器间的进程通信

与线程的区别

  • 状态：创建、就绪、运行、阻塞和死亡
  • 时间：创新(分配空间)、切换（页表）
  • 空间：线程私有的栈+寄存器, 进程独立的内存空间
  • 通信：共享

进程与线程的选择

  • 需要频繁创建销毁的优先使用线程；因为对进程来说创建和销毁一个进程代价是很大的。
  • 线程的切换速度快，所以在需要大量计算，切换频繁时用线程，还有耗时的操作使用线程可提高应用程序的响应
  • 因为对CPU系统的效率使用上线程更占优，所以可能要发展到多机分布的用进程，多核分布用线程；
  • 并行操作时使用线程，如C/S架构的服务器端并发线程响应用户的请求；
  • 需要更稳定安全时，适合选择进程；需要速度时，选择线程更好。

内核

用户态切换到内核态

  • 系统调用
  • 异常： 缺页中断
  • 外部中断

切换过程

  • 找到进程的内核栈（3G）
  • 将用户空间的信息推入内核栈
  • 执行完后，iret特权指令退栈

中断

  • CPU外部引起: I/O中断
  • CPU内部事件: 程序非法操作
  • 系统调用

文件

fcb

连接

  • 硬连接 ln S A S A 文件名不同，但都指向同一inode,id相同。删除A或S只是count–
  • 软连接 ln -s S A A的内容是S的路径名，二者是两个文件，inode不同，删除S后A也找不文件。通过A找到S仅仅是靠路径名，与inode无关。A的内容可以是任意路径名，不存在都行。

FCB

  • 目录文件中是多个FCB，FCB={fielname, inodeid}, inode中有具体信息
  • inode都存在节点表中。找文件先到目录文件中匹配到FCB，通过FCB.inodeid在节点表找inode，然后才定位到数据块的物理地址

索引

文件结构：一个文件有好多个块构成，如何找到这些块？

  • 顺序（按filename或time）FCB.inode指出start和end，扩展性不好，可能前后没有空间
  • 琏式 FCB.inode指出琏表头，当琏的存储方式是顺序，也就是用数组实现琏，叫作文件分配表（FAT），for windows
  • 索引 : 由索引表(树)决定位置，FCB.inode指向树根，由树子结点指向最终的块。for linux，三级索引

读写

  • open：建立fd 和 磁盘地址的关系，说白了就是先找到文件。
  • mmap：建立虚拟地址和磁盘地址关系，虚拟地址中选块地址，插入vm_area_struct琏。虚拟地址和inode(由fd找到)写表
  • read/write: (第一次时DMA )磁盘→内核空间，内核空间->每个进程的用户空间

调页置换算法

  • opt：一个理想算法，内存每个页面统计下还要等多久才能执行到它，数最大的被抛弃。
  • FIFO
  • LRU 时间
  • NRU: Clock (循环)置换：初始0，某被命中置1。当被命中时要置换，扫一圈直到遇到0将其抛弃,途中将1变0，若遇不到0就抛弃起点。

磁盘

  • 最小的存储单元叫扇区，文件系统一般读取多个扇区，叫作块或者簇
  • 中断 1字
  • DMA 1块
  • 通道 多块

内存

虚地址

  • 页表是将虚拟地址映射成内存地址或者磁盘地址。当磁盘地址时，就是缺页，从磁盘调入内存（全相），更新页表。
  • 虚拟地址变物理地址时，先TLB后page，再缺页中断，缺页中断产生后，先判断再调入物理页
  • 先遍历vm_area_struct链表，若不虚拟地址不在start和end间，产生段错误。进程使用了某个地址才会挂到vm_area_struct链，琏中没有说明没使用。Linux用树而不是琏
  • 若在start和end间且越权（prot），触发保护异常（段错误），也就是vm_area_struct上规定的权限跟page上的不一致。调页return后再TLB。

内存分区分配

  • 首次适应度，低端碎片多
  • 循环首次适应度，从上次那开始，大空闲区少
  • 最佳适应度，对空闲区从小到大排序，小碎片多
  • 最坏适应度，从大到小排序，大空间少

内存泄漏

  • 堆内存泄漏 free
  • 系统资源泄露 socketid
  • 没有将基类的析构函数定义为虚函数

malloc

glibc内存管理ptmalloc源代码分析 3.2

  • 一个进程有1个主分配区(sbrk+mmap)+n个非主分配区(mmap), 环形相连。
  • 线程首先要占区加锁，或开新区加锁。
  • 分配区通过sbrk批发128KB作heap(top chunk), (非主分配区是64MB)：
    小于128KB且heap不够，sbrk(size)，堆区, 收缩时释放 大于128KB时，mmap，映射区. munmap释放
  • sbrk和mmap都有映射，sbrk相当于精简版mmap
  • 分配区零售给malloc，128条双向链表, 条每个结点是同大小的空闲块chunk
    fast bins
    small bins
    fast bins -> unsorted_bins
    large bins(非精确)
    top chunk

STL分配器

  • 由16个琏表组成，初始长度为0，通过malloc申请一块大内存作为内存池。每个琏将由一些映射同大小内存空间（8,16,…）的结点串连而成。
  • 当STL需要8byte空间的内存，先构造映射8byte内存的琏，长度尽量长但小于20，也就是先从数据区划分20x8内存出来造琏，取琏首return(malloc时取尾)。当释放时再挂回琏。
  • 数据区用光再malloc，malloc失败再拼凑空间，再失败就抛错
  • 当STL所需要内存超过128bytes直接malloc/free

异步

阻塞与非阻塞针对系统层次
同步与异步是针对代码层次，通过封装改变

  • 同步阻塞：系统不会通知，你要在等
  • 同步非阻塞: 系统不会通知，你可以轮询等
  • 异步阻塞： 系统会通知，但你偏要等
  • 异步非阻塞：系统会通知，你不要等

水壶（同步），响水壶（异步），阻塞（等），非阻塞（轮询）