[OSC] Problem sheet 2

1.Using a simple system call as an example (e.g. getpid, or uptime), describe what is generally involved in providing the result, from the point of calling the function in the C library to the point where that function returns.
A system call is completed as follows:
  • As the function is called, an interrupt of the type “software exception” is placed on the processor, causing a Context Switch to take place between the calling function and the kernel.
  • The exception handler will clear out and save user registers to the kernel stack so that control may be passed on to the C function corresponding to the syscall.
  • The syscall is executed.
  • The value(s) returned by the syscall is placed into the correctly corresponding registers of the CPU
  • The handler takes this value, restores user registers and returns said value to the user program that called it.
2.Describe a sequence the sequence of step that occur when a timer interrupt occurs that eventually results in a context switch to another application.
  • Timer interrupt is called.
  • Trap into kernel space, switching to kernel stack
  • Current applications’s registers are saved
  • Scheduler gives next thread that should be run
  • Context switch to other thread(load its stack, flush the TLB)
  • Load user registers from the kernel stack
  • PC register shifts to the beginning of the other application’s instruction
3.Briefly explain what a context switch is (i.e. not a mode switch) and describe the different actions that you would expect an operating system to take to carry out a context switch.
  • When a context switch takes place, the system saves the state of the old process and loads the state of the new process
  • switching process
    1.Save process state(program counter, registers)
    2.Update PCB(running->ready/blocked)
    3.Move PCB to appropriate queue(ready/blocked)
    4.Run scheduler, select new process
    5.Update to running state in the new PCB
    6.Update memory management unit(MMU)
    7.Restore process
4.List and briefly explain the three conditions that a solution to the critical section problem must satisfy.
mutual exclusion: only one process can be in its critical section at any one point in time
Progress: any process must be able to enter its critical section at some point in time
Fairness/bounded waiting: processes cannot be made to wait indefinitely
5.List and briefly explain the 4 conditions that must hold for deadlocks to occur (known as Coffman’s conditions). Give two examples of how you could undermine these conditions to prevent deadlocks from happening.
  • mutual exclusion: a resource can be assigned to at most one process at a time
  • hold and wait: a resource can be held whilst requesting new resources
  • No preemption: resources cannot be forcefully taken away from a process
  • Circular wait: there is a circular chain of two or more processes, waiting for a resource held by the other processes
Example 1 : temporarily release all resource before requesting a new one to prevent hold and wait
Example 2 : Allocate resources a number and force resource requests to be made in numerical order
6.List one advantage and one disadvantage for each of the following file systems:
i. Contiguous
ii. Linked list
iii. File allocation table
iv. I-nodes
  • Contiguous
    Pros: Simple to implement/optimal read/write performance
    Cons: the exact size of file(process) is not always known beforehand/ Allocation algorithms needed to decide which free blocks to allocate to a given file/Deleting a file results in external fragmentation
  • Linked lists
    Pros: Easy to maintain/file sizes can grow dynamically/no external fragmentation/Sequential access is straightforward
    Cons: Random access is very slow/internal fragmentation/A block is no longer a power of 2/ Diminished reliability
  • FAT
    Pros: Block size remains power of 2/Index table can be kept in memory allowing fast non-sequential/random access
    Cons: The size of the file allocation table grows with the number of blocks, and might be too big
  • I-nodes
    Pros: I-node is only loaded when the file is open
    Cons:
7.Explain how the Linux file system (ext3 and ext4) improves performance and reliability over the standard Unix i-node file system.
Ex3 builds upon the Ex2 file system by adding:
  • Tree based structures for directory files to facilitate indexing
  • Journaling capabilities

评论

发表评论

此博客中的热门博文

[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
阅读全文