5 synchronization

computer architecture › 6.004 computation structures

20 concurrency & synchronization

前言：翻了一下以前看61c的笔记不禁扶额，写得什么鬼。之前的笔记感觉就是简单概念的堆砌加抄写教授讲授的东西，没有太多的思考，所以才感觉学了和没学一样。不管怎么说，既然现在在学6.004，那么就按照课程设置的标准都搞定。

Scenerio 1: video compression algorithms represent each video frame as an array of 8-pixel by 8-pixel macroblocks.

Scenario 2: Applications like video games are naturally divided into the “front-end” user interface and “back-end” simulation and rendering engines.

problem: What’s the advantage of using multiple processes instead of just a single process? How should the processes communicate with each other?

Data-/Event- driven applications have the need to improve the efficiency. We can divide computation among multiple threads of execution. Independent sequential threads compete for shared resource while cooperating sequential threads communicate with each other.

We can divide communication models into:

  1. shared memory
  2. Message passing

goal: synchronization and thread-safe programming

Synchronous Communication in producer-consumer model

Producer sends char to consumer and consumer receives char.

  • constraints

    1. The consumer can’t consume data before it’s produced.
    2. The producer can’t overwrite data before it’s consumed.

  • design a FIFO(first-in first-out) buffers: The producer can run up to N values ahead of the consumer.

    Implementation: ring buffer in shared memory. Consumers control write pointer, producers control read pointer. After space is full, producer starts to write char into receiver.

  • design a data type for synchronization: semaphores

    Basic structure: an integer ≥ 0
    semaphore s = K; // initialize s to K
    New operations (defined on semaphores):

    • wait(semaphore s)
      wait until s > 0, then s = s – 1

    • signal(semaphore s)
      s = s + 1 (one waiting thread may now be able to proceed)

    • Semantic guarantee: A semaphore s initialized to K enforces the precedence constraint:

      The ith call to signal(s) must complete before the (i+K)th call to wait(s) completes.

    Implementation:

    • use a special instruction that performs an atomic read-modify-write
    • use system calls.Works in uniprocessors only, where the kernel is uninterruptible
    1. for precedence: Declare semaphore = 0 -> signal(s) at start of arrow->wait(s) at end of arrow
    2. for resource allocation: Invariant: Semaphore value = number of resources left in pool.

scenerio1:single producer + single consumer

solution: enforce precedence and avoid buffer overflow

Scenerio2: multiple producers and consumers

Problem: producers interfere with each other.

disign: set constraint(mutual exclusion) to critical sections. Only one thread can execute critical sections at the time.

  • Issue: lock granularity->How many locks do we need?

    It depends. Think about the extreme sides: one lock for all accounts or one lock per account? We can choose the middle case.

scenerio3: in the transfer scenario, account A transfer M money to account B.

1
2
3
4
5
6
7
8
9
10
void transfer(int account1, int account2, int amount) {
  //int a = min(account1, account2); dead lock solution
	//int b = max(account1, account2);
	wait(lock[account1]);
	wait(lock[account2]);
	balance[account1] = balance[account1] - amount;
  balance[account2] = balance[account2] + amount;
	signal(lock[account2]);
	signal(lock[account1]);
}

Downside: dead lock: no thread can make progress because all the process are locked.

  • Example: dining philosophers

    问题来源于他们几个人几个筷子，而吃饭的顺序是先拿左边的筷子，当每个人都拿了这只筷子后等待右边有没被拿的筷子，而这种情况无法发生，所有就一直等待，陷入僵局。

    解决这个问题只需要改变用餐的顺序，只要能够避免筷子同时被拿的情况就行。

    solution: Assign a unique number to each chopstick, request resources in a consistent order

  • solution: Establishing and using a global order for shared resources

21 system-level communication

computer system technologies: each part has a detailed specification of the functionality and interface. We can still add things together without knowing the details of those implementations for things evolve rapidly.

Problem: what is the appropriate interface choices for interconnecting system components?

communication channel

fact: the synchronous multi-signal channels of earlier systems -> asynchronous point-to-point channels nowadays

problem 1 : how hard can it be to build a communication channel?