[OSC] Problem sheet 1

1.List two examples where it is important for the operating system to take the architecture of the hardware into account.

• Processes: multi-core scheduling, processor affinity, true parallelism
• Memory: large memories, multi-level page tables, inverted page tables, MMU, TLB
• FS + Disks: solid state disks eliminate rotational latency/seek times, disk scheduling becomes less important, no rotational delays, FCFS becomes more practical

2.Keeping in mind the implementation differences between threads and processes on an operating system level,
explain why thread creation and switching are faster than process creation and switching.

• Thread control blocks contain less information, less data structures have to be created. Hence, creating the thread control block is much faster than creating the process control block
• Since threads share memory with processes, the memory map/page table does not change when a context switch takes place between threads. Also the TLB entries remain valid

3.In which situations would you favour user level threads? In which situations would you favour kernel level threads. Explain your answer.

• User threads run entirely in user space and rely on user libraries. These are useful when the underlying operating system does not provide thread support, or is a single CPU machine
• User level threads do not support true parallelism in multicore/multiprocessor architectures. Kernel level threads do enable to use true parallelism

4.
5.List one advantage and one disadvantage for each of the following memory management schemes:

• Mono-programming
• Fixed partitions with equal size
• Dynamic partitions
• Paging
• Virtual memory with paging

Mono-programming:
Pros: Simple to implement, No protection between different user processes required (one process)
Cons: Since a process has direct access to the physical memory, it may have access to OS memory/ Low utilisation of hardware resources (CPU, I/O devices, etc.)/ Mono-programming is unacceptable as multiprogramming is expected on modern machines
Fixed partitions with equal size:
Pros: Very little overhead and simple implementation
Cons: Internal fragmentation
Dynamic partitions:
Pros: A process is allocated the exact amount of contiguous memory it requires, thereby preventing internal fragmentation
Cons: External fragmentation/ The exact memory requirements may not be known in advance (heap and stack grow dynamically)
Paging:
Pros: Allows jobs to be allocated in non-contiguous memory location/ Eliminates external fragmentation/Easy to allocate physical memory
Cons: Internal fragmentation still exists, though in last page
Virtual memory with paging:
Pros: Virtual memory allows the logical address space (i.e processes) to be larger than physical address space (i.e. main memory)/Memory allocation easier
Cons: still needs TLB to speed up/additional overhead on context switch
6.What is thrashing? Explain why it can happen?

• Thrashing occurs when pieces are swapped out and loaded again immediately
• Page is evicted that needs to be reloaded soon. Process causes page faults every few instructions,
• Causes:
• Degree of multi-programming too high(i.e., the total demand (i.e., the sum of all working set sizes) exceeds supply (i.e. the available frames))
• Process allocated too few pages, working set cannot be loaded in memory
• Bad page replacement algorithm

7.Briefly explain the principle behind address relocation. Why it is a necessity on modern day interactive/multi-tasking machines. Explain how address relocation works in virtual memory with paging. Include an illustration.
There are two main address, physical and logical address.

• Code contains logical address, usually relative to the start of the program
• Code can run at any location in physical memory
• Improve level of multiprogramming
• A mapping/translation has to take place between the logical and physical address(MMU)

Because on multi-tasking machines, there will be more than one process, so we need to manage different process image on the same time.
In virtual memory with paging, multiple “base registers” will be required and each logical address needs a separate “base register” that specifies the start of the frame.
There will be a page table which demonstrates the relation between page number and frame number. The physical address will be the corresponding logical(page number) translated to frame number and add the offset.
8.Consider a computer that has 1 GB of memory. 200 Mb is reserved for the operating system, and each process takes on average 200Mb. By how much would you expect the CPU utilization to increase by adding an additional gigabyte of memory? Assume that the I/O rate is 80% and that each additional process takes up 200Mb.
• (1-0.8^4 ) = utilization for 1Gb
• (1-0.8^9 ) = utilization for 2Gb
• (1-0.8^9 )/ (1-0.8^4 ) = increase in utilisation
9.
The address space is 16bit and there are 4 bit for number of pages, so the rest of 12 bit will be the offset
2^12 = 4096
logical address 1234 = page 0 + offset 1234 = frame 2 + offset 1234 = 8192+ 1234 = 9426
logical address 12288 = page 3 + offset 0 =frame 0 = 0
logical address 25810 = page 6 + offset 1234 = frame
10.Assuming that the memory access time is 90ns and the time it takes to search the translation lookaside buffer is 15ns. What is the average memory access time for a page table with 3 levels and a 98% hit rate (write down in equations how you get the result)?

Assume that a fetch from main memory takes T nano seconds
With a single page table level , access is 2 * T
With a two page table levels , access is 3 * T

TLB hit time = 15+ 90 = 105ns
TLB Miss time = 15* 4*90 = 375ns
Average access time = 105*98% + 375*2%
11.Consider a swapping system for which the free list indicates the following blocks of memory (a) 10KB, (b) 15KB, (c) 12KB, (d) 21KB, (e) 30KB, (f) 9KB, (g) 16KB (in that order). Assume that requests for blocks of memory of 12KB, 9KB and 25KB come in (in that order). Which partitions would be allocated for the first fit, next fit, and best fit algorithm?
First fit: bae
Next fit: bce
Best fit: cfe
12.Assume that you have a process with 8 logical pages and a system with 4 physical frames. Considering the order in which the pages are referenced given below, how many page faults would be generated by the least recently used page replacement algorithm? Please include the steps of your working. Page references: 6 7 2 5 6 3 5 1 5 7 3 3
page fault = 7
13.Explain why hard links do not work across different machines.
Because hard links maintain references to the same i-node but i-node is unique in every machine within the filesystem
14.Cylinder skew adds an offset to the sectors on adjacent cylinders on traditional magnetic hard drives. If a disk rotates at 10000 rpm, the seek time between two adjacent cylinders is 1 millisecond, and each track contains 600 sectors, how many sectors should the cylinder skew be?