[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] Linear Classification

图片
Linear Classification Discriminant functions Least squares for classification Fisher’s linear discriminant K-Nearest Neighbour(KNN) Classification What’s decision boundaries/linearly separable? The goal in classification is to take an input vector x and to assign it to one of K discrete classes \(C_k\) where k = 1,…,K. In the most common scenario, the classes are taken to be disjoint, so that each input is assigned to one and only one class. The input space is thereby divided into decision regions whose boundaries are called decision boundaries or decision surfaces. In this blog, we consider linear models for classification , by which we mean that the decision surfaces are linear functions of the input vector x and hence are defined by (D-1) -dimensional hyperplanes within the D-dimensional input space. For example: in 3D input space, the decision boundary will be a 2D surface What is Linear Separability Linearly separable data: Datasets whose classes can be separated by
阅读全文

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

[CS231] Neural Networks

图片
Neural Network Table of Contents: Quick intro without brain analogies Modeling one neuron Biological motivation and connections Single neuron as a linear classifier Commonly used activation functions Neural Network architectures Layer-wise organization Summary Additional references Quick intro It is possible to introduce neural networks without appealing to brain analogies. In the section on linear classification we computed scores for different visual categories given the image using the formula \( s = W x \), where \(W\) was a matrix and \(x\) was an input column vector containing all pixel data of the image. In the case of CIFAR-10, \(x\) is a [3072x1] column vector, and \(W\) is a [10x3072] matrix, so that the output scores is a vector of 10 class scores. An example neural network would instead compute \( s = W_2 \max(0, W_1 x) \). Here, \(W_1\) could be, for example, a [100x3072] matrix transforming the image into a 100-dimensional intermediate vector. The funct
阅读全文