OS 实验2 创建共享内存 thread_create()分析

OS

https://www.zybuluo.com/SovietPower/note/1824664

创建共享内存

通过共享内存，完成生产者-消费者模型的创建，并用gdb进行调试。

使用man+函数名即可查看函数帮助文档。

mmap()

#include <sys/mman.h>
void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *start, size_t length);

创建新的虚拟内存区域，并将一个文件或对象映射到该区域。
执行成功时，返回被映射区域的指针；否则返回MAP_FAILED，其值为(void *)-1。

参数：
start：映射区的开始地址，为0时表示由系统决定映射区的起始地址。
length：映射区的长度，以字节为单位（会补齐到整数倍内存页大小）。
prot：期望的内存保护标志（使用该空间的权限），不能与文件的打开模式冲突。

prot可通过or组合以下值作为参数：
PROT_EXEC：页内容可被执行。
PROT_READ：页内容可读。
PROT_WRITE：页内容可写。
PROT_NONE：页不可访问。

flags：指定映射对象的类型，映射选项和映射页是否可以共享。

flags可通过or组合以下值作为参数（仅列举常用值）：
MAP_FIXED：使用指定的映射起始地址，且起始地址必须落在页的边界上。如果由start和len参数指定的内存区与已有的映射空间重叠，重叠部分会被丢弃。如果指定的起始地址不可用，操作失败。
MAP_SHARED：与其它所有映射这个对象的进程共享映射空间。对共享区的写入，相当于输出到文件。但进程在映射空间对共享内容的改变并不会直接写到磁盘文件中，只有调用msync()或munmap()后，共享区才会被更新。与MAP_PRIVATE互斥，只能且必须使用其中一个。
MAP_PRIVATE：建立一个写时拷贝的私有映射。对内存区域的写入不会影响到原文件。与MAP_SHARED互斥，只能且必须使用其中一个。
MAP_ANONYMOUS：匿名映射，映射区不与任何文件关联（无需指定fd）。可避免文件的创建与打开，但只能用于具有父子关系的进程。

fd：文件描述符，一般为open()的返回值。可以为-1，表示不指定文件，此时flags必须包含MAP_ANON。
offset：被映射对象内容的起点。

功能：
1. 允许用户程序直接访问设备内存，相比于在用户空间和内核空间互相拷贝数据，效率更高。
2. 使进程之间可通过映射同一个普通文件实现共享内存。

munmap()

#include <sys/mman.h>
void *mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset);
int munmap(void *start, size_t length);

取消start所指的虚拟映射内存，length表示取消的空间大小。
执行成功时，返回0；否则返回-1。

进程结束，或通过exec执行其他程序时，映射内存会自动被解除。但关闭文件描述符时不会解除映射。

shm_open()

#include <fcntl.h> /* For O-* constants */
#include <sys/stat.h> /* For mode constants */
#include <sys/mman.h>
int shm_open(const char *name, int oflag, mode_t mode);
int shm_unlink(const char *name);

注意编译时要链接库，即在最后加参数-lrt。
shm_open的帮助文档中，语法要求Link with -lrt.。NOTES中：Programs using these functions must specify the -lrt flag to cc in order to link against the required ("realtime") library.

Linux共享内存通过tmpfs文件系统实现。tmpfs文件系统完全驻留在RAM中，其读写速度极快。
tmpfs默认位于/dev/shm目录，因此对该目录下的文件读写即通过tmpfs文件系统进行，其速度与读写内存速度一样。
/dev/shm的默认容量为系统内存的一半。只有在其中含有文件时，才真正占用对应的内存大小，否则不会占用内存。

用于打开或创建文件。
执行成功时，返回对应文件描述符；否则返回-1。返回的文件描述符一定是最小的未被使用的描述符。

shm_open与open基本相同，但其操作的文件一定位于tmpfs文件系统，即位于/dev/shm。

参数：
name：指定要打开或创建的文件名。注意因为shm_open操作的文件位于/dev/shm，所以不需且不能包含路径，不同于open()的pathname（不过也可包含路径，但要保证/dev/shm中包含对应路径。此外tmpfs不是一定在/dev/shm中）。
oflag：指定打开或创建的文件模式。

oflags可通过or组合以下值作为参数（仅列举常用值）：
O_RDONLY：以只读模式打开。
O_WRONLY：以只写模式打开。
O_RDWR：以可读可写模式打开。以上三种模式只可选择一种。
O_APPEND：以追加方式打开。
O_CREAT：如果文件不存在，则创建文件。
O_EXCL：如果使用了O_CREAT且文件已存在，返回-1（并更新错误信息errno）。
O_TRUNC：如果文件已存在（且以可写模式打开），清空该文件。

mode：使用O_CREAT新建文件时，该文件的权限标志。由4位数字组成。

mode的第一位数代表特殊权限（suid:4，sgid:2，sbit:1，即setUid/setGid/粘着位），一般为0即可，可省略。
后三位数分别表示：所有者、群组、其他用户所具有的权限。每位数通过加权表示权限：4:读权限，2:写权限，1:执行权限。

shm_unlink()

#include <fcntl.h> /* For O-* constants */
#include <sys/stat.h> /* For mode constants */
#include <sys/mman.h>
int shm_open(const char *name, int oflag, mode_t mode);
int shm_unlink(const char *name);

删除/dev/shm目录下的指定文件。
执行成功时，返回0；否则返回-1。

用unlink()并指定/dev/shm+name作为目录，可实现同样效果。但tmpfs不是一定在/dev/shm中。
shm_open()创建的文件，如果不使用shm_unlink()删除，会一直位于/dev/shm中，直到操作系统重启或用rm删除。

ftruncate()

#include <unistd.h>
#include <sys/types.h>
int truncate(const char *path, off_t length);
int ftruncate(int fd, off_t length);

truncate和ftruncate均可重置文件大小为length字节。若文件缩小，则部分信息会丢失；若文件扩大，则用空字符\0填充。
执行成功时，返回0；否则返回-1。

任何通过open()或shm_open()打开的文件都可使用。
使用truncate，需保证文件可写；使用ftruncate，需保证文件已打开且可写。

生产者-消费者模型调试

编译文件
文件使用传入的参数决定运行生产者还是消费者。

调试生产者、运行消费者
在输出信息的位置（78行）添加断点。使用producer参数运行生产者。
使用consumer参数运行消费者。

输出/接收信息
调试在输出信息的位置（断点处）暂停，生产者用continue输出一条信息，消费者收到信息。

输出/接收信息（第二条）
调试在输出第二条信息的位置暂停，生产者继续用continue输出第二条信息，消费者收到第二条信息。

输出/接收信息（第三条）
调试在输出第三条信息的位置暂停，生产者继续用continue输出第三条信息，消费者收到第三条信息。

代码：
使用需传入参数：p或producer表示生产者，c或consumer表示消费者。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>
#include <sys/stat.h>
void *Mmap(void *start, size_t length, int prot, int flags, int fd, off_t offset)
{
    void *ptr = mmap(start, length, prot, flags, fd, offset);
    if(ptr==MAP_FAILED)
    {
        puts("mmap failed.");
        exit(-1);
    }
    return ptr;
}
int Munmap(void *start, size_t length)
{
    int res=munmap(start, length);
    if(res==-1)
    {
        puts("munmap failed.");
        exit(-1);
    }
    return res;
}
int Shm_open(const char *name, int oflag, mode_t mode)
{
    int res=shm_open(name, oflag, mode);
    if(res==-1)
    {
        puts("shm_open failed.");
        exit(-1);
    }
    return res;
}
int Shm_unlink(const char *name)
{
    int res=shm_unlink(name);
    if(res==-1)
        puts("shm_unlink failed."), exit(-1);
    return res;
}
int Ftruncate(int fd, off_t length)
{
    int res=ftruncate(fd, length);
    if(res==-1)
        puts("ftruncate failed."), exit(-1);
    return res;
}
const int SIZE = 4096;
const char *NAME = "Messages";
namespace Producer
{
    const int message_size=3;
    const char *messages[message_size]={
        "message 1,",
        "message 2,",
        "message 3!"
    };
    int main()
    {
        puts("Producer begins.");
        //用tmpfs文件系统创建文件，并设置大小
        int shm_fd = Shm_open(NAME, O_RDWR|O_CREAT, 0666);
        Ftruncate(shm_fd, SIZE);
        //将文件映射到ptr所指的虚拟内存区域
        void *ptr = Mmap(0, SIZE, PROT_WRITE, MAP_SHARED, shm_fd, 0);
        for(int i=0; i<message_size; ++i)
        {
            sprintf((char *)ptr, "%s", messages[i]);
            ptr += strlen(messages[i]);
        }
        return 0;
    }
}
namespace Consumer
{
    int main()
    {
        puts("Consumer begins.");
        //打开与生产者相同的文件
        int shm_fd = Shm_open(NAME, O_RDONLY, 0666);
        //将同一文件映射到虚拟内存区域，以共享内存
        void *ptr = Mmap(0, SIZE, PROT_READ, MAP_SHARED, shm_fd, 0);
        for(int i=0; i<3; )
            if(strlen((char *)ptr)>0)
            {
                printf("Consumer: %s\n", (char *)ptr);
                ptr += strlen((char *)ptr);
                ++i; //强制接收3条消息
            }
        //消费者使用完成后删除文件（shm_open()创建的文件不会在结束时自动删除）
        Shm_unlink(NAME);
        return 0;
    }
}
int main(int argc, char **argv)
{
    for(int i=0; i<argc; ++i)
        printf("argv[%d]=%s\n",i,argv[i]);
    if(argc!=2)
        return puts("Argument Error."), 1;
    if(argv[1][0]=='p')
        return Producer::main();
    else if(argv[1][0]=='c')
        return Consumer::main();
    else
        return puts("Argument Error."), 1;
    return 0;
}

thread_create()解析

分析pintos中创建线程的函数thread_create()的源代码。

函数原型：

#include <thread.c>
tid_t thread_create (const char *name, int priority, thread_func *, void *);

函数介绍：

宏定义

tid_t
线程标识符，为int。

typedef int tid_t;

uint8_t
8位无符号整数，即unsigned char。用于表示栈指针。

typedef unsigned char uint8_t;

thread_func
void类型函数的函数指针，参数为void *aux。

typedef void thread_func (void *aux);

PGBITS
页的位数，为$12$。

#define PGBITS  12                         /* Number of offset bits. */

PGSIZE
页的大小，为$2^{12}$。

#define PGSIZE  (1 << PGBITS)              /* Bytes in a page. */

THREAD_MAGIC
堆栈金丝雀的默认值，为一个随机出的值。

#define THREAD_MAGIC 0xcd6abf4b

链表

内核中使用循环链表。

结构list表示循环链表，含有头、尾两个链表元素。
结构list_elem表示链表元素，含有两个双向的链表元素指针。

相关结构体/函数

allocate_tid()

为新线程分配一个可用的tid。
会执行：将tid_lock上锁（阻塞后来需要分配tid的线程）；分配tid，值为next_tid++；将tid_lock解锁（解除后来线程的阻塞）。

tid_lock：进程标识符tid的锁。用于分配tid。

static tid_t allocate_tid (void);

alloc_frame()

为线程t分配size字节的栈帧（将其栈顶指针减少size），并返回当前的栈指针。
size必须为整数倍的字大小（即$4k$字节）。

static void *alloc_frame (struct thread *t, size_t size);

intr_level

用来表示是否接受中断。含两种值。
关闭中断是pintos实现原子操作的方式。

enum intr_level 
{
    INTR_OFF,             /* 关闭中断 */
    INTR_ON               /* 开启中断 */
};

intr_disable()

关闭中断，并返回调用前的中断状态。

enum intr_level intr_disable (void);

通过该函数，可以实现在执行某操作时不被中断，从而实现一个原子操作。

enum intr_level old_level = intr_disable ();
// do something without being interrupted
intr_set_level (old_level);

intr_enable()

开启中断，并返回调用前的中断状态。

enum intr_level intr_enable (void);

init_thread()

初始化一个线程t，并将其加入到all_list（一个包含所有线程的链表）。
初始化包括：将其命名为name，设置其优先级为priority；设置状态status为阻塞THREAD_BLOCKED，调用enum intr_level intr_disable (void);关闭中断，并更新old_level为INTR_OFF(?)；设置栈指针（值为(uint8_t *) t + PGSIZE）；设置金丝雀值magic为THREAD_MAGIC。

static void init_thread (struct thread *t, const char *name, int priority);

kernel_thread()

内核线程的基础函数。
用于：开启中断接收（调度程序在运行时关闭了中断接收），执行线程的函数，结束并杀死线程。

static void
kernel_thread (thread_func *function, void *aux) 
{
    ASSERT (function != NULL);
    intr_enable ();       /* 调度程序在运行时会关闭中断 */
    function (aux);       /* 执行线程函数 */
    thread_exit ();       /* 如果函数成功返回，结束线程 */
}

kernel_thread_frame

内核线程函数kernel_thread()的栈帧。
保存了：线程函数的返回地址、要调用的函数、调用函数的辅助信息。

struct kernel_thread_frame 
{
    void *eip;                  /* 返回地址 */
    thread_func *function;      /* 要调用的函数 */
    void *aux;                  /* 函数的辅助信息 */
};

lock

锁。
包含两个值：拥有该锁的线程（用于调试），控制权限的二进制信号量。

struct lock 
{
    struct thread *holder;      /* Thread holding lock (for debugging). */
    struct semaphore semaphore; /* Binary semaphore controlling access. */
};

lock_acquire()

请求锁。
会将给定锁的信号量减1（如果减1前为0则等待，直至其为正可减），并设置给定锁的所有者为当前线程thread_current()。
该函数可能会等待（sleep），所以不能在中断处理程序中被调用（会导致内核错误）。

void lock_acquire (struct lock *lock);

lock_release()

释放锁。
会将给定锁的信号量加1，并设置给定锁的所有者为NULL。
需保证锁被当前线程拥有。

void lock_release (struct lock *lock);

palloc_flags

表示分配的页的模式。
包含三种：PAL_ASSERT（内核错误），PAL_ZERO（将页用0填充），PAL_USER（用户页，表示从用户池中获取页，否则从内核池中获取页）。

enum palloc_flags
{
    PAL_ASSERT = 001,           /* 内核错误 */
    PAL_ZERO = 002,             /* 页内容用0填充 */
    PAL_USER = 004              /* 用户页 */
};

内核错误（Kernel Panic）指操作系统在监测到内部的致命错误，但无法安全处理此错误时采取的操作。此时内核会尽可能将它此时能获取的全部信息打印出来。
常见原因：
1. 中断处理程序执行时，它不处于任何一个进程上下文，此时使用可能导致睡眠的函数（如信号量），会破坏系统调度，导致内核错误。
2. 栈溢出。
3. 对于除0异常、内存访问越界、缓冲区溢出等错误，若发生在应用程序，则内核的异常处理程序会进行处理，即使终止原程序也不会影响其它程序；若发生在内核，则会引起内核错误。
4. 内核陷入死锁状态，自旋锁有嵌套使用的情况。
5. 内核线程中存在死循环。

palloc_get_page()

创建一个页，返回其虚拟地址（如果无可用页则返回NULL）。
新页的模式与传入的flags有关：PAL_ASSERT（内核错误），PAL_ZERO（将页用0填充），PAL_USER（用户页，表示从用户池中获取页，否则从内核池中获取页）。

void *palloc_get_page (enum palloc_flags flags);

switch_entry()

进程切换入口？switch.c中无该函数的源码，在switch.S中有。

void switch_entry (void);

switch_entry_frame

switch_entry()的栈帧。
保存了一个返回地址，其类型为void类型函数的指针。

struct switch_entry_frame
{
    void (*eip) (void);
};

switch_threads()

进程切换函数。switch.c中无该函数的源码，在switch.S中有。
将当前进程从cur切换到next：保存next的上下文，切换到cur的上下文。
cur必须是当前正在运行的线程，next必须正在运行该函数。

struct thread *switch_threads (struct thread *cur, struct thread *next);

switch_threads_frame

switch_threads()的栈帧。
保存了4个寄存器的值、返回地址（为void类型函数的指针）、switch_threads()的cur参数、switch_threads()的next参数。

struct switch_threads_frame 
{
    uint32_t edi;               /*  0: 保存 %edi */
    uint32_t esi;               /*  4: 保存 %esi */
    uint32_t ebp;               /*  8: 保存 %ebp */
    uint32_t ebx;               /* 12: 保存 %ebx */
    void (*eip) (void);         /* 16: 返回地址 */
    struct thread *cur;         /* 20: switch_threads()的 CUR 参数 */
    struct thread *next;        /* 24: switch_threads()的 NEXT 参数 */
};

thread

一个线程结构表示一个内核线程或用户进程。
一个线程结构存储在一个4KB的页中。页的最下方（偏移量为0的位置）存储页信息，通常为若干字节，不超过1KB；页的剩余部分为内核栈，自顶向下增长（偏移量为4KB的位置）。
页信息的最上方为magic，即栈内金丝雀，用以判断栈使用的空间是否过大。
elem是一个链表元素，既可以表示运行队列里的一个元素（当线程处于就绪状态时，位于thread.c），也可表示信号等待队列里的一个元素（当线程处于阻塞状态时，位于synch.c）。
每个线程只含有4KB的栈大小，所以大数组或大的数据结构应动态分配其内存。

struct thread
{
    /* Owned by thread.c. */
    tid_t tid;                          /* 线程标识符 */
    enum thread_status status;          /* 线程状态 */
    char name[16];                      /* 线程名称（调试用） */
    uint8_t *stack;                     /* 栈指针 */
    int priority;                       /* 优先级 */
    struct list_elem allelem;           /* 链表元素，用于放在一个包含所有线程链表中 */
    /* 该元素在 thread.c 和 synch.c 间共享 */
    struct list_elem elem;              /* 链表元素 */
#ifdef USERPROG
    /* Owned by userprog/process.c. */
    uint32_t *pagedir;                  /* 页路径（当线程为用户进程时） */
#endif
    /* Owned by thread.c. */
    unsigned magic;                     /* 检测栈溢出 */
};

thread_current()

返回正在运行的线程。此外会对要返回的结果进行检查。

struct thread *thread_current (void);

thread_start()

执行需要抢先执行的线程（preemptive thread，由中断安排）。同时创建idle线程。

void thread_start (void);

thread_status

表示进程所处的状态。

enum thread_status
{
    THREAD_RUNNING,     /* Running thread. */
    THREAD_READY,       /* Not running but ready to run. */
    THREAD_BLOCKED,     /* Waiting for an event to trigger. */
    THREAD_DYING        /* About to be destroyed. */
};

thread_block()

将当前进程转为阻塞状态。这样阻塞的进程在调用thread_unblock()之前不会再被调度。
必须在关闭中断时使用。
阻塞当前进程后，会调用schedule()（见实验3）调度其它可用进程。

void thread_block (void);

thread_unblock()

将进程t从阻塞状态转为就绪状态，并将其加入到就绪队列。
需保证t处于阻塞状态。
该函数不会取代正在运行的线程。如果调用者关闭了中断，它可能会自动解除一个线程的阻塞并更新其它信息(?)。

void thread_unblock (struct thread *t);

解析

功能：
创建一个内核线程，其名称为name，优先级为priority，需要执行函数function，需要的参数为aux。
如果创建成功，返回其tid；否则返回TID_ERROR。

整体过程：
1. 为新线程创建一个页、分配tid，并将其设为阻塞状态。
2. 创建三个函数的栈帧，这三个函数用于切换并调用线程。（猜测）当线程被调度执行时，调用线程切换函数switch_threads()，然后进入相应的线程切换入口switch_entry()，最后进入函数kernel_thread()，执行该线程的函数、最终杀死线程。
3. 创建完栈帧后，将进程设为就绪状态。
4. 返回其tid。

注意：
如果thread_start()已经被调用，则在thread_create()返回之前，新线程可能就已被安排调用，甚至已经结束返回。相反地，在新线程被安排调用之前，原线程可能会运行任意长的时间。如果要确保有序，需使用信号量或其他的同步方式。
该函数为新线程分配了优先级priority，但pintos利用优先级影响调度的功能还未实现，这就是问题1-3的目标。

代码：

//所有涉及的类型与函数均在上面介绍过
tid_t
thread_create (const char *name, int priority,
               thread_func *function, void *aux)
{
    // 定义新线程的指针t，为函数 kernel_thread(), switch_entry(), switch_threads() 分配栈帧。
    // 栈帧用于保存函数的信息/数据。
    struct thread *t;
    struct kernel_thread_frame *kf;
    struct switch_entry_frame *ef;
    struct switch_threads_frame *sf;
    tid_t tid;
    ASSERT (function != NULL);
    // 为线程分配1页，令t指向分配的空间。若无可用页则返回TID_ERROR。
    t = palloc_get_page (PAL_ZERO);
    if (t == NULL)
        return TID_ERROR;
    // 初始化线程（具体内容见`init_thread()`），并分配其tid。
    init_thread (t, name, priority);
    tid = t->tid = allocate_tid ();
    // 分配`kernel_thread()`的栈帧，初始化信息为：返回地址NULL；要调用的函数function；参数aux。
    kf = alloc_frame (t, sizeof *kf);
    kf->eip = NULL;
    kf->function = function;
    kf->aux = aux;
    // 分配`switch_entry()`的栈帧，初始化信息为：返回地址，指向`kernel_thread()`。
    ef = alloc_frame (t, sizeof *ef);
    ef->eip = (void (*) (void)) kernel_thread;
    // 分配`switch_threads()`的栈帧，初始化信息为：返回地址，指向`switch_threads()`；保存的%ebp值为0。
    sf = alloc_frame (t, sizeof *sf);
    sf->eip = switch_entry;
    sf->ebp = 0;
    // 解除线程t的阻塞状态，设为就绪状态，并将其加入到就绪队列。
    thread_unblock (t);
    // 创建成功，返回其tid。
    return tid;
}