西维蜀黍

【Operating System】进程 - 进程通讯 - 信号量(Semaphore)

信号量 Semaphore 信号量(Semaphores)机制被用作进程/线程间同步,且包括两个原语(primitive), down 和 up 。 信号量机制最初由 Dijkstra 在 1965 年提出   ...


【Concurrent Control】CAS(Compare-and-swap)

CAS(Compare and swap)

CAS(比较与交换,Compare and swap) 算法是一种有名的非阻塞算法(non-blocking algorithm),同时也是一种无锁算法(lock-free algorithm),即在没有锁的情况下实现同步(并发控制),基于**乐观并发控制(optimistic concurrent control)**的思想。

2021.5 update:

  • 这里避免使用“乐观并发控制(optimistic lock)”这个词,原因是这可能会带来confusion
  • 因为“乐观并发控制”本身 imply使用到了锁(lock),而锁本来就是悲观的(pessimistic),这与乐观(optimistic)相互矛盾
  • 另外,乐观并发控制其实描述的是一种进行并发控制(concurrent control)的思想,在这种思想中并不存在锁
  • 因而,就可能导致 confusion
  • 如果称为乐观并发控制(optimistic concurrent control),就会更准确。因而在本文中,不会使用“乐观锁”这个词,而是使用乐观并发控制。
  • 也可能称为无锁并发控制(lock-free concurrent control)

java.util.concurrent包中的原子类(比如 AtomicInteger)就是通过CAS来实现乐观并发控制的。

当多个线程尝试使用 CAS 同时更新同一个变量时,只有其中一个线程能成功地更新变量的值,而其它线程都失败,失败的线程并不会被挂起,而是被告知这次竞争中失败,并可以再次尝试。

  ...


【Golang】源码 - sync 包 - Mutex

Background

悲观锁和乐观并发控制机制

悲观锁是一种悲观思想,它总认为最坏的情况可能会出现,它认为数据很可能会被其他人所修改,不管读还是写,悲观锁在执行操作之前都先上锁。

对读对写都需要加锁导致性能低,所以悲观锁用的机会不多。但是在多写的情况下,还是有机会使用悲观锁的,因为乐观并发控制机制遇到写不一致的情况下会一直重试,会浪费更多的时间。

乐观并发控制机制的思想与悲观锁的思想相反,它总认为资源和数据不会被别人所修改,所以读取不会上锁,但是乐观并发控制机制在进行写入操作的时候会判断当前数据是否被修改过。

乐观并发控制机制的实现方案主要包含CAS和版本号机制。乐观并发控制机制适用于多读的场景,可以提高吞吐量。

CAS

CAS即Compare And Swap(比较与交换),是一种有名的无锁算法。即不使用锁的情况下实现多线程之间的变量同步,也就是在没有线程被阻塞的情况下实现变量的同步,所以也叫非阻塞同步。CAS涉及三个关系:指向内存一块区域的指针V、旧值A和将要写入的新值B。

总结来说:

  • CAS 算法:会执行一个原子操作
  • 在这个原子操作中,先检查当前value是否等于current,如果相等,则意味着value没被其他线程修改过,更新并返回true。如果不相等,compareAndSet则会返回false,然后循环继续尝试更新。

CAS实现的乐观并发控制会带来潜在的ABA问题。

CAS 的权衡

轻度到中度的争用情况下,非阻塞算法的性能会超越阻塞算法,因为 CAS 的多数时间都在第一次尝试时就成功,而发生争用时的开销也不涉及线程挂起和上下文切换,只多了几个循环迭代。没有争用的 CAS 要比没有争用的锁便宜得多(这句话肯定是真的,因为没有争用的锁涉及 CAS 加上额外的处理),而争用的 CAS 比争用的锁获取涉及更短的延迟。

高度争用的情况下(即有多个线程不断争用一个内存位置的时候),基于锁的算法开始提供比非阻塞算法更好的吞吐率,因为当线程阻塞时,它就会停止争用,耐心地等候轮到自己,从而避免了进一步争用。但是,这么高的争用程度并不常见,因为多数时候,线程会把线程本地的计算与争用共享数据的操作分开,从而给其他线程使用共享数据的机会。

版本号机制

版本号机制是通过一个版本号version来实现版本控制。

自旋锁(Spin Lock)

之前介绍的CAS就是自旋锁的一种具体实现。同一时刻只能有一个线程获取到锁,没有获取到锁的线程通常有两种处理方式:

  • 一直循环等待判断该资源是否已经释放锁,这种锁叫做自旋锁,它不用将线程阻塞起来(NON-BLOCKING);
  • 把自己阻塞起来,等待重新调度请求,这种是互斥锁。

自旋锁的原理比较简单,如果持有锁的线程能在短时间内释放锁资源,那么那些等待竞争锁的线程就不需要做内核态和用户态之间的切换进入阻塞状态,它们只需要等一等(自旋),等到持有锁的线程释放锁之后即可获取,这样就避免了用户进程和内核切换的消耗。

但是如果长时间上锁的话,自旋锁会非常耗费性能,它阻止了其他线程的运行和调度。线程持有锁的时间越长,则持有该锁的线程将被OS调度程序中断的风险越大。如果发生中断情况,那么其他线程将保持旋转状态(反复尝试获取锁),而持有该锁的线程并不打算释放锁,这样导致的是结果是无限期推迟,直到持有锁的线程可以完成并释放它为止。

解决上面这种情况一个很好的方式是给自旋锁设定一个自旋时间,等时间一到立即释放自旋锁。自旋锁的目的是占着CPU资源不进行释放,等到获取锁立即进行处理。

信号量 Semaphore

信号量是 Edsger Dijkstra 发明的数据结构,在解决多种同步问题时很有用。其本质是一个整数,并关联两个操作:

  • 申请acquire(也称为 waitdecrementP 操作)
  • 释放release(也称 signalincrementV 操作)

acquire操作将信号量减 1,

  • 如果结果值为负则线程阻塞,且直到其他线程进行了信号量累加为正数才能恢复。
  • 如结果为正数,线程则继续执行。

release操作将信号量加 1,如存在被阻塞的线程,此时他们中的一个线程将解除阻塞。

Go 运行时提供的runtime_SemacquireMutexruntime_Semrelease函数可用来实现sync.RWMutex互斥锁。

  ...


【IoT】Home Assistant集成米家蓝牙湿度计

温度/湿度传感器 - miaomiaoce.sensor_ht.t2

https://www.home-assistant.io/integrations/mitemp_bt/

   NAME:     Temperature & humidity sensor
   ID:       blt.3.150ujduhc5g00
   BLE KEY:  4C5A05AF79C346188FE6916AFB0C3945
   TOKEN:    589A9A1FEC9B3798588A4BA3
   MODEL:    miaomiaoce.sensor_ht.t2

Verify 配置文件:

$ hass --script check_config -c .
  ...


【Linux】操作 - 解压

Install

unzip

$ sudo apt install unzip -y

Achieve

tar

# [c]reate an archive and write it to a [f]ile:
$ tar cf target.tar file1 file2 file3

# [c]reate a g[z]ipped archive and write it to a [f]ile:
$ tar czf target.tar.gz file1 file2 file3

# [c]reate a g[z]ipped archive from a directory using relative paths:
$ tar czf target.tar.gz --directory=<path/to/directory> .
  ...