Spring '25 - F16 - CSC 345 - Midterm

I. General Concepts

(I-1) [30 points; 5 points each]

How are iOS and Android similar? How are they different?

Similarities

• Both are based on existing kernels (Linux and Mac OS X).

• Both have architecture that uses software stacks.

• Both provide frameworks for developers.

Differences

• iOS is closed-source, and Android is open-source.

• iOS applications are developed in Objective-C, Android in Java.

• Android uses a virtual machine, and iOS executes code natively.

(I-2) [25 points; 5 points each]

What are the five major activities of an operating system in regard to file management?

• The creation and deletion of files

• The creation and deletion of directories

• The support of primitives for manipulating files and directories

• The mapping of files onto secondary storage

• The backup of files on stable (nonvolatile) storage media

(I-3) [10 points] Why is the separation of mechanism and policy desirable?

Mechanism and policy must be separate to ensure that systems are easy to modify. No two system installations are the same, so each installation may want to tune the operating system to suit its needs. With mechanism and policy separate, the policy may be changed at will while the mechanism stays unchanged. This arrangement provides a more flexible system.

(I-4) [5 points] What are the advantages of using loadable kernel modules?

It is difficult to predict what features an operating system will need when it is being designed. The advantage of using loadable kernel modules is that functionality can be added to and removed from the kernel while it is running. There is no need to either recompile or reboot the kernel.

II. Process / Threads (II-1) [30 points; 10 points each] Describe the differences among short-term, medium-term, and longterm scheduling.

a. Short-term (CPU scheduler)—selects from jobs in memory those jobs that are ready to execute and allocates the CPU to them.

b. Medium-term—used especially with time-sharing systems as an intermediate scheduling level. A swapping scheme is implemented to remove partially run programs from memory and reinstate them later to continue where they left off.

c. Long-term (job scheduler)—determines which jobs are brought into memory for processing.

The primary difference is in the frequency of their execution. The short term must select a new process quite often. Long-term is used much less often since it handles placing jobs in the system and may wait a while for a job to finish before it admits another one.

(II-2) [20 points; 5 points each]

Using the following program, identify the values of pid at lines A, B, C, and D.

(Assume that the actual pids of the parent and child are 2600 and 2603, respectively.)

A = 0, B = 2603, C = 2603, D = 2600

fork(): On success, the PID of the child process is returned in the parent, and 0 is returned in the child.

On failure, -1 is returned in the parent, no child process is created, and errno is set appropriately.

(II-3) [20 points; 10 points each]

A system with two dual-core processors has four processors available for scheduling. A CPU-intensive application is running on this system. All input is performed at program start-up, when a single file must be opened. Similarly, all output is performed just before the program terminates, when the program results must be written to a single file. Between startup and termination, the program is entirely CPU bound. Your task is to improve the performance of this application by multithreading it. The application runs on a system that uses the one-to-one threading model (each user thread maps to a kernel thread).

• How many threads will you create to perform the input and output? Explain.

• How many threads will you create for the CPU-intensive portion of the application? Explain.

• How many threads will you create to perform the input and output? Explain.

ANS: It only makes sense to create as many threads as there are blocking system calls, as the threads will be spent blocking. Creating additional threads provides no benefit. Thus, it makes sense to create a single thread for input and a single thread for output.

• How many threads will you create for the CPU-intensive portion of the application? Explain.

Ans: Four. There should be as many threads as there are processing cores. Fewer would be a waste of processing resources, and any number > 4 would be unable to run.

III. Concurrency / Synchronization [70 points]

The first known correct software solution to the critical-section problem for two processes was developed by Dekker. The two processes, P0 and P1, share the following variables:

boolean flag[2]; /* initially false */

int turn;

The structure of process Pi (i 0 or 1) is shown in code below; the other process is Pj (j == 1 or 0). Prove that the algorithm satisfies all three requirements for the critical-section problem.

This algorithm satisfies the three conditions of mutual exclusion. (1) Mutual exclusion is ensured through the use of the flag and turn variables. If both processes set their flag to true, only one will succeed, namely, the process whose turn it is. The waiting process can only enter its critical section when the other process updates the value of turn. (2) Progress is provided, again through the flag and turn variables. This algorithm does not provide strict alternation. Rather, if a process wishes to access their critical section, it can set their flag variable to true and enter their critical section. It sets turn to the value of the other process only upon exiting its critical section. If this process wishes to enter its critical section again— before the other process—it repeats the process of entering its critical section and setting turn to the other process upon exiting. (3) Bounded waiting is preserved through the use of the turn variable. Assume two processes wish to enter their respective critical sections. They both set their value of flag to true; however, only the thread whose turn it is can proceed; the other thread waits. If bounded waiting were not preserved, it would therefore be possible that the waiting process would have to wait indefinitely while the first process repeatedly entered—and exited—its critical section. However, Dekker’s algorithm has a process set the value of turn to the other process, thereby ensuring that the other process will enter its critical section next.

IV. Scheduling

Consider the following set of processes, with the length of the CPU burst time given in milliseconds:

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

(IV-1) [20 points; 5 points each] Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, non-preemptive priority (a larger priority number implies a higher priority), and RR (quantum = 2)

(IV-2) [20 points; 5 points for each scheduler] What is the turnaround time of each process for each of the scheduling algorithms in part a?

NOTE: For the question (IV-2) and (IV-3), you need to answer correctly for all process’ time per column, to get partial credit (column-wise). This is because it doesn’t make sense that you get some processes perfectly right (thus, row-wise) while others incorrect if you understand the scheduler algorithm correctly

(IV-3) [20 points; 5 points for each scheduler]

What is the waiting time of each process for each of these scheduling algorithms?

(IV-4) [10 points] Which of the algorithms results in the minimum average waiting time (over all processes)?

Shortest Job First

V. Deadlocks [70 points] In class, we describe a situation in which we prevent deadlock by ensuring that all locks are acquired in a certain order. However, we also point out that deadlock is possible in this situation if two threads simultaneously invoke the transaction() function. Fix the transaction() function to prevent deadlocks.

file:///Users/afshansultana/Desktop/PracticeMidtermExams/MidtermPracticeExamF16-CSC345.pdf