AdarshShankar__HW2

Prévia do material em texto

Adarsh B Shankar		COMPSCI 143A SS2
UCI ID: 11972805		Homework 2
HOMEWORK 2
Exercise 2.1.1: State transitions.
Indicate whether each series of state transitions is valid or invalid.
(a) new ➛ ready ➛ suspended ➛ blocked ➛ suspended. -> VALID
(b) suspended ➛ blocked ➛ suspended ➛ blocked ➛ ready ➛ running. -> VALID
(c) running ➛ blocked ➛ ready ➛ blocked ➛ suspended. -> INVALID
(d) new ➛ ready ➛ running ➛ ready ➛ new. -> INVALID
Exercise 2.3.1: Creation hierarchy without linked lists.
Processes 0-4 are related as follows: 1, 2, 3 are children of 0, and 4 is a child of 2. PCBs are implemented as an array indexed by the process number. Each PCB has the links: parent (p), first child (c), younger sibling (ys), and older sibling (os).
(a) Complete the PCB array to show the values of the 4 links (p, c, ys, os) for all processes, to reflect the parent-child hierarchy.
	 
	0
	1
	2
	3
	4
	p
	-
	0
	0
	0
	2
	c
	1
	-
	4
	-
	-
	ys
	-
	-
	1
	1
	-
	os
	-
	3
	3
	-
	-
(b) Modify the array to reflect the creation of a new child, 5, of process 2.
	 
	0
	1
	2
	3
	4
	5
	p
	-
	0
	0
	0
	2
	2
	c
	1
	-
	4
	-
	-
	-
	ys
	-
	-
	1
	1
	-
	4
	os
	-
	3
	3
	-
	5
	-
Exercise 2.3.2: RL without linked lists.
The RL can be implemented without dynamically managed linked lists by creating a new field, next, in each PCB, which points to the next PCB on the same list. Each entry of the RL then points to the first PCB on the list.
(a) Assume that RL contains 3 processes at level 5 and 1 process at level 0. Draw a diagram showing the RL and the modified PCBs.
Exercise 2.4.1: The suspend and activate functions.
suspend(p) {
 if (p.process_state == blocked)
 p.process_state = suspended_blocked
 else p.process_state = suspended_ready
}
 
activate(p) {
 if (p.process_state == suspended_ready)
 p.process_state = ready
 else p.process_state = blocked
 scheduler()
}
(a) What changes must be made to the scheduler or other functions to make suspend/activate work correctly?
The scheduler must be able to reactivate suspended_blocked to suspended_ready in the cases of when the previous process has finished performing the I/O operation. Here the activate function reverses the suspended_ready state to ready but it should also know when to change the state of a suspended_blocked process to suspended_ready.
(b) Why is the scheduler called only in activate but not in suspend?
The scheduler is called only in activate because after we activate a process the next step is to load the process into the memory to be executed. We do not call the scheduler in suspend because the main purpose of suspend is to change the process state and if we call the scheduler we risk activating another process while one is still running. 
(c) A process must be prevented from calling suspend() or activate() on itself. Why?
If a process is allowed to suspend or activate itself, the process could arbitrarily call these functions when it should not which can cause various errors from activating more than one process on the CPU while another is already running to suspending a process in the middle of the execution state.
(d) A process must be prevented from calling suspend() on an already suspended process, or calling activate() on a currently active (ready) process. Why?
This not only creates a redundancy in the OS but also calling suspend on an already suspended process could unintentionally change a process state from suspended_ready to suspended_blocked or vice-versa and this could cause problems in terms of process scheduling.
Similarly, calling activate on an already active process could cause errors such as unintentionally changing the state from active to blocked thereby stopping execution of the process when it should not or calling the scheduler when there CPU is not ready to execute the next process.
Exercise 2.5.1: Request and release functions in action.
Two processes (7 and 8) are currently on RL. Process 8 is at the head of the list and is running. The next field of process 8 points to process 7, which is ready.
· Process 7 is currently holding two resources (15 and 25). The other_resources field of process 7 points to resource 15, which in turn points to the next resource, 25.
(a) Show all changes to the data structures after process 8 requests resource 15.
(b) Show all changes to the data structures after process 7 releases resource 15.
Assume that processes are entered into RL at the end of the list.
Exercise 2.5.2: Effect of operations on processes and resources.
Consider a system of processes and resources and make the following assumptions:
· The Ready List (RL) has 3 priority levels, 0, 1, and 2 (0 being the lowest).
· The create function is simplified: create(n) creates a new child process with the priority n. The process is placed at the end of the corresponding RL queue.
· Only a single CPU exists. The currently running process continues running until the process:
· blocks by requesting an unavailable resource, or
· is interrupted by a function timeout(), which moves the process from the head of the current RL queue to the end of the same queue; the process currently at the head of the RL queue starts running
· The system has 3 resources, 0, 1, 2.
· At the start, only a single process, described by PCB 0, exists and is running at priority 2.
(a)
Assume the following sequence of functions is issued (each function is executed by the currently running process). The create function always uses the next available PCB 1, 2, 3, ...:
1. create(1) 
2. create(2)
3. timeout()
4. create(0)
5. timeout()
6. create(2)
Determine how many child processes each process has at the end of the above sequence.
Ans: Only process 2 has a child process since it is the only resource called twice.
(b)
Assume that the above sequence continues as follows:
1. timeout()
2. request(1)
3. timeout()
4. request(2)
5. request(1)
6. timeout()
7. request(2)
Determine which processes are blocked at the end of the above sequence.
Ans: Process 5 is blocked at the end of the above sequence because a timeout or interrupt is called (line 6)
(c)
Assume that the currently running process executes destroy(2). Determine:
1. The total number of processes in the system. -> 2 processes in the system
2. Which resources are free. -> Only resource 0 is free.
Exercise 2.6.1: Single-threaded vs multi-threaded computation.
A server accepts and processes requests from clients. The server keeps the results of the most recent requests in memory as a cache.
· The processing of each request takes 15 ms.
· If the requested result is not in the memory cache, additional 75 ms are needed to access the disk.
· On average, 80% of all requests can be serviced without disk access.
· The creation of a new thread takes 10 ms.
(a)
To minimize average response time, should the server be implemented as a single-threaded or a multi-threaded process? Justify your answer.
To minimize response time the server should be implemented as a multi-threader process so that the requests can be processes concurrently and in a timely manner while maximizing the efficiency of the server usage. For example if one server request is taking longer than normal, another request can be processed in the mean time.
(b)
What percentage of requests would have to be satisfied without disk access for the two approaches to break even?
Given the two approaches, 80% of requests can be serviced without disks i.e given a 100 requests on average the time taken would be 1200 ms for 80 of those requests. The remaining 20 will take 75 ms each totaling at 1500 ms. So for the two approaches to break even at least 85% of requests should be able to be serviced without disk access.