剑指offer

按牛客网的顺序。

二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
  bool Find(int target, vector<vector<int> > array) {
    if(array.empty() || array[0].empty() || array[0][0] > target) 
      return false;
    int n = array.size(), m = array[0].size();
    int i = 0, j = m-1;
    while(i < n && j >= 0) {
      if(array[i][j] == target) 
        return true;
      else if(array[i][j] < target) 
        ++i;
      else 
        --j;
    }
    return false; 
  }
};

epoll

内部监听的事件以epitem组织为一个红黑树

注册和事件添加到epoll的rdlist都是通过调用f_op->poll

注册时是通过将epoll添加到文件的wait_queue_head中

rdlist上的epitem通常是由被监听文件自己挂上去的

data struct

• fs/eventpoll.c
• epoll_create (SYSCALL_DEFINE1(epoll_create) -> do_epoll_create

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
38
39
40
41
42

// 有 strc
struct eventpoll {
  	spinlock_t lock; // 保护对eventpoll的访问
  	struct mutex mtx; // ctl 和 事件收集时用到

    /* Wait queue used by sys_epoll_wait() */
    wait_queue_head_t     wq;
    /* Wait queue used by file->poll() */
    wait_queue_head_t       poll_wait;
	
    struct file *file;
    
    struct list_head rdllist; // 所有 ready 的 fd
	struct rb_root_cached rbr; // 所有 add 进来的 fd -> epitem
    struct epitem *ovflist; // 单项链表存储所有 epitem
};

struct epoll_event {
    __poll_t events;
    __u64 data;
} EPOLL_PACKED;

struct epoll_filefd {
    struct file *file;
    int fd;
} __packed;

struct eppoll_entry {
    struct list_head llink; // 指向 epitem 中的 pwqlist，从而将 epitem 连成链表
    struct epitem *base; // 指向所属的 epitem
    wait_queue_entry_t wait; // 要加入被监听文件的wait_queue的回调函数
    wait_queue_head_t *whead;
};

struct epitem {
	struct eventpoll *ep; // 指向所属的 eventpoll
   	/* The file descriptor information this item refers to */
	struct epoll_filefd ffd; // epitem 对应的 struct file 和 fd
    struct list_head fllink; // epitem 中的 struct file 通过这个组织成一个链表
    struct list_head pwqlist; // poll wait queues，指向 epoll_entry 中的 llink
    struct epoll_event event;
};

• 相关的数据结构

  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 38 39 40 41 42 43 44 45 46 47 48

  struct wait_queue_head { spinlock_t lock; struct list_head head; }; typedef struct wait_queue_head wait_queue_head_t; struct mutex { atomic_long_t owner; spinlock_t wait_lock; struct optimistic_spin_queue osq; // 优化 mutex 的性能 struct list_head wait_list; }; /* * Leftmost-cached rbtrees. * * We do not cache the rightmost node based on footprint * size vs number of potential users that could benefit * from O(1) rb_last(). Just not worth it, users that want * this feature can always implement the logic explicitly. * Furthermore, users that want to cache both pointers may * find it a bit asymmetric, but that's ok. */ struct rb_root_cached { struct rb_root rb_root; struct rb_node *rb_leftmost; }; struct file { struct path f_path; struct inode *f_inode; /* cached value */ const struct file_operations *f_op; spinlock_t f_lock; // 对于epollfd指向 struct event_poll void *private_data; #ifdef CONFIG_EPOLL /* Used by fs/eventpoll.c to link all the hooks to this file */ struct list_head f_ep_links; // 所有监听此文件的 epitem 的链表 struct list_head f_tfile_llink; #endif /* #ifdef CONFIG_EPOLL */ // .... }; struct callback_head { struct callback_head *next; void (*func)(struct callback_head *head); } __attribute__((aligned(sizeof(void *)))); #define rcu_head callback_head

1. Course

• MIT 6.828
• ustc os
• ustc linux操作系统分析
• stanford cs240
• cmu 15410

2. 系统启动

现代计算机使用UEFI，可以一次加载超过512B的boot sector。

以下为JOS启动流程。

• 计算机通电后先读取BIOS，加载到960KB~1MB地址出。
• BIOS进行硬件自检，同时打印硬件信息在屏幕上。有问题蜂鸣器会响。
• 之后计算机读取BIOS设置好的优先级最高的外部存储设备。读取第一个扇区（512字节，即主引导记录MBR）到0x7c00处。如果这个扇区最后两个字节是0x55和0XAA表明可以启动，否则不能。
• 主引导记录即boot.S，其中的主要流程包括：
  • 关中断，开A20线（兼容性问题，寻找范围更大），加载段表(lgdt gdtdesc)（包含操作系统内核的段信息），寻址方式变为segment:offset
  • 设置CR0寄存器的CR0_PE_ON为1：从实模式（16bit寻址）切换到保护模式（32bit寻址）
    • 实模式下寻址方式：物理地址 = 段基址<<4 + 段内偏移，早期寄存器是16位，地址线是20位，只能访问1MB
      • 例如：%cs = xff00，%ax = 0x0110，则物理地址为：0xff00<<4 + 0x0110 = 0xff110
    • 保护模式下寻址方式：segment:offset，segment找到该段的基址base，（检查flags可访问的话）之后直接与offset相加得到线性地址，如果没有分页则线性地址等于物理地址。
      • 程序员看到的是虚拟地址，但指令中出现的是逻辑地址即segment:offset
  • 跳转到保护模式代码段，该段主要执行：
    • 设置各寄存器的值，包括cs指令地址，ds数据段地址，ss栈指针等，jos设置其指向0x7c00
    • call bootmain：即boot/main.c中的代码
• bootmain的主要工作：
  • 将硬盘上的kernel加载到内存里的0x10000处，其中.text段在0x100000处。并执行ELFHDR->e_entry(0x10000C处，boot/entry.S)。内核映像为ELF格式。
    • entry处的代码主要：这是CR3寄存器，开启分页，设置内核堆栈的起始地址（0xf0110000），之后call i386_init

UML类图

类的关系

泛化（generalization）

继承非抽象类，箭头指向父类

实现（realize）

继承抽象类，箭头指向接口

聚合（aggregation）

整体和部分不是强依赖的，B不存在，A仍可存在

组合（composition）

强依赖的，B不存在，A也不存在

一、关键字

1、volatile

• 起源：最早出现于 19 世纪 70 年代，被用于处理 memory-mapeed I/O (MMIO)带来的问题。

  1 2 3 4 5 6 7 8

  unsigned int *p = GetMagicAddress(); // 可能不是内存地址而是I/O设备地址 unsigned int a, b; a = *p; //（1）读I/O设备第一个int b = *p; //（2）读I/O设备第二个int *p = a; //（3）写入I/O设备第一个int *p = b; //（4）写入I/O设备第二个int // (1)和(2) 的乱序或直接将 b = a 会造成问题 // (3)和(4) 可能被编译器优化消除掉，无意义的赋值

• 作用：

  • 易变性：让编译器每次操作该变量时一定要从内存中真正取出，而不是使用已经存在寄存器中的值

  1 2	a = f(c); b = a + 1; // 此时可能会直接拿 rax 寄存器中的值。gcc 4.1会，8.1不会，加volatile关键字则都不会

  • 不可优化：即使是无用的常量也不会被优化消除掉，加-O2也不会
  • 顺序性：gcc的优化仅保证一段程序的输出，在优化前后无变化。可能会改变前后两行变量的赋值顺序。
    • volatile变量与非volatile变量间的赋值顺序也可能被调换，JAVA不会。
    • volatile变量间的赋值顺序不会被调换
    • volatile仅保证编译器不会乱序，不保证CPU乱序

• 使用场景：

  • 内嵌汇编操纵栈可能会导致出现编译无法识别的变量改变；
  • 更多的可能是多线程并发访问共享变量时，一个线程改变了变量的值，怎样让改变后的值对其它线程 visible；
  • 中断服务程序中修改的供其它程序检测的变量需要加volatile；
  • 多任务环境下各任务间共享的标志应该加volatile；
  • 存储器映射的硬件寄存器通常也要加volatile说明，因为每次对它的读写都可能由不同意义；

优化器

BuildParseTree

• libpg_query：裁剪出的postgresql的语法解析和词法解析。

• BuildParseTree：对parser生成的语法树进行解析，得到SelectStatement，其中记录了语句的各个组件。

  1 2 3 4 5 6 7 8 9 10 11

  class SelectStatement : public SQLStatement { std::unique_ptr<TableRef> from_table; bool select_distinct; std::vector<std::unique_ptr<expression::AbstractExpression>> select_list; std::unique_ptr<expression::AbstractExpression> where_clause; std::unique_ptr<GroupByDescription> group_by; std::unique_ptr<SelectStatement> union_select; std::unique_ptr<OrderDescription> order; std::unique_ptr<LimitDescription> limit; };

Workflow scheduling in cloud: a survey

Modeling and definition

static workflow scheduling

1. Task selection Select the first task from the scheduling list;
2. Resource selection Allocate the task to selected resource.

List scheduling heuristic

static: priorities are constructed before any task allocation
dynamic: the priorities of unscheduled tasks are recomputed after each task scheduling step

Usage

1
2
3
4
5
6
7
8
9

cd tpch/dbgen
cp makefile.suite Makefile
# modify the Makefile
#  CC = gcc
#  DATABASE = ORACLE
#  MACHINE = LINUX
make
./dbgen -h
./dbgen -vf -s 1

• for postgresql

  1	find -name "*.tbl" | xargs sed -i "s/|$//"

前言

• 只摘录关键知识点，不做详细笔记，仅为方便日后复习有个方向
• 学习: 如果一个系统能够通过执行某个过程改进它的性能，这就是学习。 — Herbert A. Simon

1.统计学习

• 统计学习的特点，对象，目的，方法，研究
• 本章主要将监督学习

监督学习

• 从给定有限的训练数据出发, 假定数据是独立同分布的, 而且假设模型属于某个假设空间, 应用某一评价准则, 从假设空间中选取一个最优的模型, 使它对已给训练数据及未知测试数据再给定评价标准意义下有最准确的预测.
• 基本概念：input space, output space, feature space
• 其它名词：instance, feature vector, 联合概率分布
• 假设空间: $ \mathcal{F} = \{ f\;| \mathit{Y} = f(X) \} $
• 最终变成求 $\min\limits_{f\in\mathcal{F}}R_{emp}(f)$ 或 $min_{f\in\mathcal{F}}R_{srm}(f)$ 的问题

介绍

• 以往数据库调优是 DBA 在问题发生后进行调整，self-driving （自治）数据库不仅优化当前工作负载，还可以预测以后的负载情况，从而事先做好准备，并且可以为现代高性能数据库提供更多复杂的新的优化方案。Peloton 通过深度学习实现了self-driving。
• 现存的自动调优技术例如：Self-Tuning 物理数据库技术，自动选择索引、自动对表分区存储、自动创建和更新物化视图。自动选择底层存储方式（H2O， 2014），自动设置数据库配置参数，拷贝并及时更新所需索引的DataBase Cracking 技术，云数据库动态资源配置等等。但以上都只用于解决单一的问题，没有从全局考虑，而且 DBA 不一定能了解那么多方面去修复或优化一个系统，而且无法预测未来的负载从而提前做出决策。

问题概述

• 了解应用的工作负载，HTAP（hybrid transaction analytical processing）可能执行事务和查询的时间几乎是同时的，所以不能用为 OLAP 和 OLTP 分别创建一个数据库的方法。HTAP 可自动的选择是使用 OLAP 还是 OLTP 的方式来优化。
• 需要预测资源使用率的趋势。如错开高峰时段进行更新，对即将可能出现的问题提前告警。
• 有了预测能力之后，DBMS 需要为预计的负载情况选择合适的优化方式。Self-driving 不支持需要数据库外部信息（如权限，数据清理和版本控制）的 DBA 任务，支持以下这些操作。对于每一个优化动作，DBMS 不仅需要估计其部署后的开销，还要估计部署它所需要的开销。
  
• 需要确定何时生成及采用相应的优化动作。即需要动态学习和改变，以适应负载的改变。
• 两个额外的限制：代码不能因为上层需求改变而需要重构；它不能依赖于仅支持某些编程环境的程序分析工具。