考试时间11-23晚7：00—9：00，因有事耽误，开始答题已经是7：30了，整个答题时间就一个半小时，所以当时只能好好把会的做完。下面是我最终提交的答案：

（一）现代的处理器提供了compare-and-swap原子操作：int compare_and_swap(int * pv, const int cv, const int nv);即比较*pv与cv，如果相等，则把*pv值替换为nv并返回*pv原值，否则返回*pv的值。请利用上述原子操作实现如下操作：int inc_if_gt_zero(int * pv);

即如果*pv > 0，则把*pv加1并返回修改后的*pv，否则返回*pv。

结果要线程安全且不使用锁、信号灯、互斥量、临界区或类似机制。

答：此题很晕，没有做。

（二）假设有一台机器A，有1G内存，另外若干台机器（B、C、D……）通过网络TCP向机器A传输数据，A机器把接收到的数据写入硬盘。B、C、D等机器的数据按记录传输，每条记录大小范围：1M~16M。 为了保证每条记录的原子性，B、C、D等机器每次先向A汇报数据量大小，然后再进行数据传输。 汇报数据大小时，A机器会给记录分配一个序号，写入文件时每个记录按序号顺序、原子写入。 B、C、D等机器处理速度和网络速度都不尽相同，因此汇报数据大小之后，记录数据传递到A的顺序可能不一定按分配好的序号顺序到达。 现在要求给A上程序设计一个数据结构，利用该数据结构能高效的接收数据并顺序高效的写入磁盘（也即是不能序号大的记录先写，然后再回写序号小的记录；也不能接收到几十个字节就写一次磁盘）。

答：

进程需要对接受的数据记录建立链表，链表节点结构如下：

enum State{TRANS,OK,ERROR};//数据记录传输状态：正在传输、传输完毕、传输错误

typedef struct node_t{

int id; //block id

int len;//data size

enum State stat;//当前记录传输状态

Buffer_head *bh;

struct node_t *next;//指向下一个数据记录

}Node;

客户端每发送一个数据记录时,先对服务器发送一个数据报报告数据量大小,此时A机器建立一个Node结构变量,分配好id,同时设置好当前记录数据的长度;后续接收到的数据存放在bh域指向的缓冲区，因为数据记录可能很大（1-16M）而且写入时需要原子写入，所以我们首先将收到记录的数据，存放在缓冲区中,这里定义缓冲区最大是4096B，方便最后的写入操作，缓冲区头节点如下：

typedef struct buffer_head_t {

char * b_data; /* pointer to data block (4096 bytes) */

struct buffer_head * b_next;

struct buffer_head * b_prev_free;

struct buffer_head * b_next_free;

}Buffer_head;

b_next指向属于一个数据记录的下一个缓冲区块链；b_next_free和b_prev_free指向空闲缓冲区节点；

因为内存1G，A机器上程序启动时，就分配256M【可调整】物理内存作缓冲区，此时对256M内存缓冲区进行初始化，当接收客户端数据时，就直接从初始化好的缓冲区空闲链表中取出即可，当将缓冲区数据写入完成后，再将缓冲区归还到缓冲区的空闲队列中，不需要每次接收数据时申请内存，也不需要写入完毕时释放缓冲区，缓冲区的管理由程序控制，类似于Linux操作系统内核维护的缓冲区，这样提高效率；

机器A的进程数据记录链表中，节点是以记录的序号id排列的，所以写入时，从链表头开始取节点，节点指向的数据记录写入磁盘，这里我们可以创建多个线程，其中一个线程负责写入操作，如果数据没有准备好，则写线程睡眠，当有数据准备好，且数据量不小于1024B(根据实际调整)时就唤醒写线程，执行写入操作，进城间的通信用信号量来实现；针对不同的客户端创建不同的线程完成数据接收工作。

对链表的操作设置读写锁，这样在将数据写入磁盘的同时，还可以接收客户端发来的数据，提高效率;

(三) 在分布式计算系统中，数据的完整性是最重要的。通常数据被存放在集群系统上，但是集群系统中可能同时会有大量的数据读写，并且每时每刻都可能出现机器宕机或者故障，请设计一种存储方案，满足如下要求：

1、保证在一台或两台机器宕机的情况下不丢失数据，并且对应用是透明的。

2、尽可能将数据的读写负载均衡到整个集群机器上。

答：

1、(1) 设置一个主服务器，保存所有文件的元数据，文件元数据中存放数据块（包括复制的块）存放的位置（哪个机器）以及文件的一些控制信息；其他机器存放数据块，每个文件数据由多个备份，每个数据块被复制到不同机器上，用户可以自定义复制的份数（至少保证三份），副本的存放策略可以是：一个放在本地机架的节点，一个放在同一机架的另一节点，另一个放在其他机架上。块机器周期性的向主服务器发送信息，对数据进行校验，服务器也周期性的接收这样的信息，如果存放数据的机器宕机，服务器会检测到这种情况，对相关的数据进行增加备份；同时主服务器会将此消息告诉管理员，由管理员增添新的节点；这使得机器的崩溃对应用程序是透明的，底层始终维护多个数据备份，维护的过程用户不可见；

(2) 当应用程序请求某个文件的操作时，请求发送到主服务器，由主服务器，决定向哪个机器节点读取数据，因为整个集群存放多个文件的备份，请求哪个备份由主服务器决定，一般请求本地或最近的机器以保证最小的传输负载；几台机子的崩溃对应用程序没有影响；

2、负载均衡

(1) 在写文件时将数据均衡到各个磁盘，可以对各个机器节点的磁盘空间作记录，每次选择磁盘剩余空间大的节点来保存文件或其备份数据；

(2)对于每个机器节点记录对应于机器节点的读写进程的数目，在执行读写操作时，主服务器首先确定文件的备份数据存储在哪些节点上，然后查看这些节点的读写进程数目，选择进程数目最少的节点执行读写操作，这样将操作均衡到了集群的各个节点上；这里的思想是从存储空间和进程操作两方面实现负载均衡，显然如果将数据存储均衡了，读写自然就均衡了，但是这不太现实，所以还要考虑实际系统中读写进程的数目，选择读写操作少(进程)的节点进行读写操作；

(3)对于负载均衡也可以动态来做，由于节点的失效或者增加，可能导致数据分布的不均匀，当某个节点的空闲空间大于一个临界值的时候，主服务器负责(或分配其他机器节点)自动将其他节点数据迁移到空闲空间大的节点上。

1介绍项目

2 vim命令：

3 让我介绍一下如果实现一个文件系统如何做，接着问了比较深入的文件系统知识

4 智力题：小熊搬桃子。

5 解析一个文件的全过程，/root/foo.c，很详细，问到内核的每个细节：如何打开文件、目录项的作用、I-node节点的结构、数据存放的位置、进程描述符结构、打开文件列表等等

6 Ping命令用到什么协议？属于哪一层？ICMP，网络层，问得比较浅。

7 网络上传输一个文件，用数据包包探测工具会发现速度呈波浪线趋势，为什么？我说是慢启动、拥塞避免算法的效果，然后他让我解释慢启动和拥塞避免的原理或算法.

主要考察Linux内核的理解

1 操作系统讨论

l 操作系统有那些主要的模块？进程管理、内存管理、文件系统、设备管理