Tag Archives: Operating System
Protected: Theory – Assn 5
Protected: Theory – Assn 4
Theory – Assn 3
1. Define the following terms precisely and briefly:
a. Race Condition
Two or more processes are reading or writing shared data and the final result depends on the sequence of the events.
b. Mutual Exclusion
One way to avoid race condition by making sure if one process is in the critical region, other processes will be blocked from entering the region (i.e. blocked from accessing the shared memory).
c. Critical Region
It is part of the program where the shared memory can be accessed.
d. Semaphore
An integer-valued synchronization primitive with the following atomic actions:
– decrementing (down): If 0, the calling thread goes to sleep.
If >0, decreases the value by one.
– Incrementing (up): If 0, awakens a sleeping thread. If <max, increases the value by one.
2. What is the Priority Inversion Problem? How can we avoid it?
No preemption: Process L with lower priority holds a resource required by process H with higher priority. H arrives after L acquires the resource and acquires CPU (busy waiting). -> None of the processes can finish.
Solution: use sleep and wakeup calls instead
With preemption: Process L with lower priority holds a resource required by process H with higher priority. H arrives after L acquires the resource and cannot proceed. M with medium priority and no dependence to the shared resource arrives after H, acquires CPU because of its higher priority compared to L, and completes its job before H.
Solution: Increase priority of L when it claims the resource.
3. Is there any difference between mutex locks and binary semaphores?
They both guarantee the mutual exclusion. Mutex is a simplified version of semaphores without the ability to count.
Binary semaphores are initialized to 1, down is called when a process is entering the critical region and up when leaving. Binary semaphores also have a corresponding list of waiting processes.
Mutex has the states unlocked (represented by 0, critical region is available) and locked for any other values (critical region denied access).
4. There are several alternatives for ensuring mutual exclusion. List these methods in rows of a table, and compare their properties in a few columns.
|
|
Multi-Core |
Security/Protection |
Hardware Support |
Busy Waiting |
Flexibility |
| Disabling Interrupts |
No |
Low |
Yes |
No |
Low |
| Lock Variables |
Yes |
Medium |
No |
Yes |
High |
| Strict Alternation |
Yes |
High |
No |
Yes |
Low |
| Person’s Solution |
Yes |
High |
No |
Yes |
High |
| The TSL Instruction hardware |
Yes |
High |
Yes |
Yes |
High |
5. Consider the scheduling algorithms First-Come-First-Served, Short Job First, Shortest Remaining Time Next, and Round Robin. Suppose a set of jobs arrive in the system at around the same time. Rank the above scheduling algorithms based on their performance with respect to each of the following criteria (one ranking per criterion):
a. Throughput – as the number of process that complete their execution per time unit;
FCFS = SJF > SRTN > RR
b. Average waiting time – Waiting time: amount of time a process has been waiting in the ready queue;
SRTN < SJF< RR <FCFS
c. Average Response Time – Response Time: amount of time it takes from when a request was submitted until the first response is produced (the process starts running);
RR < SRTN < SJF < FCFS
d. Proportionality – the maximum ratio of the turnaround time to the expected running time;
RR < SRTN < SJF < FCFS (roughly)
e. Average Turnaround Time.
SRTN < SJF < RR < FCFS
Theory – Assn 2
1. What happens to the children, when the parent process is killed? What happens to them when the parent terminates?
In both cases, they continue running.
2. Does the child process see changes in variables made by the parent process before the fork() statement that creates the child? What about the value changes after the fork() statement?
The child process can see changes by the parent before the fork() statement, but cannot see the value change after the fork() statement.
3. Suppose the process P1 is running that it has to block for an I/O operation. A second process P2 in front of the ready queue. List the key context switch steps by referring to P1 and P¬2
a. Save context of P1 to PCB
1. Save registers, address space, I/O Information (e.g. list of opened files), accounting information;
2. Update PCB of P1 to reflect new state (Blocked);
3. Move PCB of P1 to the Blocked queue.
b. Flush data and instruction caches;
c. Decide which process to run -> P2
d. Reload P2 using its PCB
1. Update new PCB state, queues.
2. Reload registers, Update memory management data structures.
4. Why is a threading model useful?
A threading model is useful because they can run in parallel, increased performance and responsiveness, easier coordination and sharing of resources.
5. Which of the following components of program state are shared across threads in a multithreaded process?
a. Register values
b. Heap memory
c. Global variables
d. Stack memory
6. Explain why system calls are needed to set up shared memory between processes. Does sharing memory between multiple threads of the same process also require system calls to be set up?
The system calls are needed because each process has its own address space and kernel has the memory mapping of processes.
Threads do not need system call because they are already sharing the address space in a process.
7. Why a web server usually spawns off a thread per Web client request, but not a process per request?
Threads are light-weight, which means creating threads and switching between threads is faster compared to processes; also they can access shared resources more easily.
8. What are the models of inter-process communication? Compare the models by outlining their requirements, pros, and cons.
Shared Memory: Processes can exchange data in a shared region of the memory. It is efficient concerning the speed, but lack of protection.
Message Passing: Processes exchange data by creating communication links. It is more secure, but slower.
My Little Space 
You must be logged in to post a comment.