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