Introduction to Operating Systems

Tutorial 5

Note: Task refers to process or thread, i.e. do not distinguish between process and thread.

Q1

[Race Conditions] Consider the following two tasks, A and B, to be run concurrently and use a shared variable x. Assume that:

• load and store of x is atomic
• x is initialized to 0
• x must be loaded into a register before further computations can take place.

Task A	Task B
x++; x++;	x = 2*x;

How many relevant interleaving scenarios are possible when the two threads are executed? What are all possible values of x after both tasks have terminated? Use a step-by-step execution sequence of the above tasks to show all possible results.

Answer

Load and store instructions to variable x are the only instructions whose interleaving can affect the value of x. The sequences of such instructions for both processes are shown below:

Task A	Task B
A1: load x A2: store x A3: load x A4: store x	B1: load x B2: store x

Interleaving scenarios can be conveniently represented as a sequence (e.g., A1-A2-A3-A4-B1-B2). How many possible interleaving patterns are there?

Lets start with A1-A2-A3-A4 (the order of instructions cannot change) and see in how many ways we can insert B1 and B2 so that B1 is before B2. We can insert B1 into one of 5 slots (before each A instruction and after the last one). In each of these insertions we have created one new slot for B2, which can now be inserted into one of 6 slots – 30 possible sequences in total. However, in only half of these B1 is before B2, so 5x6/2=15. All of them are shown below, together with the outcomes:

B1-A1-A2-A3-A4-B2 🡪 x = 0
B1-A1-A2-A3-B2-A4 🡪 x = 2
B1-A1-A2-B2-A3-A4 🡪 x = 1
B1-A1-B2-A2-A3-A4 🡪 x = 2
B1-B2-A1-A2-A3-A4 🡪 x = 2
A1-B1-A2-A3-A4-B2 🡪 x = 0
A1-B1-A2-A3-B2-A4 🡪 x = 2
A1-B1-A2-B2-A3-A4 🡪 x = 1
A1-B1-B2-A2-A3-A4 🡪 x = 2
A1-A2-B1-A3-A4-B2 🡪 x = 2
A1-A2-B1-A3-B2-A4 🡪 x = 2
A1-A2-B1-B2-A3-A4 🡪 x = 3
A1-A2-A3-B1-A4-B2 🡪 x = 2
A1-A2-A3-B1-B2-A4 🡪 x = 2
A1-A2-A3-A4-B1-B2 🡪 x = 4

There are five possible outcomes: 0, 1, 2, 3, 4. Note that the outcome would be non-deterministic even if each statement was executed atomically, because x=2*x and x++ are not commutative operations.

Q2

[Critical Section] Can disabling interrupts avoid race conditions? If yes, would disabling interrupts be a good way of avoiding race conditions? Explain.

Answer

Yes, disabling interrupts and enabling them back is equivalent to acquiring a universal lock and releasing it, respectively. Without interrupts, there will be no quantum-based process switching (because even timer interrupts cannot happen); hence only one process is running. However:

• This will not work in a multi-core/multi-processor environment since another process may enter the critical section while running on a different core.
• User code may not have the privileges needed to disable timer interrupts.
• Disabling timer interrupts means that many scheduling algorithms will not work properly.
• Disabling non-timer interrupts means that high-priority interrupts that may not even share any data with the critical section may be missed.
• Many important wakeup signals are provided by interrupt service routines and these would be missed by the running process. A process can easily block on a semaphore and stay blocked indefinitely, because there is nobody to send a wakeup signal.
• If a program disables interrupts and hangs, the entire system will no longer work since it cannot switch tasks and perform anything else.

Therefore disabling interrupts is not a good choice for the purpose of locking.

Q4

[AY 19/20 Midterm – Low Level Implementation of CS] You are required to implement an intra-process mutual exclusion mechanism (a lock) using Unix pipes. Your implementation should not use mutex (pthread_mutex) or semaphore (sem), or any other synchronization construct.

Information to refresh your memory:

• In multithreaded processes, file descriptors are shared between all threads in a process. If multiple threads simultaneously call read() on a file descriptor, only one thread will be successful in reading any available data up to the buffer size provided, the others will remain blocked until more data is available to be read.
• The read end of a pipe is at index 0, the write end at index 1.
• System calls signatures for read, write, open, close, pipe (some might not be needed):

int pipe(int pipefd[2]);
int open(const char *pathname, int flags, mode_t mode);
int close(int fd);
ssize_t read(int fd, void *buf, size_t count);
ssize_t write(int fd, const void *buf, size_t count);

Write your lock implementation below in the spaces provided. Definition of the pipe-based lock (struct pipelock) should be complete, but feel free to add any other elements you might need. You need to write code for lock_init, lock_acquire, and lock_release.

/* Define a pipe-based lock */
struct pipelock {
    int fd[2];
};

/* Initialize lock */
void lock_init(struct pipelock *lock) {
    // COMPLETE THIS
}

/* Function used to acquire lock */
void lock_acquire(struct pipelock *lock) {
    // COMPLETE THIS
}

/* Release lock */
void lock_release(struct pipelock * lock) {
    // COMPLETE THIS
}

Answer

struct pipelock {
    int fd[2];
};

void lock_init(struct pipelock *lock) {
    pipe(lock->fd);
    write(lock->fd[1], "a", 1);
    
    //The first write is meant to initialize the lock such that exactly one thread can acquire the lock.
}

void lock_acquire(struct pipelock *lock) {
    char c;
    read(lock->fd[0], &c, 1);
    
    //read will block if there is no byte in the pipe.
    
    //Closing the reading or writing end of the pipe in a thread will cause closing that end for all threads of the process (shared variable). Also, it will prevent all other threads to acquire or release the lock.
}

void lock_release(struct pipelock * lock) {
    write(lock->fd[1], "a", 1);
    
    //Need to write/read exactly one byte to simulate increment/decrement by 1 of a semaphore. It might work with multiple bytes, but you need to take care how many bytes are read/written.
}

Tutorial 9

Q2 (4 Level Page Tables)

[Page Table Structure] The Linux machines in the SoC cluster used in the labs have 64-bit processors, but the virtual addresses are 48-bit long (the highest 16 bits are not used). The physical frame size is 4KiB. The system uses a hierarchical direct page table structure, with each table/directory entry occupying 64 bits (8 bytes) regardless of the level in the hierarchy.

Assume Process P runs the following simple program on one of the lab machines:

#include <stdio.h>
#include <stdlib.h>

#define ONE_GIG 1<<30
#define NUM_PAGES 1<< 18

void main(){
    char* array = malloc(ONE_GIG);
    int i;
    for (i=0; i<NUM_PAGES; i++)
        array[i<<12]='a';
    printf("0x%lX\n", array); // line 9
    // point of interest
    free(array);
}

At line 9, the program prints out the value of variable array in hexadecimal:

$$\text{0x7F9B55226010}$$

Consider the point in time when the process execution reaches the point of interest (line 10 in the listing). Answer the following questions:

a. If we use a single-level page table, how much memory space is needed just to store the page table for process P?

b. How many levels are there in the page-table structure for process P?

c. How many entries in the root page directory are holding information related to process P's dynamically allocated data?

d. How many physical frames are holding information related to process P's dynamically allocated data in the second level of the hierarchical page-table structure (next after the root)?

e. How many physical frames are holding information related to process P's dynamically allocated data in the penultimate level of the page-table structure (i.e., the level before the last one).

f. How many physical frames are holding information related to process P's dynamically allocated data in the last level of the page-table structure?

Answer

a.

$2^{39}$ bytes

• Each Page Table Entry(PTE) = 8 bytes
• Virtual address is 48 bits: page/frame size is
  $2^{12}$, so 12 bits is used for offset, 36 bits is used for "idx of pages"
• Total size = number of pages * size of PTE =
  $2^{36}\times 2^3=2^{39}$ bytes

b. 4 levels

• Note: size of page table = size of a page/frame =
  $2^{12}$ bytes
• So, number of entries per table =
  $\frac{2^{12}}{2^3}=2^9$
• So, each level can points to
  $2^9$ next level tables
• Hence, we need
  $\frac{2^{36}}{2^9}=4$ levels
• Assumption: a memory pointer is the same size as a PTE for simplicity

c. 1 entry

• From d., we know we need 1 frame at second level. So we just need 1 entry at root level to point to one page table

d. 1 frame

• From e., we know we need 2 frames at second last level. So we just need 1 page table at this level, which is 1 frame

e. 2 frames

• From f., we know we need
  $2^9+1$ frames at last level. So we just need 2 page tables at this level to holld
  $2^9+1$ frames
• 2 page tables will occupy 2 frames

f.

$2^9+1=513$ frames

• Size of malloc:
  $2^{30}$ bytes
• Size of one page =
  $2^{12}$ bytes
• So minimally need
  $\frac{2^{30}}{2^{12}}=2^{18}$ pages
• But, notice that the address of array printed is not at the page boundary.
• Hence, in total we need
  $2^{18}+1$ pages
• Remeber one page table can hold
  $2^9$ entries, so we need
  $\frac{2^{18}}{2^9}=2^9$ page table to hold
  $2^{18}$ entries
• In total we need
  $2^9+1$ page tables, which is
  $2^9+1$ frames

AY1516 S1 Midterm

Q2 & Q3

Given a program P with two independent tasks A and B, let us examine the two implementations below: i. Sequential implementation: Single program that executes task A then task B. ii. Multithreaded implementation: A program with two threads working on task A and B concurrently.

Suppose both tasks are CPU-intensive, which of the following statement(s) is/are TRUE if the two implementations are executed on a single CPU (single core)?

i. If the threads are implemented as user threads, then multithreaded implementation will finish execution in shorter amount of time compared to the sequential implementation.

ii. If the threads are implemented as kernel threads, then multithreaded implementation will finish execution in shorter amount of time compared to the sequential implementation.

Answer

Both are FALSE

Suppose task A is CPU-intensive and task B is I/O intensive (reading from a file), which of the following statement(s) is/are TRUE if the two implementations are executed on a single CPU (single core)?

i. If the threads are implemented as user threads, then multithreaded implementation will finish execution in shorter amount of time compared to the sequential implementation.

ii. If the threads are implemented as kernel threads, then multithreaded implementation will finish execution in shorter amount of time compared to the sequential implementation.

Answer

Only (ii) is TRUE

Q10

Suppose there a number of tasks (>1) share the following variables:

• sCurrent = integer, initialized to 0, sNext = integer, initialized to 2.
• sArray[0….50000] = an array of Boolean variables. Elements [0], [1] are initialized to FALSE, all other elements sArray[2…49999] are initialized to TRUE.

For your convenience, all shared variables have a "s" prefix.

Each task executes the following code (in pseudo code):

while (TRUE) {
    while ( sCurrent is equal to sNext)
        sleep for 1 second;
    
    if (sNext >= 50000) end task;

    factor = sNext;
    sCurrent = sNext;

    for (j = factor*2; j < 50000; j = j + factor) //sieving through the array
        sArray[j] = FALSE

    for (k = factor+1; k < 50000; k++) //looking for the next prime
        if (sArray[k] is TRUE)
            if (k > sNext)
                sNext = k;
            break loop;
    
    if (k >= 50000)
        sNext = 50000+1;
        end task;
}

The above is an attempt to parallelize the famous Sieve of Eratosthenes algorithm. Essentially, we eliminate all multiples of a prime number, e.g. use 2 to eliminate of 4, 8, 10, 12… Then the smallest number > 2 that is not eliminated (e.g. 3) will be used as the next prime number. The process is then repeated until the whole range is exhausted (50,000 in this case). The algorithm is an efficient way to find out all primes in a given range.

a. Line 12 seems redundant (sNext is used as factor, so how can k > sNext?) Do you think it is needed? Briefly explain.

b. The code currently still exhibits race conditions, use two tasks to identify the race conditions. You only need to list down the line numbers that respective tasks executes that causes the race condition.

c. If you can use critical sections to solve the issues in (b), indicates the absolute minimal lines of code you will protect. Give the corresponding line numbers in the answer sheet.

Answer

a. It is not redundant, as other task may have increased sNext to a much larger number.

b.
The code is "carefully written badly" such that there is only one point of failure. If you think through it carefully, there are many possibilities of wasted computation (e.g. re-sieve the array with a known prime, two or more task used the same prime to sieve etc), but they will not result in incorrect execution. So, to properly shows a race condition, you need to pinpoint that single point of failure.

The point of failure is in line 12-13. Part (a) is actually a failed attempt to correct the error!

	Task 1	Task 2
t0	5-12
t1		5-17
t2		2-17
t3	13(!)-17

c.
From the above discussion, the minimal answer is "line 12, 13". Note that this essentially "sequentialize" the tasks.

Alternative answer: "line 5,6 and line 12,13" is acceptable (though "5,6" is not critical).

AY1617 S1 Midterm

Q8

Consider the 5-threads global sum program:

5 threads execute the following code, where globalVar is shared

for (int i = 0; i < 50000; i++)
    globalVar++;

a. What is the smallest possible value for globalVar at the end of execution (i.e. after all threads terminated)?

b. Briefly describe the interleaving pattern which gives you the answer in (a).

c. If the loop counter "i" is changes to a shared variable among the 5 threads, what is the smallest and largest possible value for globalVar at the end of execution.

Answer

a. The smallest globalVar is 2.

b.
Consider the following:

1. Task A loaded globalVar into register (0) and swapped out.
2. Task B finished 49, 999 iterations and swapped out.
3. Task A STORES the incremented registers to globalSum and wiped out all the increments so far (globalSum = 1).
4. Task B wakes up, take the globalSum into register (1) and swapped out again.
5. Task A finishes the rest of the iterations.
6. Task B wakes up, continue with the increment and stores the result (2) back to globalSum.

You can easily extend the above to 5 threads (just "kill off" the other 3 threads and make sure that two threads follow the above pattern).

c.
Smallest globalVar is 1. Consider the following:

1. Task A loaded globalsum into register (0) and swapped out.
2. Other tasks incremented i until it is larger than 49999. globalSum at that point is not important.
3. Task A wakes up, add 1 time, store globalSum (1).
4. Taks A reads i, check condition and terminated the loop.

Largest globalVar is HUGE. Consider the following:

1. Task B added one time, and read the i (preparing to do the "i++). However, just before writing i, it was swapped out.
2. Task A did all the hardwork and incremented globalSum 49,999 times, but before the last check, it was swapped out.
3. Task B wakes up and write (1) to "i".
4. Task A wakes up and loaded i for checking and found that it has still close to 49,999 iterations…

Task B can do the above EVERYTIME Task A finishes near to 49,999 times.

BUT, that's not all, we can use Task C to restart Task B when it is finally near the end and restart the entire process for A and B. Don’t forget that we still have task D and E…

Q11

Below is the blocking solution for producer-consumer problem:

Producer Process:

while (TRUE) {
    Produce Item;
    
    wait( notFull );
    wait( mutex );
    buffer[in] = item;
    in = (in+1) % 5;
    count++;
    signal( mutex );
    signal( notEmpty );
}

Consumer Process:

while (TRUE) {
    wait( notEmpty );
    wait( mutex );
    item = buffer[out];
    out = (out+1) % 5;
    count--
    signal( mutex );
    signal( notFull );
    
    Consume Item;
}

Suppose we initialized the semaphores as follows (note that the size of the shared buffer is 5 and pay attention to the two incorrect initializations):

• notFull = Semaphore(3); //incorrect!
• notEmpty = Semaphore(1); //incorrect!
• mutex = Semaphore(1); //correct

a. Briefly describe the effect of the incorrect notFull semaphore initialization. You should ignore the effect of the wrong notEmpty in this question.

b. Briefly describe the effect of the incorrect notEmpty semaphore initialization. You should ignore the effect of the wrong notFull in this question.

c. Suppose we have 5 producers tasks (P1 to P5) and 3 consumers tasks (C1 to C3) using the incorrect initialization as stated. Give a snapshot of the semaphores (the value and the blocked tasks on them) at any point during the execution. The only restriction is that the status of all 8 tasks must be clearly stated or implied in the snapshot.

d. If you were to mark your friend's answer on part (c) above, give the rules that you use to determine correctness. Your rule should be concise and has clear outcome (i.e. if XXXX, then it is wrong / correct or similar). You can also consider using formula to express relationship.

Answer

a.
Difficulty = Medium. Key point, the wrong semaphore init value limits the number of concurrent producer task (or the total useful value in buffer). Note that I was (very) strict for this part. Your answer should show that you understand all 5 locations of the buffer can still be used (e.g. after the first 3 production, consumer consumed 3, then the subsequent production will utilize buffer[3] and buffer[4] and wraps around etc). So, if you simply say "two slots will not be used" (or similar), that is INCORRECT.

b.
Difficulty = Easy. Key point, one consumer can start consuming without the data being placed in the buffer.

c.
Difficulty = Medium. The key phrase in the question is "All tasks status should be clearly stated or deducible". The "clearly stated" part refers to tasks shown explicitly on the semaphore queue, i.e. you know they are blocked. The "deducible" part can have a few example, e.g. if one task is missing from the picture and mutex is 0 -> that task is in the critical section.

So, the simplest answer is to just follow up on the original setup:

Mutex = 0, Queue = P2, P3, C1

notFull = 0, Queue = P4, P5

notEmpty = 0, Queue = C2, C3

The missing P1 is clearly in the critical section.

Note that if your answer need to write "P1, P2 is doing …, P3 is …" explicitly outside of the semaphore -> incorrect.

There are (way too) many alternatives. Feel free to explore a few other.

d.

1. If you gave generic rules that are just reiterating semaphore property, e.g. "value cannot be negative", "value = init – wait + signal", etc. NO MARK.
2. If you gave simple rules that are applicable to independent semaphore in this question, e.g. "If value of notfull > 4 == incorrect". 1‐2 marks.
3. If you gave rules that link the semaphores together, e.g. "notFull + notEmpty <= 4". 3 marks.
4. If you gave any incorrect rules, penalty is applied. e.g. "notFull cannot be > 3" or "notEmpty cannot be > 1".

AY1718 S1 Midterm

Q3

Which of the following statment(s) regarding zombie process is TRUE?

i. Zombie process takes up a slot in the OS PCB table.

ii. Zombie process is created so that wait() system call can be implemented properly.

iii. A user command running in the background under a shell interpreter can become a zombie process.

Answer

i. Correct. Zombie process retains PID and stores termination status and result at its PCB table.

ii. Correct. As dicussed in lecture, without the zombie state, we wont be able to return information about terminated child process to the parent process.

iii. Correct. This is essentially similar to (ii). A foreground process is waited by the shell interpreter directly. A background process, on the other hand, is not CS2106 1718S1 Midterm Solution and Explanation waited. That's how the interpreter can continue to accept user input. So, if the background process terminated, it will turned into a a zombie process.

Q5

Given the following pseudo code:

Code A	Code B
wait( S ); <do some work> signal( S );	<heavy computation>

Which of the following setup can potentially cause priority inversion?

a. A high priority task running code B and a lower priority task running code A.

b. A high priority task running code A and a lower priority task running code B.

c. The highest and lowest priority tasks running code A and a middle priority task running task B.

d. The highest and lowest priority tasks running code B and a middle priority task running task A.

e. None of the above

Answer

Ans: c

Priority inversion: ‐ Assume priority based pre‐emptive scheduling algorithm. ‐ A low priority task acquires a resource needed by high priority task. ‐ The low priority task is preempted by high priority task -> cannot release the resource -> blocks high priority task. ‐ A medium priority task can execute despite the existence of a high priority task.

The code above construct a simple demonstration of this problem. If a high priority task H and a low priority task L run code A, then it is possible that the L enter the critical section but get pre‐empted by H before finishing its work. So, L still "holds" the semaphore, preventing H from executing. At this time, if a medium task M enter the system to run code B, it will get picked over H despite having a lower priority.

AY1718 S2 Midterm

Q17

We have the following 4 processes that have access to 3 shared binary semaphores s1, s2 and s3, initially set to 1. The read() and write() operations are non-blocking asynchronous calls (i.e. they exit immediately after being called regardless of whether there is a corresponding write/read). The “sem_pend” operation decrements the given semaphore while the “sem_post” operation increments it.

P1 while(1): sem_pend(&s1); sem_post(&s2); write(f1); read(f2); send_post(&s1); sem_pend(&s2);	P2 while(1): sem_pend(&s1); sem_pend(&s2); read(f2); write(f1); send_post(&s2); sem_post(&s1);
P3 while(1): sem_pend(&s2); sem_pend(&s1); read(f1); write(f2); send_post(&s1); sem_post(&s2);	P4 while(1): sem_pend(&s1); sem_pend(&s2); read(f1); write(f2); send_post(&s2); sem_post(&s1);

Which of the following pairs of processes may cause deadlock?

a. P1 and P2

b. P1 and P4

c. P1 and P3

d. P2 and P4

e. None of the above pairs in a. to d. may cause deadlocks.

Answer

c

AY2122 S1 Midterm

Q2

Which of the following statement(s) regarding the difference between library calls and system calls is/are TRUE?

i. Library calls are programming language dependent, while system calls are dependent on the operating system.

ii. A system call may be invoked during a library call.

iii. If a system call and library call both execute approximately the same code, the library call is likely to take a longer amount of time to complete, as the system call is lower-level.

Answer

i. Correct

ii. Correct

iii. Incorrect, system call will take longer, context switch. It is ambiguous and unclear what "system call is lower-level" means, or if that is the reason for library calls taking longer to execute.

AY1718 S1 Final

Q1

On a system using pure paging-scheme, when we attach a share memory region to a process, the memory address returned by the shmat() function is likely to be at the boundary of a memory page. True or False and explain why.

Answer

True. The translation (i.e. frame number) to the shared region must be different from other memory locations.

Q2

All threads in the same process can share the same page table. True or False and explain why.

Answer

True. All threads in the same process still using same virtual memory space.

Q3

The size of a Page Table Entry (PTE) is dependant on the total size of the logical / virtual memory space of a process. True or False and explain why.

Answer

False. PTE stores frame number mainly, which is influenced directly by the size of physical RAM not the size of the virtual memory space.

Q4

The size of a Direct Paging Page Table (i.e. the number of page table entries) of a Process is dependant on the total size of the logical / virtual memory space utilized by the process. True or False and explain why.

Answer

False. Page table has the same number of entries regardless of actual usage.

Q5

The Virtual Address (VA) can never be the same as the Physical Address (PA), i.e. there can be no instance where VA 0xZZZZ ZZZZ get translated to PA 0xZZZZ ZZZZ. True or False and explain why.

False. It is possible for a Page to map to a frame with the same number, i.e. Page 123 to Frame 123 by chance.

Q6

Accessing the Nth block of a file managed by FAT scheme requires O(N) hard disk accesses in the worst case. True or False and explain why.

False. FAT scheme is the linked list v2.0 implementation learnt in class. FAT is an in-memory structure, the linked list traversal takes place in memory not hard disk. So it requires zero hard disk accesses.

Q7

Suppose process A is current executing and is given 2 time units time quantum to run:

1	2	3	4
A	A	...	...

In Unix, a new Process B can only arrive in the system during the shaded region. Note that ITI is not part of the shaded region. True or False and explain why.

Answer

True. In UNIX, process can be created only via fork()/clone() mechanism. So, A has to invoke one of these. Hence, it can only happend when A is executing

Q14

Outline a simple program that can find out the page size of a machine. You should state clearly how to run the program and interpret the result.

Answer

Many possibilities.

Common approaches:

• Using timing (page fault / TLB fault incurs a much longer latency then normal memory access).
• Using segmentation fault. In pure paging scheme, seg.fault can only be detected by going beyond a page.

Sample answer:

• Create an array of large size.
• Access the item sequentially and monitor the time needed for each access.
• When there is a huge spike, it is likely we have hit the page boundary.

Common wrong / partially wrong answers:

• Assumed I/O buffer size is the same as page size and use the printf() example from tutorial to find the buffer size.
• Assumed that the memory address will have a "huge jump" between pages. This is a pretty serious misunderstanding as it confused logical address (seen by the program) and the physical address (translated and used by hardware). If you print the address of a variable inside the program (e.g. printf("%p", &myVar)), you only see the logical address.

Q15

Upon the termination of a process P, operating system is supposed to "clean up the resources used by P". Answer the following briefly:

a. How is the OS notified of P's termination?

b. Indicate the resources to be cleaned up and how can the OS find out the relevant information to perform the cleaning. You should be as specific as possible and refer to ideas covered in this course.

Answer

a. Process will calls exit() system call implicitly or explicitly.

b. Use process's page table to find out memory frames used. Use process's file descriptors table to find out file opened.

Q16

Indicate whether the working set W(T, Δ) increases (more pages are needed), decreases (less pages are needed) or stable (no change in number of pages needed) for the following scenarios:

a. We are executing a loop to calculate values to be stored in a large array.

b. We are currently executing a recursive function.

c. We are currently blocked on a critical section implemented by busy waiting.

State any assumption if necessary.

Answer

a. Increases. Data pages for the array needs to be read in / write out.

b. Increases. Stack space will increases.

c. Stable. Code executed is the same (busy waiting is usually an infinite loop).

Alternative answers with assumptions:

• If we look at a small enough time window, then it can be argued that a. and b. has "stable" number of pages. e.g. if the time window covers only one iteration of loop in a., then we only access a single element (from one page) every window. Similar argument can be made for b..

AY2021 S1 Final

Q5

A computer supports 64-bit virtual memory addresses. The page size is 1KiB (

$2^{10}$ bytes), the size of a page table entry is two bytes. Assuming the addressing is at the word (8 bytes) level, calculate the size of the standard page table (in bytes).

A.

$2^{58}$

B.

$2^{57}$

C.

$2^{54}$

D.

$2^{55}$

E.

$2^{52}$

Answer

A.

$2^{58}$

Since the addressing is at word (8 bytes) level, the system can support

$2^{64}\times 8$ bytes in total with 64-bit virtual address.

number of pages =

$\frac{2^{64}\times 8}{2^{10}}=2^{57}$

size of page table = size of page table entry * number of pages =

$2^{57}\times 2=2^{58}$

Q7

Consider a virtual memory system with the page table stored in memory (memory resident). If a memory access takes 200 nanoseconds, what is the longest time that a paged memory reference takes?

A. 600 ns

B. 600 ns + time to service a page fault

C. 400 ns + time to service a page fault

D. 200 ns + time to service a page fault

E. More than 600 ns + time to service a page fault.

*time to service a page fault includes the time to bring the page from SWAP to memory.

Answer

B. 600 ns + time to service a page fault

1st memory access: search page table

2nd memory access: page fault

3rd memory access: succesfully get page needed

Total = 600ns + time to server page fault after 2nd access

Q4

A process is generating a page fault while accessing a memory region for which is does not have access rights. What happens in this case?

A. The operating system will handle the page fault and the process can continue the execution with the next instructions.

B. A signal SIGSEGV is sent to the process. If the operating system does not have a signal handler set for SIGSEGV, the process is terminated.

C. A signal SIGSEGV is sent to the process. The process might terminate.

D. A signal SIGSEGV is sent to the operating system. If the operating system does not have a signal handler set for SIGSEGV, the process is terminated.

E. The operating system will handle the page fault, and the process retries the instruction that caused the page fault.

Answer

C. A signal SIGSEGV is sent to the process. The process might terminate.

Q15

Throughout their execution, parent and child processes share ALL entries in the system-wide open file table, but different file descriptor tables.

A. True

B. False

Answer

B. False. All files opened by parent before fork() is shared between parent and child. After fork(), files open by parent and child are not shared.

Q19

A process creates multiple threads (using pthread library); next, each thread opens the same file and reads 32 bytes from the file (using read system call). What will each thread read?

A. Same information (same bytes).

B. Different parts of the file, depending on the order the threads get to read.

C. There is a race condition because the threads read from the same file.

D. If the file is open for reading by another process, it is impossible to say.

Answer

A. Same information (same bytes).

This is similar to the scenario where same process open file twice in lecture note.

Q23

In a program, the following call is used:

fd = open("/home/e1234567/myfile", O_RDONLY);

The call is successful and myfile is a hard link. How many I-nodes have been read by this call?

A. 1

B. 2

C. 4

D. 5

E. Impossible to say.

Answer

C. 4

/, /home, /home/e1234567, /home/e1234567/myfile

Q40

What would be the fastest way to transfer a large amount of data between two processes running on the same operating system? Explain your answer.

Note: The information does not need to be copied during the transfer.

Answer

mmap() is used to map a shared memory region or a shared file to both processes such that both processes are able to access the shared data on RAM without any system calls.

Q41

In general exec() syscall takes longer time to execute than fork() syscall. Briefly explain why.

Answer

fork() duplicates the current process' image and creates a chile process whereas exec() replaces the current process' image with a new executable.

Duplicating the current process image requires only memory access whereas bringing in a new executable requires access to secondary storage, which is much slower than memory access.

AY2223 S1 Final

Q1

Which of the following are used by the OS to provide isolation and protection?

i. Virtual memory

ii. Process abstraction

iii. Exception handling

iv. File permissions

a. (i) only

b. (i) and (ii) only

c. (i), (ii) and (iii) only

d. None of the above

e. All of the above

Answer

e. All of the above

Virtual memory and processes isolate user application execution instances from one another.

Exception handling delivers exceptions to the responsible party, leaving others unaffected.

File permissions have protect user files from unwanted access.

Q11 - Q16 (3 Level Page Tables)

Question 11 to 16 below uses the same set of assumptions. Namely, consider a byte-addressed virtual memory system with the following set up: (i) virtual address are 32 bits long, (ii) physical addresses are 28 bits long, (iii) a page is 4Kibyte (4096 bytes), (iv) each page table is a page in length, (v) page table entries are 4 bytes, and (vi) it uses 3 levels of page tables.

How many entries are there in a single page table?

a. 256

b. 512

c. 1024

d. 2048

e. 4096

Answer

c. 1024

Size of a page table = Size of a page

One page is 4096 bytes =

$2^{12}$ bytes

One page table entry is 4 bytes =

$2^2$ bytes

So, number of entries =

$\frac{2^{12}}{2^2}=2^{10}=1024$

Suppose a process only has one physical page frame allocated to it. What is the total memory required for the page tables (not including that final one data page frame).

a. 1029 bytes

b. 5000 bytes

c. 10821 bytes

d. 12288 bytes

e. 16384 bytes

Answer

d. 12288 bytes

The process just need one page table at each level.

Each page table is

$2^{12}$ bytes, so total

$3\times 2^{12}=12288$

Suppose a process has 10 physical page frames allocated to it. What is the minimal memory space that would be required for the page tables (not including the 10 data page frames)?

a. 10821 bytes

b. 12288 bytes

c. 16384 bytes

d. 36864 bytes

e. 45056 bytes

Answer

b. 12288 bytes

Level 3 page table can point to 10 data frames. So same as previous question.

Suppose a process has 10 physical page frames allocated to it. What is the worst case memory space that would be required for the page tables (not including the 10 data page frames)?

a. 36864 bytes

b. 45056 bytes

c. 86016 bytes

d. 167936 bytes

e. 372736 bytes

Answer

c. 86016 bytes

In the worst case, each level 3 page table point to 1 data frame. Each level 2 page table point to 1 level 3 page table. Level 1 will only has 1 page table.

Level 1:

$2^{12}$ bytes

Level 2:

$2^{12}\times 10$ bytes

Level 3:

$2^{12}\times 10$ bytes

Total =

$2^{12}+(2^{12}\times 10)+(2^{12}\times 10)=86016$ bytes

Assuming that processes do not share any pages. In the worst case, how many processes would the system be able to accommodate if each process uses 100 logical pages before it runs out of (maximum) physical memory? Assume that all pages reside in physical memory, i.e., no disk backup.

a. 13

b. 115

c. 217

d. 326

e. 512

Answer

c. 217

Same as previous question, in the worst case, page tables for 1 process will need

$2^{12}+100(2^{12})+100(2^{12})$

In total, 1 process will need (size of page tables) + (100 data frames) =

$[2^{12}+100(2^{12})+100(2^{12})]+100(2^{12})=2^{12}(301)$

Total memory available =

$2^{28}$

So,

$\lfloor \frac{2^{28}}{2^{12}(301)}\rfloor =217$

Following up on Question 15, i.e., using the same assumptions in that question except that the system turns on demand paging using an infinite disk storage to backup for data pages (but not the page tables – which remains in physical page frames), how many processes can the system accommodate in the worst case? Note that you need at least one data page in physical memory to contain some code and data for execution.

a. Infinite

b. 115

c. 217

d. 326

e. 512

Answer

d. 326

Pages can now be in disk. So we can only consider size of page tables.

$\lfloor \frac{2^{28}}{2^{12}+100(2^{12})+100(2^{12})}\rfloor =326$

Q21 - Q22 (Buddy System)

Which of the following address falls in the 512-byte size buddy block of this address: 0x485BB1

a. 0x485BA1

b. 0x4859B1

c. 0x485AB1

d. 0x485CB1

e. 0x486BB1

Answer

b. 0x4859B1

Two blocks are buddy of size 2^S, if
- The Sth bit is complement of each other
- The leading bits up to Sth bit are the same

0x485BB1 = 0100 1000 0101 1011 1011 0001

519 bytes = 2^9 bytes

So the answer will be 0100 1000 0101 1001 1011 0001 = 0x4859B1

Suppose both the 512-byte block containing 0x485BB1 and its buddy are freed. What is the starting address of the resultant 1024-byte block

a. 0x485800

b. 0x485900

c. 0x485A00

d. 0x485B00

e. 0x486C00

Answer

a. 0x485800

From previous question, we know th 9th bit will be complement of each other, and the most significant 14 bits need to be the same.

The most significant 14 bits will be the starting address when they combined.

Q24 (Inverted Table)

Suppose we have the following 2048-entry inverted table:

PID	Page Number
0	0
1	0
2	0
3	0
0	1
1	1
2	1
3	1
…	…
0	511
1	511
2	511
3	511

In other words, entry

$i$ of the table is the entry for PID =

$i$ mod 4, and page number (

$i$ >> 2) – "right shift

$i$ by 2 bits". What is the physical address for Process with ID of 1 and a virtual address of 0xAC529 assuming each page is 4096 bytes?

a. 0xAC429

b. 0xACB29

c. 0x2A0529

d. 0x2B1529

e. 0x2AC012

Answer

d. 0x2B1529

We know the virtual address can be split into two parts, page number and offset.

Since one page is 4096 bytes =

$2^{12}$ bytes, the least significant 12 bits will be offset.

So, 0xAC529: Page number = 0xAC, Offset = 0x529

Page number = 0xAC = 172, the query will be <1, 172>

Also notice that, for PID = 1:

• page 0 -> frame 1
• page 1 -> frame 5
• page 2 -> frame 9
• page
  $p$ -> frame
  $4p+1$

So, page 172 will be mapped to frame 689 = 0x2B1

Hence, the physical address will be frame number + offset = 0x2B1 + 0x529 = 0x2B1529

Note: The plus, + here doesn't mean addition, it is just for visualise.