操作系统学习笔记

• 多道程序、交替执行。即一个CPU上交替的执行多个程序：并发

  为了保证CPU在切回来的时候，还能保持原状，因此每个程序都有一个存放信息的结构：PCB

• 引入“进程”概念

  • 运行的程序和静态的程序不一样！
  • 进程是进行（执行）中的程序

• 多进程图像从启动开始到关机结束：

• 多进程如何组织？

  • 有一个进程在执行

  • 有一些进程等待执行

  • 有一些进程在等待某事件

• 多进程的组织：PCB+状态+队列

  • 运行->等待；运行->就绪；就绪->运行…

    • 该图称为进程状态图（和线程类似）
    • 它能给出进程生存期的清晰描述
    • 它是认识操作系统进程管理的一个窗口

• 多进程如何交替？

  交替的三个部分：队列操作+调度+切换

  • 就是进程调度，一个很深刻的话题
  • FIFO？(first in first out)
    • FIFO显然是公平的策略
    • FIFO显然没有考虑进程执行的任务的区别
  • Priority？
    • 优先级该怎么设定？可能会使某些进程饥饿

• 多进程如何影响？

  • 多个进程同时存在与内存会出现一些问题（类似mysql多并发影响的问题）
  • 解决办法：限制读写
  • 多进程的地址空间分离：内存管理的主要内容

• 多进程是操作系统的基本图像
• 是否可以资源不动而切换指令序列？
  • 进程 = 资源 + 指令执行序列
    • 将资源和指令执行分开
    • 一个资源 + 多个指令执行序列
    • 线程：保留了并发的优点，避免了进程切换代价
    • 实质就是映射表不变而PC指针变

• 和用户级相比，核心级线程有什么不同？

  • ThreadCreate是系统调用，内核管理TCB，内核负责切换线程
  • 如何让切换成型？ - 内核栈，TCB
    • 用户栈是否还要用？执行的代码仍然在用户态，还要进行函数调用
    • 一个栈到一套栈；两个栈到两套栈
    • TCB关联内核栈，那用户栈怎么办？

  线程切换的理解：用当前的S线程的TCB，把当前S的栈顶地址esp存下来，存下来之后进入到next下一个线程T，这时要把T线程的TCB中的栈顶地址拿出来赋给esp寄存器，这样才能把T线程的栈利用起来。

• 内核线程switch_to的五段论

  1. 中断入口（进入切换） call中断处理
  2. 中断处理 引发切换
  3. 内核栈切换 ret
  4. 中断出口 第二级切换
  5. 地址切换 内存管理 ，S、T非同一进程

• 用户级线程、核心级线程的对比

  	用户级线程	核心级线程	用户+核心级
  实现模型
  利用多核	差	好	好
  并发度	底	高	高
  代价	小	大	中
  内核改动	无	大	大
  用户灵活性	大	小	大

  核心级线程的两套栈之间的切换：

• FCFS(First Come, First Served)
• 如何缩短周转时间？ 短作业优先（SJF）
• RR：按时间片来轮转调度
• 相应时间和周转之间同时存在，怎么办？
  • 例如Word很关心相应时间，而gcc更关心周转时间，两类任务同时存在怎么办？
  • 我们怎么知道哪些是前台任务(RR)，哪些是后台任务(SJF)呢？
  • gcc就一点不需要交互吗？Ctrl+C按键怎么工作？word就不会执行一段批处理吗？Ctrl+F按键？
  • SJF中的短作业优先如何体现？如何判断作业的长度？这时未来的信息…

void Schedule(void) //在kernel/sched.c中
{ 
  while(1) { 
    c=-1; next=0; i=NR_TASKS;
		p=&task[NR_TASKS];
		while(--i){ 
      if((*p->state == TASK_RUNNING&&(*p)->counter>c) 
			c=(*p)->counter, next=i; 
    }
		if(c) break; //找到了最大的counter
		for(p=&LAST_TASK;p>&FIRST_TASK;--p)
				(*p)->counter=((*p)->counter>>1)+(*p)->priority; 
    }
	switch_to(next);
}

counter的作用：

1. counter保证了响应时间的界
2. 经过IO以后，counter就会变大；IO时间越长，counter越大，照顾了IO进程，变相的照顾了前台进程
3. 后台进程一只按照counter轮转，近似了SJF调度
4. 每个进程只用维护一个counter变量，简单、搞笑

CPU调度：一个简单的算法折中了大多数任务的需求，这就是实际工作的schedule()函数。

总结：首先是找到所有就绪任务的最大counter，大于0则切过去，否则更新所有任务的counter，即右移一位(除2使用位运算比较快)再加priority，然后进入下一次的找最大counter大于0则切否则更新counter。所以说那些没在就绪态的counter就一直在更新，数学证明出等的时间越长counter越大，等他们变成就绪态了，由于counter大，也就可以优先切过去了。

• 进程合作：多进程共同完成一个任务

  如果仅仅采取信号来控制线程是否唤醒，那么当有多个对象等待时，只能唤醒一个进程

• 信号量：sem<0则正在堵塞。-2则有两个进程在等待这个资源，若为2则代表有2个资源可以使用

​ 即解决共同修改信号量引出的问题

• 在写共享变量时阻止其他进程访问
• 临界区：一次只允许一个进程进入的该进程的那一段代码(有点类似上锁)
• 临界区代码的保护原则
  • 基本原则：互斥进入：如果一个进程在临界区中执行，则其他进程不允许进入
  • 好的临界区保护原则
    • 有空让进
    • 有限等待

进入临界区的方法：

• 轮转法 while一直尝试获取锁(类似自旋锁)
• 标记法 flag去标记是否上锁，但是会引起死锁
• 非对称标记(结合了标记和轮转两种思想)

1. 多个进程——面包店算法 标号排队+非对称标记
2. 汇编语言实现
3. 硬件原子指令法

多个进程由于互相等待对方持有的资源而造成的谁都无法执行的情况叫死锁。

死锁的成因：

1. 资源互斥使用，一旦占有别人无法使用
2. 进程占有了一些资源，又不释放，再去申请其他资源
3. 各自占有的资源和互相申请的资源形成了环路等待

死锁的4个必要条件：

1. 互斥使用
2. 不可抢占
3. 请求和保持
4. 循环等待

死锁处理方法：

1. 死锁预防
   • 破坏死锁出现的条件
2. 死锁避免
   • 检测每个资源请求，如果造成死锁就拒绝
3. 死锁检测+恢复
   • 检测到死锁出现时，让一些进程回滚，让出资源
4. 死锁忽略
   • 就好像没有出现死锁一样

有趣的是，大多数非专门的操作系统都采用了死锁忽略的策略，比如：UNIX，Linux，Windows。

• 重定位：修改程序中的地址（是相对地址）

  • 是编译时，载入时完成重定位的

    • 编译时重定位的程序只能放在内存固定位置
    • 载入时重定位的程序一旦载入内存就不能动了

  • 程序载入后还需要移动

    • 交换（swap）充分利用内存（虚拟内存？）

  • 重定位最合适的时机 - 运行时重定位

    • 在运行每条指令时才完成重定位
    • 每个进程都有各自的基地址，放在PCB中，执行指令时第一步先从PCB中取出这个基地址

• 不是将整个程序放入内存，而是将各段分别放入内存

• 操作系统（OS）对应的段表是GDT，每一个进程所拥有的段表是LDT记录了每一个段的基值，LDT存储在PCB中。

程序写入内存的步骤

1. 将程序分段（编译）
2. 在内存中开辟一个空闲的区域
3. 将文件写入

如何在内存中找到一个空闲的区域呢？ 涉及到操作系统的固定分区与可变分区。

• 核心数据结构
• 请求分配
• 释放内存
• 再次申请
  • 首先适配（均匀随机，ldt表查的快，时间复杂度o(1)）
  • 最佳适配（时间复杂度o(n)）
  • 最差适配

可变分区造成的问题：

1. 会产生内存碎片。例如将200K的内存分为了50K和150K，但此时来了一个160K的请求，这个时候就会拒绝该请求
2. 使用内存紧缩的方式可以将该请求接受，将空闲分区合并，需要移动一个段，但是内存紧缩需要花费大量时间。

因此，操作系统将内存分成页，当页载入内存后，同样需要查找页表中的地址进行重定位。

​ 为了提高内存空间利用率，页应该小，但是页小了页表就大了，那操作系统是怎么处理这个问题的呢？如果页表很大的话，大部分的逻辑地址根本不会用到，就造成了内存资源的浪费。

1. 第一种尝试，只存放用到的页。

   但是这会使得页表中的页号并不连续，就需要比较、查找，折半（二分查找）。明显不满足我们既要连续又要让页表内存占用内存少的需求。

2. 第二种尝试：多级页表，即页目录表（章）+页表（节）。

   其中没有用到的页虽然在目录表中会有对应的章，但是在内存中不需要开辟空间，提高了空间效率。但是在时间上会稍慢。那我们如何对此优化呢？

   多级页表增加了访存的次数，尤其是对64位系统而言。

   • TLB（快表）是一组相联快速存储，是寄存器。类似缓存的作用，经典的以空间换取时间。
   • TLB命中时效率会很高，未命中时效率降低（即在缓存中和不在缓存中的情况）。TLB越大越好，但是要求空间因此通常只有[64,1024]。
   • 多级页表的大小很大，而快表只有64，为什么TLB能起到作用？
     • 程序的地址访问存在局部性
     • 空间局部性
     • 计算机系统设计时应该充分利用这一局部性
   十三、段页结合的实际内存管理

   问题引出：程序员希望用段，物理内存希望用页。

   即虚拟内存，程序以段为单位映射到虚拟内存中，虚拟内存再将段打散，以页为单位映射到物理内存中。偏移就称为虚拟地址！！

   内存换入的换出就是虚拟内存的使用方式。但是并不是总是能获取到新的页，内存时有限的，因此需要有淘汰机制。

   • FIFO页面置换
   • MIN页面置换：选最远将使用的页淘汰，是最有的方案，但是MIN不能知道未来将发生的事
   • LRU页面置换，即末尾淘汰制，和mysql中的buffer pool淘汰机制类似。