实验三 同步与通信
1）通过fork的方式，产生4个进程P1,P2,P3,P4，每个进程打印输出自己的名字，例如P1输出“I am the process P1”。要求P1最先执行，P2、P3互斥执行，P4最后执行。通过多次测试验证实现是否正确。
实验的关键在于满足执行顺序，使用5个信号量控制整个进程，其中2个信号量在1执行完之后被同时设置为1从而实现P1在P2和P3之前，1个信号量被用作P2和P3的互斥，另外2个信号量分别在P2和P3执行完之后被设置为1，从而实现P4在所有进程之后。实验结果如下。可以看到完全符合题目要求。
2）火车票余票数ticketCount 初始值为1000，有一个售票线程，一个退票线程，各循环执行多次。添加同步机制，使得结果始终正确。要求多次测试添加同步机制前后的实验效果。(说明：为了更容易产生并发错误，可以在适当的位置增加一些pthread_yield()，放弃CPU，并强制线程频繁切换）
题目为典型的生产者消费者问题，其中生产者为退票现成，消费者为售票线程，ticketcount为临界资源。有了这个思路即可解决问题。
测试1
测试2
可以看到结果正确。
3）一个生产者一个消费者线程同步。设置一个线程共享的缓冲区， char buf[10]。一个线程不断从键盘输入字符到buf,一个线程不断的把buf的内容输出到显示器。要求输出的和输入的字符和顺序完全一致。（在输出线程中，每次输出睡眠一秒钟，然后以不同的速度输入测试输出是否正确）。要求多次测试添加同步机制前后的实验效果。
题目类型与上一题目相似。主要思路是引入条件变量，主要包括两个动作：一个线程等待”条件变量的条件成立“而挂起；另一个线程使“条件成立”（给出条件成立信号）。
实验结果：
4）a）通过实验测试，验证共享内存的代码中，receiver能否正确读出sender发送的字符串？如果把其中互斥的代码删除，观察实验结果有何不同？如果在发送和接收进程中打印输出共享内存地址，他们是否相同，为什么？b)有名管道和无名管道通信系统调用是否已经实现了同步机制？通过实验验证，发送者和接收者如何同步的。比如，在什么情况下，发送者会阻塞，什么情况下，接收者会阻塞？c）消息通信系统调用是否已经实现了同步机制？通过实验验证，发送者和接收者如何同步的。比如，在什么情况下，发送者会阻塞，什么情况下，接收者会阻塞？
同时运行 receiver 和 sender 如图
阅读代码发现，互斥的部分为
struct sembuf sem_b;
sem_b.sem_num = 0; //first sem(index=0)
sem_b.sem_flg = SEM_UNDO;
sem_b.sem_op = 1; //Increase 1,make sem=1
删除后再次运行 可以发现接收端无法收到信息 发送端可以正常发送
接收端：
删除掉互斥部分后 无法正常运行
分别添加语句观察地址
printf("\n[Sender] address:%p\n", shm_ptr);
printf("\n[Receiver] address:%p\n", shm_ptr);
可以发现两个进程的内存地址不同，推测原因为sender进程和receiver进程实现了对共享内存shm_ptr的访问，shm_ptr的物理地址有且唯一，但在程序进程中所查询到的地址并不是shm_ptr的物理地址，而是shm_ptr向进程所映射的虚拟地址，所以这就造成了同一块物理地址在不同的进程中的打印值不同的结果
b）
运行pipe程序 结果如图
阻塞现象的描述：
在执行open,write,read等操作时会发生阻塞现象。
因为管道和文件一样，文件read函数以O_RDONLY方式打开也会阻塞，但是文件数据在本地，读取非常快，感觉不到阻塞，但是管道以O_RDONLY方式打开，会阻塞进程，read()函数会等待管道另一端写入数据，直到另一端关闭文件描述符。
有名管道
在两个终端上分别运用fiforcv和fifosnd 得到如下结果
有名管道堵塞与无名管道相同，另外，还存在一种堵塞为通信双方中一方不存在，则另一方堵塞。
c）
在终端上运行client和server程序
队列的阻塞情况与管道类似，在队列中没有消息时读进程会阻塞，在队列中数据已满时写进程会阻塞。
5）阅读Pintos操作系统，找到并阅读进程上下文切换的代码，说明实现的保存和恢复的上下文内容以及进程切换的工作流程。
查阅资料，发现规定进程上下文切换的代码位于/threads/switch.h和/threads/switch.S中。对于该门课程原本的实验来说，这一部分的内容包含在实验一：thread里面。实验原理是通过bochs加载pintos操作系统，该操作系统会根据pintos的实现打印运行结果，通过比较标准输出文档和实际输出，来判断pintos实现是否符合要求。
如果想要了解该系统的上下文切换，我们就不得不去了解timer_sleep函数（/devices/timer.c）。系统原本是使用busy wait实现的，即线程不停地循环，直到时间片耗尽。timer_sleep的实现方式如下：
/* Sleeps for approximately TICKS timer ticks. Interrupts must
be turned on. */
void
timer_sleep (int64_t ticks)
{
int64_t start = timer_ticks ();
ASSERT (intr_get_level () == INTR_ON);
while (timer_elapsed (start) < ticks)
thread_yield();
}
对于timer_ticks函数来说，有intr_level通过intr_disable返回了一内容。继续向下寻找，可以明显发现，intr_level代表能否被中断，而intr_disable做了两件事情：调用intr_get_level()、直接执行汇编代码，调用汇编指令来保证这个线程不能被中断。
/* Returns the current interrupt status. */
enum intr_level
intr_get_level (void)
{
uint32_t flags;
/* Push the flags register on the processor stack, then pop the
value off the stack into `flags’. See [IA32-v2b] “PUSHF”
and “POP” and [IA32-v3a] 5.8.1 “Masking Maskable Hardware
Interrupts”. */
asm volatile (“pushfl; popl %0” : “=g” (flags));
return flags & FLAG_IF ? INTR_ON : INTR_OFF;
}
这个函数一样是调用了汇编指令，把标志寄存器的东西放到处理器棧上，然后把值pop到flags（代表标志寄存器IF位）上，通过判断flags来返回当前终端状态(intr_level)。
至此，函数嵌套了这么多层，整理逻辑：
intr_get_level返回了intr_level的值
intr_disable获取了当前的中断状态， 然后将当前中断状态改为不能被中断， 然后返回执行之前的中断状态。
有以上结论我们可以知道： timer_ticks的intr_get_level做了如下的事情： 禁止当前行为被中断， 保存禁止被中断前的中断状态（用old_level储存）。
/* Returns the current interrupt status. /
/ Enables or disables interrupts as specified by LEVEL and
returns the previous interrupt status. */
enum intr_level
intr_set_level (enum intr_level level)
{
return level == INTR_ON ? intr_enable () : intr_disable ();
}
对于timer_ticks剩下的内容来说，就是用t获取了一个全局变量ticks, 然后返回， 其中调用了set_level函数。set_level的实现机制，根据上述内容容易得出： 如果之前是允许中断的（INTR_ON）则enable否则就disable。intr_enable的实现和之前基本一致：
/* Enables interrupts and returns the previous interrupt status. */
enum intr_level
intr_enable (void)
{
enum intr_level old_level = intr_get_level ();
ASSERT (!intr_context ());
/* Enable interrupts by setting the interrupt flag.
See [IA32-v2b] "STI" and [IA32-v3a] 5.8.1 "Masking Maskable
Hardware Interrupts". */
asm volatile (“sti”);
return old_level;
}
这里直接返回了是否外中断的标志in_external_intr，就是说ASSERT断言这个中断不是外中断（IO等， 也称为硬中断）而是操作系统正常线程切换流程里的内中断（也称为软中断）。至此，我们可以分析出Pintos系统保持原子性的语句，即使用如下的语句包裹：
/* Enables interrupts and returns the previous interrupt status. */
enum intr_level old_level = intr_disable ();
…
intr_set_level (old_level);
对于ticks来说，从pintos被启动开始，ticks就一直在计时，代表着操作系统执行单位时间的前进计量。现在回过来看timer_sleep这个函数，start获取了起始时间，然后断言必须可以被中断，不然会一直死循环下去。
然后就是如下循环：
/* Enables interrupts and returns the previous interrupt status. */
while (timer_elapsed (start) < ticks)
thread_yield();
注意这个ticks是函数的形参不是全局变量，然后看一下这两个函数：对于timer_elapsed来说，它返回了当前时间距离then的时间间隔，那么这个循环实质就是在ticks的时间内不断执行thread_yield。最后来看thread_yield：
/* Yields the CPU. The current thread is not put to sleep and
may be scheduled again immediately at the scheduler’s whim. */
void
thread_yield (void)
{
struct thread *cur = thread_current ();
enum intr_level old_level;
ASSERT (!intr_context ());
old_level = intr_disable ();
if (cur != idle_thread)
list_push_back (&ready_list, &cur->elem);
cur->status = THREAD_READY;
schedule ();
intr_set_level (old_level);
}
thread_current
很明显是返回当前线程起始指针位置。第9行断言是个软中断，第11行至第16包裹起来的就是我们之前分析的线程机制保证的一个原子性操作。对于第12行到15行，如何当前线程不是空闲的线程就调用list_push_back把当前线程的元素扔到就绪队列里面， 并把线程改成THREAD_READY状态。
15行调用schedule:
/* Schedules a new process. At entry, interrupts must be off and
the running process’s state must have been changed from
running to some other state. This function finds another
thread to run and switches to it.
It’s not safe to call printf() until thread_schedule_tail()
has completed. */
static void
schedule (void)
{
struct thread *cur = running_thread ();
struct thread *next = next_thread_to_run ();
struct thread *prev = NULL;
ASSERT (intr_get_level () == INTR_OFF);
ASSERT (cur->status != THREAD_RUNNING);
ASSERT (is_thread (next));
if (cur != next)
prev = switch_threads (cur, next);
thread_schedule_tail (prev);
}
可以看出，首先获取当前线程cur和调用next_thread_to_run获取下一个要run的线程，如果就绪队列空闲直接返回一个空闲线程指针， 否则拿就绪队列第一个线程出来返回。如果当前线程和下一个要跑的线程不是同一个的话调用switch_threads返回给prev。
/* Switches from CUR, which must be the running thread, to NEXT,
which must also be running switch_threads(), returning CUR in
NEXT’s context. */
struct thread *switch_threads (struct thread *cur, struct thread *next);
这个函数实现是用汇编语言实现的在threads/switch.S里。分析一下这个汇编代码： 先4个寄存器压栈保存寄存器状态（保护作用）， 这4个寄存器是switch_threads_frame的成员，然后全局变量thread_stack_ofs记录线程和栈之间的间隙，我们都知道线程切换有个保存现场的过程，先把当前的线程指针放到eax中，并把线程指针保存在相对基地址偏移量为edx的地址中，切换到下一个线程的线程棧指针，保存在ecx中，再把这个线程相对基地址偏移量edx地址（上一次保存现场的时候存放的）放到esp当中继续执行。这里ecx，eax起容器的作用，edx指向当前现场保存的地址偏移量。简单来说就是保存当前线程状态，恢复新线程之前保存的线程状态。然后再把4个寄存器拿出来，这个是硬件设计要求的，必须保护switch_threads_frame里面的寄存器才可以destroy掉eax， edx， ecx。然后注意到现在eax(函数返回值是eax)就是被切换的线程栈指针。我们由此得到一个结论，schedule先把当前线程丢到就绪队列，然后把线程切换如果下一个线程和当前线程不一样的话。
至此，schedule的重点部分分析完成。逻辑继续向上回溯：
thread_schedule_tail其实就是获取当前线程，分配恢复之前执行的状态和现场，如果当前线程死了就清空资源。
schedule其实就是拿下一个线程切换过来继续run。
thread_yield其实就是把当前线程扔到就绪队列里，然后重新schedule，注意这里如果ready队列为空的话当前线程会继续在cpu执行。
最后回溯到我们最顶层的函数逻辑：timer_sleep就是在ticks时间内，如果线程处于running状态就不断把他扔到就绪队列不让他执行。