1.信号

信号是软件中断，提供了一种处理异步事件的方法

unix信号机制最简单的接口是signal函数

/*
 * sign  信号整型
 * func  函数指针
 * return ：函数指针(一个函数地址，函数有一个整型参数，无返回值)
 */
void (* signal(int sign,void (*func)(int))) (int)
  
// 其他的表达方式
typedef void signfunc(int);
signfunc *signal(int ,signfunc);

typedef void (*sighandler_t)(int);
sighandler_t signal(int signum,sighandler_t handler);

• 信号：更高层的软件形式的异常

知识拓展:

异常控制流

现代控制系统通过使控制流发生突变来对情况做出反应，我们把这些突变称为异常控制流ECF

(Exceptional Control Flow)。

• 硬件层，硬件检测到的时间会触发控制突然转移到异常处理程序
• 操作系统层，内核通过上下文切换将控制从一个进程转移到另一个进程
• 应用层，一个进程可以发送信号到另一个进程，接受者会将控制突然转移到它的一个信号处理程序

异常(exception)就是控制流的突变

硬件触发异常，通过异常处理表转移到异常处理程序，剩下的工作就是异常处理程序在软件中完成

异常的类别：

• 中断(interrupt)
• 陷阱(trap)
• 故障(fault)
• 终止（abort）

中断

中断是来自io设备的信号，是异步发生的

I/O设备（网络适配器，磁盘控制器，定时器芯片）通过相处理器芯片的一个引脚发信号，并将信号发到系统总线上，来触发中断，这个异常号标识了引起中断的设备

陷阱

陷阱是有意的异常

陷阱处理程序将控制返回到下一条指令

可以在用户程序和内核之间提供一个像过程一样的接口（system call）系统调用

故障

故障是由错误情况引起的，可能能够被故障处理程序修正

缺页异常

终止

终止时不可恢复的致命错误造成的结果

并发流

一个逻辑流的执行在时间上与另一个流重叠，称为并发流(concurrent flow)

多个流并发地执行的一般现象称为并发(concurrency)

一个进程和其他进程轮流运行的概念称为多任务(multitasking)

并行流是并发流的一个真子集，如果两个流并发地运行在不同的处理器内核或者计算机上，那我们称他们为并行流(parallel flow)

2.strstr()函数

 #include <string.h>

char *
strstr(const char *haystack, const char *needle);
// locate a subtring in string
//比喻大海捞针

3.Redis 编码格式

redis外部数据结构

redis的对象系统

• 字符串 string
• 集合 set
• 有序集合 zset
• 哈希 hash
• 列表 list

redis内部实现数据结构

// 对象编码
#define REDIS_ENCODING_RAW 0     /* Raw representation */
#define REDIS_ENCODING_INT 1     /* Encoded as integer */
#define REDIS_ENCODING_HT 2      /* Encoded as hash table */
#define REDIS_ENCODING_ZIPMAP 3  /* Encoded as zipmap */
#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
#define REDIS_ENCODING_INTSET 6  /* Encoded as intset */
#define REDIS_ENCODING_SKIPLIST 7  /* Encoded as skiplist */
#define REDIS_ENCODING_EMBSTR 8  /* Embedded sds string encoding */

1.t_string

REDIS_STRING编码类型

• REDIS_ENCODING_INT ,整数值实现的字符串对象
• REDIS_ENCODING_RAW，简单动态字符串实现的字符串对象
• REDIS_ENCODING_EMBSTR，embstr编码的简单动态字符串实现的字符串对象

embstr编码的字符串对象所有数据都保存在一块连续的内存中

object.c中实现

robj *tryObjectEncoding(robj *o) {
    long value;
    sds s = o->ptr;
    size_t len;
    // 只在字符串的编码为 RAW 或者 EMBSTR 时尝试进行编码
    if (!sdsEncodedObject(o)) return o;
    // 不对共享对象进行编码
    if (o->refcount > 1) return o;
    // 对字符串进行检查
    // 只对长度小于或等于 21 字节，并且可以被解释为整数的字符串进行编码
    len = sdslen(s);
    if (len <= 21 && string2l(s,len,&value)) {
        /* This object is encodable as a long. Try to use a shared object.
         * Note that we avoid using shared integers when maxmemory is used
         * because every object needs to have a private LRU field for the LRU
         * algorithm to work well. */
        if (server.maxmemory == 0 &&
            value >= 0 &&
            value < REDIS_SHARED_INTEGERS)
        {
            decrRefCount(o);
            incrRefCount(shared.integers[value]);
            return shared.integers[value];
        } else {
            if (o->encoding == REDIS_ENCODING_RAW) sdsfree(o->ptr);
            o->encoding = REDIS_ENCODING_INT;
            o->ptr = (void*) value;
            return o;
        }
    }
    // 尝试将 RAW 编码的字符串编码为 EMBSTR 编码
    if (len <= REDIS_ENCODING_EMBSTR_SIZE_LIMIT) {
        robj *emb;
        if (o->encoding == REDIS_ENCODING_EMBSTR) return o;
        emb = createEmbeddedStringObject(s,sdslen(s));
        decrRefCount(o);
        return emb;
    }
    // 这个对象没办法进行编码，尝试从 SDS 中移除所有空余空间
    if (o->encoding == REDIS_ENCODING_RAW &&
        sdsavail(s) > len/10)
    {
        o->ptr = sdsRemoveFreeSpace(o->ptr);
    }
    /* Return the original object. */
    return o;
}

t_list

编码方式

• REDIS_ENCODING_ZIPLIST
• REDIS_ENCODING_LINKEDLIST

/* Check if the length exceeds the ziplist length threshold. */
// 查看插入之后是否需要将编码转换为双端链表
if (subject->encoding == REDIS_ENCODING_ZIPLIST &&
    ziplistLen(subject->ptr) > server.list_max_ziplist_entries)
      listTypeConvert(subject,REDIS_ENCODING_LINKEDLIST);

t_hash

编码方式

• REDIS_ENCODING_ZIPLIST
• REDIS_ENCODING_HT

void hashTypeTryConversion(robj *o, robj **argv, int start, int end) {
    int i;
    // 如果对象不是 ziplist 编码，那么直接返回
    if (o->encoding != REDIS_ENCODING_ZIPLIST) return;

    // 检查所有输入对象，看它们的字符串值是否超过了指定长度
    for (i = start; i <= end; i++) {
        if (sdsEncodedObject(argv[i]) &&
            sdslen(argv[i]->ptr) > server.hash_max_ziplist_value)
        {
            // 将对象的编码转换成 REDIS_ENCODING_HT
            hashTypeConvert(o, REDIS_ENCODING_HT);
            break;
        }
    }
}

t_set

编码方式

• REDIS_ENCODING_INSET
• REDIS_ENCODING_HT

void setTypeConvert(robj *setobj, int enc) {

    setTypeIterator *si;

    // 确认类型和编码正确
    redisAssertWithInfo(NULL,setobj,setobj->type == REDIS_SET &&
                             setobj->encoding == REDIS_ENCODING_INTSET);

    if (enc == REDIS_ENCODING_HT) {
        int64_t intele;
        // 创建新字典
        dict *d = dictCreate(&setDictType,NULL);
        robj *element;

        /* Presize the dict to avoid rehashing */
        // 预先扩展空间
        dictExpand(d,intsetLen(setobj->ptr));

        /* To add the elements we extract integers and create redis objects */
        // 遍历集合，并将元素添加到字典中
        si = setTypeInitIterator(setobj);
        while (setTypeNext(si,NULL,&intele) != -1) {
            element = createStringObjectFromLongLong(intele);
            redisAssertWithInfo(NULL,element,dictAdd(d,element,NULL) == DICT_OK);
        }
        setTypeReleaseIterator(si);

        // 更新集合的编码
        setobj->encoding = REDIS_ENCODING_HT;
        zfree(setobj->ptr);
        // 更新集合的值对象
        setobj->ptr = d;
    } else {
        redisPanic("Unsupported set conversion");
    }
}

t_zset

编码方式

• REDIS_ENCODING_ZIPLIST
• REDIS_ENCODING_SKIPLIST

4.欧几里得算法(辗转相处法)

欧几里得算法:

• 求最大公约数的算法
• 算法的核心思想：两个数的最大公约数等于较小的数和两数相除余数的最大公约数

应用：

• 判断两个数组成的分数是否最简，即最大公约数是否为1

// pseudocode
function gcd(a,b):
	     while b!= 0:
            t = b
            b = a % b
            a = t
        return a

递归形式

public int gcd(a,b){
     return b != 0? gcd(b,a%b): a;
}

• 拓展

计算两个数的最大公约数的另一种方法

更相减损法

//pseudocode
function gcd(a,b):
		 while true:
          if a> b:  a-=b
          else if a < b: b -=a
          else  return a

5.语法问题

c++中全局阈，只能声明、初始化变量

不能用于赋值、运算和调用函数等

关于初始化及赋值

• 程序中的变量可以声明多次，但只能定义一次
• 只有当声明变量也是定义的时候，声明才有初始化式（只有定义才分配存储空间，初始化必须要有存储空间来初始化）
• 声明+初始化式 就是 定义
• 赋值是一种运算，赋值等号是从右到左的运算符，对于全局变量，不能用于运算

多余传参编译警告问题

函数传入参数未使用，编译会包报warning警告

参考redis代码中的解决方案

How to anti-warning

// define a marco
#define REDIS_NOTUSED(V)  ((void) V)

// function
int function(int arg){
  
  REDIS_NOTUSED(arg);
  
  printf("fucntion\n");
}

6. 受限指针

受限指针，一般出现在指针的声明中

int * restrict p;

如果指针p指向的对象在之后需要修改，那么该对象不会允许通过除指针p之外的任何方式访问

对程序有高性能要求才会添加

7.Python(zip,yield)

zip( iterables)*

生成一个迭代器重新组合可迭代元素

matrix是一个二维矩阵

zip(*matrix) ，返回一个matrix矩阵每列的元素

# zip()
# Make an iterator that aggregates elements from each of the iterables.
def zip(*iterables):
    # zip('ABCD', 'xy') --> Ax By
    sentinel = object()
    iterators = [iter(it) for it in iterables]
    while iterators:
        result = []
        for it in iterators:
            elem = next(it, sentinel)
            if elem is sentinel:
                return
            result.append(elem)
        yield tuple(result)

>>> x = [1, 2, 3]
>>> y = [4, 5, 6]
>>> zipped = zip(x, y)
>>> list(zipped)
[(1, 4), (2, 5), (3, 6)]
>>> x2, y2 = zip(*zip(x, y))
>>> x == list(x2) and y == list(y2)
True

yield

Delegating to a subgenerator

Allowing a generator to delegate part of its operations to another genrator

8.线程

线程通过pthread_create函数来创建其他线程

#include <pthread.h>

int
pthread_create(pthread_t *thread, const pthread_attr_t *attr,
         void *(*start_routine)(void *), void *arg);

成功返回，新创建线程id会设置成thread指向的内存单元；

新建的线程会从start_routine(线程例程)函数地址开始运行;

互斥量 & 条件变量

• 互斥量mutex，本质上来说就是一把锁，在访问共享资源critical seciton对互斥量进行设置(加锁)

• 条件变量，是线程可用的另一种同步机制，条件变量给多个线程提供了一个会和的场所

条件变量+互斥量 一起使用，允许线程以无竞争的方式等待特定条件的发生

条件变量是由互斥量保护，线程在改变条件状态之前必须先锁住互斥量

#include <pthread.h>
int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex);

• 1.传递给pthread_cond_wait的互斥量mutex对条件进行保护
• 2.调用者把锁住的互斥量传递给函数
• 3.函数将调用者放到等待条件的的线程列表上，对互斥量进行解锁
• 4.函数返回后，互斥量再次被锁住

9.fcntl sync

#include <fcntl.h>
// file control
int fcntl(int fildes, int cmd, ...);

改变已经打开文件的属性

Manipulate file descriptor

NAME
     sync -- force completion of pending disk writes (flush cache)

unix 系统实现在内核中设有缓冲区高速缓存或页高速缓存

大多数磁盘io都通过缓冲区进行

向文件中写入数据（delayed write）

• 1.内核copy到缓冲区(排队队列)
• 2.缓冲区到磁盘

当需要重用缓冲区来存放其他磁盘数据，需要执行2步骤(flush)

Sync,fsync主要是用来保证磁盘上实际文件系统与缓冲区内容一致性

10.文件共享

unix系统支持在不同进程间共享打开文件

内核用于所有I/O的数据结构

使用是3种数据结构表示打开的文件

• 进程表项
• 文件表项
• v节点表项

注意区分 文件描述符 FD

文件状态标志 FL

两个文件描述符指向同一文件表项，所以共享同一文件状态标志

文件重定向

digit1 > &digit2

表示要将描述符digit1 重定向到描述符digits2的同一文件

./a.out > outfile  2 > &1
# 标准输出到outfile
# 执行dup将标准输出复制到描述符2(标准错误)上
# 1，2 指向同一文件表项

./a.out  2 > &1  > outfile
# 描述符2 成为终端
# 标准输出重定向到outfile
# 描述符1 指向 outifle 文件表项
# 描述符2 指向 终端 的文件表项

11. IO函数

io函数都是围绕文件描述符

标准io库都是围绕流(stream)

标准io函数fopen，返回一个指向FILE对象的指针

12.编译与链接

// .o 可重定位目标文件
gcc -v   // 可以显示版本

// 标准指令
gcc - Og -o prog main.c sum.c

// 指令拆解
// 1.预处理器 cpp
cpp [other arguments] main.c /tmp/main.i
main.c   -> mian.i  // ascii码的中间文件
// 2.c编译器  ccl
ccl /tmp/mian.i  -Og [other arguments] -o /tmp/main.s   // ascii码的汇编语言文件
// 3.汇编器 as
as [other arguments] -o /tmp/main.o /tmp/mian.s
// main.o  可重定位目标文件
  
// 4.链接器
ld -o prog [system objects files and args] /tmp/mian.o /tmp/sum.o

// 5.运行

>./prog
# shell调用os中一个叫做加载器loader的函数，将可执行文件prog中代码和数据复制到内存
# 并将控制转移到程序的开头

程序执行的流程

内核执行c程序时，使用一个exec()函数

• 1.c程序总是从main函数开始执行
• 2.内核在调用main函数之前，先调用一个特殊的启动例程
• 3.可执行程序文件将此启动例程指定为程序的起始地址
• 4.启动例程从内核取得命令行参数和环境变量值

如果目标文件是由c代码编译生成的，用gcc做链接就可以，整个程序的入口点是ctr1.o中提供的 _start;
它首先做一些初始化工作（以下成为启动例程 startup routine）, 然后调用c代码中提供的main函数；
真正正确的描述_start才函数真正的入口点，main函数是_start调用的
/usr/lib/gcc/i486-linux-gun/4.3.2/../../../../lib/ctr1.0a

13.原型设计模式

原型prototype，对象创建型设计模式

• abstract factory 抽象工厂模式，动态配置产生 原型模式
• 抽象工厂模式，单个实例，产生单例模式

在spring框架的bean工厂 beanfactory有较多的应用

14.动态语言vs静态语言

动态语言：动态语言也叫弱类型语言，运行时才确定数据类型语言(js，python)

静态语言：静态语言也叫强类型语言，编译时变量数据类型就可以确定（java,c/c++）