代码编织梦想

Lock-based Concurrent Data Structures

带着问题:给定一个数据结构,如何给其添加锁使其拥有正确性和高效性?

1. Concurrent Counters

1.1 Simple But Not Scalable

在这里插入图片描述
在这里插入图片描述
上述代码满足了正确性,但是对于性能,我们一无所知。为了了解性能优劣,做了一个基准测试,如下所示(precise)
在这里插入图片描述
从上图可以看出,单线程性能可以,但是一旦多线程,性能极差!

perfect scaling:多处理器处理多线程性能和单处理器处理单线程性能几乎一样。

1.2 Scalable Counting

一种解决可扩展问题的方法叫approximate counter(近似计数)
近似计数的基本思想如下:当在给定内核上运行的线程希望增加计数器时,它会增加其本地计数器,通过相应的本地锁同步对该本地计数器的访问。由于每个CPU都有自己的本地计数器,所以CPU上的线程可以在不用争的情况下更新本地计数器,因此该计数器的更新是可伸缩的。为了使全局计数器保持最新,通过获取全局锁并将其递增本地计数器的值,本地值会定期传输到全局计数器。
看一个例子,定期传输阈值为5。如下所示
在这里插入图片描述
再看一次下图(approximate)
在这里插入图片描述
性能非常好(very good)!

下图展示了传输阈值对性能的影响:
在这里插入图片描述
S越小,虽然性能越低,但是全局计数器越精确;S越大,性能越好,但是全局计数器越滞后。(精度/性能不可兼得

下面是近似计数的代码
在这里插入图片描述

2. Concurrent Linked Lists

在这里插入图片描述
对于上述代码,我们能否重写List_Insert()List_Lookup()使其在并发插入情况下避免失败路径也需要调用unlock
在这里插入图片描述

2.1 Scaling Linked Lists

一种在list中实现更多并发性的技术:hand-over-hand locking
其基本思想如下:不是整个list有一个锁,而是list中的每个node都有一个锁。在遍历list时,代码首先获取下个node的锁,然后释放当前node的锁。

这种方法确实有意义,实现了list操作的高度并发性。但是很难使这种结构比简单的单锁方法快(获取和释放遍历list中每个node的锁太耗时)。

3. Concurrent Queues

在这里插入图片描述
有两个锁,一个队头一个队尾,分别适用于入队和出队。

4. Concurrent Hash Table

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

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/weixin_51703174/article/details/111088538

计算机操作系统(虚拟存储器篇含分页存储管理方式与页面置换算法等)OperatingSystem-VirtualMemory-爱代码爱编程

操作系统虚拟存储器篇 一、虚拟存储器简介 1、虚拟存储器定义 虚拟存储器是指具有请求调入功能和置换功能,能从逻辑上对内存容量加以扩充的一种存储器系统。虚拟存储器只是一个容量非常大的存储器的逻辑模型,不是任何实际的物理存储器。它借助于磁盘等辅助存储器来扩大主存容量,使之为更大或更多的程序所使用。虚拟存储器指的是主存-外存层次,它以透明的方式为用户提供了

模拟进程调度算法四种(Java)-爱代码爱编程

在这里插入代码片@TOC 模拟进程调度算法四种(Java) 这是大三上学期操作系统的模拟进程调度的实验,一开始其实都不知道该怎么写去表示进程调度的过程,后来翻阅了许多博客并加以总结才知道,可能有错误之处,希望大家能多多指出错误,一起进步一起学习。 算法一:先来先服务(FCFS) 按照进程进入就绪队列的先后顺序调度并分配处理机执行。先来先服务调度算法

惊艳!Chrome和Edge最大威胁来了....-爱代码爱编程

现如今,浏览器在工作和学习中扮演的角色越来越重。 随之而来的问题就是浏览器变得越来越臃肿、越来越混乱。 密密麻麻的选项卡、无处不在的浏览器窗口。虽然,它举足轻重,但是与其他应用程序之间一直是隔离状态,无法与其他内容进行很好的集成在一起。 今天要介绍的这款浏览器,完全改变了这些。 下面就来开始介绍本文的主角--Sidekick。 Side

性能分析Linux服务器CPU利用率-爱代码爱编程

1.  指标范围 1.1  User mode CPU utilization+ System mode CPU utilization 合理值:60-85%,如果在一个多用户系统中us+sy时间超过85%,则进程可能要花时间在运行队列中等待,响应时间和业务吞吐量会受损害;us过大,说明有用户进程占用很多cpu时间,需要进一步的分析其它软硬件因素;sy

图文:console terminal tty shell 这些概念的历史渊源-爱代码爱编程

在很久以前,人们使用的电脑是可以通过一些按键直接控制比如寄存器等底层硬件设备的。这些按键所在的操作面板就是控制台(console)。 简单的说那时候没有操作系统帮助你控制输入输出,控制寄存器内存,所以全是手动操作。 后来为了不局限于距离(脑补的…),人们开始使用电缆去连接计算机,这时候电缆的开始端就是这台计算机,另一边当然就是终端(Terminal)。

第四章-存储器管理 (地址变换必考!SWUST操作系统期末复习试题+历届真题)-爱代码爱编程

1.何谓装入时动态链接?装入时动态链接方式有何优点? 装入时动态链接是指用户将源程序编译后所得到的一组目标模块,在装入内存时,采用边装入边链接的一种链接方式,即在装入一个目标模块时,若发生一个外部的模块调用事件,将引入装入程序去相应的外部目标模块,把它装入内存中,并修改目标模块中的相对地址。 优点:①便于修改和更新②便于实现对目标模块的共享2.何谓运行时动