TeaPort

Scheduling: Introduction Workload Assumptions A number of simplifying simplifying assumptions about the process running in the system, sometimes collectively called the workload. We will make the following assumptions about the processes, sometimes called jobs, that are running in the system: Each job runs for the same amount of time. All jobs arrive at the same time. Once started, each job runs to completion. All jobs only use the CPU. The run-time of each job is known. Scheduling Metrics Tur ...

Mechanism: Limited Direct Execution A few challenges: Performance Control Basic Technique: Limited Direct Execution OS: Create entry for process list. Allocate memory for program. Load program into memory. Set up stack with argc/argv. Clear registers. Execute call main(). Program: Run main(). Execute return from main. OS: Free memory of process. Remove from process list. Problem #1: Restricted Operations What if the process wishes to perform some kind of restricted operation, such a ...

Interlude: Process API The fork System Call 123456789101112131415161718192021#include <stdio.h>#include <stdlib.h>#include <unistd.h>int main(int argc, char *argvp[]) { printf("hello world (pid:%d)\n", (int) getpid()); int rc = fork(); if (rc < 0) { // fork failed fprintf(stderr, "fork failed\n"); exit(1); } else if (rc == 0) { // child (new process) printf("hello, I am child (pid:%d)", (int) getpid());  ...

Operating Systems: Three Easy Pieces The Abstraction: The Process One of the most fundamental abstractions that the OS provides to users: the process (a running program). The OS creates the illusion of nearly-endless supply of CPUs by virtualizing the CPU. The basic technique, known as time sharing （分时） of the CPU, allows users to run many concurrent processes. To implement virtualization of the CPU, and to implement it well, the OS will need both some low-level machinery and some high-level i ...

Introduction Computer Systems: Three Easy Pieces Virtualization: the OS takes a physical resource and transforms it into a more general, powerful, and easy-to-use virtual form of itself. Thus, the OS is sometimes referred to as a virtual machine. A typical OS exports a few hundred system calls that are available to applications. The OS provides a standard library to applications. The OS is sometimes known as a resource manager for CPU, memory, and disk. Virtualizing 123456789101112131415161718 ...

Seeing is believing. It used to be such a universally acknowledged viewpoint that almost all languages, eastern or western, possess similar expressions. Throughout history, this common idea has guided us and encouraged our ancestors to seek the truth, and, to some extent, it also leads to the advent of experimental science and other branches of scientific knowledge. With a deeper understanding of the world we live, people begin to doubt and challenge this proverb. Given the interest in, debate o ...

There is an intriguing fact in this age: when people turn on the television or their mobile phones, they frequently find out that there is abundant shocking news concerning celebrities. Most of them uncovers appalling dark sides of these people who seemed to be perfect and admirable in the past. It seems that no one is innocent under media scrutiny and it is only a matter of fact before some negative evidence appears. How do we interpret this phenomenon? Two main factors contribute to this fact. ...

When compiling, computer needs to manage variables: Inserting (new variables) Searching (references of variables) Dynamic Searching Problems Two main problems about Hashing: Calculating positions: creating a hashing function to locate the keyword Dealing with Collisions Hashing Table Name: SymbolTable Data Object Set: Name-Attribute Operation Set: 123456SymbolTable InitializeTable(int TableSize);bool IsIn(SymbolTable Table, NameType Name);AttributeType Find(SymbolTable Table, NameType Name); ...

Quick Sort Divide and Conquer Choosing the Principal Component Remark: rand() is not very efficient! One common approach is to use the median number at the head, tail and center of the array: 1234567891011ElementType Median3(ElementType A[], int Left, int Right) { int Center = (Left + Right) / 2; if (A[Left > A[Center]]) Swap(&A[Left], &A[Center]); if (A[Left] > A[Rihgt]) Swap(&A[Left], &A[Right]); if (A[Center] > A[Right]) Swap(&A[ ...

Lower Bound of Time Complexity Inversion For index i and j, if A[i] > A[j] then (i, j) is an inversion. For insertion sort: T(N,I)=O(N+I)T(N, I)=O(N+I) T(N,I)=O(N+I) Theorem A: For N different elements, the average number of inversions are I=N(N−1)/4I=N(N-1)/4 I=N(N−1)/4 Theorem B: For any algorithm which only swaps the adjacent 2 elements, the average time complexity is: From B we know that if we want to make our algorithms more efficient, we should eliminate more than one inversions each ti ...