[OSC] Day1: OSC revision overview and Introduction

Overview

In this term, we learned the following parts about operating system:
enter image description here
From then on, i’ll review these parts and introduce each parts as detailed as possible.

Introduction

Resources: Tanenbaum Chapter 1, sections 1.1, 1.3, 1.7

“Defining” operating systems:

A virtual machine providing abstractions
  • An operating system is a layer of indirection on top of the hardware:
    It provides abstractions for application programs (e.g., file systems)
    It provides a cleaner and easier interface to the hardware and hides the complexity of “bare metal”
    It allows the programmer to be lazy by using common routines :-)
one picture you should really know about:
enter image description here
A resource manager
  • Many modern operating systems use multi-programming to improve user experience and maximise resource utilisation
  • The operating system must allocate/share resources (including CPU, memory, I/O devices) fairly and safely between competing processes (Tanenbaum page3):
    In time, e.g. CPUs and printers
    In space, e.g., memory and disks
  • The execution of multiple programs (processes) needs to be interleaved with one another. This requires:
    This requires context switches and process scheduling ⇒ mutual exclusion, deadlock avoidance, protection
The transition between kernel mode and user mode:
The operating system runs in kernel mode and has access to all instructions
Applications run in user mode and have access to a subset of instructions
enter image description here
There is a mode bit in PSW(Program Status Word) register, which control these two mode.
Some properties of OS:
  • Sits directly on top of the hardware
  • Has access to the full capabilities of the hardware
  • Provides abstractions for the user/programmer
  • Makes sure that everything is organised and runs in an orderly fashion
  • Improve the hardware interface

Computer Hardware


CPU

A CPU’s basic cycle consist of fetch, decode, and execute (pipelines, or superscalar)
Every CPU has his own instruction set, which means Pentium can not execute SPARC program and vice versa
Because visiting memory to get instruction or data is much more time consuming than executing it, a CPU has a set of registers (extremely fast memory close to the CPU “core”) to store key variables and temporary register.
Excluding to these common register, most CPU has
program counter: It stores the address of next instruction, and when the instruction was fetched out, it is updated to point next instruction.
Stack pointer: points to the top of stack, the stack stores relative parameters and local variables
Program Status Word (PSW): This register contains CPU priority, mode bit(user-kernel mode) and other control bit. It is important in System call and I/O
Context switching must save and restore the CPU’s internal state, including its registers
To improve performance, now modern CPU use pipeline, which is to execute instruction n as well as decode instruction n+1 and fetch instruction n+2.
One more advanced way is superscalar CPU, which has more than one execution unit. For example, one CPU can be used to integer calculation, one used to floating number calculation and another used to bool calculation. Two or more instruction was fetched, decoded and stored in the holding buffer. If one execution unit is free, it gets one from holding buffer.
a is pipeline and b is superscalar
(a) pipeline (b)superscalar

Memory management unit(MMU)


We start by this question on the slide.
The answer is same and No.
This is because the logical address is displayed for both processes. However, both logical addresses are mapped onto different physical addresses, which means that they can of course contain different values. Hence why the actual value for the variables displayed on the screen is different.
In summary:
- the two processes have the same logical address
- the logical addresses are mapped onto different physical addresses
- the physical addresses contain different values for both processes.
Address translation takes place in the Memory Management Unit (MMU)
physical = f (logical )
A context switch between processes invalidates the MMU (as well as registers, cache, … )
⇒ The CPU’s internal state must be saved and restored for every context switch (by the OS in the process control block)

Timer Interrupts

Interrupts temporarily pause a process’s normal operation
Different types of interrupts exist, including:
  • Timer interrupts by CPU clock
  • I/O interrupts for I/O completion or error codes
  • Software generated, e.g. errors and exceptions

Multi-core, hyperthreaded processors

Evolution in hardware has implications on operating system design
- XP did not support multi processor architectures
- Process scheduling needs to account for load balancing and CPU affinity
- Cache coherency becomes important

Memory

Fast and expensive memory is used for caching
Slow and inexpensive memory is used for long term storage
Memory includes, registers, L1/L2 cache, main/core memory, disk, etc.
L1 Cache: always in CPU, usually put the decoded instruction to CPU’s execution unit
L2 CacheIf: the instructions are not present in the L1 cache then it looks in the L2 cache, which is a slightly larger pool of cache, thus accompanied by some latency.

I/O devices

Device driver interacts with the controller, controller interacts with the device (e.g., disk controller)
The operating system/device driver typically communicates with the controller through registers
I/O can take place through:
  • Busy waiting: In the simplest method, a user program issues a system call, which the kernel then translates into a procedure call to the appropriate driver. The driver then starts the I/O and sits in a tight loop continuously polling the device to see if it is done (usually there is some bit that indicates that the device is still busy). When the I/O has completed, the driver puts the data (if any) where they are needed and returns. The operating system then returns control to the caller.
    Disadvantage: always polling until IO is finished
  • Interrupt based: The CPU issues commands to the I/O module then proceeds with its normal work until interrupted by I/O device on completion of its work. When the controller detects the end of transfer, it generates a interrupt to signal completion
  • Direct memory access (using DMA chip): Direct Memory Access, a special way

Questions and Solutions

  • What is multi-programing?
  • Multiprogramming is the rapid switching of CPU between multiple processes in the memory. It is commonly used to keep the CPU busy while one or more processes are doing I/O.
  • What is a trap instruction?
  • A trap instruction switches the execution mode of a CPU from the user mode to the kernel mode. This instruction allows a user program to invoke functions in the operating system kernel.
  • What is the difference between a trap and a interrupt?
  • A trap is caused by the program and is synchronous with it. If the program is run again and again, the trap will always occur at exactly the same position in the instruction stream. An interrupt is caused by an external event and its timing is not reproducible.

评论

发表评论

此博客中的热门博文

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