【操作系统学习笔记】进程与线程(二)调度程序激活机制与上行调用

简介: 本文为个人学习操作系统的笔记。
本文首发于稀土掘金。该平台的作者 逐光而行 也是本人。

调度程序激活机制(scheduler activation)

  • 目标:为线程包提供用户态才能实现的高性能和灵活性,并模拟内核态的功能。
  • 实现:内核给每个进程安排一定数量的虚拟处理器,用户态运行时系统将线程分配到处理器上。进程可申请更多处理器,用时分配,不用时退回。

上行调用

  • 概念:内核了解到一个线程被阻塞后,通知该进程的运行时系统,并在堆栈中以参数形式传递有问题的线程编号和所发生事件的描述。这种通过在已知起始地址启动运行时系统并发出通知的机制被称为上行调用,这是对信号的一种粗略模拟。

(读者注:我个人读完原著相关文字描述之后,觉得上行调用并不是仅指我加粗字上的那回事。上行调用应该是一个抽象的概念,而这里列举出的概念只是一个示例而已。上行调用应该词如其名,即逆常规。比如在金字塔结构中,下层为上层提供服务,上层是下层的抽象,但是上行调用则相反,它往上调用,让上层为下层提供服务)

两者关系

调度程序激活机制的目标是作为上行调用的信赖基础。

使单线程代码多线程化会遇到的问题及解决方案

全局变量的冲突

  • 问题:对线程而言是全局变量,但对整个程序而言并不是。
  • 解决方案:

    • 全面禁止全局变量(不太现实)
    • 为每个线程赋予其私有的全局变量

    (即线程的属性中可增加一个全局变量)

访问私有全局变量

  • 为全局变量分配一块内存,并以额外参数的形式传到线程中的每个过程。
  • 引入新的库过程,该调用会在堆或转为线程保留的特殊区域上为指针分配存储空间,只有线程才可访问其全局变量。及时另一个线程创建了同名全局变量,也会因为地址不同无法访问。

库过程的不可重入性

例子1:

网络发送消息,线程切换后,缓冲区被覆盖

例子2:

内存分配,指针指向不定,容易导致空指针异常引起程序崩溃

可能的解决方案:

为每个过程提供一个包装器,其中设置二进制标志位标志正在使用,在此期间其他线程无法占用。

哪个线程应该捕捉信号

堆栈的管理

线程有自己的堆栈,一个进程有多个线程。因为多线程的存在,内核无法掌握所有的堆栈情况,分配的堆栈跟不上实际需要的堆栈,会导致栈出错。

总结

给已有系统进入线程而不实质性重新设计系统是不可行的!

进程间通信

要解决的问题

  • 规定进程如何将信息传递给另一个。
  • 如果保证两个或多个进程在关键活动中不会出现交叉。
  • 上述问题也适用于线程。(个人理解:因为本质上线程是进程的一部分)

竞争条件

两个或多个进程读写某些共享数据,而最后的结果取决于进程运行的精确时序。

临界区

对共享内存进行访问的程序片段。

解决方案:使两个进程不同时处于临界区中,即能避免竞争条件。

进阶要求:保证并发正确且高效

  • 不事先对CPU的速度和数量作任何假设
  • 临界区外的进程不得阻塞其他进程
  • 不得使进程无限制等待进入临界区

实现互斥

屏蔽中断

单处理系统中,使每个进程在刚进入临界区后立即屏蔽其所有中断。

  • 缺点:这相当于是把中断权利交给用户进程,屏蔽中断对操作系统本身而言合适,但对用户进程来说并不是。若某个进程屏蔽中断后不再打开,将可能导致整个系统终止;且若数据状态不一致时就发生中断,将导致竞争条件。

设置变量表示锁

每个进程进入临界区前读取锁变量的值,若为0则进入并设其为1,;若为1则等待

  • 缺点:两个进程依然可能 同时 访问临界区,造成竞争条件。(因为它们可能同时读取到了锁的0状态,即使修改值前再次确认值也有相同的问题,有可能a再次确认之后b就去改)

严格轮换法

字面意思,严格按照指定的规则顺序轮换。

  • 缺点:违反了进阶要求的第2条(临界区外的进程不得阻塞其他进程)

三种解法(因其本质一样,效果又比前几种好所以合在一块说)

  • 方法:Peterson解法、TSL指令、XCHG指令
  • 本质:检查想进入临界区的进程是否被允许进入,若不允许,则等待,直到被允许
  • 缺点:忙等待,可能导致优先级反转问题

Peterson解法

#define FALSE 0
#define TRUE 1
#define N 2  //进程数量
int turn;//当前轮到的进程
int interested[N];//当前某个进程是否想进入临界区,想为1,不想为0,初始化为0
void enter_region(int process){
    int other=1-process;//另一个进程的状态
    interested[process]=TRUE;
    turn=process;
    while(turn==process&&interested[other]==TRUE) ;//当前进程执行且另一个进程等待中
}

void leave_region(int process){
    interested[process]=FALSE;
}

注:以下两种需要硬件支持

TSL指令(test and set lock)

将一个内存字lock读到寄存区器RX中,并在该内存地址上存一个非零值。执行TSL的CPU将锁住内存总线,以禁止其他CPU在本指令结束之前访问内存。

注:锁住内存总线并不等于屏蔽中断。

XCHG

本质上和TSL差不多,字面意思:原子性地交换两个位置的内容。

producer-consumer(bounded-buffer)

有可能引发竞争条件的情况:count=0时,调度程序暂停consumer(未睡眠),producer将count增为1后尝试发送wakeup信号唤醒consumer(因为之前count为0,误认为consumer已睡眠);wakeup信号丢失,consumer再次运行时,读取的是先前读到的count=0的值,于是睡眠;producer不断产生新数据,直到缓冲区满,producer最终也陷入睡眠。

  • 解决方案:加一个唤醒等待位(wakeup信号的小仓库),但治标不治本,因为该数量随进程数量增加。

信号量(semaphore)

用一个整型变量累计唤醒次数

信号量如何解决producer-consumer问题

注:代码中的up和down对应wakeup和sleep

#define N 100 //缓冲区中的槽数目 
typedef int semaphore;  
semaphore mutex=1; //对临界区的访问
semaphore empty=N; //缓冲区的空槽数目
semaphore full=0;//满槽数目

void producer(void){
    int item;
    while(1){
        item=produce_item();//该函数没有具体写出,表示产生数据
        down(&empty);//空槽数目减1
        down(&mutex);//进入临界区
        insert_item(item);//表示插入数据到缓冲区中
        up(&mutex);
        up(&full);//满槽数目+1 
    }
} 

void consumer(void){
    int item;
    while(1){
        item=produce_item();//该函数没有具体写出,表示产生数据
        down(&full);//空槽数目减1
        down(&mutex);//进入临界区
        item=remove_item();//表示插入数据到缓冲区中
        up(&mutex);
        up(&empty);//空槽数目+1 
        consume_item(item);//处理数据项 
    }    
}

互斥量

处于加锁或解锁状态,用一个整型表示,0为解锁,其他值为加锁。

Q:如果进程有不连续的地址空间,在Peterson算法、信号量、公共缓冲区中,如何共享turn变量?

  • 共享数据结构
  • 让进程与其他进程共享部分地址空间(若没有,就共享文件)

如果共享大部分地址空间,进程和线程之间的差别就变得模糊起来。不过,区分它们的点依然在于前述提到的进程和线程拥有的属性。

管程(monitor)

管程的示例代码如下:

monitor example
    integer i;
    condition c;
    
    procedure producer();
    ...
    end;
    
    procedure consumer();
    ...
    end;
end monitor;
  • 进程可在任何需要的时候调用管程中的过程,但它们不能在管程之外声明的过程中直接访问管程内的数据结构。
  • 任一时刻管程中只能有一个活跃进程。
  • Java中的同步方法与其他经典管程有本质区别:Java没有内嵌的条件变量。

避免锁

最快的锁是没有锁。

  • 在某些情况下,可以允许 写操作 来更新数据结构,即使还有其他的进程正在使用它。

参考书籍

《现代操作系统》 Andrew S.Tanenbaum,Herbert Bos著,陈向群,马洪兵等译

相关文章
|
17小时前
|
Java 程序员
Java多线程编程是指在一个进程中创建并运行多个线程,每个线程执行不同的任务,并行地工作,以达到提高效率的目的
【6月更文挑战第18天】Java多线程提升效率,通过synchronized关键字、Lock接口和原子变量实现同步互斥。synchronized控制共享资源访问,基于对象内置锁。Lock接口提供更灵活的锁管理,需手动解锁。原子变量类(如AtomicInteger)支持无锁的原子操作,减少性能影响。
15 3
|
1天前
|
调度
进程与线程的区别与联系
进程与线程的区别与联系
|
1天前
|
数据挖掘 调度 开发者
Python并发编程的艺术:掌握线程、进程与协程的同步技巧
并发编程在Python中涵盖线程、进程和协程,用于优化IO操作和响应速度。`threading`模块支持线程,`multiprocessing`处理进程,而`asyncio`则用于协程。线程通过Lock和Condition Objects同步,进程使用Queue和Pipe通信。协程利用异步事件循环避免上下文切换。了解并发模型及同步技术是提升Python应用性能的关键。
|
4天前
|
Linux Shell C语言
Linux进程控制——Linux进程程序替换
Linux进程控制——Linux进程程序替换
12 2
|
4天前
|
消息中间件 分布式计算 物联网
深入理解操作系统之进程与线程管理
操作系统的核心职责之一是进程与线程管理,它关乎系统的效率和稳定性。本文将剖析进程与线程的基本概念、生命周期以及它们在现代操作系统中的实现机制。通过对比分析,我们将揭示进程与线程的区别、优势及其适用场景,并探讨它们对系统性能的具体影响。进一步,文章将讨论进程间通信(IPC)的几种方式,以及同步和异步处理在多任务环境中的重要性。最后,我们将展望未来操作系统在进程与线程管理方面可能的发展趋势。
|
6天前
|
存储 网络协议 算法
【进程与线程】最好懂的讲解
【进程与线程】最好懂的讲解
13 1
|
7天前
|
并行计算 算法 C#
C# Mandelbrot和Julia分形图像生成程序更新到2010-9-14版 支持多线程计算 多核处理器
此文档是一个关于分形图像生成器的介绍,作者分享了个人开发的M-J算法集成及色彩创新,包括源代码和历史版本。作者欢迎有兴趣的读者留言交流,并提供了邮箱(delacroix_xu@sina.com)以分享资源。文中还展示了程序的发展历程,如增加了真彩色效果、圈选放大、历史记录等功能,并分享了几幅精美的分形图像。此外,还提到了程序的新特性,如导入ini文件批量输出图像和更新一批图片的功能。文档末尾附有多张程序生成的高分辨率分形图像示例。
|
10天前
|
安全 开发者 Python
Python中的多线程与多进程编程
Python作为一种广泛使用的编程语言,在处理并发性能时具有独特的优势。本文将深入探讨Python中的多线程与多进程编程技术,分析其原理和应用,帮助读者更好地理解并发编程在Python中的实现与优化。
|
4天前
|
存储 缓存 安全
Linux基础——冯诺依曼体系结构与操作系统
Linux基础——冯诺依曼体系结构与操作系统
24 1
Linux基础——冯诺依曼体系结构与操作系统
|
5天前
|
网络协议 Linux 数据安全/隐私保护
【Linux操作系统】权限管理和粘滞位
【Linux操作系统】权限管理和粘滞位
【Linux操作系统】权限管理和粘滞位