Question

1. Distinguish between PCS and SCS scheduling.

2. A CPU-scheduling algorithm determines an order for the execution of its scheduled processes. Given n processes to be scheduled on one processor, how many different schedules are possible? Give a formula in terms of n.

3. Consider a computer system that runs 5,000 jobs per month with no deadlockprevention or deadlock-avoidance scheme. Deadlocks occur about twice permonth, and the operatormust terminate and rerun about 10 jobs per deadlock. Each job is worth about $2 (in CPU time), and the jobs terminated tend to be about half-done when they are aborted. A systems programmer has estimated that a deadlock-avoidance algorithm (like the banker’s algorithm) could be installed in the system with an increase in the average execution time
per job of about 10 percent. Since the machine currently has 30-percent idle time, all 5,000 jobs per month could still be run, although turnaround time would increase by about 20 percent on average. .
a) What are the arguments for installing the deadlock-avoidance algorithm
b) What are the arguments against installing the deadlock-avoidance algorithm?

4. Consider the following resource-allocation policy. Requests for and releases of resources are allowed at any time. If a request for resources cannot be satisfied because the resources are not available, then we check any processes that are blocked waiting for resources. If a blocked process has the desired resources, then these resources are taken away from it and are given to the requesting process. The vector of resources for which the blocked process is waiting is increased to include the resources that were taken away.
For example, consider a system with three resource types and the vector Available initialized to (4,2,2). If process P0 asks for (2,2,1), it gets them. If P1 asks for (1,0,1), it gets them. Then, if P0 asks for (0,0,1), it is blocked (resource not available). If P2 now asks for (2,0,0), it gets the available one (1,0,0) and one thatwas allocated to P0 (since P0 is blocked). P0’s Allocation vector goes down to (1,2,1), and its Need vector goes up to (1,0,1).
a. Can deadlock occur? If you answer “yes,” give an example. If you answer “no,” specify which necessary condition cannot occur.
b. Can indefinite blocking occur? Explain your answer.

5. Consider the following snapshot of a system:
      Allocation         Max
       ABCD             ABCD
P0   3014                5117
P1    2210                3211
P2    3121                3321
P3    0510               4612
P4    4212               6325

Using the banker’s algorithm, determine whether or not each of the following states is unsafe. If the state is safe, illustrate the order in which the processes may complete. Otherwise, illustrate why the state is unsafe. (10 Marks)
a. Available = (0, 3, 0, 1)
b. Available = (1, 0, 0, 2)

6. Consider a logical address space of 64 pages of 1024 words each, mapped onto a physical memory of 32 frames.
a. How many bits are there in the logical address?
b. How many bits are there in the physical address?

7. What is the effect of allowing two entries in a page table to point to the same page frame in memory? Explain how this effect could be used to decrease the amount of time needed to copy a large amount of memory from one place to another. What effect would updating some byte on the one page have on the other page?

8. Assuming a 1-KB page size, What are the page numbers and offsets for the following address references (provided as decimal numbers):
a. 2375
b. 19366
c. 30000
d. 256
e.1685

9. Consider a logical address space of 32 pages with 1,024 words per page, mapped onto a physical memory of 16 frames.
a. How many bits are required in the logical address?
b. How many bits are required in the physical address?

10. An operating system supports a paged virtual memory, using a central processor with a cycle time of 1 microsecond. It costs an additional 1 microsecond to access a page other than the current one. Pages have 1000 words, and the paging device is a drum that rotates at 3000 revolutions per minute and transfers 1 million words per second. The following statistical measurements were obtained from the system:
- 1 percent of all instructions executed accessed a page other than the current page.
- Of the instructions that accessed another page, 80 percent accessed a page already in memory.
- When a new page was required, the replaced page was modified 50 percent of the time.

Calculate the effective instruction time on this system, assuming that the system is running one process only and that the processor is idle during drum transfers

Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

1.
While PCS relates to scheduling threads locally by the user, SCS relates to scheduling threads by the kernel. The two are complementary task scheduling procedures (rather than competing approaches) that should interleave differently depending on the application model of the OS.

That is; PCS threads are actively programmed using a dedicated library (API), are derived from a process without direct OS involvement. SCS threads on the other hand, do not directly bind to processes, but rather schedule CPU to the user threads.


2.
There are n factorial (n!) different schedules possible for an n size execution list; the number of possible combination.

That is; given a single processor, all the tasks must be arranged in a single ordered list, hence all possible combinations....

This is only a preview of the solution. Please use the purchase button to see the entire solution

Related Homework Solutions

System Calls in Linux
Homework Solution
$25.00
Computer Science
Linux
File Management
Lab Notes
System Calls
Buffer
Reads
Writes
Algorithms
Codes
Scripts
Input
Output
Errors
Arguments
Results
Programming Questions
Homework Solution
$65.00
Programming
Computer Science
Parent Processes
Codes
C++
Linux
Fork
Child Processes
Code Segments
Ordinary Pipes
Strings
Messages
UNIX
Web Servers
Basic Mutex
Bank Accounts
Functions
SJF Algorithm
Linux & C++ Problems
Homework Solution
$30.00
Computer Science
Linux
C++
Functions
Statements
Variables
Loops
Conditions
File Management
Commands
Codes
Child Processes
Command Line
Parent Processes
Executable Program
Buffers
Forks
Operators
Computer Science Problems
Homework Solution
$30.00
Computer Science
Linux
C Programming Language
Kernel Source Tree
Systems
Numbers
Architecture
Integers
Input
Output
Strace Utility
Basic Commands
Algorithms
File Management
Compilers
Three Simple Shell Scripts
Homework Solution
$15.00
Shell
Bash
Script
List
Directory
Lsdirs
Sh
File
See
Wordlen
Type
Long
Word
Test
Read
Wc
Argument
Bourne
Get help from a qualified tutor
Live Chats