2019-05-09 14:47:51 weixin_41521186 阅读数 168

Pintos操作系统 Project1_Thread

参考声明:Pintos-斯坦福大学操作系统Project详解-Project1

Misson 1 ALARM CLOCK

实验说明

重新实现timer_sleep()。此代码已经提供了一个实现,采用的是忙等待策略,即即它在循环中检查当前时间是否已经过去ticks个时钟,并循环调用thread_yield()直到循环结束。我们要重新实现来避免它的忙等待。

实现思路

调用timer_sleep的时候直接把线程阻塞掉,然后给线程结构体加一个成员ticks_blocked来记录这个线程被sleep了多少时间, 然后利用操作系统自身的时钟中断(每个tick会执行一次)加入对线程状态的检测, 每次检测将ticks_blocked减1, 如果减到0就唤醒这个线程。

实验过程

给线程的结构体加上我们的ticks_blocked成员:

/* Record the time the thread has been blocked. */
int64_t ticks_blocked;

然后在线程被创建的时候初始化ticks_blocked为0, 加在thread_create函数内:

1   t->ticks_blocked = 0;

然后修改时钟中断处理函数, 加入线程sleep时间的检测, 加在timer_interrupt内:

1   thread_foreach (blocked_thread_check, NULL);

这里的thread_foreach就是对每个线程都执行blocked_thread_check这个函数:

 1 /* Invoke function 'func' on all threads, passing along 'aux'.
 2    This function must be called with interrupts off. */
 3 void
 4 thread_foreach (thread_action_func *func, void *aux)
 5 {
 6   struct list_elem *e;
 7 
 8   ASSERT (intr_get_level () == INTR_OFF);
 9 
10   for (e = list_begin (&all_list); e != list_end (&all_list);
11        e = list_next (e))
12     {
13       struct thread *t = list_entry (e, struct thread, allelem);
14       func (t, aux);
15     }
16 }

aux就是传给这个函数的参数。

然后, 给thread添加一个方法blocked_thread_check即可:

thread.h中声明:

1 void blocked_thread_check (struct thread *t, void *aux UNUSED);

thread.c:

 1 /* Check the blocked thread */
 2 void
 3 blocked_thread_check (struct thread *t, void *aux UNUSED)
 4 {
 5   if (t->status == THREAD_BLOCKED && t->ticks_blocked > 0)
 6   {
 7       t->ticks_blocked--;
 8       if (t->ticks_blocked == 0)
 9       {
10           thread_unblock(t);
11       }
12   }
13 }

这样timer_sleep函数唤醒机制实现完成

在这里插入图片描述

  • 可以看到MISSION1中还有一个priority没有完成,这个我们在后面的test中会解决

优先级调度

实现思路

我们之前分析timer_sleep的时候其实已经对线程的调度有了非常深刻的剖析了,这里实现优先级调度的核心思想就是: 维持就绪队列为一个优先级队列。

换一种说法: 我们在插入线程到就绪队列的时候保证这个队列是一个优先级队列即可。

那么我们在什么时候会把一个线程丢到就绪队列中呢?

  1. thread_unblock
  2. init_thread
  3. thread_yield

那么我们只要在扔的时候维持这个就绪队列是优先级队列即可。

实现过程

直接修改thread_unblock函数把list_push_back改成:

1   list_insert_ordered (&ready_list, &t->elem, (list_less_func *) &thread_cmp_priority, NULL);

然后实现一下比较函数thread_cmp_priority:

1 /* priority compare function. */
2 bool
3 thread_cmp_priority (const struct list_elem *a, const struct list_elem *b, void *aux UNUSED)
4 {
5   return list_entry(a, struct thread, elem)->priority > list_entry(b, struct thread, elem)->priority;
6 }

然后对thread_yield和thread_init里的list_push_back作同样的修改:

init_thread:

1   list_insert_ordered (&all_list, &t->allelem, (list_less_func *) &thread_cmp_priority, NULL);

thread_yield:

1     list_insert_ordered (&ready_list, &cur->elem, (list_less_func *) &thread_cmp_priority, NULL);

做完这些工作之后, 就可以发现alarm_priority这个测试pass了。

在这里插入图片描述
好的, 我们实现了一个优先级队列, 但是因为这个优先级机制还会引出一系列的问题, 就是我们接下来要解决的问题。

下面让我们来pass这两个test:

  • priority-change

  • priority-preempt

先分析一下抢占式调度的测试, 其实就是在创建一个线程的时候, 如果线程高于当前线程就先执行创建的线程。

所以我们得出一个结论就是: 测试线程(我们称为thread1)创建了一个PRI_DEFAULT+1优先级的内核线程thread2,然后由于thread2优先级高,

所以线程执行直接切换到thread2, thread1阻塞, 然后thread2执行的时候调用的是changing_thread, 又把自身优先级调为PRI_DEFAULT-1,

这个时候thread1的优先级就大于thread2了, 此时thread2阻塞于最后一个msg输出, 线程切换到thread1, 然后thread1又把自己优先级改成PRI_DEFAULT-2,

这个时候thread2又高于thread1了, 所以执行thread2, 然后在输出thread1的msg, 于是整个过程就有了图中的测试输出结果。

分析这个测试行为我们得出的结论就是: 在设置一个线程优先级要立即重新考虑所有线程执行顺序, 重新安排执行顺序。

好, 弄清楚思路实现其实就非常简单了, 直接在线程设置优先级的时候调用thread_yield即可, 这样就把当前线程重新丢到就绪队列中继续执行, 保证了执行顺序。

此外, 还有在创建线程的时候, 如果新创建的线程比主线程优先级高的话也要调用thread_yield。

2019-03-16 16:03:19 yyy_xiaoxiao 阅读数 104
实验一 操作系统基础

计科1601 16281052 杨涵晨

一.系统调用实验

  1. 参考下列网址中的程序。阅读分别运行用API接口函数getpid()直接调用和汇编中断调用两种方式调用Linux操作系统的同一个系统调用getpid的程序(请问getpid的系统调用号是多少?linux系统调用的中断向量号是多少?)。
  2. 上机完成习题1.13。
  3. 阅读pintos操作系统源代码,画出系统调用实现的流程图。
1.1题解答:

​ API 接口函数的直接调用代码如下:可以看到直接利用getpid()函数进行,然后返回到预先定义好的变量pid中。然后将pid打印出来。

#include <stdio.h>
#include <unistd.h>

int main()
{
    pid_t pid;

    pid = getpid();
    printf("%d\n",pid);

    return 0;
}

​ 利用gcc进行编译,生成可执行文件然后运行得到:3064

​ 通过查看文档发现,getpid()函数功能为进行进程的查看,返回值为进程识别码。

​ 通过进行linux系统调用号查询,查看vim 中的文件,可以看到这我的系统中getpid为172.但是上网查询(64位linux的编号为39,32位20)

​ 在汇编代码中调用中,利用汇编的软中断进行调用,int 0x80;将汇编代码嵌套在c中。代码如下:

#include <stdio.h>  
#include <unistd.h>  
int main()  
{  
        pid_t tt;  
        asm volatile (  
             "movl $0x14,%%eax\n\t"  
             "int $0x80\n\t"  
             "movl %%eax,%0\n\t"  
             :"=m"(tt)  
        );  
        printf(" current PID is : %u\n",tt); 
        return 0; 
}

1.2题解答:

​ C语言的程序代码如下进行gcc编译与执行,直接调用printf()函数,进行实现

#include <stdio.h>

int main()
{
    printf("hello world!!!");
    return 0;
}

​ 执行结果如下:

​ 汇编的代码如下,通过nasm进行编译和实现。

section .data                          
msg     db      "Hello, world!",0xA  
len     equ     $ - msg              
section .text                          
   global _start       
_start:
       mov     eax,4   
       mov     ebx,1   
       mov     ecx,msg 
       mov     edx,len 
       int     0x80    
       mov     eax,1   
       xor     ebx,ebx 
       int     0x80 

​ 执行结果如下:

1.3题解答:

​ pintos中关于系统调用的主要源码:

  1. /src/lib/user/syscall.c

宏定义了四种系统调用的方式,分别是不传递参数、传递一个参数、传递两个参数、传递三个参数,如下所示:

define syscall0(NUMBER) ...
define syscall1(NUMBER, ARG0) ...
define syscall2(NUMBER, ARG0, ARG1) ...
define syscall3(NUMBER, ARG0, ARG1, ARG2) ...

定义了20种系统调用函数

void halt (void);
void exit (int status)
pid_t exec (const char *file);
int wait (pid_t pid);
bool create (const char *file, unsigned initial_size);
bool remove (const char *file);
int open (const char *file);
int filesize (int fd) ;
int read (int fd, void *buffer, unsigned size);
int write (int fd, const void *buffer, unsigned size);
void seek (int fd, unsigned position) ;
unsigned tell (int fd) ;
void close (int fd);
mapid_t mmap (int fd, void *addr);
void munmap (mapid_t mapid);
bool chdir (const char *dir);
bool mkdir (const char *dir);
bool readdir (int fd, char name[READDIR_MAX_LEN + 1]) ;
bool isdir (int fd);
int inumber (int fd);
  1. src/userprog/syscall.c

    这个文件中只有两个函数syscall_init 和syscall_handler,其中syscall_init是负责系统调用初始化工作的,syscall_handler是负责处理系统调用的。syscall_init函数这个函数内部调用了intr_register_int函数,用于注册软中断从而调用系统调用处理函数

    流程图如下:区分用户态和内核态。

二. 并发实验

  1. 编译运行该程序(cpu.c),观察输出结果,说明程序功能。(编译命令: gcc -o cpu cpu.c –Wall)(执行命令:./cpu)
  2. 再次按下面的运行并观察结果:执行命令:./cpu A & ; ./cpu B & ; ./cpu C & ; ./cpu D & 程序cpu运行了几次?他们运行的顺序有何特点和规律?请结合操作系统的特征进行解释。
2.1题解答:

主要功能为:

  • 当输入两个参数时,进行stderr标准错误,打印“usage:cpu”

  • 但是当只有一个参数时进行打印,通过循环语句进行限制,循环10次后停止。中间通过sleep(2)让程序执行过程中阻塞两秒。

​ 四个程序同步进行时我们可以看见。执行时好像没有规律可循。

​ 主要原因如下:现代操作系统中进程的运行都是并发实现的,并不是像以前的单道批处理的操作系统那样,总是按照进程进入内存的先后顺序来执行,因此进程的运行的顺序并没有规律。现代CPU一般都是多核CUP,因此实验中的四个进程可能也不是简单的在一个CPU中并发,而有可能是在多个CPU核心中并行运行,也有可能某两个进程在一个CPU核心中并发运行,和其他的进程在不同的CPU核心中并行运行。所以进程的运行顺序并没有特别的规律。

​ 代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <assert.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
    if (argc != 2) {
    fprintf(stderr, "usage: cpu <string>\n");
    exit(1);
    }
    char *str = argv[1]; 
    int i = 10;
    while (i-- >= 0) {
    sleep(2);
    printf("%s\n", str);
    }
    return 0;
}

三.内存分配实验

  1. 阅读并编译运行该程序(mem.c),观察输出结果,说明程序功能。(命令: gcc -o mem mem.c –Wall)
  2. 再次按下面的命令运行并观察结果。两个分别运行的程序分配的内存地址是否相同?是否共享同一块物理内存区域?为什么?命令./mem &; ./mem &
3.1题解答

主要功能为:通过一个while循环对分配好的内存地址进行累加。每累加一次进行一次sleep。

运行程序如下:我们可以看到开辟的两个进程用了两个不同的物理地址,分别为0x7f9010,0x20c7010.所以物理地址并不相同

操作系统在进行对每个进程分配空间时不会直接在memory上直接对应存储,而是通过‘虚拟内存技术’,为每个进程分配4G内存空间,0-3G 属于用户空间,3G-4G 属于内核空间。每个进程的用户空间不同,但内核空间相同。

所以从进程的不同性上面来说,有可能对应相同的虚拟地址。但是真实物理地址不会相同,这种虚拟内存也保证不同进程相互隔离,错误的程序不会干扰别的正确的进程。

通过命令进行,尝试关闭ALSR 地址空间随机化

sysctl -w kernel.randomize_va_space=0

实验结果中,分配的地址进行了变化,都指向0x602010,当我们取消随机分配的时候,操作系统应该会进行连续分配。直接从用户块的首地址往下进行分配,所以两个不同进程对应的地址相同,但是其实都是不同物理地址。

实验代码如下:

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

int main(int argc, char *argv[])
{
    int *p = malloc(sizeof(int)); // a1
    assert(p != NULL);
    printf("(%d) address pointed to by p: %p\n",getpid(), p); 
    *p = 0; // a3
    int i=10;
    while (i-->=0) {
    sleep(1);
    *p = *p + 1;
    printf("(%d) p: %d\n", getpid(), *p); // a4
    }
    return 0;
}

四、共享的问题

  1. 阅读并编译运行该程序,观察输出结果,说明程序功能。(编译命令:gcc -o thread thread.c -Wall –pthread)(执行命令1:./thread 1000)
  2. 尝试其他输入参数并执行,并总结执行结果的有何规律?你能尝试解释它吗?(例如执行命令2:./thread 100000)(或者其他参数。)
  3. 提示:哪些变量是各个线程共享的,线程并发执行时访问共享变量会不会导致意想不到的问题。
4.1题解答

主要功能:通过命令行输入参数到loop,然后利用pthread_create()进行线程开辟,其中第三个参数是线程运行函数的地址。

利用worker函数进行累加counter,因为counter是一个全局变量,利用两个pthread_create()进行两个累计,然后利用pthread_join()函数进行进程回收。最后利用printf()打印全局变量counter的值。

实验代码如下:

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <errno.h>
#include <ctype.h>

volatile int counter = 0;
int loops;

void *worker(void *arg) {
    int i;
    for (i = 0; i < loops; i++) {
        counter++;
    }
    return NULL;
}

int main(int argc, char *argv[])
{
    if (argc != 2) {
    fprintf(stderr, "usage: threads <value>\n");
    exit(1);
    }
    loops = atoi(argv[1]);
    pthread_t p1, p2;
    printf("Initial value : %d\n", counter);

    pthread_create(&p1, NULL, worker, NULL);
    pthread_create(&p2, NULL, worker, NULL);
    pthread_join(p1, NULL);
    pthread_join(p2, NULL);
    printf("Final value : %d\n", counter);
    return 0;
}

对代码进行编译运行。我们可以发现,大部分结果都是输入参数的两倍,但是在线程数足够大的时候就会小于两倍,两个线程共享了一个执行函数worker,进行for循环对counter进行累加。

其中counter,loops这两个全局变量,和worker()函数是共享的。

由于两个线程在同一个进程中,并且访问操作的是共享的变量。如果每个线程对内存都是可读可写的话,就会发生读取脏数据的问题。现代CPU一般采用了加锁的解决办法,通过加锁使另一个线程不能读取。但是由于现代计算机都是多核心的,对于每个独立的CPU核心来说,都不会发生问题。线程数过大时,就会用不同的cpu核心进行互相读脏数据,依然存在问题。

当输入的参数比较小的时候,一个CPU的核心足够处理,就是单核CPU运行多线程,由于每个核心都有内存锁机制,所以计算结果没有错误当输入的参数比较大的时候,使用多个CPU核心进行运算,就会发生读取脏数据的问题。

github 地址

https://github.com/jackyanghc/2019_BJTU_OS_16281052

个人博客地址

https://jackyanghc.github.io

2019-03-16 18:47:59 qq_42283139 阅读数 121

实验题目

一、 (系统调用实验)了解系统调用不同的封装形式。
1、参考下列网址中的程序。阅读分别运行用API接口函数getpid()直接调用和汇编中断调用两种方式调用Linux操作系统的同一个系统调用getpid的程序(请问getpid的系统调用号是多少?linux系统调用的中断向量号是多少?)。
2、上机完成习题1.13。
3、阅读pintos操作系统源代码,画出系统调用实现的流程图。

二、 (并发实验)根据以下代码完成下面的实验。
1、编译运行该程序(cpu.c),观察输出结果,说明程序功能。
(编译命令: gcc -o cpu cpu.c –Wall)(执行命令:./cpu)
2、再次按下面的运行并观察结果:执行命令:./cpu A & ; ./cpu B & ; ./cpu C & ; ./cpu D &程序cpu运行了几次?他们运行的顺序有何特点和规律?请结合操作系统的特征进行解释。

三、 (内存分配实验)根据以下代码完成实验。
1、 阅读并编译运行该程序(mem.c),观察输出结果,说明程序功能。(命令: gcc -o mem mem.c –Wall)
2、 再次按下面的命令运行并观察结果。两个分别运行的程序分配的内存地址是否相同?是否共享同一块物理内存区域?为什么?命令:./mem &; ./mem &

四、 (共享的问题)根据以下代码完成实验。
1、 阅读并编译运行该程序,观察输出结果,说明程序功能。(编译命令:gcc -o thread thread.c -Wall)(执行命令1:./thread 1000)
2、 尝试其他输入参数并执行,并总结执行结果的有何规律?你能尝试解释它吗?(例如执行命令2:./thread 100000)(或者其他参数。)
3、 提示:哪些变量是各个线程共享的,线程并发执行时访问共享变量会不会导致意想不到的问题。

实验解答

一、
1、 getpid的系统调用号位14H,Linux系统调用的中断向量号是80H。
所给代码的程序运行结果如下
在这里插入图片描述

2、Linux系统调用实现
(1)使用C语言程序代码如下

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int main(int argc, char *argv[]){
	write(1,"hello world\n",11);
	return 0;
}

程序运行结果如下
在这里插入图片描述

(2)使用汇编语言程序代码如下

#include <stdio.h>
#include <unistd.h>
void main (){
char const *MASSAGE = “hello world\n”;
int len = 11;
int result = 0;
asm volatile(
“mov %2, %%edx:\n\r”
“mov %1, %%ecx;\n\r”
“mov $1, %%ebx;\n\r”
“mov $4, %%eax;\n\r”
“int $0x80”
:”=m”(result)
:”m”(msg),”r”(len)
:”%%eax”
);
}

程序运行结果如下
在这里插入图片描述

3、通过源代码可知,pintos操作系统的系统调用实现流程图如下
在这里插入图片描述

二、
1、使用题中给的编译命令和执行命令,运行结果如下。
在这里插入图片描述

根据运行结果并结合代码可以看出,该程序的功能是输出命令行参数的内容。并且如果没有输入参数,那么会输出提示信息——如上图所示。
对原代码中问题的解决:common.h头文件改为unistd.h。并且吧spin()函数改为speel()函数。
2、使用题中给的执行命令,运行结果如下。
在这里插入图片描述

可以看到有四个程序在同时运行,四个程序的进程号是相邻的。并且输出顺序和参数的输入顺序(ABCD)是不一致的,并且输出顺序是在不断变化的。并且输出是在不断进行的,每次会输出四个字母。
究其原因,四个程序在宏观上是同时运行的,微观上是在CPU中交替运行的。因为四个程序的优先级相同,先进行的程序不一定是先结束,所以这四个程序同时运行时,结束的顺序是不确定的,进而导致输出顺序是不确定的。
三、
1、使用所给的编译命令和执行命令,运行结果如下。
在这里插入图片描述

首先,打印程序进程号并且输出指针p被分配的内存地址。然后给p所指的内存单元赋值为0。然后在一个每次延时一秒的循环中,对p指向的内存单元中的值进行递增1的操作。并且输出进程号和当前p指向的内存单元中的值。
2、使用所给的编译命令和执行命令,运行结果如下。
在这里插入图片描述

从运行结果来看,两个程序中的指针p指向的内存地址不同并且相距较远。进而可知,两个独立运行的程序分配的内存地址不同,并且不共享一块物理地址。
这是因为操作系统虚拟化了内存,每个进程访问自己的私有虚拟地址空间,然后操作系统通过某种方式把虚拟地址空间映射到机器的物理内存。这样一个程序的内存引用不会影响其他进程(包括OS本身)的地址空间。
四、
1、使用所给的编译命令和执行命令,运行结果如下。
在这里插入图片描述

输出的结果中,起始值为0,而最终值2000为输入参数1000的两倍。
程序使用pthread.create()函数创建了两个线程。每个线程中运行一个worker()函数,该函数的作用是循环递增,循环次数上限为输入的参数。这里输入的参数为1000,两个线程中的worker()函数每个把counter的值“加1”1000次,所以counter的最终值为2000。
程序的功能是输入参数为N时,程序最终输出值为2N。
2、不断增大输入的参数的值,会发现得到输出不是2N。
计数器递增,需要三个指令:计数器的值从存储器加载到寄存器中、递增、存储回内存。这三条指令不是同时执行的,所以这些操作之间的执行顺序是不固定的。而counter、 loops这两个全局变量是被这两个线程共享的,当两个的线程一起被调用时,共享全局变量counter。 多线程程序中,同一个变量可能被多个线程修改。所以当参数变得很大时,可能会因为指令调用顺序和参数共享的缘故导致输出结果的错误。

程序代码及可执行程序详见git链接

2017-06-25 21:46:00 weixin_33753003 阅读数 122

pintos是斯坦福大学自己开发的一个教学用操作系统。里面的代码给我们留了很多坑。我们的目标就是解决这些坑!详细的实现大家能够看看这篇blog,尽管我的代码并非所有跟着他写的,可是这确实是一篇非常好地blog,没有这blog根本写不出来。
PS:pintos代码,thread部分能够在这里下载

操作系统实验一

阅读数 39

没有更多推荐了,返回首页