西维蜀黍

【Golang】源码 - Atomic 包

Definition

// A Value provides an atomic load and store of a consistently typed value.
// The zero value for a Value returns nil from Load.
// Once Store has been called, a Value must not be copied.
//
// A Value must not be copied after first use.
type Value struct {
	v interface{}
}

// ifaceWords is interface{} internal representation.
type ifaceWords struct {
	typ  unsafe.Pointer
	data unsafe.Pointer
}
  ...

Posted by Wei on 2021-07-31, Last Modified on 2025-08-11

【Golang】使用 - Atomic Counters

  ...

Posted by Wei on 2021-07-31, Last Modified on 2025-08-11

【Lock】活锁（Livelock）

活锁（Livelock）

Analygy

考虑一个场景：进程P1占有A资源并请求占用资源B，进程P2占有B资源并请求占用资源A。

如果是等待式的请求，两者都会陷入无尽的等待中。这是死锁（deadlock）。

如果请求不是等待式的，而是一旦发现资源已经被占有了，就释放所有等待占用和已经占用的资源，并重新开始。此时P1放弃占有资源A重新开始，P2放弃占有资源B重新开始。则P1、P2可能会出现重复不断的开始-回滚循环。这种情况我们称之为活锁（livelock）。

相比死锁，活锁更难检测，也更浪费资源（重复不断的开始-回滚循环）。

  ...

Posted by Wei on 2021-07-31, Last Modified on 2025-08-11

【Lock】自旋锁（Spinlock）

背景

在介绍自旋锁前，我们需要介绍一些前提知识来帮助大家明白自旋锁的概念。

阻塞或唤醒一个Java线程需要操作系统进行 context swtich（e.g., kernel space <-> user space, interrupt handling due to I/O or waiting for synchrnization operation to complete）来完成，

Refer to https://swsmile.info/post/os-context-swtich/ in details.

这种 context 转换需要耗费处理器时间。如果同步代码块中的内容过于简单，context 转换消耗的时间有可能比用户代码执行的时间还要长。

在许多场景中，同步资源的锁定时间很短，为了这一小段时间去切换线程，线程挂起和恢复现场的花费可能会让系统得不偿失。如果物理机器有多个处理器，能够让两个或以上的线程同时并行执行，我们就可以让后面那个请求锁的线程不放弃CPU的执行时间，看看持有锁的线程是否很快就会释放锁。

而为了让当前线程“稍等一下”，我们需让当前线程进行自旋，如果在自旋完成后前面锁定同步资源的线程已经释放了锁，那么当前线程就可以不必阻塞而是直接获取同步资源，从而避免切换线程的开销。这就是自旋锁。

  ...

Posted by Wei on 2021-07-31, Last Modified on 2025-08-11

【Operating System】进程 - 进程间通讯中的问题

一些概念

竞态条件（Race Conditions）

在一些操作系统中，一起协同工作的进程可能共享一块存储空间，任何一个进程可以读或者写这个存储空间。这个存储空间可以是内存中的一块区域，也可以是文件系统中的一个文件。

举个例子，在多任务打印缓存处理器（print spooler）的工作场景中，当一个进程希望打印一个文件时，它会将这个文件的名称输入到一个特定的缓存处理器目录（spooler directory）中。打印机守护进程（printer daemon）会周期性地检查缓存处理器目录中是否存在任何文件名，当存在时，则打印他们，并且将这个文件名从目录中移除。

  ...

Posted by Wei on 2021-07-30, Last Modified on 2025-08-11

【Operating System】进程 - 生产者消费者问题（Producer-consumer Problem）

生产者-消费者问题（The Producer-Consumer Problem）

也称为有界缓冲区问题（Bounded-buffer Problem）。

In the producer–consumer problem, one process (the producer) generates data items and another process (the consumer) receives and uses them. They communicate using a queue of maximum size N and are subject to the following conditions:

  • the consumer must wait for the producer to produce something if the queue is empty;
  • the producer must wait for the consumer to consume something if the queue is full.

The semaphore solution to the producer–consumer problem tracks the state of the queue with two semaphores: emptyCount, the number of empty places in the queue, and fullCount, the number of elements in the queue. To maintain integrity, emptyCount may be lower (but never higher) than the actual number of empty places in the queue, and fullCount may be lower (but never higher) than the actual number of items in the queue. Empty places and items represent two kinds of resources, empty boxes and full boxes, and the semaphores emptyCount and fullCount maintain control over these resources.

The binary semaphore useQueue ensures that the integrity of the state of the queue itself is not compromised, for example by two producers attempting to add items to an empty queue simultaneously, thereby corrupting its internal state. Alternatively a mutex could be used in place of the binary semaphore.

Solution

生产者-消费者问题是利用 Sleep and Wakeup 方案提供进程间互斥（Mutual Exclusion）的一个具体实例。

两个进程共享一个大小固定的缓冲区，其中的一个进程（称为生产者），将信息放入缓冲区中；而另一个进程（称为消费者），将信息从缓冲区中取出。

事实上，包含 m 个生产者和 n 个消费者是完全有可能的，只是我们通过最小化数量突出解决方案模型本身。

当缓冲区满时，生产者进行休眠，直到有任何消费者从缓冲区中移除内容时而被唤醒；当缓冲区为空时，消费者进行休眠，直到有生产者将内容放入缓冲区时而被唤醒。

  ...

Posted by Wei on 2021-07-30, Last Modified on 2025-08-11

【Operating System】进程 - 优先级翻转（Priority Inversion）

Background

By far the most pervasive mechanism to control the sequencing of tasks in time-constrained systems is priority scheduling. Priority scheduling means that whenever a task or thread is ready to execute, its priority relative to other threads determines the actual order of execution. Ideally, priorities in a time-constrained system should always reflect the time constraints for the tasks. A useful priority assignment heuristic is to assign higher priorities to tasks that are part of tighter time constraints. Thus, a task that needs to respond in a shorter time will get higher priority than a task that needs to respond in a longer time.

The most desirable state of a priority scheduler is that the system should always be executing the task with the highest priority. However, it is impossible for an operating system to invariably achieve this state. When circumstances within the system force a higher-priority task to wait for a lower-priority task, priority inversion occurs. This can lead to unbounded priority inversion (discussed in the next section), where a high-priority thread misses its deadline.

优先级反转（Priority Inversion）

Priority inversion is a bug that occurs when a high priority task is indirectly preempted by a low priority task. For example, the low priority task holds a mutex that the high priority task must wait for to continue executing.

This violates the priority model that high priority tasks can only be prevented from running by higher priority tasks and briefly by low priority tasks which will quickly complete their use of a resource shared by the high and low priority tasks.

Bounder Priority Inversion

In the simple case, the high priority task (Task H) would be blocked as long as the low priority task (Task L) held the lock. This is known as “bounded priority inversion,” as the length of time of the inversion is bounded by however long the low priority task is in the critical section (holding the lock).

As you can see in the diagram above, Task H is blocked so long as Task L holds the lock. The priority of the tasks have been indirectly “inverted” as now Task L is running before Task H.

  ...

Posted by Wei on 2021-07-30, Last Modified on 2025-08-11

【Golang】生产者消费者问题（Producer–consumer Problem）

不需要close

Sequential Producer

package main

import (
	"fmt"
	"time"
)

type producer struct {
	data chan int
}

func main() {
	prod := &producer{
		data: make(chan int, 10),
	}

	// producer
	go func() {
		var i int32 = 0
		for {
			i = calculateNextInt(i)
			prod.data <- int(i)
		}
	}()

	// consumer
	for {
		a := <-prod.data
		fmt.Printf("consume %v\n", a)
	}
}

func calculateNextInt(prev int32) int32 {
	time.Sleep(1 * time.Second) // pretend this is an expensive operation
	return prev + 1
}
  ...

Posted by Wei on 2021-07-29, Last Modified on 2021-07-29

【Golang】使用 - Semaphore

Demo

package main

import (
	"context"
	"fmt"
	"log"
	"time"

	"golang.org/x/sync/semaphore"
)

// Example_workerPool demonstrates how to use a semaphore to limit the number of
// goroutines working on parallel tasks.
//
// This use of a semaphore mimics a typical “worker pool” pattern, but without
// the need to explicitly shut down idle workers when the work is done.
func main() {
	ctx := context.TODO()

	var (
		maxWorkers = 2
		sem        = semaphore.NewWeighted(int64(maxWorkers))
		out        = make([]int, 6)
	)

	// Compute the output using up to maxWorkers goroutines at a time.
	for i := range out {
		// When maxWorkers goroutines are in flight, Acquire blocks until one of the
		// workers finishes.
		fmt.Println("wanna acquire", i, time.Now())
		if err := sem.Acquire(ctx, 1); err != nil {
			log.Printf("Failed to acquire semaphore: %v", err)
			break
		}
		fmt.Println("acquired", i, time.Now())

		go func(i int) {
			defer sem.Release(1)
			out[i] = collatzSteps(i + 1)
			fmt.Println("release", i, time.Now())

		}(i)
	}

	// Acquire all of the tokens to wait for any remaining workers to finish.
	//
	// If you are already waiting for the workers by some other means (such as an
	// errgroup.Group), you can omit this final Acquire call.
	if err := sem.Acquire(ctx, int64(maxWorkers)); err != nil {
		log.Printf("Failed to acquire semaphore: %v", err)
	}

	fmt.Println(out)

}

// collatzSteps computes the number of steps to reach 1 under the Collatz
// conjecture. (See https://en.wikipedia.org/wiki/Collatz_conjecture.)
func collatzSteps(n int) (steps int) {
	if n <= 0 {
		panic("nonpositive input")
	}

	for ; n > 1; steps++ {
		if steps < 0 {
			panic("too many steps")
		}

		if n%2 == 0 {
			n /= 2
			continue
		}

		const maxInt = int(^uint(0) >> 1)
		if n > (maxInt-1)/3 {
			panic("overflow")
		}
		n = 3*n + 1
	}

	time.Sleep(2 * time.Second)
	return steps
}

output:

wanna acquire 0 2021-07-29 21:29:55.972384 +0800 +08 m=+0.000192241
acquired 0 2021-07-29 21:29:55.97253 +0800 +08 m=+0.000338301
wanna acquire 1 2021-07-29 21:29:55.972537 +0800 +08 m=+0.000345751
acquired 1 2021-07-29 21:29:55.97254 +0800 +08 m=+0.000348581
wanna acquire 2 2021-07-29 21:29:55.972543 +0800 +08 m=+0.000351301

release 0 2021-07-29 21:29:57.974328 +0800 +08 m=+2.002084988
release 1 2021-07-29 21:29:57.974341 +0800 +08 m=+2.002097828
acquired 2 2021-07-29 21:29:57.974401 +0800 +08 m=+2.002157377
wanna acquire 3 2021-07-29 21:29:57.974408 +0800 +08 m=+2.002164457
acquired 3 2021-07-29 21:29:57.974414 +0800 +08 m=+2.002170807
wanna acquire 4 2021-07-29 21:29:57.974418 +0800 +08 m=+2.002175267

release 3 2021-07-29 21:29:59.974625 +0800 +08 m=+4.002330347
acquired 4 2021-07-29 21:29:59.974662 +0800 +08 m=+4.002367247
wanna acquire 5 2021-07-29 21:29:59.974668 +0800 +08 m=+4.002373527
release 2 2021-07-29 21:29:59.97462 +0800 +08 m=+4.002325277
acquired 5 2021-07-29 21:29:59.974684 +0800 +08 m=+4.002389377

release 4 2021-07-29 21:30:01.977041 +0800 +08 m=+6.004694503
release 5 2021-07-29 21:30:01.977047 +0800 +08 m=+6.004701013
[0 1 7 2 5 8]
  ...

Posted by Wei on 2021-07-29, Last Modified on 2025-08-11

【Cache System】Cache Replacement Algorithms

Cache Algorithm (Cache Replacement Algorithms, Cache Replacement Policies, Eviction Policy)

In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions, or algorithms, that a computer program or a hardware-maintained structure can utilize in order to manage a cache of information stored on the computer. Caching improves performance by keeping recent or often-used data items in memory locations that are faster or computationally cheaper to access than normal memory stores. When the cache is full, the algorithm must choose which items to discard to make room for the new ones.

  ...

Posted by Wei on 2021-07-28, Last Modified on 2025-08-11

FEATURED TAGS
algorithm algorithmproblem architecturalpattern architecture aws blockchain c# cachesystem codis compile concurrentcontrol database dataformat datastructure debug design designpattern distributedsystem django docker domain engineering freebsd git golang grafana hackintosh hadoop hardware hexo http hugo ios iot java javaee javascript kafka kubernetes linux linuxcommand linuxio lock macos markdown microservices mysql nas network networkprogramming nginx node.js npm oop openwrt operatingsystem padavan performance programming prometheus protobuf python redis router security shell software testing spring sql systemdesign truenas ubuntu vmware vpn windows wmware wordpress xml zookeeper
ABOUT ME
avatar

🐒 Software engineer | 📷 Photographer | 👹 Urban explorer

FRIENDS