Transcript Lecture Notes

Project: Processes and Resource
Management
Textbook: pages 482-491
Lubomir Bic
Assignment
• Design/implement a simplified process and resource
manager
• Required functionalities:
– process: create/destroy
– resource: request/release
– time-out interrupt
– multi-unit resources (5.1. page 490 of textbook)
– extensive error checking
Operating Systems
2
Overall Organization
• Problem: we do not have the actual processes or hardware
• Solution: your terminal (or test files) represent
– currently running process, and
– the hardware causing interrupts
Operating Systems
3
Overall Organization
• Write presentation/test shell
– it reads command from terminal or test file
– it invokes kernel function
– it displays reply (on terminal or to output file)
• which process is running
• any errors
your
terminal/
test files
Operating Systems
repeat
get f, par
invoke f(par)
get reply
display reply
Process and
Resource
Manager
4
Presentation/test shell
Example:
*Process Init is running
. . .
shell> cr A 1
*Process A is running
shell> cr B 2
*Process B is running
shell> cr C 1
*Process B is running
shell> req R1,1
*Process B is blocked; Process A is running
. . .
Operating Systems
5
Process states and operations
• Process states: ready, running, blocked
• Possible Operations:
– Create: (none)  ready
– Destroy: running/ready/blocked  (none)
– Request: running  blocked
– Release: blocked  ready
– Time_out: running  ready
– Scheduler: ready  running/running  ready
Operating Systems
6
Process Control Block (PCB)
•
•
•
•
•
•
•
•
PID
CPU state — not used
Memory — not used
Open_Files — not used
Other_resources
Status: Type & List
Creation_tree: Parent/Children
Priority: 0, 1, 2 (Init, User, System)
Operating Systems
7
The Ready List (RL)
• 3-level priority list
2 = “system”
1 = “user”
0 = “init”
• Priorities don’t change
• Every process (PCB) is either on the RL on a blocked list
Operating Systems
8
Create a process
Create(initialization parameters){
create PCB data structure
initialize PCB using parameters
link PCB to creation tree
insert(RL, PCB)
Scheduler() }
•
•
Init process is created at start-up & can create first system
or user process
Any new or released process is inserted at the end of the
queue (RL)
Operating Systems
9
Destroy a process
Destroy (pid) {
get pointer p to PCB using pid
Kill_Tree(p)
Scheduler() }
Kill_Tree(p) {
for all child processes q Kill_Tree(q)
free resources
delete PCB and update all pointers }
• Process can be destroyed by any of its ancestors or by
itself (exit)
Operating Systems
10
Representation of Resources
• There is a fixed set of resources
• Resource Control Block (RCB)
– RID
– Status: counter for number of free units
– Waiting_List: list of blocked processes
Operating Systems
11
Request resource (1-unit resources)
Request(rid) {
r = Get_RCB(rid);
if (r->Status == 'free') {
r->Status = 'allocated‘;
insert(self->Other_Resources, r);
} else {
self->Status.Type = 'blocked';
self->Status.List = r;
remove(RL, self);
insert(r->Waiting_List, self);
Scheduler(); }
• all requests are satisfied in strict FIFO order
Operating Systems
12
Release resource (1-unit resources)
Release(rid) {
r = Get_RCB(rid);
remove(self->Other_Resources, r);
if (r->Waiting_List == NIL} {
r->Status = 'free';
} else {
remove(r->Waiting_List, q);
q->Status.Type = 'ready';
q->Status.List = RL;
insert(q->Other_Resources, r);
insert(RL, q);
Scheduler(); }}
Operating Systems
13
Scheduling
•
•
•
•
3-level priority scheduler
Use preemptive round-robin scheduling within level
Time sharing is simulated by function call
Init process serves a dual purpose:
– dummy process: lowest priority/never blocked
– root of process creation tree
Operating Systems
14
Scheduler
• Called at the end of every kernel call
(1) Scheduler() {
(2)
find highest priority process p
(3)
if (self->priority < p->priority ||
(4)
self->Status.Type != 'running' ||
(5)
self == NIL)
(5)
preempt(p, self) }
Condition (3): called from create or release
Condition (4): called from request or time-out
Condition (5): called from destroy
Preemption:
• Change status of p to running (status of self already changed
to ready/blocked)
• Context switch—output name of running process
Operating Systems
15
Time-out Interrupts
• Simulate time-sharing
Time_out() {
find running process q;
remove(RL, q);
q->Status.Type = 'ready';
insert(RL, q);
Scheduler();}
Operating Systems
16
Presentation/Test Shell
• Mandatory Commands
–
–
–
–
–
–
init
cr <name> <priority>
de <name>
req <resource name> <# of units>
rel <resource name> <# of units>
to
Operating Systems
17
Presentation/Test Shell
• Optional commands (examples):
– list all processes and their status
– list all resources and their status
– provide information about a given process
– provide information about a given resource
Operating Systems
18
Summary of tasks
• Design/implement the process and resource manager
– data structures and functions
• Design/implement a driver program (shell)
– command language and interpreter
• Instantiate the manager to include at start-up:
– A Ready List with 3 priorities
– A single process, Init
– 4 resources labeled: R1, R2, R3, R4 (each Ri has i units))
• Submit your program for testing, submit documentation for
evaluation
Operating Systems
19
Sample test 1
cr x 2
cr y 1
to
cr z 2
to
req R1 1
to
req R1 1
de z
rel R1 1
de x
init x x x x z z x z x x init
20
cr x 1
cr p 1
cr q 1
cr r 1
to
req R2 1
to
req R3 3
to
req R4 3
to
to
req R3 1
req R4 2
req R2 2
to
de q
to
to
Sample test 2
init x x x x p p q q r r x p q r x x x p x
21