Qustions
-
How can we summarize a Process?
At any instant in time, we can summarize a process by taking an inventory of the different pieces of the system it accesses or affects during the course of its execution.
-
Tell me about the elements that constitute a Process?
- Memory：Instructions lie in memory and the data that a programme reads or writes sits in memory too.
- Registers：During the execution of a program , instuctions reads or writes some registers.
- PC(Program Counter) tells us which instructions of the program will be execute next.
- Stack Pointer and Frame Pointer are used to manage the stack for function parameters,local variables and return addresses.
- Persistence Storage Device：the I/O imformation might include a list of files the program currently open.
-
Do you know some primary APIs of Process that are available in any operating system?
- Create
- Destory：kill the process forcefully
- Wait: wait to stop the process
- Suspend/Resume
- Status
-
The snippet below shows the data structure of Process and the define of process states , it also shows the register context which is useful for schduling the Process.
// the registers xv6 will save and restore
// to stop and subsequently restart a process
struct context {
int eip;
int esp;
int ebx;
int ecx;
int edx;
int esi;
int edi;
int ebp;
};
// the different states a process can be in
enum proc_state { UNUSED, EMBRYO, SLEEPING,
RUNNABLE, RUNNING, ZOMBIE };
// the information xv6 tracks about each process
// including its register context and state
struct proc {
char *mem; // Start of process memory
uint sz; // Size of process memory
char *kstack; // Bottom of kernel stack
// for this process
enum proc_state state; // Process state
int pid; // Process ID
struct proc *parent; // Parent process
void *chan; // If !zero, sleeping on chan
int killed; // If !zero, has been killed
struct file *ofile[NOFILE]; // Open files
struct inode *cwd; // Current directory
struct context context; // Switch here to run process
struct trapframe *tf; // Trap frame for the
// current interrupt
};
Exercise
Here is the code provided by the course,we can use diffrent options to generate some processes and caculate the cpu and io utilazition,for example,we can use '-l 5:100 5:100' to generate two processes, each of which has 5 instructions use CPU only.
#! /usr/bin/env python
import sys
from optparse import OptionParser
import random
# process switch behavior
SCHED_SWITCH_ON_IO = 'SWITCH_ON_IO'
SCHED_SWITCH_ON_END = 'SWITCH_ON_END'
# io finished behavior
IO_RUN_LATER = 'IO_RUN_LATER'
IO_RUN_IMMEDIATE = 'IO_RUN_IMMEDIATE'
# process states
STATE_RUNNING = 'RUNNING'
STATE_READY = 'READY'
STATE_DONE = 'DONE'
STATE_WAIT = 'WAITING'
# members of process structure
PROC_CODE = 'code_'
PROC_PC = 'pc_'
PROC_ID = 'pid_'
PROC_STATE = 'proc_state_'
# things a process can do
DO_COMPUTE = 'cpu'
DO_IO = 'io'
class scheduler:
def __init__(self, process_switch_behavior, io_done_behavior, io_length):
# keep set of instructions for each of the processes
self.proc_info = {}
self.process_switch_behavior = process_switch_behavior
self.io_done_behavior = io_done_behavior
self.io_length = io_length
return
def new_process(self):
proc_id = len(self.proc_info)
self.proc_info[proc_id] = {}
self.proc_info[proc_id][PROC_PC] = 0
self.proc_info[proc_id][PROC_ID] = proc_id
self.proc_info[proc_id][PROC_CODE] = []
self.proc_info[proc_id][PROC_STATE] = STATE_READY
return proc_id
def load_file(self, progfile):
fd = open(progfile)
proc_id = self.new_process()
for line in fd:
tmp = line.split()
if len(tmp) == 0:
continue
opcode = tmp[0]
if opcode == 'compute':
assert(len(tmp) == 2)
for i in range(int(tmp[1])):
self.proc_info[proc_id][PROC_CODE].append(DO_COMPUTE)
elif opcode == 'io':
assert(len(tmp) == 1)
self.proc_info[proc_id][PROC_CODE].append(DO_IO)
fd.close()
return
def load(self, program_description):
proc_id = self.new_process()
tmp = program_description.split(':')
if len(tmp) != 2:
print 'Bad description (%s): Must be number <x:y>' % program_description
print ' where X is the number of instructions'
print ' and Y is the percent change that an instruction is CPU not IO'
exit(1)
num_instructions, chance_cpu = int(tmp[0]), float(tmp[1])/100.0
for i in range(num_instructions):
if random.random() < chance_cpu:
self.proc_info[proc_id][PROC_CODE].append(DO_COMPUTE)
else:
self.proc_info[proc_id][PROC_CODE].append(DO_IO)
return
def move_to_ready(self, expected, pid=-1):
if pid == -1:
pid = self.curr_proc
assert(self.proc_info[pid][PROC_STATE] == expected)
self.proc_info[pid][PROC_STATE] = STATE_READY
return
def move_to_wait(self, expected):
assert(self.proc_info[self.curr_proc][PROC_STATE] == expected)
self.proc_info[self.curr_proc][PROC_STATE] = STATE_WAIT
return
def move_to_running(self, expected):
assert(self.proc_info[self.curr_proc][PROC_STATE] == expected)
self.proc_info[self.curr_proc][PROC_STATE] = STATE_RUNNING
return
def move_to_done(self, expected):
assert(self.proc_info[self.curr_proc][PROC_STATE] == expected)
self.proc_info[self.curr_proc][PROC_STATE] = STATE_DONE
return
def next_proc(self, pid=-1):
if pid != -1:
self.curr_proc = pid
self.move_to_running(STATE_READY)
return
for pid in range(self.curr_proc + 1, len(self.proc_info)):
if self.proc_info[pid][PROC_STATE] == STATE_READY:
self.curr_proc = pid
self.move_to_running(STATE_READY)
return
for pid in range(0, self.curr_proc + 1):
if self.proc_info[pid][PROC_STATE] == STATE_READY:
self.curr_proc = pid
self.move_to_running(STATE_READY)
return
return
def get_num_processes(self):
return len(self.proc_info)
def get_num_instructions(self, pid):
return len(self.proc_info[pid][PROC_CODE])
def get_instruction(self, pid, index):
return self.proc_info[pid][PROC_CODE][index]
def get_num_active(self):
num_active = 0
for pid in range(len(self.proc_info)):
if self.proc_info[pid][PROC_STATE] != STATE_DONE:
num_active += 1
return num_active
def get_num_runnable(self):
num_active = 0
for pid in range(len(self.proc_info)):
if self.proc_info[pid][PROC_STATE] == STATE_READY or
self.proc_info[pid][PROC_STATE] == STATE_RUNNING:
num_active += 1
return num_active
def get_ios_in_flight(self, current_time):
num_in_flight = 0
for pid in range(len(self.proc_info)):
for t in self.io_finish_times[pid]:
if t > current_time:
num_in_flight += 1
return num_in_flight
def check_for_switch(self):
return
def space(self, num_columns):
for i in range(num_columns):
print '%10s' % ' ',
def check_if_done(self):
if len(self.proc_info[self.curr_proc][PROC_CODE]) == 0:
if self.proc_info[self.curr_proc][PROC_STATE] == STATE_RUNNING:
self.move_to_done(STATE_RUNNING)
self.next_proc()
return
def run(self):
clock_tick = 0
if len(self.proc_info) == 0:
return
# track outstanding IOs, per process
self.io_finish_times = {}
for pid in range(len(self.proc_info)):
self.io_finish_times[pid] = []
# make first one active
self.curr_proc = 0
self.move_to_running(STATE_READY)
# OUTPUT: headers for each column
print '%s' % 'Time',
for pid in range(len(self.proc_info)):
print '%10s' % ('PID:%2d' % (pid)),
print '%10s' % 'CPU',
print '%10s' % 'IOs',
print ''
# init statistics
io_busy = 0
cpu_busy = 0
while self.get_num_active() > 0:
clock_tick += 1
# check for io finish
io_done = False
for pid in range(len(self.proc_info)):
if clock_tick in self.io_finish_times[pid]:
io_done = True
self.move_to_ready(STATE_WAIT, pid)
if self.io_done_behavior == IO_RUN_IMMEDIATE:
# IO_RUN_IMMEDIATE
if self.curr_proc != pid:
if self.proc_info[self.curr_proc][PROC_STATE] == STATE_RUNNING:
self.move_to_ready(STATE_RUNNING)
self.next_proc(pid)
else:
# IO_RUN_LATER
if self.process_switch_behavior == SCHED_SWITCH_ON_END and self.get_num_runnable() > 1:
# this means the process that issued the io should be run
self.next_proc(pid)
if self.get_num_runnable() == 1:
# this is the only thing to run: so run it
self.next_proc(pid)
self.check_if_done()
# if current proc is RUNNING and has an instruction, execute it
instruction_to_execute = ''
if self.proc_info[self.curr_proc][PROC_STATE] == STATE_RUNNING and
len(self.proc_info[self.curr_proc][PROC_CODE]) > 0:
instruction_to_execute = self.proc_info[self.curr_proc][PROC_CODE].pop(0)
cpu_busy += 1
# OUTPUT: print what everyone is up to
if io_done:
print '%3d*' % clock_tick,
else:
print '%3d ' % clock_tick,
for pid in range(len(self.proc_info)):
if pid == self.curr_proc and instruction_to_execute != '':
print '%10s' % ('RUN:'+instruction_to_execute),
else:
print '%10s' % (self.proc_info[pid][PROC_STATE]),
if instruction_to_execute == '':
print '%10s' % ' ',
else:
print '%10s' % 1,
num_outstanding = self.get_ios_in_flight(clock_tick)
if num_outstanding > 0:
print '%10s' % str(num_outstanding),
io_busy += 1
else:
print '%10s' % ' ',
print ''
# if this is an IO instruction, switch to waiting state
# and add an io completion in the future
if instruction_to_execute == DO_IO:
self.move_to_wait(STATE_RUNNING)
self.io_finish_times[self.curr_proc].append(clock_tick + self.io_length)
if self.process_switch_behavior == SCHED_SWITCH_ON_IO:
self.next_proc()
# ENDCASE: check if currently running thing is out of instructions
self.check_if_done()
return (cpu_busy, io_busy, clock_tick)
#
# PARSE ARGUMENTS
#
parser = OptionParser()
parser.add_option('-s', '--seed', default=0, help='the random seed', action='store', type='int', dest='seed')
parser.add_option('-l', '--processlist', default='',
help='a comma-separated list of processes to run, in the form X1:Y1,X2:Y2,... where X is the number of instructions that process should run, and Y the chances (from 0 to 100) that an instruction will use the CPU or issue an IO',
action='store', type='string', dest='process_list')
parser.add_option('-L', '--iolength', default=5, help='how long an IO takes', action='store', type='int', dest='io_length')
parser.add_option('-S', '--switch', default='SWITCH_ON_IO',
help='when to switch between processes: SWITCH_ON_IO, SWITCH_ON_END',
action='store', type='string', dest='process_switch_behavior')
parser.add_option('-I', '--iodone', default='IO_RUN_LATER',
help='type of behavior when IO ends: IO_RUN_LATER, IO_RUN_IMMEDIATE',
action='store', type='string', dest='io_done_behavior')
parser.add_option('-c', help='compute answers for me', action='store_true', default=False, dest='solve')
parser.add_option('-p', '--printstats', help='print statistics at end; only useful with -c flag (otherwise stats are not printed)', action='store_true', default=False, dest='print_stats')
(options, args) = parser.parse_args()
random.seed(options.seed)
assert(options.process_switch_behavior == SCHED_SWITCH_ON_IO or
options.process_switch_behavior == SCHED_SWITCH_ON_END)
assert(options.io_done_behavior == IO_RUN_IMMEDIATE or
options.io_done_behavior == IO_RUN_LATER)
s = scheduler(options.process_switch_behavior, options.io_done_behavior, options.io_length)
# example process description (10:100,10:100)
for p in options.process_list.split(','):
s.load(p)
if options.solve == False:
print 'Produce a trace of what would happen when you run these processes:'
for pid in range(s.get_num_processes()):
print 'Process %d' % pid
for inst in range(s.get_num_instructions(pid)):
print ' %s' % s.get_instruction(pid, inst)
print ''
print 'Important behaviors:'
print ' System will switch when',
if options.process_switch_behavior == SCHED_SWITCH_ON_IO:
print 'the current process is FINISHED or ISSUES AN IO'
else:
print 'the current process is FINISHED'
print ' After IOs, the process issuing the IO will',
if options.io_done_behavior == IO_RUN_IMMEDIATE:
print 'run IMMEDIATELY'
else:
print 'run LATER (when it is its turn)'
print ''
exit(0)
(cpu_busy, io_busy, clock_tick) = s.run()
if options.print_stats:
print ''
print 'Stats: Total Time %d' % clock_tick
print 'Stats: CPU Busy %d (%.2f%%)' % (cpu_busy, 100.0 * float(cpu_busy)/clock_tick)
print 'Stats: IO Busy %d (%.2f%%)' % (io_busy, 100.0 * float(io_busy)/clock_tick)
print ''
The snippet shown below shows some detail of the options：
Options:
-h, --help show this help message and exit
-s SEED, --seed=SEED the random seed
-l PROCESS_LIST, --processlist=PROCESS_LIST
a comma-separated list of processes to run, in the
form X1:Y1,X2:Y2,... where X is the number of
instructions that process should run, and Y the
chances (from 0 to 100) that an instruction will use
the CPU or issue an IO
-L IO_LENGTH, --iolength=IO_LENGTH
how long an IO takes
-S PROCESS_SWITCH_BEHAVIOR, --switch=PROCESS_SWITCH_BEHAVIOR
when to switch between processes: SWITCH_ON_IO,
SWITCH_ON_END
-I IO_DONE_BEHAVIOR, --iodone=IO_DONE_BEHAVIOR
type of behavior when IO ends: IO_RUN_LATER,
IO_RUN_IMMEDIATE
-c compute answers for me
-p, --printstats print statistics at end; only useful with -c flag
(otherwise stats are not printed)
-
Run
process-run.pywith the following flags:-l 5:100,5:100. What should the CPU utilization be (e.g., the percent of time the CPU is in use?)Answer: Simply easy, 100%
-
Now run with these flags:
./process-run.py -l 4:100,1:0. These flags specify one process with 4 instructions (all to use the CPU), and one that simply issues an I/O and waits for it to be done. How long does it take to complete both processes?Answer：10 ticks time
At first,We don't know the IO length of each instruction, after checking the details of options,we find out that the default IO length is 5 ticks . So we can answer this question.
1 Run:process 0 Ready:process 1 2 Run:process 0 Ready:process 1 3 Run:process 0 Ready:process 1 4 Run:process 0 Ready:process 1 5 done Run:process 1 6 done Wait:process 1 7 done Wait:process 1 8 done Wait:process 1 9 done Wait:process 1 10 done done -
Switch the order of the processes:
-l 1:0,4:100. What happens now? Does switching the order matter? Why?Answer: Yes ,it explicitly is different.
Because of losing connection to the terminal,we can't do this exercise right now. But I will still try to make an answer for the question,using my ability of reasoning. The answer will be different to the answer of the question 2.
1 Run:process 0 Ready:process1 2 Wait:process 0 Run: process1 3 Wait:process 0 Run: process1 4 Wait:process 0 Run: process1 5 Wait:process 0 Run: process1 6 done done -
We’ll now explore some of the other flags. One important flag is
-S, which determines how the system reacts when a process issues an I/O. With the flag set toSWITCH_ON_END, the system will NOT switch to another process while one is doing I/O, instead of waiting until the process is completely finished. What happens when you run the following two processes (-l 1:0,4:100 -c -S SWITCH_ON_END), one doing I/O and the other doing CPU work?Answer:
No, the CPU process will not use the cpu when the IO process is in WAIT state, CPU will switch to CPU process when the IO process is done.
1 Run:process 0 Ready:process1 2 Wait:process 0 Ready:process1 3 Wait:process 0 Ready:process1 4 Wait:process 0 Ready:process1 5 Wait:process 0 Ready:process1 6 done Run:process 1 7 done Run:process 1 8 done Run:process 1 9 done Run:process 1 -
Now, run the same processes, but with the switching behavior set to switch to another process whenever one is
WAITINGfor I/O (-l 1:0,4:100 -c -S SWITCH_ON_IO). What happens now?Answer: the answer is same as the answer 3.
-
One other important behavior is what to do when an I/O completes. With
-I IO_RUN_LATER, when an I/O completes, the process that issued it does not necessarily run right away; rather, whatever was running at the time keeps running. What happens when you run this combination of processes? (Run./process-run.py -l 3:0,5:100,5:100,5:100 -S SWITCH_ON_IO -I IO_RUN_LATER -c -p) Are system resources being effectively utilized?Answer: IO_RUN_LATER mains that the IO process has to wait until all the CPU processes have done. During the execution, there are two part which need to promote, one is process 0 is having an Ready State when process 2 and process 3 are Running, the other is the last three of IO waiting when the cpu is idle.
-
Now run the same processes, but with
-I IO_RUN_IMMEDIATEset, which immediately runs the process that issued the I/O. How does this behavior differ? Why might running a process that just completed an I/O again be a good idea?Answer：It will be a good idea when the process have to do other IO tasks.