CSAPP-Synchronization

现代操作系统提供三种构造并发程序的方法：

1.进程

2.I/O多路复用

3.线程

基于进程的并发编程

1.内核自动管理多个逻辑流

2.每个进程有私有的地址空间（进程切换的时候要保存和载入数据）

void sigchld_handler(int sig){
    while (waitpid(-1, 0, WNOHANG) > 0)
        ;
    return;
    // Reap all zombie children
}
int main(int argc, char **argv) {
    int listenfd, connfd;
    socklen_t clientlen;
    struct sockaddr_storage clientaddr;
    
    Signal(SIGCHLD, sigchld_handler);
    listenfd = Open_listenfd(argv[1]);
    while (1) {
        clientlen = sizeof(struct sockaddr_storage);
        connfd = Accept(listenfd, (SA *) &clientaddr, &clientlen);
        if (Fork() == 0) {
            Close(listenfd); // Child closes its listening socket
            echo(connfd); // Child services client
            Close(connfd); // Child closes connection with client
            exit(0); // Child exits
        }
        Close(connfd); // Parent closes connected socket (important!)
    }
}

服务器在accept函数中等待连接请求，然后客户端通过调用connect函数发送连接请求，最后服务器在accept中返回connfd并且fork一个子进程来处理客户端链接，链接就建立在listenfd和connfd之间。

• 每个客户端由独立的子进程处理，而且必须回收僵尸进程，避免内存泄漏

• 不同进程之间不共享数据

• 父进程和子进程都有listenfd和connfd，所以父进程中要关闭connfd，子进程要关闭listenfd

  • 内核会保存对每个socket的引用计数，(refcnt(connfd)=2)，所以父进程需要关闭connfd，这样在子进程结束后引用计数才会变为0

优点：只共享已打开的file table，无论是descriptor还是全局变量都不共享，不容易造成同步问题。

缺点：带来额外的进程管理开销，进程间通信需要用IPC

基于事件 I/O multiplexing

1.由程序员手动控制多个逻辑流。

2.所有逻辑流共享同一个地址空间

基于线程

内核自动管理多个逻辑流

每个线程共享地址空间

属于基于进程和基于事件的混合体

传统观点下的进程

线程

一个进程有多个线程，每个线程有自己的线程id，有自己的逻辑控制流，也有自己用来保存局部变量的栈（其他线程可以修改）。而且共享所有代码，数据和内核上下文。

多线程

概念上的

实际上的

不同线程之间的数据其实可以相互访问

Shared variable

a variable x is shared if and only if multiple threads reference some instance of x

global & local variable

example

ptr是全局变量，shared by main thread and thread 1&2

i is only referenced by main, so not shared

msgs is referenced by all 3 threads, so is is shared

myid is only referenced by thread 1 & 2 seperately

static int cnt is referenced by both 1 &2

so if multiple threads reference the same x instance, the x is shared

bad example

看loop的汇编代码

正常结果

下图是线程2提前Load了cnt，结果rdx2为0，正确结果是等到线程1store之后线程2再load

volatile

volatile的本意是“易变的” 因为访问寄存器要比访问内存单元快的多,所以编译器一般都会作减少存取内存的优化，但有可能会读脏数据。当要求使用volatile声明变量值的时候，系统总是重新从它所在的内存读取数据，即使它前面的指令刚刚从该处读取过数据。精确地说就是，遇到这个关键字声明的变量，编译器对访问该变量的代码就不再进行优化，从而可以提供对特殊地址的稳定访问；如果不使用valatile，则编译器将对所声明的语句进行优化。（简洁的说就是：volatile关键词影响编译器编译的结果，用volatile声明的变量表示该变量随时可能发生变化，与该变量有关的运算，不要进行编译优化，以免出错）

再看信号量:

信号量的提出，是为了解决同步不同执行线程问题的方法。

什么是信号量？

信号量s是一个具有非负值的全局变量。

只能由两种特殊操作P，V来处理

P，V原理如上图

定义P和V，为了确保一个正在运行的程序绝不可能进入s是负值的状态，这个属性叫信号量不变性

使用信号量实现互斥

代码实现

volatile int cnt=0; 
sem_t mutex; //声明信号量mutex

Sem_init(&mutex,0,1);//主线程中初始化


//在线程例程中对共享变量cnt的更新包围P和V操作，从而保护他们
for(i=0;i<niters;i++){

    P(&mutex);
    cnt++;
    V(&mutex);
}

使用信号量来调度共享资源

生产者和消费者

读者和写者问题

线程安全

一个函数如果被多个并发线程反复调用的时候，会一直产生正确的结果，否则就是线程不安全的。

1.不保护共享变量的函数

解决方案，利用P,V这样的同步操作来保护共享的变量

2.保持跨越多个调用状态的函数

3.返回指向静态变量的指针的函数

4.调用线程不安全函数的函数。

1.如果函数f调用线程不安全函数g。那么f可能不安全。
2.如果g是第二类，那么f一定不安全，也没有办法去修正，只能改变g.
3.如果g是第一，三类，可以用加锁-拷贝技术来解决。

竞争

当一个程序的正确性依赖于一个线程要在另一个线程到达y点之前到达它的控制流中的x点，就会发生竞争。

1.通常，竞争发生的理由是因为程序员假定某种特殊的轨迹线穿过执行状态空间。

死锁

练习：

判断 myid会不会出现竞争

// 版本一
void *foo(void *vargp)
{
    int myid;
    myid = *((int *)vargp);
    Free(vargp);
    printf("Thread %d\n", myid);
}
int main()
{
    pthread_t tid[2];
    int i, *ptr;
    
    for (i = 0; i < 2; i++)
    {
        ptr = Malloc(sizeof(int));
        *ptr = i;
        Pthread_create(&tid[i], 0, foo, ptr);
    }
    Pthread_join(tid[0], 0);
    Pthread_join(tid[1], 0);
}

循环中每次创建不同的指针，两个线程不是共享同一个变量。

---

// 版本二
void *foo(void *vargp)
{
    int myid;
    myid = *((int *)vargp);
    printf("Thread %d\n", myid);
}
int main()
{
    pthread_t tid[2];
    int i;
    
    for (i = 0; i < 2; i++)
        Pthread_create(&tid[i], NULL, foo, &i);
    Pthread_join(tid[0], NULL);
    Pthread_join(tid[1], NULL);
}

两个线程共享i变量，而i++和myid = ((int )vargp)
会发生竞争，当然前提是传的是引用&i，因为这样的话foo函数会改变i本身的值，若如果是传值i，则只会改变i的一个副本。