lab7

mutex

锁的好处：

  • 锁可以避免更新丢失
  • 使多步操作成为原子操作
  • 锁帮助维护不变量

错误使用锁的问题：

  • 死锁（deadlock） ——改用顺序获取释放锁

  • 模块化（modularity）

  • 性能（performance） ——拆分数据结构

锁实现：

  • 通过硬件实现锁获取的原子性
  • 关闭中断，例如当线程获取锁进入临界区，在临界区产生中断，而中断处理程序也需要获取该，从而产生死锁

_sync_lock_test_and_set 是 GNU Compiler Collection (GCC) 提供的一种原子操作函数

1
2
3
4
5
6
7
8
9
10
11
12
acquire：
while(_sync_lock_test_and_set(&lk_>locked, 1) != 0)
    ;
在locked原子地写入1，但是返回之前的值，若之前的值等于0（没人拿到过锁），代表该进程成功获得锁，退出循环
__sync_synchronize();

...
    
__sync_synchronize();

__sync_lock_release(&lk->locker);
release

__sync_synchronize() 会发出一个全内存屏障，确保在屏障之前的所有内存操作（包括加载和存储）都已完成，并且对之后的操作可见。

  • 死锁：当线程1获得文件A的锁，定时器中断导致切换到线程2，线程2也请求获得该锁，导致发生死锁（除非线程1成功释放文件A的锁,，线程2因为获取锁的时候关闭中断导致无法切换线程）

  • 无锁编程：无锁编程通过使用原子操作和其他同步机制来避免这些问题，从而提高并发性能和可伸缩性。

线程

线程——序列化地执行、寄存器、PC、栈

  • 多线程交织

    • 多核cpu
  • 线程切换（线程通常多余cpu数）

  • 共享内存 ——> 共享数据结果需要锁

    • xv6 内核线程 —— yes

    • xv6 用户线程 —— no 因为xv6并没有实现线程

    • Linux 用户线程 —— yes 在linux，线程就是共享内存的进程

不同任务之间共享一台计算机

  • 事件驱动编程
  • 状态机

线程实现

  • 线程切换——调度器（scheduling）
  • 保存什么寄存器

  • 如何处理计算密集型

    • 时钟中断——>内核——>另一线程
    • PRE-EMPTIVE SCHEDULING（抢占式调度）

  • THREAD“STATE”

    • RUNNING

    • RUNNABLE

    • SLEEPING

context上下文切换

  1. yield()，定时中断引发中断
  2. sched()，确认中断条件
  3. swtch，保存部分寄存器
  4. scheduler，寻找处于RUNNABLE的进程
  5. swtch，保存部分寄存器
  6. sched(),返回
  7. yileld()

swtch实际类似于函数调用

  • 没有保存pc，因为它是一个可预测的值（我们知道要返回到ra寄存器执行）

  • 保存不是调用者保存的寄存器（不保存全部寄存器）

  • 不用c编程是c难以访问特定寄存器
  • 我们需要锁使得上面五个步骤是原子性的。部分操作要禁止中断。

Uthread: switching between threads (moderate)

模仿进程切换保存寄存器。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
	.globl thread_switch
thread_switch:

  		sd ra, 0(a0)
        sd sp, 8(a0)
        sd s0, 16(a0)
        sd s1, 24(a0)
        sd s2, 32(a0)
        sd s3, 40(a0)
        sd s4, 48(a0)
        sd s5, 56(a0)
        sd s6, 64(a0)
        sd s7, 72(a0)
        sd s8, 80(a0)
        sd s9, 88(a0)
        sd s10, 96(a0)
        sd s11, 104(a0)

        ld ra, 0(a1)
        ld sp, 8(a1)
        ld s0, 16(a1)
        ld s1, 24(a1)
        ld s2, 32(a1)
        ld s3, 40(a1)
        ld s4, 48(a1)
        ld s5, 56(a1)
        ld s6, 64(a1)
        ld s7, 72(a1)
        ld s8, 80(a1)
        ld s9, 88(a1)
        ld s10, 96(a1)
        ld s11, 104(a1)



	/* YOUR CODE HERE */
	ret    /* return to ra */

设置保存寄存器的结构体。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct user_context{
  uint64 ra;    //存储返回地址
  uint64 sp;
  // callee-saved
  uint64 s0;
  uint64 s1;
  uint64 s2;
  uint64 s3;
  uint64 s4;
  uint64 s5;
  uint64 s6;
  uint64 s7;
  uint64 s8;
  uint64 s9;
  uint64 s10;
  uint64 s11;
};
struct thread {
  char       stack[STACK_SIZE]; /* the thread's stack */
  int        state;             /* FREE, RUNNING, RUNNABLE */
  struct     user_context user_context;
};

这里是模拟线程的执行，通过设置ra寄存器为要执行的线程的函数地址，使之返回时达到线程执行的效果。通过设置sp寄存器为结构体stack地址（堆上内存），将堆模拟为栈，实现不同线程拥有各自栈的情况。

同时，相较于进程切换需要保存两次寄存器（原进程跳转到scheduler再跳转到新进程），这里的线程切换只需要保存一次寄存器，然后由scheduler循环调度（不存在选择线程情况）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void 
thread_schedule(void)
{
 ...
    /* YOUR CODE HERE
     * Invoke thread_switch to switch from t to next_thread:
     * thread_switch(??, ??);
     */
    thread_switch((uint64)&t->user_context,(uint64)&current_thread->user_context);

}

void 
thread_create(void (*func)())
{
  struct thread *t;

  for (t = all_thread; t < all_thread + MAX_THREAD; t++) {
    if (t->state == FREE) break;
  }
  t->state = RUNNABLE;
  // YOUR CODE HERE
  t->user_context.ra = (uint64)(*func);
  t->user_context.sp = (uint64)t->stack + STACK_SIZE; 
}

Using threads (moderate)

实际上让我们熟悉锁。我们只需在临界区加锁即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
pthread_mutex_t lock[NBUCKET];


static 
void put(int key, int value)
{
 	...
 
    pthread_mutex_lock(&lock[i]);
    insert(key, value, &table[i], table[i]);
    pthread_mutex_lock(&lock[i]);
  }
}


int
main(int argc, char *argv[])
{
  pthread_t *tha;
  void *value;
  double t1, t0;

  for(int i = 0; i < NBUCKET; i++)
  {
    pthread_mutex_init(&lock[i], NULL);
  }
}

Barrier(moderate)

用锁实现屏障。

  • 当线程未全部到达时，阻塞所有线程
  • 当最后一个线程到达时，达成条件，越过屏障，增加round，置零nthread，同时唤醒所有线程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
static void 
barrier()
{
  // YOUR CODE HERE
  //
  // Block until all threads have called barrier() and
  // then increment bstate.round.
  //
  pthread_mutex_lock(&bstate.barrier_mutex);
  bstate.nthread++;
 
  //fprintf(stderr, "%d", bstate.nthread);
  if (bstate.nthread != nthread ) {
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);   //在此等待
  }
  if (bstate.nthread == nthread) {
    bstate.nthread = 0;
    bstate.round++;
     pthread_cond_broadcast(&bstate.barrier_cond);
  }
  pthread_mutex_unlock(&bstate.barrier_mutex);
  
}