By

原表中有许多维度的细粒度记录,如domain,status,time三者共同作为Key，但是有需要查询所有domain的某时间状态数据，此时由于记录太多，查询速度非常慢，所以有需要将表进行降维，即消除domain维度，将Key变为status+time的二维。

降维

降维的操作可以用到group by和sum.

1
select status, time ... sum (xxx) as xxx from table where (...) group by time, status;

group by会以time+status为id对所有记录进行分类，使用聚合函数sum则可以将同类数据相加，还可按需使用max,min等函数从而达到降维目的。

Read More

By

并发问题中我们需要对一系列的指令进行“原子操作”，但是由于中断和多处理器的存在，这无法保证，因此引入了Lock的概念。我们将critical section用Lock标注包围，从而使之成为原子操作。

比如说要对以下代码进行原子操作

1
balance = balance + 1

以上代码包含三个基本指令：取值、相加、存储，因而有可能中途被打断，我们可以执行如下的操作。

1
2
3
4
5
lock_t mutex; // some globally-allocated lock ’mutex’
...
lock(&mutex);
balance = balance + 1;
unlock(&mutex);

代码中的mutex就是Lock，如果mutex是available，那么就会立即返回线程进入执行被保护代码，如果当前是acquired，那么就会被block一直等待，直到mutex状态变为available。mutex意为mutual exclusive，它也包含其它信息，如当前拥有它的线程，以及预定该Lock的队列等，但对用户并不可见。

1
2
3
4
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&lock); 
balance = balance + 1;
pthread_mutex_unlock(&lock);

Read More

By

前言

Linux system call是kernel入口，通常不会被直接调用，而是由对应的C函数库包装来完成一些必要的步骤（trapping to kernel mode)，同时也使用调用方式与普通库没有什么区别。

一般C包装函数功能如下：

  • 将参数与system call代号copy到kernel指定的寄存器
  • trapping to kernel mode(开始执行）
  • 返回user mode时，如果返回为error number，则设置errno

C函数库也可以会为参数作预处理和返回值的后期处理。

man 2 syscalls可以查看所有的系统调用。

返回值

当出现错误时，大部分system call都会返回一个负值（如 error(3)中定义的三个负值之一），C包装库函数会向调用者隐藏此细节：返回-1并将errno的绝对值copy保存。

成功的system call一般返回0，但也有返回非0值，具体查看对应的manual page.

某些情况下，开发者必须定义一个feature test macro来从头文件（在manual page的SYNOPSYS段中指定）中获取system call的声明，该定义必须在include任何头文件之前。此种情况下，macro在manual中描述。更多关于feature test macro的说明，可以参见 man 7 feature_test_macro。

关于一些衍生UNIX术语与及相关缩写的说明，可以参阅man 7 standards。

Read More

By

Layouts

定义UI中的可视结构，如App和widget可以在XML和java中同时定义，一般来说使用XML定义可以做到界面与控制分离。也可以在XML中定义默认格式，在运行中用java来改变它，这涉及到View和Viewgroup类。一般来说XML的元素与类对应，而XML的属性则与方法对应，名字都相分直观，偶尔稍有差异，如EditText中的text属性对应java中EditText.setText().

编写XML

与HTML十分类似，使用嵌套的方式可以快速定义界面。

每个布局有一个root element，必须是View或者ViewGroup。root element之下可以加入其它layout对象或者widget来构造完整布局。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
              android:layout_width="match_parent"
              android:layout_height="match_parent"
              android:orientation="vertical" >
    <TextView android:id="@+id/text"
              android:layout_width="wrap_content"
              android:layout_height="wrap_content"
              android:text="Hello, I am a TextView" />
    <Button android:id="@+id/button"
            android:layout_width="wrap_content"
            android:layout_height="wrap_content"
            android:text="Hello, I am a Button" />
</LinearLayout>

其中LinearLayout extends ViewGroup，将文件以xml后缀保存到res/layout目录下以编译。

Read More

By

　　刚刚看完了CSAPP的linking一章，试着简单回顾一下。

　　C语言允许将工程分为多个文件单独管理和编译，这对模块化编程是很好地支持。Linking则将多个代码与数据片断连接起来成为一个完整的可很执行程序。

　　需要注意多个文件中定义同名（数据类型可同可不同）全局变量是允许的，只要它们最多只有一个进行了初始化，这其实是一个很容易导致运行时才发现错误的特性，所以有时候可以使用gcc参数-warn-common来提示这些同名的全局变量。

compiler driver

　　假设一个工程包含两个文件swap.c和main.c，我们可以将它们一起编译为一个可执行文件

1
gcc main.c swap.c -o myapp

　　这其中其它包含了预处理、汇编、编译和链接的过程，我们可以将它们分开执行。

1
cpp main.c tmp/main.i

　　如果包含了标准库，一般会生成一个很大的文本文件。

1
2
3
4
5
6
7
8
9
835 extern void funlockfile (FILE *__stream) __attribute__ ((__nothrow__ , __leaf__));
836 # 943 "/usr/include/stdio.h" 3 4
837
838 # 3 "main.c" 2
839
840 void swap();
841
842 int buf[2] = {1, 2};
843 int main(){

　　可以将此预处理后的文件转换为汇编文件。

1
gcc -S main.c

Read More

By

一般常用的page大小是4/8KB,那么一个32位的操作系统，将有1M长度的的分页表，单个表项按4字节计，page table为4MB，而每个进程都需要自己的page table,那么100个进程需要400MB内存，无疑是不小的空间开销，需要想办法压缩。

增大page

这无疑是简洁有效的，增大page会减小page table规模，但是负面效果也是明显的，大的page会导致内存利用率下降internal fragment。

许多系统支持多page size，但是多page size并不是为了减小page table而是为了减轻TLB压力。因为有些程序可以聪明地一次申请足够大的page, 将常用的数据结构放置于同一page下，从而提高内存存取效率。

混合paging & segments

当进程的堆和栈的使用率很低时，占用的内存可能是一个稀疏地址空间。也就是说绝大部分的page对进程都是invalid。此时与其保存所有page，不妨保存进程各数据段实际使用的page。

Read More

By

　　setmentation因为使用动态大小的区块划分会不可避免地带来碎片问题。于是就有了第二种方式，分页。将内存分割了一组固定大小的page frame，每一个frame可包含一个虚拟内存空间中的page。

　　分页的最大优势可能是灵活性，能高效地支持内存地址抽象，不用关心进程如何使用内存。另一个优势则是自由空间的管理。

　　OS维护一个per-process的结构page table，保存着虚拟page映射到物理frame的地址翻译。

地址翻译

　　将虚拟内存地址分割为virtual page number (VPN)和offset两部分。前者代表page号，后者为page内偏移量。通过page table将VPN替换为对应的physical frame number(PFN),从而可以得到真实的物理地址。

　　对于一个真实的32位系统，page大小为4K，那么VPN数量为2^20 = 1MB,假设每个page需要4byte信息，那么每个page table大小为4M, 如果系统中有100个进程，那么光page table就要消耗400MB空间。显然这个大小是不可能置于CPU寄存器的，只能放置在内存中（依然很大）。

Page Table Entry (PTE)

　　最简单的形式就是linear page table,用一人数组来存储，其中下标为VPN，内容为PTE。

Read More

By

　　近日在粗读操作系统相关书籍，接触到的一些知识点说起来在其它类似“微机原理”，“C程序设计”，“UNIX环境高级编程”的书中隐约都有接触，但是没有这么系统，总的来说收获还不错，粗略记录些摘要权当笔记。

内存虚拟化

　　无论是进程与进程之间，还是进程与OS之间的内存，都不应该互相干涉。进程之前内存存在干涉会导致运行错误，而进程干涉OS内存将直接导致系统崩溃等严重后果。
　　所以最好的方式是进行虚拟化，实现隔离，互相给出独立的内存空间，需要做到考虑三点
1、透明。
　　隔离必需对进程透明，进程不需要关系内存地址是否虚拟。保证程序设计的简洁性（无需关心内存类型、起始地址等）。
2、效率。
　　虚拟化不应该消耗太多的时间性能和额外存储空间。
3、安全
　　进程必须不能越界，保证隔离效果。

隔离是一种常用思想，例如理论上microkernels微内核就比monolithic kernel单内核更稳定。是不是想到了kernel pannic :-）

　　实际上只有OS能够访问实际的物理地址，进程使用的全是虚拟地址，也就是我们用C程序打印的指针值，都是虚拟地址。

Read More

By

C没有引用传递

C没有引用！C没有引用！C没有引用！重要的事说3遍。

1
2
3
4
5
//file: refer.c
void swap(int &a,int &b){
}
int main(){}

用C编译器编译：

1
2
3
4
$ cc refer.c
refer.c:1:15: error: expected ‘;’, ‘,’ or ‘)’ before ‘&’ token
 void swap(int &a,int &b){
               ^

C++中才有引用

1
2
$ g++ refer.c
$

很多博文C与C++不分，误导了不少人（例如我）。

Read More

By

Regex in C

　　正则表达式在处理文本方面十分强大，几乎稍微复杂一些的文本操作都会用到，而在python和java中使用regex都十分方便，其实Linux中的C也提供也标准库，使用也不会很复杂。遗憾的是功能较java和python的regex库要少，缺乏替换等功能，需要使用者自己去实现。
　　在Linux下输入man regcomp就可以查看所有与regex相关的函数的说明了,以下是一些关键信息的摘要，如果使用中遇到问题请自行查阅manual。

编译模式

1
int regcomp(regex_t *preg, const char *regex, int cflags);

　　regcomp用来编译文本regex生成匹配规则，执行结果保存在regex_t结构的preg参数中，执行成功时返回0。
　　由于使用java,python较多，下意识地将C函数库与java、python类库比较，C语言中常常使用结构体来实现OOP语言中与对象类似的功能。但是C语言函数调用使用值传递，且结构体与数组的定义形式与普通变量相同，数据都保存在栈中，而不是堆中（java所有的对象和数组都是new操作建立的，保存于堆中），所以常常看到将指针作为参数传入函数，但实际担当的是传递结果的角色。

执行匹配

1
2
int regexec(const regex_t *preg, const char *string, size_t nmatch,
           regmatch_t pmatch[], int eflags);

　　regexec将匹配规则与目标文本进行匹配，并将匹配结果保存在regmatch_t的结构数组pmatch[]中。

Read More