精华内容
下载资源
问答
  • 并发调度

    2019-08-14 11:51:59
    硬件级并发调度(硬件线程)、系统级并发调度(线程)、应用级并发调度(协程)。

    并发调度

    并发调度单元

    硬件级并发调度

    • 多发射处理器,同时执行多条指令。
    • 硬件多线程处理器,当某个线程因为 Cache 缺失需要等待时切换到另一个线程。解决处理器与存储器速度差的问题。
    • 多处理器。

    系统级并发调度

    以线程为最小调度单位,线程之间可以抢占,由操作系统调度。解决处理器与I/O速度差的问题。

    应用级并发调度

    以协程作为调度单元,由应用程序调度。

    展开全文
  • 数据库并发控制之并发调度

    千次阅读 2018-10-25 01:08:22
    一、并发调度的可串行性 二、两段锁协议 三、封锁的粒度 四、其他并发控制机制

    一、并发调度的可串行性

    1、可串行化调度

    定义 : 多个事务的并发执行是正确的,当且仅当其结果与按某一次串行地执行这些事务时的结果相同,称这种调度策略为可串行化调度。
    可串行性是并发事务正确调度的准则。按这个准则规定,一个给定的并发调度,当且仅当它是可串行化的,才认为是正确调度。

    2、冲突可串行化调度

    并发事务的不听调度:
    并发事务的不同调度
    冲突操作: 不同的事务对同一数据的读写操作和写写操作。
    Ri(x)与Wj(x) -->事务Ti读x,Tj写x,其中i≠j
    Wi(x)与Wj(x) -->事务Ti读x,Tj写x,其中i≠j
    其他操作是不冲突操作。
    不同事务的冲突操作和同一事务的两个操作是不能交换的。对于Ri(x)与Wj(x),若改变二者的次序,则事务Ti看到的数据库状态就发生了改变,自然会影响到事务Ti后面的行为。对于Wi(x)与Wj(x),改变二者的次序也会影响数据库的状态,x的值由等于Tj的结果变成了Ti的结果。
    一个调度Sc在保证冲突操作的次序不变的情况下,通过交换两个事务不冲突操作的次序得到另一个调度Sc‘,如果Sc’是串行的,称调度Sc为冲突可串行化的调度。若一个调度是冲突可串行化,则一定是可串行化的调度。因此可以用这种方法来判断一个调度是否是冲突可串行化的。

    冲突可串行化调度是可串行化调度的充分条件,不是必要条件。

    二、两段锁协议

    数据库管理系统普遍采用两段锁(2PL)协议的方法实现并发调度的可串行性,从而保证调度的正确性。
    定义: 所有事物必须分两个阶段对数据项加锁和解锁。

    1. 在对数据进行读、写操作之前,首先要申请并获得对该数据的封锁;
    2. 在释放一个封锁之后,事务不再申请和获得任何其他封锁。

    所谓“两段”的含义是,事务分为两个阶段:
    第一阶段是获得封锁,也称为扩展阶段,在这个阶段,事务可以申请获得任何数据项上的任何类型的锁,但是不能释放任何锁;
    第二阶段是释放封锁,也称为收缩阶段,在这个阶段,事务可以是否任何数据项上的任何类型的锁,但是不能再申请任何锁。

    若并发执行的所有事务均遵守两端锁协议,则对这些事务的任何并发调度策略都是可串行化的。

    示例:遵守两段锁协议的可串行化调度
    遵守两段锁协议的可串行化
    事务遵守两段锁协议是可串行化调度的充分条件,而不是必要条件。若并发事务都遵守两段锁协议,则对这些事务的任何并发调度策略都是可串行化的;但是,若并发事务的一个调度是可串行化的,不一定所有事务都符合两段锁协议。
    备注: 两段锁协议和防止死锁的一次封锁法的异同:

    1. 一次封锁法:要求每个事务必须一次将所有要使用的数据全部加锁,否则就不能继续执行。
    2. 两段锁协议:并不要求事务必须一次将所有要使用的数据全部加锁,印象遵守两段锁协议的事务可能发生死锁。
    3. 一次封锁法遵守两段锁协议。

    三、封锁的粒度

    封锁对象的大小称为封锁粒度。封锁对象可以是逻辑单元,也可以是物理单元。以关系数据库为例,封锁对象可以是这样一些逻辑单元:属性值、属性值的集合、元组、关系、索引项、整个索引直至整个数据库;也可以是这样一些物理单元:页(数据页或索引页)、物理记录等。
    封锁粒度与系统的并发度和并发控制的开销密切相关。

    封锁的粒度越大,数据库所能够封锁的数据单元就越少,并发度就越小,系统开销也越小;反正,封锁的粒度越小,并发度较高,但系统开销也就越大。

    1、多粒度封锁

    在一个系统中同时支持多种封锁粒度供不同的事务选择,这种封锁方法称为多粒度封锁。
    多粒度树示例:三级粒度树
    三级粒度树
    其中,根节点就是整个数据库,表示最大的数据粒度。叶结点表示最小的数据粒度。数据库的子结点为关系,关系的子结点为元组。
    多粒度封锁协议允许多粒度树多粒度树中的每个结点被独立地加锁。对一个结点加锁意味着这个结点的所有后裔结点页被加以同样类型的锁。因此,在多粒度封锁中一个数据对象可能以两钟方式封锁,显式封锁和隐式封锁。

    1. 显式封锁:应事务的要求直接加到数据对象上的锁;
    2. 隐式封锁:该数据对象没有被独立加锁,是由于其上级节点加锁而使该数据对象加上了锁。
      多粒度封锁方法中,显式封锁和隐式封锁的效果是一样的,因此系统检查封锁冲突时不仅要检查显式封锁还要检查隐式封锁。
      一般地,对某个数据对象加锁,系统要检查该数据对象上有无显式封锁与之冲突;再检查其所有上级结点,看本事务的显示封锁是否与该数据对象上的隐式封锁(即由于上级结点已加的封锁造成的)冲突;还要检查其所有下级结点,看它们的显式封锁是否与本事务的隐式封锁(将加到下级结点的封锁)冲突。
    2、意向锁

    为了解决多粒度封锁的检查方法效率低的问题,数据库管理系统无须逐个检查下一级结点的显式封锁,引进了一种新型锁–意向锁。
    含义: 如果对一个结点加意向锁,则说明该结点正在被加锁;对任一结点加锁时,必须先对它的上层结点加意向锁。

    1. 意向共享锁(IS锁)
      如果对一个数据对象加IS锁,表示它的后裔结点拟(意向)加S锁。
    2. 意向排他锁(IX锁)
      如果对一个数据对象加IX锁,表示它的后裔结点拟(意向)加X锁。
    3. 共享意向排他锁(SIX锁)
      如果对一个数据对象加SIX锁,表示对它加S锁,再加IX锁,即SIX=S+IX。

    所谓锁的强度是指它对其他锁的排斥程度。一个事务在申请封锁时以强锁代替弱锁是安全的,反之则不然。

    在具有意向锁的多粒度封锁方法中,任意事务T要对一个数据加锁,必须先对它的上层结点加意向锁。申请封锁时应该按自上而下的次序进行,释放封锁时应该按自下而上的次序进行。
    加上意向锁后锁的相容矩阵与偏序关系图:
    加上意向锁后锁的相容矩阵与偏序关系
    具有意向锁的多粒度封锁方法提高了系统的并发度,减少了加锁和解锁的开销。

    选择封锁粒度时应该同时考虑封锁开销和并发度两个因素,适当选择封锁粒度以追求得最优的结果。一般来说,需要处理某个关系的大量元组的事务可以以关系为封锁粒度;需要处理多个关系的大量元组的事务可以以数据库为封锁粒度;而对于一个处理少量元组的用户事务,以元组为封锁粒度就比较合适了。

    四、其他并发控制机制

    并发控制的方法除了封锁技术外还有时间戳方法、乐观控制法和多版本并发控制等。

    1、多版本并发控制

    多版本并发控制(MVCC)是指在数据库中通过维护数据对象的多个版本信息来实现高效并发控制的一种策略。

    版本是指数据库中数据对象的一个快照,记录了数据对象某个时刻的状态。数据库系统的数据对象保留多个版本,以提高系统的并发操作程度。

    在多版本机制中,每个write(Q)操作都创建Q的一个新版本,这样一个数据对象就有一个版本序列Q1,Q2,…,Qm与之相关联。每一个版本Qk拥有版本的值、创建Qk的事务的时间戳W-timestamp(Qk)和成功读取Qk的事务的最大时间戳R-timestamp(Qk)。其中,W-timestamp(Qk)表示数据项Q上成功执行write(Q)操作的所有事务中的最大时间戳,R-timestamp(Qk)表示在数据项上Q上成功执行read(Q)操作的所有事务中的最大时间戳。
    封锁方法与MVCC示意图:
    封锁方法与MVCC示意图
    用TS(T)表示事务T的时间戳,TS(Ti)<TS(Tj)表示事务Ti在事务Tj之前开始执行,多版本协议描述如下:
    假设版本Qk具有小于或等于TS(T)的最大时间错。若事务T发出read(Q),则返回版本Qk的内容。若事务T发出write(Q),则:

    1. 当TS(T)<R-timestamp(Qk)时,回滚T;
    2. 当TS(T)=W-timestamp(Qk)时,覆盖Qk的内容。
      否则,创建Q的新版本。
      若一个数据对象的两个版本Qk和Ql,其中W-timestamp都小于系统中最老的事务的时间戳,那么这两个版本中较旧的那个版本将不再被用到,因而可以从系统中删除。

    多版本并发控制利用物理存储上的多版本来维护数据的一致性。这就意味着当检索数据库时,每个事务都看到一个数据的一段时间前的快照,而不管正在处理的数据当前的状态。多版本并发控制和封锁机制相比,主要的好处是消除了数据库中数据对象读和写操作的冲突,有效地提高了系统的性能。

    2、改进的多版本并发控制

    多版本并方控制方法有利于提高事务的并发度,但也会产生大量的无效版本,而且在事务结束时刻,其所影响的元组的有效性不能马上确定。因此多版本协议可以进一步改进。区分事务的类型为只读事务和更新事务。对于只读事务,发生冲突的可能性很小,可以采用多版本时间戳。对于更新事务,采用较保守的两阶段封锁(2PL)协议。这样的混合协议称为MV2PL。
    除了传统的读锁(共享锁)和写锁(排他锁)外,引进一个新的封锁类型,称为验证锁(C锁)。封锁的相容矩阵如下:
    验证锁的 相容矩阵
    在这个相容矩阵中,读锁和写锁变得是相容的了。这样当某个事物写数据对象的时候,允许其他事务读数据(写操作生成一个新版本,读操作就是读旧版本)。一旦写事务要提交的时候,必须首先获得在那些加了锁的数据对象上的验证锁。由于验证锁和读锁是不相容的,所以为了得到验证锁,写事务不得不延迟它的提交,直到所有被它加上写锁的数据对象都被所有那些正在读它们的事务释放。一旦写事务获得验证锁,系统就可以丢弃数据对象的旧值,使用新版本,然后释放验证锁,提交事务。
    这样,系统最多只要维护数据对象的两个版本。多个读操作可以和一个写操作并发地执行。这种情况是传统的2PL所不允许的,提高了读写事务之间的并发度。

    3、时间戳方法

    给每一个事务盖上一个时标,即事务开始执行的时间。每个事务具有唯一的时间戳,并按照这个时间戳来解决事务的冲突操作。如果方式冲突操作,就回滚具有较早时间戳的事务,以保证其他事务的正常执行,被回滚的事务被赋予新的时间戳并从头开始执行。

    4、乐观控制法

    乐观控制法又称为验证方法。
    乐观控制法认为事务执行时很少发生冲突,因此不对事务进行特殊的管制,而是让它自由执行,事务提交前再进行正确性检查。如果检查后发现该事务执行中出现过冲突并影响了可串行性,则拒绝提交并回滚该事务。

    M2PL把封锁机制和时间戳方法相结合,维护一个数据的多个版本,即对于关系表上的每一个写操作产生r的一个新版本,同时会保存前一次修改的数据版本。M2PL和封锁机制相比,主要的好处是在多版本并发控制中对读数据的锁要求与写数据的锁要求不冲突,所以读不会阻塞写,而写也从不阻塞读,从而使读写操作没有冲突,有效地提高了系统的并发性。

    展开全文
  • 关于数据库并发控制,封锁,并发调度的学习攻略
  • 并发调度原理

    千次阅读 2018-07-16 16:14:08
    并发调度原理 并发调度MPG(解释1) Processor(简称 P),其作用类似 CPU 核,用来控制可同时并发执行的任务数量。 每个工作线程都必须绑定一个有效 P 才被允许执行任务,否则只能休眠,直到有空闲 P 时 被唤醒。...

    并发调度原理

    并发调度MPG(解释1)

    Processor(简称 P),其作用类似 CPU 核,用来控制可同时并发执行的任务数量。 每个工作线程都必须绑定一个有效 P 才被允许执行任务,否则只能休眠,直到有空闲 P 时 被唤醒。P 还为线程提供执行资源,比如对象分配内存、本地任务队列等。线程独享所绑 定的 P 资源,可在无锁状态下执行高效操作。

     

    进程内的一切都在以 goroutine(简称 G)方式运行,包括运行时相关服务,以及 main.main入口函数。需要指出,G 并非执行体,它仅仅保存并发任务状态,为任务执行提供所需栈内存空间。G 任务创建后被放置在 P 本地队列或全局队列,等待工作线程调度执行.

     

    实际执行体是系统线程(简称 M),它和 P 绑定,以调度循环方式不停执行 G 并发任务。

    M 通过修改寄存器,将执行栈指向 G 自带栈内存,并在此空间内分配堆栈帧,执行任务

    函数。当需要中途切换时,只要将相关寄存器值保存回 G 空间即可维持状态,任何 M 都

    可据此恢复执行。线程仅负责执行,不再持有状态,这是并发任务跨线程调度,实现多路

    复用的根本所在。

     

    尽管 P/M 构成执行组合体,但两者数量并非一一对应。通常情况下,P 数量相对恒定,默

    认与 CPU 核数量相同,但也可能更多或更少,而M 则是调度器按需创建。举例来说,当

    M 因陷陷入系统调用长时间阻塞时,P 就会被监控线程抢回,去新建(或唤醒)一个 M 执

    行其他任务,如此 M 的数量就会增长。

     

    因为 G 初始栈仅有 2KB,且创建操作只是在用户空间简单的对象分配,远比进入内核态

    分配线程要简单得多。调度器让多个 M 进如调度循环,不停获取并执行任务,所以我们

    才能创建成千上万个并发任务。

     

    并发调度MPG(解释2)

    Golang的最小调度单元为协程,操作系统最小的调度单元是线程,Golang调度器将众多的goroutine放在有限的线程上进行高效而公平的调度。协程比线程更加轻量级,创建几万几十万的goroutine而不用担心内存耗尽等问题。

    Mos线程(即操作系统内核提供的线程)

    PMP的中介,实现m:n 调度模型的关键,M必须拿到P才能对G进行调度,P其实限定了golang调度其的最大并发度。

    Ggoroutine,其包含了调度一个协程所需要的堆栈以及instruction pointerIP指令指针),以及其他一些重要的调度信息。

     

     

     

    golang对这层调度其实做了一定的优化,不是在一开始进行系统调用之前就新建一个新的M,而是使用一个全局监控的monitor(sysmon),定期检查进入系统调用的M,只有进入时间过长才会新建一个M。另外golang 底层基本对所有的IO都异步化了,比如网络IO,golang底层在调用read返回EAGAIN错误的时候会将当前goroutine挂起,然后使用epoll监听这个网络fd上的可读事件,在当有数据可读的时候唤醒对应的goroutine继续进行调度。其中epoll事件管理线程即golang虚拟机的sysmon线程。

    当前运行的goroutine在达到调度点(系统调用、网络IO、等待channel等)的时候,P会挂起当前运行的goroutine,从runqueue中pop一个goroutine,重新设置当前M的执行上下文继续执行(即设置为pop出来的goroutine对应的运行堆栈以及IP(instruction Point))。

    golang语言能够控制线程M在用户态执行情况下的调度行为,但是却不能控制线程在陷入内核之后的行为。即在我们调用system call陷入内核没有返回之前,go其实已经控制不了。那怎么办呢?如果当前陷入system call的线程在持有P的情况下Block很长时间,会导致其他可运行的goroutine由于没有可用的P而不能得到调度。

    为了保证调度的并发型,即保证拿到P的M能够持续进行调度而不是block,golang 调度器也没有很好的办法,只能在进入系统调用之前从线程池拿一个线程或者新建一个线程的方式,将当前P交给新的线程M1从而使得runqueue中的goroutine可以继续进行调度。当前M0则block在system call中等待G0返回。 在G0返回之后需要继续运行,而继续运行的条件是必须拥有一个P,如果当前没有可用的P,则将G0放到全局的runqueue中等待调度,M0退出或者放入线程池睡觉去。而如果有空闲的P,M0在拿到P之后继续进行调度。(P的数量很好的控制了并发度)

    P在当前local runqueue中的G全部调度完之后从global runqueue中获取G进行调度,同样系统也会定期检查golobal runqueue中的G,以确保被放入global runqueue中的goroutine不会被饿死。

     

    并发调度MPG(解释3)

    G 受管理的轻量线程

    goroutine的新建, 休眠, 恢复, 停止都受到go运行时的管理.

    goroutine执行异步操作时会进入休眠状态, 待操作完成后再恢复, 无需占用系统线程,

    goroutine新建或恢复时会添加到运行队列, 等待M取出并运行.

     

    M golang中等同于系统线程.

    go代码, 即goroutine, M运行go代码需要一个P

    原生代码, 例如阻塞的syscall, M运行原生代码不需要P

    M会从运行队列中取出G, 然后运行G, 如果G运行完毕或者进入休眠状态, 则从运行队列中取出下一个G运行, 周而复始.

    有时候G需要调用一些无法避免阻塞的原生代码, 这时M会释放持有的P并进入阻塞状态, 其他M会取得这个P并继续运行队列中的G.

    go需要保证有足够的M可以运行G, 不让CPU闲着, 也需要保证M的数量不能过多.

     

    P 代表M运行G所需要的资源.

    如果P的数量等于1, 代表当前最多只能有一个线程(M)执行go代码,

    如果P的数量等于2, 代表当前最多只能有两个线程(M)执行go代码.

    执行原生代码的线程数量不受P控制.

    因为同一时间只有一个线程(M)可以拥有P, P中的数据都是锁自由(lock free)的, 读写这些数据的效率会非常的高.

    Lock-Free 是指能够确保执行它的所有线程中至少有一个能够继续往下执行。由于每个线程不是 starvation-free 的,即有些线程可能会被任意地延迟,然而在每一步都至少有一个线程能够往下执行,因此系统作为一个整体是在持续执行的,可以认为是 system-wide 的。所有 Wait-free 的算法都是 Lock-Free 的。

     

    G的状态

    空闲中(_Gidle): 表示G刚刚新建, 仍未初始化

    待运行(_Grunnable): 表示G在运行队列中, 等待M取出并运行

    运行中(_Grunning): 表示M正在运行这个G, 这时候M会拥有一个P

    系统调用中(_Gsyscall): 表示M正在运行这个G发起的系统调用, 这时候M并不拥有P

    等待中(_Gwaiting): 表示G在等待某些条件完成, 这时候G不在运行也不在运行队列中(可能在channel的等待队列中)

    已中止(_Gdead): 表示G未被使用, 可能已执行完毕(并在freelist中等待下次复用)

    栈复制中(_Gcopystack): 表示G正在获取一个新的栈空间并把原来的内容复制过去(用于防止GC扫描)

     

    M的状态

    M并没有像G和P一样的状态标记, 但可以认为一个M有以下的状态:

    自旋中(spinning): M正在从运行队列获取G, 这时候M会拥有一个P

    执行go代码中: M正在执行go代码, 这时候M会拥有一个P

    执行原生代码中: M正在执行原生代码或者阻塞的syscall, 这时M并不拥有P

    休眠中: M发现无待运行的G时会进入休眠, 并添加到空闲M链表中, 这时M并不拥有P

    自旋中(spinning)这个状态非常重要, 是否需要唤醒或者创建新的M取决于当前自旋中的M的数量.

     

    P的状态

    空闲中(_Pidle): 当M发现无待运行的G时会进入休眠, 这时M拥有的P会变为空闲并加到空闲P链表中

    运行中(_Prunning): 当M拥有了一个P后, 这个P的状态就会变为运行中, M运行G会使用这个P中的资源

    系统调用中(_Psyscall): 当go调用原生代码, 原生代码又反过来调用go代码时, 使用的P会变为此状态

    GC停止中(_Pgcstop): 当gc停止了整个世界(STW)时, P会变为此状态

    已中止(_Pdead): 当P的数量在运行时改变, 且数量减少时多余的P会变为此状态

     

    通用内核名词,函数解释

    systemstack()

    systemstack会切换当前的g到g0, 并且使用g0的栈空间, 然后调用传入的函数, 再切换回原来的g和原来的栈空间,切换到g0后会假装返回地址是mstart, 这样traceback的时候可以在mstart停止.

    这里传给systemstack的是一个闭包, 调用时会把闭包的地址放到寄存器rdx, 具体可以参考上面对闭包的分析.

    TLSThread Local Storage

    线程局部存储。

    getg()

    goget()用来获取当前线程正在执行的协程g。该协程g被存储在TLS中。

    mcall()

    mcall在golang需要进行协程切换时被调用,用来保存被切换出去协程的信息,并在当前线程的g0协程堆栈上执行新的函数。一般情况下,会在新函数中执行一次schedule()来挑选新的协程来运行。接下来我们就看看mcall的实现。

     

    程序初始化

    go程序的入口点是runtime.rt0_go, 流程是:

    调用runtime.schedinit执行共同的初始化

    这里的处理比较多, 会初始化栈空间分配器, GC, 按cpu核心数量或GOMAXPROCS的值生成P等

    生成P的处理在procresize中

    调用runtime.newproc创建一个新的goroutine, 指向的是runtime.main

    runtime.newproc这个函数在创建普通的goroutine时也会使用, 在下面的"go的实现"中会详细讲解

    调用runtime·mstart启动m0

    启动后m0会不断从运行队列获取G并运行, runtime.mstart调用后不会返回

    runtime.mstart这个函数是m的入口点(不仅仅是m0), 在下面的"调度器的实现"中会详细讲解

     

    G里面比较重要的成员如下

    stack: 当前g使用的栈空间, 有lo和hi两个成员

    stackguard0: 检查栈空间是否足够的值, 低于这个值会扩张栈, 0是go代码使用的

    stackguard1: 检查栈空间是否足够的值, 低于这个值会扩张栈, 1是原生代码使用的

    m: 当前g对应的m

    sched: g的调度数据, 当g中断时会保存当前的pc和rsp等值到这里, 恢复运行时会使用这里的值

    atomicstatus: g的当前状态

    schedlink: 下一个g, 当g在链表结构中会使用

    preempt: g是否被抢占中

    lockedm: g是否要求要回到这个M执行, 有的时候g中断了恢复会要求使用原来的M执行

     

    M里面比较重要的成员如下

    g0: 用于调度的特殊g, 调度和执行系统调用时会切换到这个g

    curg: 当前运行的g

    p: 当前拥有的P

    nextp: 唤醒M时, M会拥有这个P

    park: M休眠时使用的信号量, 唤醒M时会通过它唤醒

    schedlink: 下一个m, 当m在链表结构中会使用

    mcache: 分配内存时使用的本地分配器, 和p.mcache一样(拥有P时会复制过来)

    lockedg: lockedm的对应值

     

    P里面比较重要的成员如下

    status: p的当前状态

    link: 下一个p, 当p在链表结构中会使用

    m: 拥有这个P的M

    mcache: 分配内存时使用的本地分配器

    runqhead: 本地运行队列的出队序号

    runqtail: 本地运行队列的入队序号

    runq: 本地运行队列的数组, 可以保存256个G

    gfree: G的自由列表, 保存变为_Gdead后可以复用的G实例

    gcBgMarkWorker: 后台GC的worker函数, 如果它存在M会优先执行它

    gcw: GC的本地工作队列, 详细将在下一篇(GC篇)分析

     

    参考:

    https://studygolang.com/articles/3491

    https://blog.csdn.net/m0_37579159/article/details/79345831

    https://studygolang.com/articles/11863?fr=sidebar

    https://studygolang.com/articles/11862

     

    https://zhuanlan.zhihu.com/p/27328476?utm_campaign=studygolang.com&utm_medium=studygolang.com&utm_source=studygolang.com

     

    https://zhuanlan.zhihu.com/p/27400277

     

    https://www.cnblogs.com/zkweb/category/1108329.html

     

     

    https://zhuanlan.zhihu.com/golang-internal

     

    https://blog.csdn.net/heiyeshuwu/article/details/51178268

     

    说说Golang的runtime

    https://zhuanlan.zhihu.com/p/27328476?utm_campaign=studygolang.com&utm_medium=studygolang.com&utm_source=studygolang.com

     

     

    golang密集场景下协程调度饥饿问题

    http://xiaorui.cc/2018/06/04/golang%E5%AF%86%E9%9B%86%E5%9C%BA%E6%99%AF%E4%B8%8B%E5%8D%8F%E7%A8%8B%E8%B0%83%E5%BA%A6%E9%A5%A5%E9%A5%BF%E9%97%AE%E9%A2%98/

     

    Golang 之协程详解(对比其他网络模型优缺点)

    https://www.cnblogs.com/liang1101/p/7285955.html

     

    展开全文
  • 3-事务并发调度

    2021-11-28 21:13:52
    简单来说就是并发的事务的命令按照时间顺序组成的一个执行序列,叫做并发调度。 (1) 串行调度:按照串行的方式执行的。效率较低,一个事务执行必须等到另一个事务结束。 (2) 一致性调度:调度如果执行,能够让数据库...

    1. 事务并发

    (1) 概念:在某一个时间段内,多个事务同时存取相同的数据库数据。
    (2) 并发操作时由于不能隔离而产生的问题:

    • 丢失修改:A修改无效。在这里插入图片描述
    • 读入的数据时脏数据
      在这里插入图片描述
    • 不可重复读
      在这里插入图片描述

    2. 并发调度

    简单来说就是并发的事务的命令按照时间顺序组成的一个执行序列,叫做并发调度

    (1) 串行调度:按照串行的方式执行的。效率较低,一个事务执行必须等到另一个事务结束。

    (2) 一致性调度:调度如果执行,能够让数据库从一个正确的状态(一致性)装换成另一个一致性的状态。

    一致性状态:事务在执行的过程中,变量的状态变化是一致的。


    3. 可串行化调度

    设:T = {T1, T2, …, Tn} 是一组并发执行的事务,S 是 T 的一个串行调度,而 S’ 是 T 的一个调度。若 S’ 是与 S 有着相同一致性状态的一个调度,则称 S’ 是一个可串行化调度。

    下列始终先执行T2,在执行T1,所以是一致的。
    在这里插入图片描述
    在这里插入图片描述


    4. 冲突可串行化(一致性调度)

    哪些执行命令产生冲突呢?
    在这里插入图片描述
    在这里插入图片描述

    冲突可串行化的判断:优先图
    优先图由节点和有向弧组成,节点表示事务,有向弧表示事务的先后次序。事务的先后次序由冲突动作的先后次序决定。

    若有向弧无环,表示可串行化;否则是不可串行化。


    5. 基于封锁的并发控制机制

    1. 锁的基本形式
    • 共享锁(S锁):允许执行读操作。
    • 排他锁(X锁):允许执行读/写操作。
    1. 锁的调度策略
    • 解除一个数据对象的排他锁之前,其它事务不能对它加任何锁。
    • 一个数据对象允许加几个共享锁,但不能在共享锁之上,加排他锁。
    1. 锁的相融矩阵
      在这里插入图片描述

    2. 加锁产生的问题

    • ① 正确加锁产生错误结果
    • ② 产生死锁现象
    • ③ 产生饿死现象:对等待的事务赋予优先权,当优先级达到一定程度时不允许其它类型的锁加入。

    6. 两阶段锁协议

    所有事务分两个阶段提出加锁和解锁请求:
    ① 增长阶段:事务可以获得锁,但不能解锁;
    ② 缩减阶段:事务解锁,但不能获得锁。

    遵循了两阶段锁协议的并发控制算法所产生的调度是冲突可串行调度

    解决了正确加锁却产生错误结果的问题,但是仍存在死锁现象,级联回滚可能发生。


    7. 强两阶段锁协议

    要求事务提交之前不得释放任何锁。大部分数据库系统采用严格两阶段锁协议或强两阶段锁协议。但是这两种锁并行程度很低,有时为提高并行能力,采用锁转换机制,在写的时候将S锁转换成X锁,写完后再降为S锁。


    8. 多粒度锁及意向锁

    1. 多粒度锁的特点:
    • 显示加锁:树上每个结点都可以单独加锁
    • 隐式加锁:对当前节点加锁会导致隐式地对全部后代结点加上同类型的锁。

    检查锁冲突时,必须检查祖先、后代节点。

    1. 意向锁:一个事务对一个数据对象显示加锁前,须对它的全部祖先节点加意向锁。如果说一个节点上有意向锁,则它的后代节点被显示加锁

    意向锁分类:

    • IS 锁:对某节点加 IS,那么将对后代显示加 S 锁;
    • IX 锁:对某节点加 IX,那么将对后代显示加 X 锁;
    • SIX 锁:对某节点加 SIX,那么将对后代显示加 S 锁, 而且还加了 IX 锁,即,SIX = S + IX;
    1. 可串行多粒度锁协议:
    • 必须遵守锁类型的相容性矩阵
    • 根节点必须先加锁
    • 任何事物都必须遵守两阶段锁协议
    • 任何事物加锁都必须按从根到叶子顺序进行
    • 任何事物开锁都必须按从叶子到根顺序进行

    9. 死锁的处理

    封锁机制的实现是由锁管理器执行,锁管理器通过维护锁表控制加锁机制。

    1. 死锁: 两个或两个以上的事务都处于等待状态,每个事务都在等待其中另一个事务释放资源。

    2. 死锁的预防:

    • ① 抢占与事务回滚技术
    • ② 基于超时机制
    1. 死锁的检测:等待图

    2. 死锁的恢复:

    • 选择代价最小的事务
    • 回滚事务
    • 防止饿死,将其回滚次数考虑在代价中

    10. 基于时间戳的调度协议

    1. 时间戳:每个事务在启动数据库系统会赋予这个事务唯一的时间标记,以标记事务的开始,这个时间标记为时间戳。这个时间标记可以是系统时钟或逻辑计数值。
    2. 时间戳基本原理:事务的时间戳决定串行化顺序,若 TS(Ti) < TS(Tj),则系统必须保证产生的调度等价于 Ti, Tj 串行调度。
    展开全文
  • 事务并发调度的相关概念

    千次阅读 2020-03-20 21:40:41
    事务的并发 事务的并发:在某一时间段内,多个事务同时存取相同的数据库数据。 并发操作时由于不能隔离而产生的问题: 丢失修改:t4时间后,事务A对数据D的修改可能丢失。 读入“脏”数据:由于发生错误导致...
  • 并发调度的可串行性

    2019-10-08 09:49:37
    可串行化:多个任务并发执行是正确的,当且仅当起结果与按某种次序串行执行这些任务时产生的结果一样,称这种调度策略为可串行化调度。 冲突操作:不同任务对同一数据的读写操作和写写操作,其它任务都是不冲突的。...
  • //支持并发调度器, 最多允许2两任务进行处理 const scheduler = new Scheduler(2) scheduler.addTask(1, '1’); // 1s后输出’1' scheduler.addTask(2, '2’); // 2s后输出’2' scheduler.addTask(1, '3’); // 2...
  • 数据库原理 并发调度的可串行性

    千次阅读 2020-03-14 11:27:33
    数据库管理系统对于并发事务的不同调度会产生不同的结果 串行调度是正确的 执行结果等价于串行调度的结果也是正确的,称之为可串行化调度 1、可串行化调度 现在有两个事务,分别包含下列操作: 事务T1:读B;...
  • aiometer是一个Python 3.7+并发调度库,与asyncio和trio兼容,并受到启发。在控制并发限制(即施加)和以可预测的方式收集结果的同时,它使得同时执行大量任务变得更加容易。 该项目目前处于早期测试阶段。确保将...
  • 并发调度 一组并发事务当中的一些重要的操作按照时间的顺序给出一个排列,则称这个排列是这组事务的一个调度。 一致性状态:事务在执行的过程中,变量的状态变化是一致的,则称为一致性状态。 一致性调度:如果执行...
  • 数据库 - 并发调度的可串行性

    万次阅读 2015-05-12 17:35:31
    并发调度的可串行性DBMS对并发事务不同的调度(schedule)可能会产生不同的结果 什么样的调度是正确的?串行化(Serial)调度是正确的 对于串行调度,各个事务的操作没有交叉,也就没有相互干扰,当然也不会产生并发所...
  • 一、并发调度 并发调度啥意思? 就是当很多事务同时执行的时候应该按照什么顺序执行,应该按照排队的顺序执行,这就是 串行调度 。 串行执行肯定是正确的,但是改变一下位置有影响吗? 这就要看改变顺序之后执行的...
  • 数据库—并发调度的可串行性

    千次阅读 2017-12-27 15:00:12
    数据库管理系统对并发事务不同的调度可能会产生不同的结果,比如两个事务T1和T2,先执行T1或者先执行T2产生的结果可能是不一样的。由于串行调度没有事务间的相互干扰,所以串行调度是正确的。另外,执行结果等价于...
  • 一种Linux网络硬件加密高性能并发调度方法.pdf
  • 1.以两个并发事务情况为例证明,推导到多个事务; 2.列举出两个事务发生不可串行化时出现的情况; 3.针对2中的两种情况,证明若T1和T2遵守两段锁协议,在不发生死锁的情况下,则它们的调度是可串行化的。 ...
  • 【数据库】并发调度的可串行性

    千次阅读 2018-10-22 18:44:33
    DBMS对并行事务中各指令的安排执行(调度)是随机的,而不同的调度可能会产生不同的结果。 将所有事务串行执行的调度策略一定是正确的调度策略。 如果错了,一定是事务程序逻辑上的错误,不是因调度而产生的。 以...
  • 并发操作进行正确调度;保证事务的隔离性;保证数据库的一致性 数据不一致性:由于并发操作破坏了事务的隔离性 并发控制就是要用正确的方式调度并发操作,使一个用户事务的执行不受其他事务的干扰,从而避免...
  • 并发(并行),一直以来都是一个编程语言里的核心主题之一,也是被开发者关注最多的话题;Go 语言作为一个出道以来就自带 『高并发』光环的富二代编程语言,它的并发(并行)编程肯定是值得开发者去探究的,而 Go ...
  • 针对传统长事务处理过程中所表现出的效率低下,操作步骤烦琐复杂且不易实现的不足,提出了一种自组织长事务并发控制模型。该模型允许事务内部结构和同步关系的自主建模, 并通过EAI引擎运行期自行解析事务内部结构,...
  • 所谓并发操作,是指在多用户共享的系统中,许多用户可能同时对同一数据进行操作。所带来的问题是数据的不一致性,具体表现为:丢失更新、不可重复读、读脏数据。... 1.2 并发调度:(Concurrent Schedule)利用分...
  • Java并发编程实战-并发调度模式框架

    千次阅读 2020-03-11 09:45:48
    Java并发编程实战-并发调度模式框架 加油站:抱怨是最没有营养的一件事. 前言: 选择串行的方式执行任务,串行处理机制通常无法提高高吞吐率和快速响应性,于是我们可以显式地为任务创建线程,为每一个请求创建一个...
  • 并发调度的可串行性: 几个事务的并行执行是正确的,当且仅当其结果与按某一次序串行地执行它们时的结果相同。这种并行调度策略称为可串行化(Serializable)的调度。 可串行性是并行事务正确性的唯一准则 ...
  • 数据库是一个共享资源,可以提供多个用户使用。这些用户程序可以一个一个地串行执行,每个时刻只有一个用户程序运行,执行对数据库的存取,其他用户程序必须等到这个用户程序结束...但这样就会产生多个用户程序并发存取
  • 13.笔记go语言——并发调度

    千次阅读 2017-09-28 21:25:15
    13.笔记go语言——并发调度器 go支持创建成千上万并发任务. l 线程多路复用。 l 极小自定义初始栈。 l 任务在多个线程间切换。 三种抽象模型协作 如下图1: 系统限制,允许调整: 如下图2: 创建新并发任务。...
  • Windows 提供的常用对象可分成三类:核心应用服务、线程同步和线程间通讯。其中,开发人员可以使用线程同步对象来协调线程和进程的工作,以使其共享信息并执行任务。此类对象包括互锁数据、临界段、事件、互斥体和...
  • “我在spoon里面运行一个作业只要几秒种,但是在命令行中运行却要好几十秒?” “并行同时运行几个job,就把内存...但kettle本身的调度监控功能却非常弱。连Pentaho官方都建议采用crontab(Unix平台)和计划任务

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 264,989
精华内容 105,995
关键字:

并发调度