嵌入式操作系统

第一章
第二章
第三章
第四章
第五章
第六章
第七章
第八章
TinyOS

第一章

多道
- 多道程序设计技术是在计算机主存中同时存放几道相互独立的程序，使它们在管理程序控制之下，相互穿插地运行。当一个程序无法使用处理器资源的时候（做I/O的时候），系统可以调用另一个程序在处理器上运行。
- 特征：多道、宏观上并行、微观上串行
分时
- 分时技术是将处理器的时间分成很短的时间片，将这些时间片轮流分配给在内存中的用户程序使用。
- 分时系统具有的特点
  1. 独立性（各用户感觉独占资源）
  2. 及时性
  3. 交互性
并发
- 在系统里有多个同时进行的活动
共享
- 进程之间共享系统资源
不确定性
- 系统中含有大量不确定的事件

第二章

硬件支持：
1. 处理机的状态：目态、管态
  1. 管态指CPU上运行管理程序所处的状态，目态是指CPU上运行用户程序所处的态；
  2. 二者的区别：特权级不同，CPU在管态下可以使用全部机器指令，包括一组特权指令，可以使用所有的资源，访问整个存储区。CPU在用户态下只能使用用户态非特权指令，访问规定的存储区，使用一部分资源。
  3. 从用户态到管态切换的唯一途径是中断
2. 特权指令
  1. 改变机器状态的指令
  2. 修改特殊寄存器的指令
  3. 涉及外部设备的输入/输出指令
中断
- 中断实质是一个受保护的控制转移(protected control transfer)
- 中断分类：I/O、外中断、机器故障中断、程序性中断、访管中断
- 操作系统具备处理同时性活动的能力，重要的硬件支持是：中断系统

第三章

系统功能调用
- 命令行
- 图形用户界面
程序接口

第四章

并发：若干个程序段同时在系统中运行，若这些程序的执行在时间上存在重叠，则称为程序并发执行。
- 特点：失去了封闭性；程序与计算不再一一对应
进程
- 进程是一个程序在给定的初始环境和活动空间下，在处理机上的一次执行过程
- 组成
  - 进程控制块
  - 进程的执行程序
  - 进程总是处于某个队列
  - 处于某种状态
  - 占用系统某些资源
线程
- 轻量级进程
状态变迁
- 无等待-》运行 ❌
- 无就绪-》等待 ❌
- 如果系统中有N个进程，运行的进程最多几个，最少几个；就绪、等待呢？
  - 运行的进程最多一个，最少0个
  - 就绪最多N - 1个，最少0个
  - 等待最多N个，最少0个
- 一个状态的发生，是否一定导致另一个状态的发生？列出所有可能
  - 运行 -> 就绪一定有就绪 -> 运行
  - 就绪 -> 运行不一定有运行 -> 就绪

合作关系

进程的相互制约关系产生原因：资源共享、进程合作
互斥
- 当某一进程正在访问某临界资源时，就不允许其他进程进入，否则就会产生无法估计的错误。
- 源于对独占设备的竞争

同步

源于进程的合作

共享缓冲区的合作进程同步

生产者-消费者问题

Full：缓冲区产品数目，初值为0
Empty：缓冲区可存放产品的空位，初值为n
Mutex:缓冲区互斥信号灯，初值为1

void producer()
{
  while(生产未完成) {
    生产一个产品;
    p(empty);
    p(mutex);
    将产品放入缓冲区;
    v(mutex);
    v(full);
  }
}

void consumer()
{
  while (还要继续消费) {
    p(full);
    p(mutex);
    从缓冲区取出一个产品;
    v(mutex);
    v(empty);
    消费产品;
  }
}

读者写者问题？
誊抄问题

在地球上，竞争和合作是永恒的！
临界资源
- 一次仅允许一个进程访问的资源
临界区
- 每个进程中访问临界资源的程序段称为临界区
原子、原语：不可分割、不可中断的程序
信号灯P、V操作
- P
  1
  2
  3
  4
  5
  6
  {
  s--;
  if (s < 0) {
  挂起该进程;
  }
  }
- V
  1
  2
  3
  4
  5
  6
  {
  s++;
  if (s <= 0) {
  唤醒等待S的进程;
  }
  }
- 信号灯（s, q）
  - s代表可用资源的数目，初值应该大于等于0
- s13 = 0 表示进程P1尚未执行完成
- s23 = 0 表示进程P2尚未执行完成
- 1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  void P1()
  {
  ....;
  v(s13);
  }
  void P2()
  {
  ....;
  v(s23);
  }
  void P3()
  {
  p(s13);
  p(s23);
  .....;
  }
- 思路：为每个只能在进程i结束后才能执行的进程j设置是否可开始的信号灯\(S_{ij}\)，其初值为0，这些进程执行前先对\(S_{ij}\)进行p操作。

IPC

fork

子进程值为0，父进程中为一大于0整数

pid_t p1, p2, p3;
if ((p1 = fork()) == 0) {
    // child process
    execv("./get", NULL);
}
else if ((p2 = fork()) == 0) {
    // child process
    execv("./copy", NULL);
}
else if ((p3 = fork()) == 0) {
    // child process
    execv("./put", NULL);
}
else {
    wait(NULL);
    wait(NULL);
    wait(NULL);
}

并发实践，P80左右，注意有无else

线程
- 线程(Thread)是一个动态的对象，是处理机调度的基本单位，表示一个进程中的一个控制点，执行一系列的指令。
- 进程是系统资源的分配单位；线程是处理机调度的对象
- 与进程相同的地方
  - 线程共享父进程的代码段和数据段，拥有相同的优先级
- 不同的地方
  - 每个线程拥有自己的PC，寄存器和栈指针
- 上下文切换
  - 同一个进程中线程切换简单，因为进程中所有线程是共享一个上下文的
- 实验
  - 飞机售票
调度
- 循环轮转
  - 固定时间片
    - 优点：实现简单、系统开销小
    - 缺点：不灵活，当系统中进程较少时，系统开销大
- 优先级
  - 多级反馈队列调度算法
  - I/O量大->高优先就绪队列，优先照顾
  - 计算量大->低优先就绪队列，但一次可执行500ms，适当照顾
  - I/O多->优先执行，系统的外部设备经常忙
  - I/O少->时间片长，上下文切换少系统开销小

第五章

死锁
- 死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所处的一种系统状态。
- 四个必要条件
  - 互斥-Mutual Exclusion
  - 不可剥夺-No preemption
  - 部分分配-Hold and wait
  - 循环等待-Circular wait
预防
- 预先分配一个进程要用的所有资源（静态分配）是防止死锁的一种安全而简单的方法
  - 破坏部分分配条件
  - 缺点：设备（资源）的浪费太大
避免
- 有序资源分配
  - 系统中的所有资源统一编号（如打印机为1，磁带机为2...）
  - 申请时必须以上升的次序
  - 系统要求
    - 对必须使用的而且属于同一类的资源，必须一次申请完
    - 在申请不同类资源时，必须按设备编号依次申请
- 最简单的银行家算法（书上的例子）
  - 银行家算法要求进入系统的进程必须说明它对各类资源类型的实例的最大需求量。这一数量不能超过系统各类资源的总数。当进程申请一组资源时，该算法需要检查申请者对各类资源的最大需求量，如果系统现存的各类资源的数量可以满足当前它对各类资源的最大需求量，就满足当前的申请；否则进程必须等待，直到其他进程释放足够的资源为止。
  - 问题
    - 考察每个进程对各个资源的申请需花费较多的时间
    - 过于谨慎

第六章

映射
- 逻辑、物理转换
- 静态地址映射
  - 在作业装入过程中进行地址映射
  - 需软件重定位装入程序
  - 需要花费较多CPU时间
  - 不灵活
- 动态地址映射
  - 在程序执行期间进行地址映射
  - 需要硬件地址变换机构-重定位寄存器
  - 地址变换快
  - 灵活
分配
- 放置策略
- 调入策略
  - 请调
  - 预调
- 淘汰策略
扩充
- 虚拟存储-为用户提供一种不受物理存储器结构和容量限制的存储器
- 核心
  - 程序执行的局部性原理
  - 逻辑地址和物理地址的分离
保护
- 上下界 -> 物理
  - 下界寄存器：存放程序装入内存后的开始地址
  - 上界寄存器：存放程序装入内存后的末地址
  - （下界寄存器）\(\le\) 物理地址 < （上界寄存器）
- 基址限长 -> 逻辑
  - 0 \(\le\) 逻辑地址 < 限长
- 仅适用于连续分配
动态分区
- 自由主存队列
- 首次适应算法
  - 按空闲区首址升序的方法组织
  - 尽可能地利用低地址的空闲区，而尽量地保证高地址的大空闲区
- 最佳适应算法
  - 按空闲区大小升序方法组织
  - 将申请者放入与其大小最接近的空闲区中
  - 若系统中存在与申请区大小相等的空闲区，这种算法肯定能将这种空闲区分配给申请者（首次适应则不一定）
- 最坏适应算法
  - 按空闲区大小降序的方法组织
  - 将最大的空闲区切去一部分给请求者
  - 克服最佳适应算法把空闲区分割得太小的缺点
- 高、低地址优先
页式系统
- 页表
  
  页号块号
- 快表
  - Translation Look-aside Buffers, TLB
- 地址变换过程
  
  内存地址 = 块号 * 页大小 + 位移量
  - 按字节编址
  - 1KB = 10位
  - 2KB = 11位
  - 1MB = 20位
  - 1GB = 30位
  程序地址以十进制给出
  - 页号 = 虚地址 % 页大小
  - 位移量 = 虚地址 mod 页大小
- TLB
  - 查TLB = \(\epsilon\) 时间
  - 查内存 = 1 毫秒
  - 命中率 = \(\alpha\)
  - Effective Access Time(EAT) = \((1+\epsilon)\alpha+(2+\epsilon)(1-\alpha)\)
- 请求分页，扩充页表位
  - 扩展页表
    
    页号块号中断辅存地址引用修改访问方法
  - 中断位：0 -> 在内存，1 -> 不在内存
  - 引用位：0 -> 没有进程访问，1 -> 有进程访问
  - 修改位：0 -> 调入后没修改，2 -> 调入后修改过
- 页面置换算法
  - 先进先出
    - 建立一个页面进入主存的先后次序表
    - 建立一个替换指针，指向最早进入主存的页面
    - 当需要置换一页时，选择替换指向的一页，然后调整替换指针的内容
    - 每次有新页面进入内存更新次序表
  - LRU-Least Recently Used
    - 需要淘汰页时，选择最长时间未使用的页
  - 近似LRU（实现）
页式系统最终面貌

优点：
- 不要求作业的程序和数据段在内存中连续存放，解决了碎片问题
- 可以利用的存贮空间大大增加，提高了主存利用率
- 请求式系统提供了统一管理的虚拟存储实现方案
缺点：
- 硬件支持，成本
- 系统开销大，页表维护与管理，缺页中断
- 抖动
段页式系统
- 区别、变换
  - 页是物理单位，段是逻辑单位
  - 页大小是固定的，段大小不固定
- 段页式系统：段内分页
- 难度小于课件上例子

第七章

独立性：用户在编程式所使用的设备与实际设备无关
- 逻辑设备名：用户指定的设备名（可更改的）
- 物理名：系统提供的设备的标准名称（不可更改）
- 优点
  - 方便用户
  - 改善设备利用率
  - 提高系统的可扩展性和可适应性
独占设备：采用动态分配有可能造成死锁
- 让一个设备在整个运行区间独占使用
共享设备：不会死锁
- 由多个作业、进程共同使用的设备
设备分配
- 先来先服务
- 优先级高者优先
- 独占分配：在一作业执行前，将它所要使用的设备分配给它；当它结束撤离时，将分配给它的这类设备收回
- 共享分配：动态分配，进程提出资源申请，由设备管理模块进行分配，进程使用完毕后立即归还
- 虚拟分配
  - 将独占设备转换为共享设备的一种技术
  - 通常把用来代替独占类型设备的那部分外存空间称为虚拟设备
  - 当进程需要与独占设备交换信息时，系统将分配磁盘空间，并建立相应的数据结构，这种分配方法称为虚拟分配
缓冲管理
- 预存缓写
- 不让进程长时间等待外设完成操作
- 缓写

第八章

文件
- 逻辑结构
  - 流式 Byte Sequence
    - 无结构，流式文件是相关的字符的集合，文件的长度为所含字符数
  - 记录式 Record Structure
    - 记录式文件是记录的集合，每个记录由相关的域构成
- 物理结构
  - 连续文件
    - 文件内容存放在连续编号的磁盘块中
    - 优点
      - 结构简单，容易实现
      - 不需要额外开销
    - 缺点
      - 空间利用率低
      - 不利于文件的动态增加和修改
  - 串联文件
    - 文件的内容放在若干不要求连续编号的磁盘块中
    - 一个文件占用的磁盘块链接成一个磁盘块链，链接指针存放在每磁盘块的最末一个字（或第一个字）
    - 优点
      - 存储空间利用率高
      - 文件动态扩充和修改容易
    - 缺点
      - 随机存取效率太低
  - FAT
    - 文件映照
    - 把串联文件中的链接集中在一个结构中，这样既保持了串联文件的优点，也克服了其缺点
  - 索引文件
    - 每个文件有一个索引表，登记文件的逻辑块与物理块间的对应关系
    - i_addr[0]~i_addr[9] 为直接索引
    - i_addr[10]为一级间接索引块
    - i_addr[11]为二级间接索引块
    - i_addr[12]为三级间接索引块

空闲空间

位示图
- 用一个位向量表示哪一块空闲

成组连接-Grouping

空闲inode
- s_nfree 空闲块数，初值为1
- s_free[100] 空闲块块号，s_free[0]初值为0
第一组是99块，中间都是100块，最后一组<=100块

回收算法free

void free()
{
  if (s_nfree < 100) {
    s_free[s_nfree++] = 释放磁盘块号;
  }
  else {
    将s_free[]写到释放磁盘块中;
    s_nfree = 1;
    s_free[0] = 释放磁盘号;
  }
  return;
}

分配算法alloc

磁盘块 alloc()
{
  s_nfree--;
  if (s_nfree == 0) {
    if (s_free[0] == 0) {
      sleep();
    }
    a = s_free[0];
    将s_free[0]块读到filsys;
    s_nfree = 100;
    return a;
  }
  else {
    return s_free[s_nfree];
  }
}

文件图示
- 树形
  - 目录文件是有文件目录项组成的文件
  - 文件目录项由文件名和inode组成
    
    文件名 inode
  inode
- 绝对／相对路径
- 链接
  - 硬链接：目录项中指向同一个inode
  - 软链接：目录项中指向不同的inode，链接文件的磁盘块里存储链接对象的inode
- 文件共享
  - 被多个用户使用，由存取权限控制
  - 被多个进程使用，但各用自己的读写指针
  - 被多个进程使用，但共享读写指针
- 文件操作（FCB）
  - 打开
  - 重命名
  - 移动

TinyOS

组件化编程，连接配置文件
- Application = Graph of Components
执行机制
- 分阶段作业，无阻塞
- 主动消息通信
中断
事件
- 事件驱动
- 优先级高于任务
任务
- 轻量级线程。任务之间平等，不能相互抢占，先入先出进行调度
- 任务一般用于对时间要求不是很高的应用中，要求每个任务都很短小，能够使系统的负担较轻
- 不能有返回值和参数

习题

输入输出控制的主要功能是什么？
- 解释用户的I/O系统调用命令
- 设备驱动
- 中断处理
实时系统的基本特征：
- 安全性
- 实时性
- 高可靠
- 没有公平响应！
文件的物理结构：
- 连续
- 串联
- 索引
设备独立性是指用户程序中使用的设备独立于具体的物理设备
所谓操作系统虚拟机的概念，是指在裸机上配置操作系统
常用的资源分配策略有优先调度和先来先服务两种
文件目录采用树型结构而不采用简单表结构的最主要原因是解决重名问题
在请求分页系统中，为实现淘汰页面的功能，在页表中增加引用位和改变位两个数据项
常用的设备分配技术有独占分配、共享分配和虚拟分配3种
文件系统中的链接技术，指的是在目录表目之间进行链接
操作系统是由一组资源管理程序组成的，其中文件系统是对软件资源的管理。
UNIX缓冲管理中，使用的队列结构有空闲缓冲区队列和设备缓冲区队列两种
在整个中断向量处理过程中，硬件负责中断响应过程
进程从结构上讲，包括程序、数据和PCB几个部分
一组进程间发生了死锁，这时这些进程都占有资源
用户存取信息是用来进行I/O操作的基本单位