系统级编程

Bit Operation / 位运算

isNonNegative

1
2
3
4
5
6
7
8
// return 1 if x >= 0, return 0 otherwise
// Example: isNonNegative(-1) = 0; isNonNegative(0) = 1;
// Legal ops:! ~ & ^ | + << >>
// Max ops:6

int isNonNegative(int x) {
    return !(x>>31);
}

isEqual

1
2
3
4
5
6
7
8
// return 1 if x == y, return 0 otherwise
// Example: isEqual(5,5) = 1; isEqual(4,5) = 0;
// Legal ops:! ~ & ^ | + << >>
// Max ops:5

int isNonNegative(int x) {
    return !(x^y);
}

SetByte

1
2
3
4
5
6
7
8
9
10
11
/*
* SetByte - Set byte n from word x to 0xFF
* Bytes numbered from 0 (LSB) to 3 (MSB)
* Examples: SetByte(0x12345678,1) = 0x1234FF78 
* Legal ops:! ~ & | << >>
* Max ops: 6
*/

int SetByte (int x,int n) {
    return 0xFF << (n << 3) | x;
}

NegativeNum

1
2
3
4
5
6
7
8
9
10
/* 
* NegativeNum using only ~ and & , ignore 0
* Example: NegativeNum(-5) retrun -5 , NegativeNum(5) retrun -5, Negative(0) can return any value
* Legal ops: ~ &
* Max ops: 8 
*/

int NegativeNum (int x){

}

tMIN

1
2
3
4
5
6
7
8
/*
* tMIN - Returns the minimum two's complement integer * Bytes numbered from 0 (LSB) to 3 (MSB)
* Legal ops:! ~ & ^ | + << >>
* Max ops: 4
*/
int tMIN() {
    return 0x1<<31;
}

CountNoneZeroByte

1
2
3
4
5
6
7
8
9
10
11
/*
* CountNoneZeroByte - Returns the number of none zero byte in integer x * For example: x= 0xff000001, CountNoneZeroByte(x) will return 2

* Bytes numbered from 0 (LSB) to 3 (MSB) 
* Legalops:! ~ & ^ | + << >>
* Max ops:20
*/

int CountNoneZeroByte(int x){
    return !(x & 0xFF) + !(x>>8 & 0xFF) + !(x>>16 & 0xFF) + !(x>>24 & 0xFF);
}

getByte

1
2
3
4
5
6
7
8
9
/*
* getByte - Extract byte n from word x
* Bytes numbered from 0 (LSB) to 3 (MSB) * Examples: getByte(0x12345678,1) = 0x56 
* Legal ops:! ~ & ^ | + << >>
* Maxops:6
*/
int getByte(int x, int n) {
    return x >> (n << 3) & 0xFF;
}

negate

1
2
3
4
5
6
7
8
// return -x
// Example: negate(1) = -1
// Legal ops:! ~ & ^ | + << >>
// Max ops:5

int negate(int x) {
    return ~x + 1;
}

isPositive

1
2
3
4
5
6
7
8
// return 1 if x > 0, return 0 otherwise
// Example: isPositive(-1) = 0
// Legal ops:! ~ & ^ | + << >>
// Max ops:8

int isPositive(int x) {
    return !(x >> 31) & !(!x);
}

shiftsAreArithmetic

逻辑右移：补0

算术右移：如果符号位为1则补1，符号位为0则补0

1
2
3
4
5
6
7
8
9
/*
* shiftsAreArithmetic()
* Function returns 1 when run on a machine that uses arithmetic right shifts for int’s, and 0 otherwise.
* Max ops: 8
*/

int shiftsAreArithmetic() {
    return (-1 >> 31) & 1;
}

isEven

1
2
3
4
5
6
7
8
9
/*
* isEven - tests whether a number is even
* Examples: isEven(2) = true isEven(3) = false
* Legal ops:! ~ & ^ | + << >>
* Max ops:5
*/
bool isEven(int x) {
    return !(0x1 & x);
}

copyMSB

1
2
3
4
5
6
7
8
9
/*
* isEven - set all bits of result to most significant bit of x
* Examples: copyMSB(0x80000000) = 0xFFFFFFFF, copyMSB(0x70000000) = 0x00000000
* Legal ops:! ~ & ^ | + << >>
* Max ops:5
*/
int copyMSB(int x) {
    return x >> 31;
}

leastBitPos

1
2
3
4
5
6
7
8
9
10
/*
* leastBitPos - return a mark that marks the position of the least significant 1 bit. if x == 0, return 0
* example: leastBitPos(96) = 20
* legal ops:! ~ & ^ | + << >>
* max ops:6
*/

int leastBitPos(int x){
    return x & ((~x) + 1);
}

Exception/异常

异常类型

异步异常

  • 中断(Interrupt)：I/O设备的信号
    • 计时器中断
    • I/O中断

同步异常

流控：在计算机执行指令的过程中，从一个指令跳转到下一个指令的过程。

Caused by events that occur as a result of executing an instruction

异常：异常是控制流的突变，用来响应处理器状态中的某些变化。

  • 陷阱(Trap)：策划的异常
    • 系统调用
    • 断点
  • 故障(Fault)：潜在的可恢复错误
    • 分页故障
    • 保护故障
    • 浮点数异常
  • 终止(Abolt)：不可恢复错误
    • 不合法指令
    • ECC内存确认

异常与操作系统的关系

异常提供了基本的构建块，为操作系统提供进程的概念。

GC 伪代码 / 描述

什么是垃圾收集

垃圾收集就是在可分配内存空间不够时，检测并回收那些垃圾内存块，使得这些内存单元能够被重新使用。

mark/sweep 伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
void GC(){
    HaltAllProcessing();
    ObjectCollection roots = GetRoots();
    for(int i = 0;i < roots.getCounts(); ++i){
        mark(root[i]);
    }
    sweep();
}

void mark(ptr p){
    if((b = isPtr(p)) == NULL){
        return;
    }
    if(blockMarked(b)){
        return;
    }

    markBlock(b);
    len = length(b);
    for(int i = 0;i < len;i++){
        mark(b[i]); // 深度优先搜索
    }
    return;
}

void sweep(ptr b, ptr end){
    while(b < end){
        if(blockMarked(b)){
            unmarkBlock(b);
        } else if(blockAllocated(b)){
            free(b);
        }
        b = nextBlock(b);
    }

    return;
}

Copying Collection / 复制法

维护两个堆，一个是正在使用的，一个是垃圾回收时使用的，在没空间时，将正在使用的堆上可以到达的内存块，都复制到另一个堆上，然后清空正在使用的堆，转换角色。

优点：比标记清除法更快，因为只遍历了一遍堆空间。

缺点：1. 只能使用一半的堆空间。2. 和标记清除一样有不可预测的周期性中断。

Reference counting / 引用计数法

  • 保持对每个对象的指针数量的跟踪，即引用数。
  • 当引用数为0时，对象变为不可达到的垃圾。

优点：动态和增量的方式，当有赋值或其他堆操作时进行。

缺点：1. 引用计数的花费。2. 不能解决循环结构。

Generation Garbage Collection / 分代式垃圾回收法

通过经验观察： 频繁扫描新对象，不频繁扫描旧对象。

优点：无需遍历整棵引用树。