精华内容
下载资源
问答
  • Windows 进程进入临界区调度原则

    千次阅读 2010-10-19 23:29:00
    进程进入临界区调度原则是:  ①如果有若干进程要求进入空闲的临界区,一次仅允许一个进程进入。  ②任何时候,处于临界区内的进程不可多于一个。如已有进程进入自己的临界区,则其它所有试图...

    进程进入临界区的调度原则是:

     ①如果有若干进程要求进入空闲的临界区,一次仅允许一个进程进入。

     ②任何时候,处于临界区内的进程不可多于一个。如已有进程进入自己的临界区,则其它所有试图进入临界区的进程必须等待。

     ③进入临界区的进程要在有限时间内退出,以便其它进程能及时进入自己的临界区。

     ④如果进程不能进入自己的临界区,则应让出 CPU,避免进程出现“忙等”现象。

     

     

     

    #include <windows.h>
    #include <iostream>
    #include <tchar.h>

    using namespace std;


    DWORD WINAPI FuncProc3(LPVOID lpParameter);

    DWORD WINAPI FuncProc4(LPVOID lpParameter);
    int ctickets = 100;

    CRITICAL_SECTION g_csA;

    void main(void)
    {
           InitializeCriticalSection(&g_csA);
           InitializeCriticalSection(&g_csB);

           HANDLE thread1;
           HANDLE thread2;
           thread1 = CreateThread(NULL, 0, FuncProc3, NULL, 0, NULL);
           thread2 = CreateThread(NULL, 0, FuncProc4, NULL, 0, NULL);

     

           CloseHandle(thread1);
           CloseHandle(thread2);

           Sleep(4000);

           DeleteCriticalSection(&g_csA);
           DeleteCriticalSection(&g_csB);
           system("pause");
    }

     

     

    DWORD WINAPI FuncProc3(LPVOID lpParameter)
    {
            while(TRUE)
           {
                   EnterCriticalSection(&g_csA);

                   //Sleep(100);

                   Sleep(1);

                  if(ctickets > 0)
                  {
                         cout<<"thread1 sell ticket: "<<ctickets--<<endl;
                         LeaveCriticalSection(&g_csA);
                  }else{
                         LeaveCriticalSection(&g_csA);
                         break;
                  }
           }
            return  0;
    }


    DWORD WINAPI FuncProc4(LPVOID lpParameter)
    {
             while(TRUE)
            {
                    EnterCriticalSection(&g_csA);

                    // Sleep(100);

                    Sleep(1);
                  if(ctickets > 0)
                  {
                          cout<<"thread2 sell ticket: "<<ctickets--<<endl;
                  }else{
                          break;
                  }

                  LeaveCriticalSection(&g_csA);
            }
            return  0;
    }

    上面这段代码如果把休眠时间改成0.1秒,则会报内存地址访问错误。

    (开发环境:windows7、Microsoft Visual Studio 2008)

     

    参考:http://baike.baidu.com/view/1237110.htm

     

     

     

    展开全文
  • 1.临界区管理  临界区:并发进程中与共享变量有关的...3.临界区调度原则 一次至多允许一个进程进入临界区内 如果已有进程在临界区中,试图进入此临界区的其他进程应等待; 进入临界区的进程应在有限时间...

    1.临界区管理

     临界区:并发进程中与共享变量有关的程序段

    •  临界资源:共享变量代表的资源

    2.临界区解决互斥问题

    如果能保证进程在临界区执行时,不让另一个进程进入临界区,即各进程对共享变量的访问是互斥的,就不会造成与时间有关的错误

    3.临界区的调度原则

    • 一次至多允许一个进程进入临界区内

    • 如果已有进程在临界区中,试图进入此临界区的其他进程应等待;
    • 进入临界区的进程应在有限时间内退出,以便让等待队列中的一个进程进入

    临界区调度原则可总结成四句话:互斥使用、有空让进;忙则等待、有限等待;择一而入、让权等待;算法可行  算法可行是指不能因为所选的调度策略造成进程饥饿甚至死锁

    4.实现临界区管理的软件方法

    (1)Dekker算法

    Dekker算法用一个指示器turn来指示应该哪一个进程进入临界区。

    • 若turn=0则进程P1可以进入临界区
    • 若turn=1则进程P2可以进入临界区

    算法实现

    前提条件:共享变量有turn和flag[],turn==0&&flag[1]==ture则轮到po运行临界区代码;turn==1&&flag[1]==ture则轮到p1运行临界区代码

    1. 首先要运行的线程将自己对应的flag置为true,ture代表请求访问(小学生举手提问)
    2. 接着判断其他县城是否也将自己的flag也置为ture(判断其他小学生是不是也举手了)
    3. 如果其他线程的flag为false开始判断trun的值,如果turn的值为1也就是说轮到了其他线程,则将当前线程的flag置为false,并开始循环等待,等待条件就是监测turn的值,当turn的值改变的时候,将当前县城的flag置为true,开始临界区访问,访问结束将turn值改变并将flag置为false(如果有其他小学生举手了,就要判断是不是现在轮到其他小学生,如果是轮到其他小学生则让当前小学生把手放下并且等其他小学生提问完,当提问完后再把举手,之后提问问题,问题提问完后把话语权给其他小学生并且当前小学生把手放下)
    1)P0的逻辑
    
    while(true){
        flag[0] = true;// 首先P0举手示意我要访问
        while(flag[1]) {// 判断P1是否也举手了
            if(turn==1){// 如果P1也举手了,那么就看看到底轮到谁
                flag[0]=false;// 如果确实轮到P1,那么P0先把手放下(让P1先)
                while(turn==1);// 只要还是P1的时间,P0就不举手,一直等
                flag[0]=true;// 等到P1用完了(轮到P0了),P0再举手
            }
            flag[1] = false; // 只要可以跳出循环,说明P1用完了,应该跳出最外圈的while
        }
        visit();// 访问临界区
        turn = 1;// P0访问完了,把轮次交给P1,让P1可以访问
        flag[0]=false;// P0放下手
    }
    2)P1的逻辑
    while(true){
        flag[1] = true;// 先P1举手示意我要访问
        while(flag[0]) {// 如果P0是否也举手了
            if(turn==0){// 如果P0也举手了,那么久看看到底轮到谁
                flag[1]=false;// 如果确实轮到P0,那么P1先把手放下(让P0先)
                while(turn==0);// 只要还是P0的时间,P1就不举手,一直等
                flag[0]=true;// 等到P0用完了(轮到P1了),P1再举手
            }
            flag[0] = false; // 只要可以跳出循环,说明P0用完了,应该跳出最外圈的while
        }
    visit();// 访问临界区
    turn = 0;// P1访问完了,把轮次交给P0,让P0可以访问
    flag[1]=false;// P1放下手

    (2)Peterson算法

    Peterson算法是一个实现互斥锁的并发程序设计算法,可以控制两个线程访问一个共享的单用户资源而不发生访问冲突。Gary L. Peterson于1981年提出此算法

    此算法需要将步骤首先需要队turn赋值

    void procedure0(){
        while(true){
            flag[0]=true;
            while(flag[1]&&turn==1);/*若flag[1]为false,P0就进入临界区;若flag[1]为tureP0循
                                        环等待,只要P1退出临界区,P0即可进入*/
            visit();/*访问临界区*/
            flag[0]=false;/*访问临界区完成,procedure0释放出临界区*/
            turn=1;
            /*remainder section*/
        }
    }
    void procedure1(){
        while(true){
            flag[1]=true;
            while(flag[0]&&turn==0);/*若flag[1]为false,P1就进入临界区;若flag[0]为tureP0循
                                        环等待,只要P0退出临界区,P1即可进入*/
            visit();/*访问临界区*/
            flag[1]=false;/*访问临界区完成,procedure1释放出临界区*/
            turn=0;
            /*remainder section*/
        }
    }

    (3)测试只用一个标志变量 

    发现也可以实现临界区管理

        @Override
        public void run() {
            while(true){
                while(turn==ids){
                    ss=(ss+1)%12000;
                    if(ss==0) System.out.println("饿死了");
                }
                pp();
                turn=ids;
            }
        }
    
        public void pp(){
            number+=1;
            number+=1;
            System.out.println("this number id :"+id+"is number:"+number);
            number-=1;
            number-=1;
        }

    5.实现临界区管理的硬件设施

    • 由于进程切换需要依赖中断来实现,如果屏蔽中断,则不会引起进程切换
    • 因此为了实现对临界资源的互斥使用,可以在进程进入临界区之前关闭中断,等进程退出临界区以后在打开中断
    • 中断被屏蔽后,处理器不响应中断,则不会被切换
    • 于是一旦屏蔽中断,进程就可以进入临界区修改访问共享变量,而不用担心其他进程介入

    (1)关中断 

    • 关中断是实现互斥的最简单方法之一
    • 进程在测试标志之前,首先关中断,直到测试完并设置标志之后才开中断
    • 进程在临界区执行期间,计算机系统不响应中断
    • 因此,不会转向调度,也就不会引起进程或线程切换,正在执行标志测试和设置的进程或线程不会被打断,从而保证了互斥

    关中断方法的缺点

    • 关中断时间过长会影响系统效率,限制处理器交叉执行程序的能力
    • 关中断方法也不适用于多CPU系统,因为,在一个处理器上关中断,并不能防止进程在其他处理器上执行相同临界区代码

    硬件设施缺点

    • 忙等现象仍然存在,但由于使用机器指令测试,则忙等时间可以忍受 (忙等的含义是当一个进程位于其临界区内时,任何试图进入其临界区的进程都必须在其进入代码中连续地循环)
    • 导致饥饿:临界区空闲时,执行循环检测的若干进程能进入临界区的几率是相等的,有的进程可能运气很不好,很难有机会进入临界区,因而饥饿
    • 导致死锁:进程P1和P2,P1的优先级低于P2,P1通过测试进入临界区,这时P2到, P2抢占了P1的处理器开始执行, P2也要求进入临界区,但临界区被P1占,而P1的优先级没有P2高不可能抢占P2的处理器。这样,这两个进程互相等待, P1等P2释放处理器, P2一直忙等P1释放临界区,如果没有外力,这两个进程处于死锁
    • 不会成为一种通用的方法

    解决方案

    • 软件方法和硬件方法都存在忙等问题,浪费了处理器的时间
    • 信号量方法可以实现进程同步与互斥,而不需要忙等

    6.总结

    前面种种方法解决临界区调度问题的缺点

    • 1)对不能进入临界区的进程,采用忙等测试法,浪费CPU时间;
    • 2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性,加重了用户编程负担。

    通过临界区的学习,我们可以知道主要是通过标志变量决定临界区进入的决定权,当一个线程进入临界区的时候,其他线程通过循环等待也就是忙等来等待进入临界区。由于忙等的问题会浪费处理器时间,所以接下来我们学习下一章节信号量来解决忙等这一缺陷的问题。

     

     

     

    展开全文
  • 临界区管理

    2019-09-03 20:57:37
    临界区调度原则 一次只允许一个进程进入临界区内执行 如果已有进程在临界区,其他视图进入的进程等待 进入临界区内的进程应在有限的时间内进出,一遍使等待进程中的一个进入 实现临界区管理的几种错误算法 两个...

    临界区的调度原则

    临界区与临界资源

    并发进程中与共享变量有关的程序段成为临界区,共享变量代表的资源成为临界资源。

    临界区调度原则

    • 一次只允许一个进程进入临界区内执行
    • 如果已有进程在临界区,其他视图进入的进程等待
    • 进入临界区内的进程应在有限的时间内进出,一遍使等待进程中的一个进入

    实现临界区管理的几种错误算法

    • 两个进程都认为对方不在临界区中,同时进入了临界区
    • 两个进程都认为对方在临界区中,进而永久等待

    实现临界区管理的Peterson算法

    该算法为每个进程设置一个标志,当该标志为true时表示此进程要进入临界区另外设置一个指示器turn,一直是哪个进程可以进入临界区

    boolean flag[2];
    int turn;
    void procedure0()
    {
    while(true)
    {
    flag[0]=true;
    turn=1;
    while(flag[1]&&turn==1) /*若flag[1]为false,P0就进入临界区;若flag[1]为tureP0循环等待,只要P1退出临界区,P0即可进入*/
    {
    /* donothing*/
    }
    visit();/*访问临界区*/
    flag[0]=false;/*访问临界区完成,procedure0释放出临界区*/
    /*remainder section*/
    }
    
    }
    void procedure1()
    {
    while(true)
    {
    flag[1]=true;
    turn=0;
    while(flag[0]&&turn==0)
    {
    /* donothing*/ ;
    }
    visit();/*访问临界区*/
    flag[1]=false;/*访问临界区完成,procedure1释放出临界区*/
    /*remainder section*/
    }
    }
    void main()
    {
    flag[0]=flag[1]=false;
    /*start procedure0 and procedure1*/ ;
    }
    

    在上面的例子中,我们先假设turn被赋值为1,后赋值为0,那么线程0就该进入临界区,线程1则因为flag[0]&&turn==0而等待,当线程0访问临界区结束后释放了临界区资源–flag[0]=false;,那么此时flag[0]&&turn==0不成立,线程1因此可以运行临界区

    实现临界区管理的硬件设施

    关中断

    • 进程在进入临界区之前关中断,退出临界区时开中断,关中断期间,进程调度程序失去终端机或的机会,不会切换线程,保证了临界区的互斥执行
    • 关中断缺点:限制交叉执行程序的能力,关中断方法不适合多CPU系统,关中断权利赋予给用户十分危险

    测试并建立指令

    TS(X){
    若x=true,则x=false;
    return true;
    否则 return false;
    }
    
    

    用TS指令实现临界区管理(互斥)的算法如下

    bool TS(bool &x){
    	if(x){
    	x=false;
    	return true;
    	}
    }
    

    利用TS指令实现进程会吃的算法如下

    bool s=true;
    cobegin
    	process Pi(){
    	//i=1,2,3...n;
    	while(!TS(s))
    	s=true;
    	}
    

    对换指令

    void SWAP(bool &a,bool &b){
    bool temp=a;
    a=b;
    b=temp;
    }
    
    展开全文
  • 4 临界区(Critical section) 5 信号量与管程(Dijkstra提出的信号量) 6 死锁 7 进程间通信(IPC) 1 进程(process)描述 1.1 进程定义 一个具有一定独立功能的程序在一个数据集合上的一次 动态 执行过程。 ...

    课程地址
    https://www.bilibili.com/video/av30708793?p=38

    进程管理主要涉及内容有: 进程(process)描述、进程状态(state)、线程(thread)、进程间通信(inter-process communication)、进程互斥与同步、死锁(deadlock)、

    1 进程(process)描述

    1.1 进程定义

    一个具有一定独立功能的程序在一个数据集合上的一次动态执行过程。

    进程(Process)是计算机中的程序关于某数据集合上的一次运行活动,是系统进行资源分配和调度的基本单位,是操作系统结构的基础。在早期面向进程设计的计算机结构中,进程是程序的基本执行实体;在当代面向线程设计的计算机结构中,进程是线程的容器。程序是指令、数据及其组织形式的描述,进程是程序的实体。
    (进程理解起来比较抽象,是一次活动,是程序执行过程)

    1.2 进程组成

    一个进程应该包括:

    • 程序的代码
    • 程序处理的数据
    • 程序计数器中的值,指示下一条将运行的指令
    • 一组通用的寄存器的当前值,堆,栈
    • 一组系统资源(如网卡调用、 文件 等等)

    总之,进程包括了正在运行的一个程序的所有状态信息。

    进程与程序的联系

    • 程序是产生进程的基础
    • 程序的每次运行构成不同的进程(一个程序多次执行可能会产生不同的进程,程序每次执行起来产生的进程可能是不一样的(比如调用的资源可能就不一样))
    • 进程是程序功能的体现
    • 通过多次执行,一个程序可对应多个进程
    • 通过调用关系,一个进程可以包括多个程序

    进程与程序的区别

    • 进程是动态的,程序是静态的;程序是有序代码的集合,进程是程序的执行,进程有核心态、用户态。(我们写程序只是在用户态,但进程却可能有核心态,进程需要调用操作系统里的系统资源时,操作系统代替进程执行这些操作)
    • 进程是暂时的,程序是永久的;进程是一个转台变化的过程,程序可永久保存
    • 进程与程序的组成不同:进程的组成包括程序、数据和进程控制块(即进程状态信息)

    在这里插入图片描述

    1.3 进程特点

    • 动态性:可动态地创建、结束进程;
    • 并发性:进程可以被独立调度并占用处理机运行;
    • 独立性:不同进程的工作不相互影响(操作系统调度不同进程执行时,进程的正确性必须不被破坏,操作系统依靠页表访问地址区间 保证进程不互相破坏);
    • 制约性:因访问共享数据/资源或进程间同步而产生制约;
      在这里插入图片描述

    并行是指多个进程在同一时刻同时执行。 并发是指在一段时间内可以同时执行多个进程。
    如果只有一个单核的CPU是没办法执行并行这一操作的,但是是可以并发的。只有多核的CPU才能够执行并行。
    多核心CPU,每个核心都有单独的控制器、运算器、寄存器。
    CPU核心和线程的关系

    CPU的核心数是指物理上,也就是硬件上存在着几个核心。比如,双核就是包括2个相对独立的CPU核心单元组,四核就包含4个相对独立的CPU核心单元组,等等,依次类推。

    线程数是一种逻辑的概念,简单地说,就是模拟出的CPU核心数。比如,可以通过一个CPU核心数模拟出2线程的CPU,也就是说,这个单核心的CPU被模拟成了一个类似双核心CPU的功能。我们从任务管理器的性能标签页中看到的是两个CPU。
    cpu线程是一堆寄存器,例如当前指令寄存器地址,堆栈指针,页面寄存器等.x86
    cpu刚刚开始支持多线程切换,并在cpu指令级实现线程切换,如任务门。但是操作系统通常不使用此函数,而是仅使用一个线程通过修改堆栈指针来实现线程切换。,64位x86将取消任务门。

    因此,cpu的线程与操作系统所说的线程几乎没有关系。即使CPU不支持线程,操作系统也可以实现线程。要说连接,现在多核cpu,有多个虚拟cpu,每个虚拟cpu都有一个cpu线程,为了发挥cpu的最大效果,操作系统还必须准备相应数量的线程。

    1.4 进程控制结构

    操作系统怎么维护进程?

    操作系统为每个进程搞了个数据结构,名字叫进程控制块(process control block,PCB),操作系统为每个进程都创建了一个PCB,用来保存于该进程有关的各种状态信息。

    进程控制块:

    操作系统管理控制进程运行所用的信息集合。操作系统用pcb来描述进程的基本情况以及运行变化的过程。pcb是进程存在的唯一标志。

    PCB含有以下三大类信息才能胜任:

    1. 进程标识信息。如进程的标识,本进程的产生者表示(父进程标识),用户标识、
    2. 处理机状态信息保存区。保存进程的运行现场信息:(1)用户可见寄存器:用户程序可以使用的数据、地址等寄存器;(2)控制和状态寄存器:如程序计数器、程序状态字;(3)栈指针:过程调用、系统调用、中断处理和返回时需要用到它。
    3. 进程控制信息: 在这里插入图片描述

    PCB组织方式:

    链表:同一状态的进程其pcb呈一链表; 多个状态对应多个不同的链表; 各状态的进程组成不同的链表:就绪链表、阻塞链表。
    索引表:在专用系统里常用,因为专用系统里不太常对进程进行花里胡哨地创建删除。
    在这里插入图片描述

    2 进程状态 (动态的内容)

    2.1进程的生命期管理

    进程创建、运行、等待、唤醒、结束。

    创建
    引起进程创建的3个主要事件:

    • 系统初始化时候
    • 用户请求创建一个新进程
    • 正在运行的进程执行了创建进程的系统调用

    运行
    创建出来的所有进程就叫就绪进程,操作系统根据一些调度算法选择某个进程到CPU执行。
    等待
    在下面这些情况,进程等待(阻塞)

    • 请求并等待系统服务,无法马上完成
    • 启动某种操作,无法马上完成
    • 需要的数据没有到达

    进程只能自己阻塞自己,因为只有进程本身才能知道何时需要等待某个事件的发生。
    唤醒
    唤醒进程的原因:

    • 被阻塞进程需要的资源可被满足
    • 被阻塞进程等待的事件到达
    • 将该进程的PCB插入到就绪队列

    进程只能被别的进程或者OS 唤醒。

    结束

    • 正常退出(自愿的)
    • 错误退出(自愿的)
    • 致命错误(强制性的)
    • 被其他进程(比如OS的管理进程觉得你这个进程占用内存太多要导致崩溃)kill掉(强制性的)
      在这里插入图片描述

    2.2 进程状态变化模型

    进程的三种基本状态

    进程在生命结束前处于且仅处于三种基本状态之一。

    不同系统设置的进程状态数目不同。

    运行状态(running):当一个进程正在处理机上运行时。
    就绪状态(ready):一个进程获得了除处理机之外的一切所需资源,一旦得到处理机即可运行。
    等待状态(blocked)又称阻塞状态,一个进程正在等待某一件事情而暂停运行。如等待某资源、等待输入输出完成。
    在这里插入图片描述
    如果考虑创建和结束状态:
    在这里插入图片描述

    2.3 进程挂起模型

    为了合理且充分的利用系统资源。进程在挂起状态时意味着进程没有占用内存空间,处于挂起状态的进程映像在磁盘上。

    • 阻塞挂起状态是指进程在外存并等待某事件的出现
    • 就绪挂起状态是指进程在外存,但只要进入内存即可运行。

    在这里插入图片描述

    操作系统管理不同进程

    状态队列:由OS来维护一组队列,用来表示系统当中所有进程的当前状态。

    在这里插入图片描述

    2.4 windows进程终止方式

    进程终止后,windows会释放进程锁使用的内存、句柄等所有资源

    • 主线程的入口函数返回(正常终止,推荐)
    • 进程主动退出:一个线程调用ExitProcess;
    • 进程被动终止:另一个进程调用了TerminateProcess (没善后的那些代码执行了)
    • 进程中的所有线程都终止

    3 线程(thread)管理

    60年代提出进程为基本单位,80年代中期提出以线程为基本单位。

    3.1 为什么使用线程

    举例:一个MP3播放软件,包含读取、解码、播放。

    main
    {
      while(1)
      {
      	读取
      	解码
      	播放
      }
    }
    

    单进程 声音可能会断断续续。
    那么如果把读取 解码 播放放在三个进程里去执行,又会占用很多系统资源来管理这三个进程。

    解决: 提出一种新的实体,满足下面特性:
    (1)实体之间可以并发地执行;
    (2)实体之间共享相同的地址空间。

    3.2 什么是线程

    线程定义:进程当中的一条执行流程。
    从2个方面来重新理解进程

    • 从资源组合的角度:进程把一组相关的资源组合起来,构成了一个资源平台(环境),包括地址空间(代码段、数据段)、打开的文件等各种资源;
    • 从运行的角度:代码在这个资源平台上的一条执行流程(线程)。

    在这里插入图片描述
    线程

    • 创建于一个进程的上下文中,在进程的地址空间中运行;
    • 线程是动态的一个进程,至少要有一个线程
    • 进程中的所有线程共享进程的地址空间,

    组成部分分为两个部分

    • 一个是核心态的对象,操作系统用来保存现成的信息,
    • 一个部分是线程堆栈,用于存放现成运行时的函数参数与局部变量等

    windows线程终止方式

    • 线程函数返回
    • 线程调用ExitThread
    • 其他线程调用TrerminateThread
    • 改线程所在的进程终止

    等式:

    线程 = 进程 - 共享资源
    

    线程的优点

    • 一个进程中可以同时存在多个线程
    • 各个线程之间可以并发的执行
    • 各个线程之间可以共享地址空间和文件等资源

    线程的缺点

    • 一个线程崩溃会导致其所属进程的所有线程崩溃(因为破坏了共享数据)。

    所以需要考虑何时使用进程、何时使用线程:

    • 需要性能要线程(气象学);
    • 浏览器开网页最好用进程,一个网页崩溃了,不至于浏览器死掉了。打开网页是不需要啥性能的,更需要安全性,不至于一个网页崩溃掉整个浏览器;

    在这里插入图片描述
    线程与进程的比较

    1 进程是资源分配的单位,线程是CPU调度的单位;
    2 进程拥有一个完整的资源平台,而线程只独享必不可少的资源,如寄存器与栈;
    3 线程同样具有就绪、阻塞和执行三种基本状态,同样具有状态之间的转换关系;
    4 线程能减少并发执行的时间和空间开销:

    • 线程的创建时间比进程短;(不需要再次创建那些资源)
    • 线程的终止时间比进程短;
    • 同一进程内的线程切换时间比进程短;(同一地址空间,同一页表,页表不需要切换)
    • 由于同一进程的各线程间共享内存和文件资源可直接进行,不通过内核的通信。

    3.3 线程的实现

    主要三种实现方式:

    用户线程:在用户空间实现(操作系统是看不到的,用户线程库来实现): POSIX Pthreads, Mach C-threads,Solaris threads
    内核线程:在内核中实现(操作系统看得到): Windows,Solaris,Linux
    轻量级进程:在内核中实现,支持用户线程 Solaris

    操作系统只能管理进程,管理不了进程内部的用户线程。进程管理着用户线程的生命周期。允许每个进程拥有自定义的线程调度算法。

    3.3.1 用户线程缺点:

    • 阻塞性的系统调用如何实现?如果一个线程发起系统调用而阻塞,则整个进程在等待。
    • 当一个线程开始运行后,除非它主动交出CPU使用权,否则它所在的进程当中的其他线程将无法运行。(操作系统在一个中断事件来临后可以强制停下CPU上的进程)。
    • 由于时间片分配给进程,故与其他进程比,在多线程执行时,每个线程得到的时间片较少,执行会较慢。

    3.3.2 内核线程
    是指在操作系统的内核当中实现的一种线程机制,由操作系统的内核来完成线程的创建、终止和管理。
    此时进程里的线程是由操作系统来管理,进程主要负责的是资源的调度。
    此时操作系统的调度单位是线程,而不是进程。

    • 在支持内核线程的操作系统中,由内核来维护进程和线程的上下文信息(pcb和tcb)。
    • 线程的创建、终止和切换都是通过系统调用内核函数的方式来进行,由内核来完成,因此系统开销较大;
    • 在一个进程当中,如果某个内核线程发起系统调用而被阻塞,并不会影响其他内核线程的运行。
    • 时间片分配给线程,多线程的进程获得更多的CPU时间.
    • windows nt和windows2000/XP支持内核线程.

    3.3.3 轻量级进程
    内核支持的用户线程。一个进程有一个或多个轻量级进程,每个量级进程由一个单独的内核线程来支持。(LINUX / SOLARIS用的这个方法)
    SOLARIS系统是多对多,多个线程对多个内核线程,管理比较复杂,但也更灵活。
    LINUX系统是一对一,一个线程对一个内核线程。

    3.4 进程的上下文切换

    定义:停止当前运行进程(从运行状态改变成其他状态)并且调度其他进程(转变成运行状态)。
    这一部分的内容,操作系统都是汇编来写,因为和硬件是紧密联系的。
    操作系统将PCB放置在一个合适的队列里。

    • 就绪队列
    • 等待I/O队列
    • 僵尸队列

    3.4 多线程编程接口举例

    僵尸态的进程:子进程正在等待被父进程处理回收的时候就是僵尸态进程,这个子进程不能再执行起来了,但依旧存在在内存里。如果僵尸态的子进程还没被回收,父进程就没了,那僵尸态的子进程就会一直存在,直到操作系统的祖先进程来扫描扫到了,替代原父进程来回收这个僵尸态子进程。
    在这里插入图片描述

    进程的创建过程
    一旦操作系统发现了要求创建新进程的事件后,便调用进程创建原语create()按下述步骤创建一个新进程。
    1) 申请空白PCB。为新进程申请获得唯一的数字标识符,并从PCB集合中索取一个空白PCB。
    2) 为新进程分配资源。为新进程的程序和数据以及用户栈分配必要的内存空间。显然,此时操作系统必须知道新进程所需要的内存大小。
    3) 初始化进程控制块。PCB的初始化包括:
    ①初始化标识信息,将系统分配的标识符和父进程标识符,填入新的PCB中。
    ②初始化处理机状态信息,使程序计数器指向程序的入口地址,使栈指针指向栈顶。
    ③初始化处理机控制信息,将进程的状态设置为就绪状态或静止就绪状态,对于优先级,通常是将它设置为最低优先级,除非用户以显式的方式提出高优先级要求。
    4) 将新进程插入就绪队列,如果进程就绪队列能够接纳新进程,便将新进程插入到就绪队列中。

    进程的终止过程
    如果系统发生了上述要求终止进程的某事件后,OS便调用进程终止原语,按下述过程去终止指定的进程。
    1)根据被终止进程的标识符,从PCB集合中检索出该进程的PCB,从中读出该进程状态。
    2)若被终止进程正处于执行状态,应立即终止该进程的执行,并置调度标志为真。用于指示该进程被终止后应重新进行调度。
    3)若该进程还有子孙进程,还应将其所有子孙进程予以终止,以防他们成为不可控的进程。
    4)将被终止的进程所拥有的全部资源,或者归还给其父进程,或者归还给系统。
    5)将被终止进程(它的PCB)从所在队列(或链表)中移出,等待其它程序来搜集信息。

    3.5 CPU调度

    3.5.1 背景

    上下文切换定义

    • 切换CPU的当前任务,从一个进程/线程到另一个
    • 保存当前进程/线程在PCB/TCB中的执行上下文(CPU状态)
    • 读取下一个进程/线程的上下文

    CPU调度定义

    • 从就绪队列里挑选一个进程/线程作为CPU将要运行的下一个进程/线程
    • 调度程序:挑选进程/线程的内核函数
    • 什么时候进行调度

    内核运行调度程序的条件(满足一条即可)

    • 一个进程从运行状态切换到等待状态。
    • 一个进程被终结了。

    早期的OS的CPU调度是不可抢占的

    调度程序必须等待事件结束。

    可以抢占的设计

    • 调度程序在中断被相应后执行
    • 当前的进程从运行切换到就绪,或者一个进程从等待切换到就绪
    • 当前运行的进程可以被换出

    3.5.2 调度原则

    程序在CPU突发和I/O中交替

    • 每个调度决定都是关于在下一个CPU突发时将哪个工作交给CPU
    • 在时间分片机制下,线程可能在结束当前CPU突发前被迫放弃CPU

    调度评价指标:

    • CPU利用率:CPU处于忙状态所占时间的百分百
    • 吞吐量:在单位时间内完成的进程数量
    • 周转时间:一个进程从初始化到结束。包括所有等待时间所花费的时间
    • 等待时间:进程在就绪队列中的总时间
    • 响应时间:从一个请求被提交到产生第一次相应所花费的总时间

    调度目标

    减少响应时间、减少平均相应时间的波动、增加吞吐量、减少等待时间

    这些调度目标有的具有相互联系的,一个目标提升到极致后,另外的目标就必然表现欠佳,设计调度算法的时候就需要考虑平衡的问题。

    • 低延迟调度增加了交互式表示
    • 但是操作系统需要保证吞吐量不受影响
    • 吞吐量是操作系统的计算带宽
    • 响应时间是操作系统的计算延迟

    有些场景下考虑大家要公平
    举例:保证每个进程占用相同的CPU时间

    3.5.3 调度算法

    进程的调度算法包括:
    实时系统中:FIFO(First Input First Output,先进先出算法),SJF(Shortest Job First,最短作业优先算法),SRTF(Shortest Remaining Time First,最短剩余时间优先算法)。
    交互式系统中:RR(Round Robin,时间片轮转算法),HPF(Highest Priority First,最高优先级算法),多级队列,最短进程优先,保证调度,彩票调度,公平分享调度。

    3.5.4 实时调度(实时操作系统)

    定义

    正确性依赖于其时间和功能两方面的一种操作系统。

    性能指标

    时间约束的及时性
    速度和平均性能相对不重要

    主要特性

    时间约束的可预测性

    强实时系统,需要在保证的时间内完成重要的任务,必须完成。
    弱实时系统,要求重要的进程的优先级更高,尽量完成,并非必须。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    3.5.5 多处理器调度

    在这里插入图片描述

    3.5.6 优先级反转

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    4 临界区(Critical section)

    为了解决同步互斥问题。

    不同进程访问共享资源时的问题。
    进程之间互相交互的问题。

    进程/线程,计算机/设备是有必要合作的。(因为共享资源、加速、模块化设计)

    race condition (竞态条件)
    系统缺陷:结果依赖于并发执行/事件的顺序/时间。拥有不确定性。一个进程在执行过程中,由于另一个进程的打断后执行导致之前这个进程执行的结果发生了错误。

    atomic operation 原子操作
    原子操作是指一次不存在任何终端或者失败的执行。

    • 该执行的成功执行
    • 或者根本没有执行
    • 并且不应该发现任何部分执行的状态

    实际上操作往往不是原子性的

    • 有些看上去是原子操作,实际上不是;
    • 连x++这样的简单语句,实际上是有3条指令构成的
    • 有时候甚至连单条机器指令都不是原子的

    临界区(Critical section)

    临界区是指进程中的一段需要访问共享资源,并且当另一个进程处于相应代码区域时使不会被执行的代码区域。

    Mutual exclusion 互斥

    当一个进程处于临界区并访问共享内资源时,没有其他进程会处于临界区,并且访问任何相同的共享资源。

    dead lock

    两个或以上的进程在互相等待别人完成特定任务,而最终没法将自身任务进行下去。

    starvation 饥饿

    一个可执行的进程,被调度器持续忽略,以至于虽然处于可执行状态却不被执行。

    锁 lock
    解锁 unlock
    死锁 deadlock

    进程只能互斥地执行临界区的代码就可以顺利执行程序。

    临界区属性

    • 互斥,临界区里最多存在一个线程
    • 前进,最终肯定能进临界区执行成功
    • 有限等待
    • 无忙等待

    如何设计临界区?

    • 方法一 禁用硬件中断

    进入临界区之前禁用中断,出来后重启中断。但一旦中断被禁止,线程就无法被停止,整个系统都会为你停下来,其他线程将有可能处于饥饿状态;而且临界区如果过长,无法控制执行时间;多CPU情况下,此时临界区也无法继续保持互斥机制,基于这种办法只能用于单CPU;

    • 方法二 基于软件的解决办法

    在这里插入图片描述

    • 方法三 更高级的抽象

    都是为了锁机制
    在这里插入图片描述
    在这里插入图片描述

    5 信号量与管程(Dijkstra提出的信号量)

    https://blog.csdn.net/wangcg123/article/details/79666424
    为了 解决同步互斥问题。

    信号量的抽象数据类型是一个整形(sem),两个原子操作。

    由于信号量只能进行两种操作等待和发送信号,即P(sv)和V(sv),他们的行为是这样的:

    P(sv):如果sv的值大于零,就给它减1;如果它的值为零,就挂起该进程的执行

    V(sv):如果有其他进程因等待sv而被挂起,就让它恢复运行,如果没有进程因等待sv而挂起,就给它加1.

    举个例子,就是两个进程共享信号量sv,一旦其中一个进程执行了P(sv)操作,它将得到信号量,并可以进入临界区,使sv减1。而第二个进程将被阻止进入临界区,因为当它试图执行P(sv)时,sv为0,它会被挂起以等待第一个进程离开临界区域并执行V(sv)释放信号量,这时第二个进程就可以恢复执行。

    什么是管程?

    1管程可以看做一个软件模块,它是将共享的变量和对于这些共享变量的操作封装起来,形成一个具有一定接口的功能模块,进程可以调用管程来实现进程级别的并发控制。

    2进程只能互斥得使用管程,即当一个进程使用管程时,另一个进程必须等待。当一个进程使用完管程后,它必须释放管程并唤醒等待管程的某一个进程。

    3在管程入口处的等待队列称为入口等待队列,由于进程会执行唤醒操作,因此可能有多个等待使用管程的队列,这样的队列称为紧急队列,它的优先级高于等待队列。
    ———————————————— 版权声明:本文为CSDN博主「mengxuepingwxhn」的原创文章,遵循 CC 4.0 BY-SA
    版权协议,转载请附上原文出处链接及本声明。
    原文链接:https://blog.csdn.net/qq_38998213/article/details/87899231

    读者-写者问题。
    哲学家就餐问题。

    6 死锁

    https://baike.baidu.com/item/%E6%AD%BB%E9%94%81/2196938?fr=aladdin
    定义

    死锁是指两个或两个以上的线程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。

    虽然进程在运行过程中,可能发生死锁,但死锁的发生也必须具备一定的条件,死锁的发生必须具备以下四个必要条件。

    • 1)互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。
    • 2)请求和保持条件:指进程已经保持至少一个资源,但又提出了新的资源请求,而该资源已被其它进程占有,此时请求进程阻塞,但又对自己已获得的其它资源保持不放。
    • 3)不剥夺条件:指进程已获得的资源,在未使用完之前,不能被剥夺,只能在使用完时由自己释放。
    • 4)环路等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,···,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。

    7 进程间通信(IPC)

    进程间需要合作完成一个工作,需要进程间通信。
    信号
    管道
    消息队列
    共享内存

    展开全文
  • 什么是临界资源?什么是临界区

    千次阅读 2021-07-06 01:59:40
    导航:网站首页 >什么是临界资源?什么是临界区?题目类型:[问答题,简答题...试题难度:★★☆参考解析: 暂无解析匿名网友:临界区:每个进程中访问临界资源的那段程序叫做临界区。进程对临界区的访问必须互斥,...
  • 文章目录1 临界区1.1 简介1.2 程序调度法则1.3 线程同步问题2 临界区操作原语2.1 定义全局的锁CRITICAL_SECTION2)InitializeCriticalSection3)EnterCriticalSection和LeaveCriticalSection4) ...
  • 一、临界区的引出 从上一篇文章中,我们了解到了信号量的概念。信号量的数值表达的语义用来控制进程的走和停,因此,信号量的数值是非常重要的,信号量的数值吧必须和信号量的语义相一致,才能正确地决定进程的同步...
  • 简介 每个进程中访问临界资源的那段代码称为临界区(Critical Section)...进程进入临界区调度原则是: 如果有若干进程要求进入空闲的临界区,一次仅允许一个进程进入。 任何时候,处于临界区内的进程不可多于一个。
  • 临界区,临界资源

    千次阅读 2019-09-05 11:01:45
    * 什么是临界区? 答:每个进程中访问临界资源(比如全局变量等公用资源)的那段程序(代码)称为临界区(临界资源是一次仅允许一个进程使用的共享资源,如全局变量等),也称为临界段。也就说是每个进程(ucos中是...
  • 同步互斥问题背景同步互斥临界区的设计禁用硬件中断基于软件(同步)的解决方法小结更高级的抽象 背景 计算机系统里会有多个进程存在,这多个进程相互之间还会进行交互。交互会引起对共享资源的访问,如果对这些共享...
  • 临界区、相关临界区

    千次阅读 2017-10-09 09:10:27
    1.概念   临界区:每个进程中访问临界资源的那段代码称为临界区(Critical Section) 临界资源:临界资源是一次仅允许...相关临界区:多个进程中涉及到同一个临界资源的临界区称为相关临界区。 百度百科上对临界
  • Java面试题大全(2020版)

    万次阅读 多人点赞 2019-11-26 11:59:06
    发现网上很多Java面试题都没有答案,所以花了很长时间搜集整理出来了这套Java面试题大全,希望对大家有帮助哈~ 本套Java面试题大全,全的不能再全,哈哈~ 一、Java 基础 1. JDK 和 JRE 有什么区别?...
  • 操作系统——临界资源和临界区 1、临界资源 概念:一次仅允许一个...3、进程进入临界区调度原则 ① 如果有若干进程请求进入空闲的临界区(空闲即0进程访问),一次仅允许一个进程进入。 ② 任何时候,处于临界区内
  • 一、背景知识 1. 上下文切换: 切换CPU的当前任务,从一个进程/线程转换到另一个进程/线程; 但是切换之前要保护现场,保存当前进程/线程在PCB/TCP中...需要调度程序(挑选进程/线程的内核函数); 需要考虑的问题是...
  • 临界区

    2018-04-13 14:32:48
    临界区 [1] 指的是一个访问共用资源(例如:共用设备或是共用存储器)的程序片段,而这些共用资源又无法同时被多个线程访问的特性。当有线程进入临界区段时,其他线程或是进程必须等待(例如:bounded waiting ...
  • 不确定性: 如果一个操作是非原子操作, 那么...前进原则: 如果一个进程想要进入临界区, 那么在有限时间内一定会等到 临界区的实现: 方法1:禁用硬件中断: 在进入临界区之前屏蔽中断, 执行完临界区代码后再恢复 缺点:.
  • 对信号量的临界区保护

    千次阅读 2016-09-18 20:59:58
    概念介绍临界区(critical section)在任意时刻只允许一个进程对共享资源进行访问。一次只允许一个进程进入的该进程的那一段代码。对于临界资源的访问必须是互斥进行的,也就是当临界资源被占用时,另一个申请临界资源...
  • 进程同步的概念临界资源:许多硬件...临界区:人们把在每个进程中访问临界资源的那段代码称为临界区(critical section) repeat entry section critical section; exit section remainder section; until false;
  • 为避免对临界区并发访问,必须保证临界区代码被原子地执行。代码在执行期间不可被打断,如同整个临界区是一个不可分割的指令。如果两个内核任务处于同一个临界区中,这就是一种错误现象。如果确实发生这种情况,就...
  • 欢迎大家查看我的上一篇博客:多线程与并行计算简述 临界区 在上一章,我们就讨论过,在多线程程序中...通过临界区的定义我们可知,当一个线程占用了临界区资源,那么其他线程必须在这个临界区等待。等待会导致线程挂起
  • 操作系统第二章---处理机调度

    千次阅读 2020-12-12 15:32:59
    操作系统第二章---处理机调度处理机调度调度层次高级调度中级调度补充知识:进程的挂起态与七状态模型低级调度三层调度的对比知识点回顾进程调度的时机进程调度的方式进程的切换与过程知识点回顾调度算法的评价指标...
  • 1.温故知新通过对信号量的访问和修改,让进程有序推进 问题: empty值必须是正确的,如果empty错了...//生产者先判断 缓存个数 empty是否满了,empty == 0,阻塞 ... }//生产者P1 register = empty; register = reg
  • 临界资源/临界区/互斥量

    千次阅读 2017-12-25 09:39:25
    临界资源: 多道程序系统中存在许多进程,它们共享各种资源,然而有很多资源一次只能供一个进程...属于临界资源的硬件有打印机、磁带机等,软件有消息缓冲队列、变量、数组、缓冲等。 诸进程间应采取互斥方式,实现
  • CPU调度策略 FIFO:谁先进入,谁先调度 Priority:任务短可以适当优先调度 周转时间: 从开始申请执行任务,到执行任务完成 响应时间: 从开始申请执行任务到开始执行任务 相互影响和矛盾:响应时间小 ------> ...
  • 描述 互斥:同一时间,当只保证互斥,则可以保证临界资源访问不会造成临界资源数据的二义性,但是有可能占有临界资源的进程一直在占有,导致后面...如已有进程进入自己的临界区,则其它所有试图进入临界区的进程必...
  • 操作系统 之 临界区 浅析

    万次阅读 2015-11-20 11:42:01
    进程进入临界区调度原则 ①如果有若干进程要求进入空闲的临界区,一次仅允许一个进程进入。②任何时候,处于临界区内的进程不可多于一个。如已有进程进入自己的临界区,则其它所有试图进入临界区的进程必须等待。...
  • 【数据库学习】数据库总结

    万次阅读 多人点赞 2018-07-26 13:26:41
    原则:遵从概念单一化“一事一地”原则,即一个关系模式描述一个实体或实体间的一种联系。 规范的实质:概念的单一化。 规范化的方法:将关系模式投影分解成两个或两个以上的关系模式。 2,依赖和范式 1)依赖 ①...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 8,781
精华内容 3,512
关键字:

临界区调度原则