106 OS homework 2-2 成果報告書

組長：B10415025 洪昱翔
組員：B10415047 陳重佑
組員：B10415049 陳祐丞
github: https://github.com/sam5727/xv6-public-1

🙂 使用情境說明(包含流程圖)

使用者輸入 `date <TimeArea>` 查看日期

流程圖

使用者輸入 `tester <執行個數> <時間參數>` 來創建 tester process

流程圖

使用者輸入 `listpid` 查看所有 process 的狀態

查看項目
- processID
- state – 運行狀態 : RUNNING RUNNABLE SLEEPING
- priority – 優先度
- acess – 存取次數
- 總記憶體用量
流程圖

使用者輸入 `find <processID>`

流程圖

使用者輸入 `cp <processID><priority>`

流程圖

背景使用 `優先度排程`

流程圖

使用情境

先用 tester 創造一些進程
然後用 listpid 觀察這些進程
可以用他們的 pid 去 find 這些進程的細項
最後 change piroity 後再去 listpid 觀察他們
偶爾可以用 date 看看時間，培養時間觀念

😇 成功畫面

date:
listpid:
tester: 創建 process來運行

可以透過access的增長來比照RUNNING運行的正確

多創造2個 tester 來實驗 priority scheduler
cp: 更改 priority

如果將 priority 提高即可看出值在快速地下降
find:

🏃 實作過程(修改哪些檔案[含圖片])

date.c





































































#include "types.h"
#include "user.h"
#include "date.h"

int main(int argc, char *argv[])
{
	struct rtcdate r;
	if(date(&r))
	{
		printf(2, "date failed\n");
		exit();
	}

	if(argc == 2)
	{
		if(atoi(argv[1]) > 12 || atoi(argv[1]) <-12)
		{
			printf(2, "TimeArea Error\n");
			exit();
		}
		
		int newHour = r.hour + atoi(argv[1]);

		if(newHour >= 24)
		{
			r.hour = newHour - 24;
			r.day += 1;
		}
		else if(newHour < 0)
		{	
			r.hour = r.hour + 24 - atoi(argv[1]);
			r.day -= 1;
		}
		else
		{
			r.hour = newHour;
		}
	}
	else
	{
		r.hour += 8;
		if(r.hour >= 24)
		{
			r.hour -= 24;
			r.day += 1;
		}
	}
	printf(1, "The time is: ");
	pulseZero(r.year, "/");
	pulseZero(r.month, "/");
	pulseZero(r.day, " ");
	pulseZero(r.hour, ":");
	pulseZero(r.minute, ":");
	pulseZero(r.second, " ");
	printf(1, "\n");

	exit();
}

void pulseZero(int num, char* c)
{

	if(num < 10)
		printf(1,"0%d", num);
	else
		printf(1,"%d", num);

	printf(1, "%s", c);
}

listpid.c










#include "types.h"
#include "user.h"
#include "stat.h"

int main()
{
	listpid();
	exit();
	return 0;
}

tester.c










































#define PI 3.14159
#define MAXNUM 8888888.0

#include "types.h"
#include "stat.h"
#include "user.h"
#include "fcntl.h"

int main(int argc, char *argv[])
{
	int k, n, id = 0;
	double x = 0, i, d;

	if(argc < 2)
		n = 1;
	else
		n = atoi(argv[1]);

	if(n < 0 || n > 10)
		n = 2;

	if(argc < 3)
		d = 1.0;
	else
		d = atoi(argv[2]);

	for(k = 0; k < n; k++){
		id = fork();
		if(id < 0)
			printf(2, "%d failed in fork!\n", getpid());
		else if(id > 0){
			printf(1, "Parent %d creating child %d\n", getpid(), id);
			wait();
		}else{
			for(i = 0; i < MAXNUM; i += d)
				x = x + PI * 141.4;
			break;
		}
	}

	exit();
}

find.c



















#include "types.h"
#include "user.h"
#include "stat.h"
#include "fcntl.h"

int
main(int argc, char *argv[])
{
	int pid;

	if(argc < 2){
		printf(2, "Usage: find pid");
		exit();
	}
	pid = atoi(argv[1]);

	find(pid);
	exit();
}

shutdown.c










#include "types.h"
#include "user.h"
#include "stat.h"

int main()
{
	printf(1, "Shutting Down:\n");
	shutdown();
	return 0;
}

cp.c






















#include "types.h"
#include "user.h"
#include "stat.h"
#include "fcntl.h"

int
main(int argc, char *argv[])
{
	int priority, pid;

	if(argc < 3){
		printf(2, "Usage: cp pid priority");
		exit();
	}
	pid = atoi(argv[1]);
	priority = atoi(argv[2]);

	printf(1, "pid=%d, priority=%d\n", pid, priority);
	cp(pid, priority);

	exit();
}

types.h



typedef int bool;
#define true (1)
#define false (0)

defs.h




// proc.c
int showPid(void);
int changePriority(int pid, int priority);
int findpid(int pid);

proc.h




















// Per-process state
struct proc {
  uint sz;                     // Size of process memory (bytes)
  pde_t* pgdir;                // Page table
  char *kstack;                // Bottom of kernel stack for this process
  enum procstate state;        // Process state
  int pid;                     // Process ID
  struct proc *parent;         // Parent process
  struct trapframe *tf;        // Trap frame for current syscall
  struct context *context;     // swtch() here to run process
  void *chan;                  // If non-zero, sleeping on chan
  int killed;                  // If non-zero, have been killed
  struct file *ofile[NOFILE];  // Open files
  struct inode *cwd;           // Current directory
  char name[16];               // Process name (debugging)
  int priority;                // Higher value, higher priorty
  int access;                  // Process access times
  int maxp;                    // record highest priority
};

proc.c














































































































































static struct proc*
allocproc(void)
{
  struct proc *p;
  char *sp;
  acquire(&ptable.lock);

  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
    if(p->state == UNUSED)
      goto found;

  release(&ptable.lock);
  return 0;

found:
  p->state = EMBRYO;
  p->pid = nextpid++;
  p->priority = DEFAULTP;
  p->maxp = DEFAULTP;
  //cmostime(p->r);

  release(&ptable.lock);

  // Allocate kernel stack.
  if((p->kstack = kalloc()) == 0){
    p->state = UNUSED;
    return 0;
  }
  sp = p->kstack + KSTACKSIZE;

  // Leave room for trap frame.
  sp -= sizeof *p->tf;
  p->tf = (struct trapframe*)sp;

  // Set up new context to start executing at forkret,
  // which returns to trapret.
  sp -= 4;
  *(uint*)sp = (uint)trapret;

  sp -= sizeof *p->context;
  p->context = (struct context*)sp;
  memset(p->context, 0, sizeof *p->context);
  p->context->eip = (uint)forkret;
  return p;
}

void
scheduler(void)
{
  struct proc *p;
  struct proc *p1;
  struct cpu *c = mycpu();
  c->proc = 0;

  for(;;)
  {
    sti();
    struct proc *highP;
    acquire(&ptable.lock);
    for(p = ptable.proc; p < &ptable.proc[NPROC]; p++)
    {
      if(p->state != RUNNABLE)
        continue;
        
      highP = p;

      for(p1 = ptable.proc; p1 < &ptable.proc[NPROC]; p1++)
      {
        if(p1->state != RUNNABLE)
          continue;
        if(highP->priority < p1->priority)
          highP = p1;
      }

      //p = highP;
      c->proc = highP;
      highP->access += 1; //access times count

      //starvation aviodness
      if(highP->priority > DEFAULTP)
        highP->priority--;
      else
        highP->priority = DEFAULTP;

      switchuvm(highP);
      highP->state = RUNNING;
      swtch(&(c->scheduler), highP->context);
      switchkvm();

      c->proc = 0;
    }

    release(&ptable.lock);
  }
}

int 
changePriority(int pid, int priority)
{
  struct proc *p;
  acquire(&ptable.lock);

  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
    if(p->pid == pid){
      if(priority > p->priority)
        p->maxp = priority;
      p->priority = priority;
      break;
    }
  }
  
  release(&ptable.lock);

  return pid;
}

int
findpid(int pid)
{
  struct proc *p;
  bool isfind = false;
  acquire(&ptable.lock);

  for(p = ptable.proc; p < &ptable.proc[NPROC]; p++){
    if(p->pid == pid){
      isfind = true;
      break;
    }
  }
  if(isfind){
    cprintf("pid: %d\n", p->pid);
    cprintf("name: %s\n", p->name);
    cprintf("size: %d\n", p->sz);
    cprintf("priority: %d\n", p->priority);
    cprintf("highest priority: %d\n", p->maxp);
    cprintf("parent pid: %d\n", p->parent->pid);
  }else
    cprintf("pid not found in ptable\n");
  
  release(&ptable.lock);
  return pid;
}

syscall.h






// System call numbers
#define SYS_shutdown 22
#define SYS_date     23
#define SYS_listpid  24
#define SYS_cp       25
#define SYS_find     26

syscall.c


































extern int sys_shutdown(void);
extern int sys_date(void);
extern int sys_listpid(void);
extern int sys_cp(void);
extern int sys_find(void);

static int (*syscalls[])(void) = {
[SYS_fork]    sys_fork,
[SYS_exit]    sys_exit,
[SYS_wait]    sys_wait,
[SYS_pipe]    sys_pipe,
[SYS_read]    sys_read,
[SYS_kill]    sys_kill,
[SYS_exec]    sys_exec,
[SYS_fstat]   sys_fstat,
[SYS_chdir]   sys_chdir,
[SYS_dup]     sys_dup,
[SYS_getpid]  sys_getpid,
[SYS_sbrk]    sys_sbrk,
[SYS_sleep]   sys_sleep,
[SYS_uptime]  sys_uptime,
[SYS_open]    sys_open,
[SYS_write]   sys_write,
[SYS_mknod]   sys_mknod,
[SYS_unlink]  sys_unlink,
[SYS_link]    sys_link,
[SYS_mkdir]   sys_mkdir,
[SYS_close]   sys_close,
[SYS_shutdown] sys_shutdown,
[SYS_date]    sys_date,
[SYS_listpid] sys_listpid,
[SYS_cp]      sys_cp,
[SYS_find]    sys_find,
};

user.h











// system calls
int shutdown(void);
int date(struct rtcdate*);
int listpid(void);
int cp(int, int);
int find(int);
// date.c
void pulseZero(int, char*);
// ulib.c
void itoa(int, char*);
void reverse(char*);

usys.S





SYSCALL(shutdown)
SYSCALL(date)
SYSCALL(listpid)
SYSCALL(cp)
SYSCALL(find)

sysproc.c


















































// shutdown syscall
int
sys_shutdown(void)
{
  char *p = "Shutdown";
  for(; *p; p++)
    outw(0xB004, 0x2000);
  return 0;
}

// changePriority syscall
int
sys_cp(void)
{
  int pid, priority;
  if(argint(0, &pid) < 0)
    return -1;
  if(argint(1, &priority) < 0)
    return -1;

  return changePriority(pid, priority);
}

// find syscall
int
sys_find(void)
{
  int pid;
  if(argint(0, &pid) < 0)
    return -1;
  return findpid(pid);
}

// listpid syscall
int
sys_listpid(void)
{
  return showPid();
}

// date syscall
int
sys_date(struct rtcdate *r)
{
  if (argptr(0, (void *)&r, sizeof(*r)) < 0)
    return -1;

  cmostime(r);
  return 0;
}

Makefile






















UPROGS=\
	_cat\
	_echo\
	_forktest\
	_grep\
	_init\
	_kill\
	_ln\
	_ls\
	_mkdir\
	_rm\
	_sh\
	_stressfs\
	_usertests\
	_wc\
	_zombie\
	_shutdown\
	_date\
	_listpid\
	_cp\
	_tester\
	_find\

ulib.c




























void
itoa(int n, char s[])
{
  int i, sign;
  if((sign = n) < 0)
    n = -n;
  i = 0;
  do{
    s[i++] = n % 10 + '0';
  }while((n /= 10) > 0);
  if(sign < 0)
    s[i++] = '-';
  s[i] = '\0';

  reverse(s);
}

void
reverse(char s[])
{
  int i,j;
  char c;
  for(i = 0, j = strlen(s)-1; i < j; i++, j--){
    c = s[i];
    s[i] = s[j];
    s[j] = c;
  }
}

😎 結論

原先 xv6 的 Round Robin Scheduler 以公平的狀態循環去執行 process，而我們將其改為 Priority Scheduler，不僅能給 user 自由控制 process 的執行優先度，還透過動態增減優先度來預防 starvation。
在 Makefile 預設 cpu 有兩顆
- listpid 顯示 state 會有兩個在 RUNNING。
- 當有 process 的 priority比其他高時，較低優先度的 process 還是會執行，只是需要跟其他 process 共享資源。
- 當 process 的 priority 一樣時，會依 Round Robin scheduler 執行。
- 當有兩個 process 的 priority 比 sh 還高的話，就不能輸入在 command。
- 所以 scheduler 真的是 OS 中很重要的一環。
透過 access 的增減，能更進一步了解 OS 運作的原理。

📅 組員分工

B10415025 洪昱翔
- Priority Scheduling、Starvation Prevent
B10415047 陳重佑
- cp <pid> <priority>、date <timeArea>
B10415049 陳祐丞
- listpid、find <pid>、boolean type

106 OS homework 2-2 成果報告書

🙂 使用情境說明(包含流程圖)

使用者輸入 date <TimeArea> 查看日期

使用者輸入 tester <執行個數> <時間參數> 來創建 tester process

使用者輸入 listpid 查看所有 process 的狀態

使用者輸入 find <processID>

使用者輸入 cp <processID><priority>

背景使用 優先度排程

使用情境

😇 成功畫面

🏃 實作過程(修改哪些檔案[含圖片])

date.c

listpid.c

tester.c

find.c

shutdown.c

cp.c

types.h

defs.h

proc.h

proc.c

syscall.h

syscall.c

user.h

usys.S

sysproc.c

Makefile

ulib.c

😎 結論

📅 組員分工

使用者輸入 `date <TimeArea>` 查看日期

使用者輸入 `tester <執行個數> <時間參數>` 來創建 tester process

使用者輸入 `listpid` 查看所有 process 的狀態

使用者輸入 `find <processID>`

使用者輸入 `cp <processID><priority>`

背景使用 `優先度排程`