OS2019_winter

发表于 | 分类于 | 阅读量： 次

前言

经一年半的学习，发现计科本科生课程中与计算机原理相关的课程多是隔靴搔痒，用到时再查书/百度也不迟，故接下来的课程中将关注点放在各章的开头1~2节，若有兴趣再继续深入。

参考书目：《操作系统教程（第5版）》费翔林

第一章 操作系统概论

PPT内容主要讲述以下问题：

1. 单道/多道程序的CPU效率问题。

2. 对于一个操作系统来说，它要有哪些功能？

3. 从发明至今，有哪些操作系统，特点是什么？

第三章 同步、通信与死锁

PPT内容主要讲述以下问题：

什么是并发进程

并发进程与时间无关的充分条件Bernstein条件

Bernstein条件：

设进程A引用变量集合为R1，改变变量集合为W1，进程B引用变量集合为R2，改变变量集合为W2。那么只要满足：

(R1 ∩ W2) ∪ (R2 ∩ W1) ∪ (W1 ∩ W2) = ∅

那么进程A和进程B与时间无关。

简而言之就是A和B的读写不冲突，也不会往同一个变量里写。

并发进程间的交互：

  • 竞争关系/间接制约关系：对于同一资源区，进程互斥访问，一个进程在用资源区的时候，其他进程只能等着
  • 协作关系/直接制约关系：进程间互发信号控制对方是沉睡还是唤醒

并发进程引起的时间问题：

  • 结果不唯一，比如订票，抢红包
  • 永远等待

临界区(critial section)是什么？

定义：共享资源所在程序段

调度原则：

  • 一次只能进一个
  • 里面的，不能一直呆在里面
  • 外面的，不能一直等在外面
  • 有空让进，无空等待，择一而入，算法可行

临界区管理方法：

  • 先检测，后置位。弊端是检测完后可能有其他进程也进入临界区。

    1
    2
    3
    4
    5
    6
    7
    8
    inside1, inside2: Boolean
    inside1 = false;
    inside2 = false;
    for process P1:
    while inside2; //等待P2退出临界区
    inside1 = true;
    临界区;
    inside1 = false;

  • 先置位，后检测。弊端是置位后可能inside2又被置1，可能永远等待。

    1
    2
    3
    4
    5
    for process P1:
    inside1 = true;
    while inside2; //等待P2退出临界区
    临界区;
    inside1 = false;

临界区管理软件方法：

  1. Dekker算法

    基本思想：

    1. 进程P1进入临界区时，将inside1置为true。
    2. 若P2在临界区，则P1等待。若P2不在临界区但也想进入，询问turn变量，由turn指示谁进入。若P2不在临界区且不想进入临界区，那么P1进入临界区。

    代码：

    1
    2
    > TODO
    >

  2. Peterson算法

    基本思想：

    1. 进程P1进入临界区时，将inside1置为true，指示器turn置为2。
    2. 若P2在临界区内且turn为2，则P1等待。否则P1进入临界区，然后inside1置为false。

    代码：

    1
    2
    > TODO
    >

临界区管理硬件方法：

  1. 关中断

    进入临界区前关中断，进入临界区，出临界区后开中断

  2. 用TS指令(test and set)

    反复TS代表临界区的lock变量，即“上锁”，如果该临界区空闲，会返回true，否则返回false。如果空闲，就进入临界区，否则一直反复。出临界区后lock置为true，即“开锁”。

    TS(x)指令等价于这段代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    bool TS(bool &x) {
        if(x == true){
            x = false;
            return true;
        }
        else{
            return false;
        }
    }

  3. 用SWAP指令(在x86-64架构下是XCHG指令)

    一开始置临界区的lock变量为false，进程P的变量为key，置为true。交换一次lock和key(“上锁”)就检测一次key，如果key为false，说明临界区此时为空闲，进入临界区，出来后再次交换lock和key，即“开锁”。

    代码：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    bool lock = false;
    cobegin
        process P() {
            bool key = true;
            do{
                SWAP(key, lock);    //上锁
            } while(key);
            临界区;
            SWAP(key, lock);        //开锁
        }
    coend

进程同步问题

书上没讲定义，按我的理解就是对共享资源的读写一致性问题，说白了还是前面的并发进程问题没解决呗。

百度说，进程同步是指的进程相互协作、等待的过程。

同步的办法有3种，信号量与PV操作、管程、消息传递。

信号量与PV操作

信号量用来表示一个物理资源的使用情况，PV操作用来控制资源使用。

同步原语：P(Proberen,测试)，V(Verhogen,增量)。

除了赋初值外，信号量只能由同步原语操作。

(所谓原语，就是一段在执行过程中不许中断的指令序列)

管程

进程通信

死锁问题

具体问题的解决方案

  • 生产者-消费者问题
  • 五个哲学家吃通心面问题
  • 读者-写者问题
  • 理发师问题

课程简介

成绩组成

平时作业：10%
实验：30%
期中：10%
期末：50%

实验类似PA，阶段之间有联系，硬DDL
期中讲完3章考

第一章 操作系统概述

杂记

一些敏感系统不用操作系统的原因：

  1. 直接汇编放内存速度快
  2. 防止出错？？

裸机：未安装操作系统的计算机

操作系统的主要目标：

  1. 扩大机器功能
  2. 管理系统资源
  3. 提高系统效率
  4. 构筑开发环境
  5. 方便用户使用

资源管理技术：复用、虚拟、抽象

资源复用

空分复用共享

例如，将内存、磁盘，按4KB一页划分，分配给不同进程。

时分复用共享

时分独占式：
进程1使用一个完整周期后才释放资源。

时分共享式：
例如，将CPU使用时间分为若干个时间片，进程1使用第1、3、5片，进程2使用第2、4、6片…

资源虚拟

把物理资源变成逻辑上的多个对应物。
例如，计算机连接到打印机，发送打印命令时，先发到虚拟的打印机，等一个打印文件完全发到虚拟打印机后，物理打印机才开始打印。有多个文件请求打印时，进入虚拟的打印机的队列。

资源抽象

用软件来屏蔽硬件实现细节，只要调用API就行了

操作系统：管理计算机硬件资源的系统软件，为用户提供交互界面，提升硬件使用效率，主要方法是复用、虚拟和抽象。
2019-2-26

认识操作系统的四种观点

服务用户观点

系统调用向API提供服务

操作系统提供良好的人机界面

进程交互观点

操作系统作为进程执行的控制者和执行者

  • OS需要提供机制，解决并发进程的互斥、同步、通信和死锁问题

系统实现观点

操作系统作为扩展机或虚拟机，把硬件的复杂性与用户隔离开来。

  • 把操作系统分为若干层次，逐步添加到裸机上，系统功能就能增加一点形成操作系统虚拟机
  • 扩充后的虚拟机不仅能使用硬件指令，还能使用系统指令

资源管理观点

操作系统对软硬件资源进行资源复用、虚拟和抽象

管理各种资源

操作系统功能

处理器管理

多道程序设计，提高处理器效率。

存储管理

主要是管理内存，包括

  • 内存分配
  • 地址转换
  • 存储保护
  • 内存共享
  • 存储扩充

设备管理

主要任务

  • 管理外设
  • 发挥设备的并行性
  • 提供设备驱动程序和中断处理程序

核心功能

  • 设备中断处理
  • 缓冲区管理
  • 设备独立性
    • 实现逻辑设备到物理设备之间的映射
  • 设备的分配和回收
  • 共享型设备的驱动调度
  • 虚拟设备

文件管理

对用户文件和系统文件进行管理

  • 文件逻辑组织方法
  • 文件物理组织方法
  • 文件存取和使用方法
  • 文件目录管理
  • 文件共享和安全性控制

网络与通信管理

通过网络协议进行管理

操作系统主要特性

并发性

并发：指的是两个或两个以上的事件在同一时间间隔内（比如1分钟内）发生
并行：在同一时刻发生

要求实现多个进程间的安全切换

共享性

解决读写一致问题、临界区之类的问题

异步性

进程的开始、暂停、前进速度都是随机的

作业到达系统的类型和时间是随机的

操作员发命令或按按钮的时刻是随机的

程序出错是随机的

软硬件中断是随机的

所以需要解决和时间有关的错误

多道程序设计效果

  1. 提高了系统效率

  2. 延长了每道题的计算时间

  3. 牺牲了用户的响应时间

假设程序等待IO的时间占其运行时间比为p，n道程序同时等待的概率是$p^n$，那么CPU效率是$1-p^n$。

批处理操作系统

作业是指把程序、数据连同作业说明书组织起来的任务单位

批作业是指把批中的作业预先输入作业队列，由操作系统按照说明来调度和控制作业执行，形成自动转接和连续处理作业。

特点：

  • 用户脱机工作
  • 成批处理作业
  • 多道程序运行
  • 作业周转时间长

分时操作系统

  • 多个联机用户同时使用一个计算机系统在各自的终端上进行交互式对话
  • 程序、数据和命令都在会话过程中产生，通过问答方式控制程序
  • 处理器分为时间片给不同用户

实时操作系统

  • 外部事件产生时，快速处理

地址转换

2019-2-28

操作系统基本服务和用户接口

基本服务和用户接口

基本服务

  • 创建程序
  • 执行程序
  • 数据IO
  • 通信服务
  • 错误检测和处理
  • 资源分配、统计、保护

程序接口与系统调用

各种Linux版本之间相同点在于内核，内核只有版本号不一样。即内核版本相同的ubuntu和debian，能支持一样的软件。

用户态->内核态通过IDT，内核态->用户态iret

异常分类：

  • 故障(fault)：可恢复错误
  • 陷阱(trap)：用户态->内核态
  • 终止(abort)：不可恢复错误，不返回

POSIX标准：
规定操作系统必须提供API，未规定接口的实现是采用系统调用、库函数还是其他形式。

函数库：

  • 静态库：编译时把库函数作为代码的一部分，生成bin
  • 动态库/共享库：如DLL，编译时只给出入口地址，运行到这才加载

系统调用时的过程、内核栈

区分系统调用过程中的中断向量号和系统调用号：压栈时取反再压

禁用一个syscall: sys_ni_syscall

添加一个syscall: 看ppt

操作接口

作业控制方式：

  • 联机：有命令行交互，人敲一句机器干一句/处理一个.bat文件
  • 脱机：用JCL(job control language)语言把作业说明书塞给机器，然后人走了机器继续干活

系统程序

运行于用户态

分类：

  • 文件管理
  • 状态信息
  • 对编程语言的支持

操作系统结构与运行模型

结构分类

  • 单体式：模块组合，互相接口，可以互相调用，数据是全程量，缺点：牵一发而动全身
  • 层次式：分中断-内存-进程-IO（不全）等等多层，自下到顶
  • 微内核：仅具有很少的必要功能，很小
  • 虚拟机：用一个物理机模拟另一个物理机，通过分时使用管理多台机器。CMS?用户交互CMS，CMS交互硬件。

原语不可中断

单内核功能多，效率高，但修改之后要重新编译
微内核容量小，额外功能都通过服务来完成，不用重新编译

Linux的做法：可加载内核模块，需要的时候像零件一样装上去拆下来，不用重新编译整个内核

Linux中断处理

中断分快中断和慢中断

x86提供了15根 IRQ 线，但可以接入的设备不止15台，连到同一根 IRQ 线的设备有不同的中断服务例程

最早的“下半部”实现机制：bottom half，静态创建，32个元素的链表，全局同步，不允许在任何两个 BH 同时执行