search

alicemare / ideas

用Issue来记录一些简单的笔记？
0 stars 0 forks source link

OS Spring 2019 Weekly Test #11

Open alicemare opened 5 years ago

alicemare commented 5 years ago

在第三次小测前开了这个issue，准备在每次小测前按照老师给的notes内容复习相关专题，并且给出每次小测的内容答案

alicemare commented 5 years ago

预留给整理第一次小测

alicemare commented 5 years ago

预留给整理第二次小测

alicemare commented 5 years ago

第三次小测

Notes March 27

4 CPU Scheduling (continued)

  1. RT scheduling (goal? How?) a) Priority-inheritance protocol b) Priority-ceiling protocol

实时调度

指系统能够在限定的响应时间内提供所需水平的服务，更为接受的说法是

一个实时系统是指计算的正确性不仅取决于程序的逻辑正确性，也取决于结果产生的时间，如果系统的时间约束条件得不到满足，将会发生系统出错。——Donald Gillies

优先级反转现象

目前市面流行的实时操作系统都是采用可抢占式的基于优先级的调度方式，其保证了处于就绪状态的优先级高的任务可以先于优先级低的任务而执行。但这并不是绝对的，优先级反转是实时系统中的一个经典特例。其大体流程如下： 假设系统中有3个task，优先级分别为高、中、低，以task_high,task_middle,task_low代称

  1. 一开始，task_high,task_middle处于挂起状态，task_low在运行
  2. task_low要访问共享资源，获取了一个信号量semaphore
  3. 这之后task_high等待的事件到来，task_high抢占了task_low开始运行，在运行过程中，也需要访问同一共享资源，所以也要去拿semaphore，由于它已经被task_low取得，所以task_high再次被挂起。
  4. task_low继续运行
  5. task_middle等待的事件这时候到来，它从task_low手里抢来了CPU，开始运行
  6. task_middle运行结束或再次挂起，让出CPU
  7. task_low继续运行，完成共享资源的访问，释放semaphore

  8. task_high获得semaphore，得以继续运行。

    task_middle的优先级是低于task_high的，原则上应该是task_high优先获得CPU得到执行。但是在这个过程中，由于共享资源的竞争访问，导致了高优先级的任务并不能被优先调度，执行的顺序看起来好像是高优先级任务task_high和中优先级任务task_middle，两者之间的优先级调换了，反转了一样。

    最差的情况，task_middle执行的是一个耗时的操作，或者task_middle不是一个任务，而是一堆优先级处于task_low和task_high之间，正好在这期间需要运行呢？那那task_low始终无法释放信号量，task_high也要被delay很久才能获得CPU。

    优先级继承协议

优先级继承暂时地将互斥量持有者的优先级提升至所有等待此互斥量的任务所具有的最高优先级。持有互斥量的低 优先级任务”继承”了等待互斥量的任务的优先级。互斥量持有者在归还互斥量时，优先级会自动设置为其原来的优先级。

优先级天花板协议

给每个信号量设置一个优先级天花板，优先级天花板的值大于所有使用该信号的任务的优先级，当某个任务得到该信号量时，将其优先级置为优先级天花板的值。

两种协议小结

优先级继承和优先级天花板，目的都是使得到信号量的任务的优先级，不低于其他在等待该信号量的任务的优先级，由此，当该任务释放资源后，任务结束前，也不会被其他较高优先级任务抢占，也就保障了如果有高优先级任务在等待该资源，那么该任务结束后高优先级任务立即就可使用该资源。

5 Thread

1) 4.1.1 Thread (What? Why?) 2) 4.1.2 Benefits (Responsiveness; resource sharing; economy; utilization of MP arch.) 3) 4.2 multithreading models (to be continued) a) User threads VS. kernel threads

什么是线程，为什么需要线程

先来看一篇通俗易懂的解释，进程和线程的关系

转自阮一峰

1.计算机的核心是CPU，它承担了所有的计算任务。它就像一座工厂，时刻在运行。

2.假定工厂的电力有限，一次只能供给一个车间使用。也就是说，一个车间开工的时候，其他车间都必须停工。背后的含义就是，单个CPU一次只能运行一个任务。

3.进程就好比工厂的车间，它代表CPU所能处理的单个任务。任一时刻，CPU总是运行一个进程，其他进程处于非运行状态。

4.一个车间里，可以有很多工人。他们协同完成一个任务。

5.线程就好比车间里的工人。一个进程可以包括多个线程。

6.车间的空间是工人们共享的，比如许多房间是每个工人都可以进出的。这象征一个进程的内存空间是共享的，每个线程都可以使用这些共享内存。

7.可是，每间房间的大小不同，有些房间最多只能容纳一个人，比如厕所。里面有人的时候，其他人就不能进去了。这代表一个线程使用某些共享内存时，其他线程必须等它结束，才能使用这一块内存。

8.一个防止他人进入的简单方法，就是门口加一把锁。先到的人锁上门，后到的人看到上锁，就在门口排队，等锁打开再进去。这就叫"互斥锁"（Mutual exclusion，缩写 Mutex），防止多个线程同时读写某一块内存区域。

9.还有些房间，可以同时容纳n个人，比如厨房。也就是说，如果人数大于n，多出来的人只能在外面等着。这好比某些内存区域，只能供给固定数目的线程使用。

10.这时的解决方法，就是在门口挂n把钥匙。进去的人就取一把钥匙，出来时再把钥匙挂回原处。后到的人发现钥匙架空了，就知道必须在门口排队等着了。这种做法叫做"信号量"（Semaphore），用来保证多个线程不会互相冲突。

不难看出，mutex是semaphore的一种特殊情况（n=1时）。也就是说，完全可以用后者替代前者。但是，因为mutex较为简单，且效率高，所以在必须保证资源独占的情况下，还是采用这种设计。

11.操作系统的设计，因此可以归结为三点：

（1）以多进程形式，允许多个任务同时运行；

（2）以多线程形式，允许单个任务分成不同的部分运行；

（3）提供协调机制，一方面防止进程之间和线程之间产生冲突，另一方面允许进程之间和线程之间共享资源。

（完）

线程的定义和理解

线程（thread）是操作系统能够进行运算调度的最小单位。它被包含在进程之中，是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流，一个进程中可以并发多个线程，每条线程并行执行不同的任务。在Unix System V及SunOS中也被称为轻量进程（lightweight processes），但轻量进程更多指内核线程（kernel thread），而把用户线程（user thread）称为线程。

同一进程中的多条线程将共享该进程中的全部系统资源，如虚拟地址空间，文件描述符和信号处理等等。但同一进程中的多个线程有各自的调用栈（call stack），自己的寄存器环境（register context），自己的线程本地存储（thread-local storage）。

一个进程可以有很多线程，每条线程并行执行不同的任务。

使用线程的优点：

在多核或多CPU，或支持Hyper-threading的CPU上使用多线程程序设计的好处是显而易见，即提高了程序的执行吞吐率。在单CPU单核的计算机上，使用多线程技术，也可以把进程中负责I/O处理、人机交互而常被阻塞的部分与密集计算的部分分开来执行，编写专门的workhorse线程执行密集计算，从而提高了程序的执行效率。

源自知乎线程和进程的区别是什么？ - zhonyong的回答 - 知乎 进程和线程都是一个时间段的描述，是CPU工作时间段的描述 如果考虑到进程是CPU分配资源最小单位，线程是CPU调度的最小单位及CPU的调度处理 可以得出 进程就是包换上下文切换的程序执行时间总和 = CPU加载上下文+CPU执行+CPU保存上下文 线程是什么呢？进程的颗粒度太大，每次都要有上下的调入，保存，调出。如果我们把进程比喻为一个运行在电脑上的软件，那么一个软件的执行不可能是一条逻辑执行的，必定有多个分支和多个程序段，就好比要实现程序A，实际分成 a，b，c等多个块组合而成。那么这里具体的执行就可能变成： 程序A得到CPU -> CPU加载上下文，开始执行程序A的a小段，然后执行A的b小段，然后再执行A的c小段，最后CPU保存A的上下文。 这里a，b，c的执行是共享了A的上下文，CPU在执行的时候没有进行上下文切换的。这里的a，b，c就是线程，也就是说线程是共享了进程的上下文环境，的更为细小的CPU时间段

线程的属性

多线程操作系统中，进程已经不是可执行的最小实体，所谓的进程处于运行态，实际是进程中某线程在执行。线程的属性如下

  1. 线程是一个轻型实体，它不拥有系统资源，但每个线程都应有一个唯一的标识符和一个线程控制块，线程控制块记录了线程执行的寄存器和栈等现场状态。
  2. 不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统为它们创建成不同的线程。
  3. 同一进程中的各个线程共享该进程所拥有的资源。
  4. 线程是处理机的独立调度单位，多个线程是可以并发执行的。在单CPU的计算机系统中，各线程可交替地占用CPU；在多CPU的计算机系统中，各线程可同时占用不同的CPU，若各个CPU同时为一个进程内的各线程服务则可缩短进程的处理时间。
  5. —个线程被创建后便开始了它的生命周期，直至终止，线程在生命周期内会经历阻塞态、就绪态和运行态等各种状态变化。
线程的实现

线程的实现可以分为两类：用户级线程(User-LevelThread, ULT)和内核级线程(Kemel-LevelThread, KLT)。内核级线程又称为内核支持的线程。

在用户级线程中，有关线程管理的所有工作都由应用程序完成，内核意识不到线程的存在。应用程序可以通过使用线程库设计成多线程程序。通常，应用程序从单线程起始，在该线程中开始运行，在其运行的任何时刻，可以通过调用线程库中的派生例程创建一个在相同进程中运行的新线程。图2-2(a)说明了用户级线程的实现方式。

在内核级线程中，线程管理的所有工作由内核完成，应用程序没有进行线程管理的代码，只有一个到内核级线程的编程接口。内核为进程及其内部的每个线程维护上下文信息，调度也是在内核基于线程架构的基础上完成。图2-2(b)说明了内核级线程的实现方式。

在一些系统中，使用组合方式的多线程实现。线程创建完全在用户空间中完成，线程的调度和同步也在应用程序中进行。一个应用程序中的多个用户级线程被映射到一些（小于或等于用户级线程的数目）内核级线程上。下图(c)说明了用户级与内核级的组合实现方式。

Notes March 29 April 03

5 Thread (continued)

1) 4.2 multithreading models a) User threads VS. kernel threads b) N:1; 1:1; N:M; two-level 2) 4.3 Thread Libraries (POSIX; Win32; Java) 3) 5.5 Thread scheduling a) LWP; local scheduling; global scheduling

多线程模型

多线程模型，即实现用户级线程和内核级线程的连接方式。

用户线程和内核线程

用户线程大概就是普通应用程序内部的线程了吧

特点如下：

  1. 用户线程在用户空间中实现，内核并没有直接对用户线程进程调度，内核的调度对象和传统进程一样，还是进程（用户进程）本身，内核并不能看到用户线程，内核并不知道用户线程的存在。

  2. 不需要内核支持而在用户程序中实现的线程，其不依赖于操作系统核心，应用进程利用线程库提供创建、同步、调度和管理线程的函数来控制用户线程。

  3. 内核资源的分配仍然是按照进程（用户进程）进行分配的；各个用户线程只能在进程内进行资源竞争。

  4. 用户级线程内核的切换由用户态程序自己控制内核切换（通过系统调用来获得内核提供的服务）,不需要内核干涉，少了进出内核态的消耗，但不能很好的利用多核Cpu。目前Linux pthread大体是这么做的。

  5. 每个用户线程并不具有自身的线程上下文。因此，就线程的同时执行而言，任意给定时刻每个进程只能够有一个线程在运行，而且只有一个处理器内核会被分配给该进程。

内核线程（kernel thread）是直接由内核本身启动的进程，内核线程实际上是将内核函数委托给独立的进程，与系统中其他进程『并行』执行。内核线程经常被称之为守护进程。它们用于执行下列任务：

  1. 周期性地将修改的内存页与页面来源块设备同步。
  2. 如果内存页很少使用，则写入交换区。
  3. 管理延时动作。
  4. 实现文件系统的事物日志。

基本上，有两种类型的内核线程：

  1. 线程启动后一直等待，直至内核请求线程执行某一特定的操作。
  2. 线程启动后按周期性间隔运行，监测特定的资源使用，在用量超出或者低于预置的限制时采取行动。

这些任务包括刷新磁盘高速缓存，交换出不用的页框，维护网络连接等等。实际上，如果以严格的线性方式执行这些任务效率不高，如果把它们放在后台调度，则会有较好的效率。这些任务委托给内核线程，内核线程不受不必要的用户态上下文的拖累

内核线程的特点有：

  1. 内核线程又称为守护进程，内核线程的调度由内核负责，一个内核线程处于阻塞状态时不影响其他的内核线程，因为其是调度的基本单位。这与用户线程是不一样的；

  2. 这些线程可以在全系统内进行资源的竞争；

  3. 内核空间内为每一个内核支持线程设置了一个线程控制块（TCB），内核根据该控制块，感知线程的存在，并进行控制。在一定程度上类似于进程，只是创建、调度的开销要比进程小。有的统计是1：10。

  4. 内核线程切换由内核控制，当线程进行切换的时候，由用户态转化为内核态。切换完毕要从内核态返回用户态，即存在用户态和内核态之间的转换，比如多核cpu，还有win线程的实现。

1) 多对一模型

将多个用户级线程映射到一个内核级线程，线程管理在用户空间完成。

此模式中，用户级线程对操作系统不可见（即透明）。

优点：线程管理是在用户空间进行的，因而效率比较高。

缺点：当一个线程在使用内核服务时被阻塞，那么整个进程都会被阻塞；多个线程不能并行地运行在多处理机上。

2) 一对一模型

将每个用户级线程映射到一个内核级线程。

优点：当一个线程被阻塞后，允许另一个线程继续执行，所以并发能力较强。

缺点：每创建一个用户级线程都需要创建一个内核级线程与其对应，这样创建线程的开销比较大，会影响到应用程序的性能。

3) 多对多模型

将 n 个用户级线程映射到 m 个内核级线程上，要求 m <= n。

特点：在多对一模型和一对一模型中取了个折中，克服了多对一模型的并发度不高的缺点，又克服了一对一模型的一个用户进程占用太多内核级线程，开销太大的缺点。又拥有多对一模型和一对一模型各自的优点

线程库

大概就是POSIX，win，Java对于多线程实现的接口

线程调度

线程调度是系统为线程分配处理器使用权的过程，主要的调度方式有两种，协同式线程调度和抢占式线程调度。

协同式线程调度

使用协同式线程调度的多线程系统，线程的执行时间由线程本身控制。线程将自己的工作做完后，要主动通知系统切换到另一个线程。

抢占式线程调度

使用抢占式线程调度的多线程系统，每个线程由操作系统分配执行时间，线程切换不由线程来决定（Java 中，可以通过 Thread.yield() 让出执行时间，当然不一定管用）。

LWP(轻量级进程)

轻量级进程（LWP）是计算机操作系统中一种实现多任务的方法。

在计算机操作系统中,轻量级进程（LWP）是一种实现多任务的方法。与普通进程相比，LWP与其他进程共享所有（或大部分）它的逻辑地址空间和系统资源；与线程相比，LWP有它自己的进程标识符，优先级，状态，以及栈和局部存储区，并和其他进程有着父子关系；这是和类Unix操作系统的系统调用vfork()生成的进程一样的。另外，线程既可由应用程序管理，又可由内核管理，而LWP只能由内核管理并像普通进程一样被调度。Linux内核是支持LWP的典型例子。

在大多数系统中，LWP与普通进程的区别也在于它只有一个最小的执行上下文和调度程序所需的统计信息，而这也是它之所以被称为轻量级的原因。一般来说，一个进程代表程序的一个实例，而LWP代表程序的执行线程（其实，在内核不支持线程的时候，LWP可以很方便地提供线程的实现）。因为一个执行线程不像进程那样需要那么多状态信息，所以LWP也不带有这样的信息。

LWP的一个重要作用是提供了一个用户级线程实现的中间系统。LWP可以通过系统调用获得内核提供的服务，因此，当一个用户级线程运行时，只需要将它连接到一个LWP上便可以具有内核支持线程的所有属性。

而因为LWP之间共享它们的大部分资源，所以它在某些应用程序就不适用了；这个时候就要使用多个普通的进程了。例如，为了避免内存泄漏（a process can be replaced by another one）和实现特权分隔（processes can run under other credentials and have other permissions）。

使用多个进程也使得应用程序在出现进程池内的进程崩溃或被攻击的情况下变得更加健壮。

6 Process synchronization

1) 6.1 Background (Data inconsistency; race condition) 2) 6.2 the critical-section problem (CS problem) a) Critical resources b) Critical section; entry section; exit section; remainder section c) What requirements must a solution to the CS problem satisfy? 3) 6.4 Synchronization Hardware a) Disable/enable interrupts b) Atomic HW instructions: TestAndSet; Swap 4) 6.5 Semaphores 5) 6.6 Classic problems of synchronization (not finished) a) PC problem b) RW problem

进程同步

Process Synchronization means sharing system resources by processes in a such a way that, Concurrent access to shared data is handled thereby minimizing the chance of inconsistent data. Maintaining data consistency demands mechanisms to ensure synchronized execution of cooperating processes. 我们把异步环境下的一组并发进程因直接制约而互相发送消息、进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。进程同步要解决的就是多任务可能导致的数据不一致的问题

CSproblem

临界区问题

A Critical Section is a code segment that accesses shared variables and has to be executed as an atomic action.

临界资源，临界区，退出区，剩余区

把一次仅允许一个进程使用的资源称为临界资源。许多物理设备都属于临界资源，如打印机等。此外，还有许多变量、数据等都可以被若干进程共享，也属于临界资源。

对临界资源的访问，必须互斥地进行，在每个进程中，访问临界资源的那段代码称为临界区。为了保证临界资源的正确使用，可以把临界资源的访问过程分成四个部分：

  1. 进入区。为了进入临界区使用临界资源，在进入区要检查可否进入临界区，如果可以进入临界区，则应设置正在访问临界区的标志，以阻止其他进程同时进入临界区。

  2. 临界区。进程中访问临界资源的那段代码，又称临界段。

  3. 退出区。将正在访问临界区的标志清除。

  4. 剩余区。代码中的其余部分

    A solution to critical section problem must satisfy the following requirements:

  5. Mutual exclusion: When a thread is executing in its critical section, no other threads can be executing in their critical sections.

  6. Progress: If no thread is executing in its critical section, and if there are some threads that wish to enter their critical sections, then one of these threads will get into the critical section.

  7. Bounded waiting: After a thread makes a request to enter its critical section, there is a bound on the number of times that other threads are allowed to enter their critical sections, before the request is granted.

    硬件同步

    计算机提供了特殊的硬件指令，允许对一个字中的内容进行检测和修正，或者是对两个字的内容进行交换等。通过硬件支持实现临界段问题的低级方法或称为元方法。

    中断屏蔽

    当一个进程正在使用处理机执行它的临界区代码时，要防止其他进程再进入其临界区访问的最简单方法是禁止一切中断发生，或称之为屏蔽中断、关中断。因为CPU只在发生中断时引起进程切换，这样屏蔽中断就能保证当前运行进程将临界区代码顺利地执行完，从而保证了互斥的正确实现，然后再执行开中断。其典型模式为： …… 关中断; 临界区; 开中断; ……

这种方法限制了处理机交替执行程序的能力，因此执行的效率将会明显降低。对内核来说，当它执行更新变量或列表的几条指令期间关中断是很方便的，但将关中断的权力交给用户则很不明智，若一个进程关中断之后不再开中断，则系统可能会因此终止。

硬件指令方法

TestAndSet指令：这条指令是原子操作，即执行该代码时不允许被中断。其功能是读出指定标志后把该标志设置为真。指令的功能描述如下：

boolean TestAndSet(boolean *lock){
    boolean old;
    old = *lock;
    *lock=true;
    return old;
}

可以为每个临界资源设置一个共享布尔变量lock，表示资源的两种状态：true表示正被占用，初值为false。在进程访问临界资源之前，利用TestAndSet检查和修改标志lock；若有进程在临界区，则重复检查，直到进程退出。利用该指令实现进程互斥的算法描述如下：

while TestAndSet (& 1 ock);
// 进程的临界区代码段;
lock=false;
// 进程的其他代码

Swap指令：该指令的功能是交换两个字节的内容。其功能描述如下。

Swap(boolean *a, boolean *b){  
    boolean temp;
    Temp=*a;
    *a = *b;
    *b = temp;
}

注意：以上对TestAndSet和Swap指令的描述仅仅是功能实现，并非软件实现定义，事实上它们是由硬件逻辑直接实现的，不会被中断。

应为每个临界资源设置了一个共享布尔变量lock，初值为false；在每个进程中再设置一个局部布尔变量key，用于与lock交换信息。在进入临界区之前先利用Swap指令交换lock 与key的内容，然后检查key的状态；有进程在临界区时，重复交换和检查过程，直到进程退出。利用Swap指令实现进程互斥的算法描述如下：

key=true;
while(key!=false)
Swap(&lock, &key); 
// 进程的临界区代码段；
lock=false;
// 进程的其他代码；

硬件方法的优点：适用于任意数目的进程，不管是单处理机还是多处理机；简单、容易验证其正确性。可以支持进程内有多个临界区，只需为每个临界区设立一个布尔变量。

硬件方法的缺点：进程等待进入临界区时要耗费处理机时间，不能实现让权等待。从等待进程中随机选择一个进入临界区，有的进程可能一直选不上，从而导致“饥饿”现象。

信号量

信号量机构是一种功能较强的机制，可用来解决互斥与同步的问题，它只能被两个标准的原语wait(S)和signal(S)来访问，也可以记为“P操作”和“V操作”。

原语是指完成某种功能且不被分割不被中断执行的操作序列，通常可由硬件来实现完成不被分割执行特性的功能。如前述的“Test-and-Set”和“Swap”指令，就是由硬件实现的原子操作。原语功能的不被中断执行特性在单处理机时可由软件通过屏蔽中断方法实现。

原语之所以不能被中断执行，是因为原语对变量的操作过程如果被打断，可能会去运行另一个对同一变量的操作过程，从而出现临界段问题。如果能够找到一种解决临界段问题的元方法，就可以实现对共享变量操作的原子性。

alicemare commented 5 years ago

第四次小测

April10 April12

6 Process synchronization

1) 6.6 Classic problems of synchronization(continued) a) PC problem b) RW problem c) DP problem 2) 6.7 Monitors

7 Deadlock

1) 7.1 System model 2) 7.2 Deadlock characterization a) 7.2.1 necessary conditions: mutual exclusion, hold and wait, no preemption, circular wait b) 7.2.2 Resource-Allocation Graph(what, cycle VS deadlock) 3) 7.3 Methods for handling deadlocks a) Prevention b) Avoidance c) Detection and recovery d) (cheapest) ignore 4) 7.4 Deadlock prevention a) 7.4.1 mutual exclusion i. Non shareable resources: must hold; printer; hard to break,how? ii. Shareable resources: need not; read-only files; b) 7.4.2 hold and wait i. allocated all only once before execution ii. request only when it has none iii. disadvantage: unused for along period;starvation c) 7.4.3 No preemption i. if request failed, those already held are preempted ii. preempt from waiting processes iii. limitation: only suitable for those resources whose state can be easily saved/restored d)7.4.4 Circular wait i.only increasing order ii.increasing order+release higher iii.difficult:ordering) 5) 7.5 Deadlock avoidance a) 7.5.1 Safe state(safe sequence) b) 7.5.2 Resource-allocation graph algorithm c) 7.5.3 Banker’s algorithm 6) 7.6 Deadlock detection and 7.7 Recovery from deadlock a) 7.6.1 Single instance of each resource type(wait-for graph) b) 7.6.2 Several instances of are source type c) 7.6.3 detection-algorithm usage (how often?How many?)