【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-04-23

【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-04-23

【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 2023-09-01

【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-03-20