[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?
enter image description here

评论

发表评论

此博客中的热门博文

[MLE] W2 Multivariate linear regression

图片
Multivariate linear regression What we have talked about in week 1 is linear regression with single feature. For example, in the house pricing predicting problem, we only use the size of house (x) to predict the price (y) . But what if there are other features like age, bedroom numbers and so on? Linear regression with multiple variables is also known as “multivariate linear regression” According to the graph above, we now have new representation symbols: n = number of features m = number of training examples \(x^{(i)}\) = \(i^{th}\) training example \(x^{(i)}_j\) = feature j in \(i^{th}\) training example 1416 is \(x_{1}^{(2)}\) in this case, m is 47 for example, n is 4. Hypothesis function The multivariable form of the hypothesis function accommodating these multiple features is as follows: if we make \(x_0\) to 1, the \(h_{\theta}(x)\) will be \(\theta^Tx\), which is \(\theta\) transpose matrix multiply by x, where \(\theta\) is a vector of 1 by(n+1) dimension an
阅读全文

[MLE] W1 Introduction

图片
Before get started The blog is based on the machine learning course on Coursera, taught by Andrew Ng . From today, i will begin my study trip on Machine learning, which will be labelled as MLE. This course will last 11 weeks and today is week 1. The application of machine learning is everywhere: Database mining Applications can’t program by hand Self-customizing program Understanding human learning(brain, real AI) Introduction What is Machine Learning Two definitions of machine learning are offered: Arthur Samuel described it as: “the field of study that gives computers the ability to learn without being explicitly programmed.” This is an older, informal definition. Tom Mitchell provides a more modern definition: “A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” If we raise a example of what is machine learning: If
阅读全文

[AIM] MetaHeuristics

图片
Day2 Outline Metaheuristics -definition Single point based search method(simple stochastic local search) Iterated local search Scheduling Tabu Search Metaheuristic what is a metaheuristic? A metaheuristic is a high-level problem independent algorithmic framework that provides a set of guidelines or strategies to develop heuristic optimization algorithms. what is the difference between heuristic and metaheuristic? Heuristic : Heuristics are problem-dependent techniques. As such, they usually are adapted to the problem at hand and they try to take full advantage of the particularities of this problem. However, because they are often too greedy, they usually get trapped in a local optimum and thus fail, in general, to obtain the global optimum solution. Metaheuristic : Meta-heuristics, on the other hand, are problem-independent techniques . As such, they do not take advantage of any specificity of the problem and, therefore, can be used as black boxes . In general, t
阅读全文