CPU Virtualization-Mechanism(Limited Direct Execution)

该节关于底层的进程切换原理，为后面的schedule章节的底层逻辑

1. Basic technique: Limited Direct Execution

Conception: run the program directly on the CPU

Steps: 1. creates a process entry for it in a process list;

2. allocates some memory for it;

3. loads the program code into memory (from disk);

4. locates its entry point (i.e., the main() routine or something similar), jumps to it, and starts running the user’s code.



Here are 2 problems:

1. If we just run a program, how can the OS make sure the program doesn’t do anything that we don’t want it to do, while still running it efficiently?(安全性/security)

2. When we are running a process, how does the operating system stop it from running and switch to another process, thus implementing the time sharing we require to virtualize the CPU?(进程切换)

2. Problem#1: Restricted Operations

User Mode: code that runs in user mode is restricted in what it can do.

Kernel Mode: code that runs can do what it likes, including privileged operations such as issuing I/O requests and executing all types of restricted instructions.

Modern hardware provides the ability for user programs to perform a system call which allows the kernel to carefully expose certain key pieces of functionality to user programs, such as accessing the file system, creating and destroying processes, communicating with other processes, and allocating more memory.

To execute a system call, a program must execute a special trap instruction. This instruction simultaneously:

1. jumps into the kernel and raises the privilege level to kernel mode; once in the kernel, the system can now perform whatever privileged operations are needed (if allowed), and thus do the required work for the calling process.

2. When finished, the OS calls a special return-from-trap instruction, which, as you might expect, returns into the calling user program while simultaneously reducing the privilege level back to user mode.

Alert: The hardware must make sure to save enough of the caller’s registers in order to be able to return correctly when the OS issues the return-from-trap instruction.

How does the trap know which code to run inside the OS? Clearly, the calling process can’t specify an address to jump to (as you would when making a procedure call); doing so would allow programs to jump anywhere into the kernel.

Trap Table: When the machine boots up, it does so in privileged (kernel) mode, and thus is free to configure machine hardware as need be. One of the first things the OS thus does is to tell the hardware what code to run when certain exceptional events occur. Being able to execute the instruction to tell the hardware where the trap tables are is a very powerful capability. Thus, it is also a privileged operation.

3. Problem#2: Switching Between Processes

A Cooperative Approach: Wait For System Calls

In this style, the OS trusts the processes of the system to behave reasonably. Processes that run for too long are assumed to periodically give up the CPU so that the OS can decide to run some other task. 这种cooperative的方式需要等待一个系统调用（类似yield）或者一个非法操作将当前线程拉起，切换到kernel模式

1. Most processes transfer control of the CPU to the OS quite frequently by making system calls, for example, to open a file and subsequently read it, or to send a message to another machine, or to create a new process. Systems like this often include an explicit yield system call, which does nothing except to transfer control to the OS so it can run other processes.
2. Applications also transfer control to the OS when they do something illegal. For example, if an application divides by zero, or tries to access memory that it shouldn’t be able to access, it will generate a trap to the OS. The OS will then have control of the CPU again (and likely terminate the offending process).

A Non-Cooperative Approach: The OS Tasks Control

前一种方法中，如果进程陷入一个无限循环当中，将无法进行线程切换，现在加入timer interrupt机制：

A timer device can be programmed to raise an interrupt every so many milliseconds; when the interrupt is raised, the currently running process is halted, and a pre-configured interrupt handler in the OS runs. At this point, the OS has regained control of the CPU, and thus can do what it pleases: stop the current process, and start a different one.

As we discussed before with system calls, the OS must inform the hardware of which code to run when the timer interrupt occurs; thus, at boot time, the OS does exactly that. Second, also during the boot sequence, the OS must start the timer, which is of course a privileged operation.

The hardware has some responsibility when an interrupt occurs, in particular to save enough of the state of the program that was running when the interrupt occurred such that a subsequent return-from-trap instruction will be able to resume the running program correctly.

Saving and Restoring Context

无论是cooperative还是non-cooperative的方式，当OS重新取得控制权时，我们需要决定是继续运行当前进程还是切换到另外一个，当我们决定切换到另一个进程时，就需要进行上下文切换(Context Switch)。Context switch: all the OS has to do is save a few register values for the currently-executing process (onto its kernel stack, for example) and restore a few for the soon-to-be-executing process (from its kernel stack). By doing so, the OS thus ensures that when the return-from-trap instruction is finally executed, instead of returning to the process that was running, the system resumes execution of another process. To save the context of the currently-running process, the OS will execute some low-level assembly code to save the general purpose registers, PC, and the kernel stack pointer of the currently-running process, and then restore said registers, PC, and switch to the kernel stack for the soon-to-be-executing process. By switching stacks, the kernel enters the call to the switch code in the context of one process (the one that was in- terrupted) and returns in the context of another (the soon-to-be-executing one). When the OS then finally executes a return-from-trap instruction, the soon-to-be-executing process becomes the currently-running process. And thus the context switch is complete.

4. Worried About Concurrency

We also need to consider the concurrency. This part will be discussed on concurrency.