Welcome to MDGSF's Blog!

This is my github blog

[Linux] 内核学习

2016-04-12

Linux

Linux Kernel C Asm
书籍推荐

Linux内核学习四库全书

http://www.oldlinux.org/

内核源码下载

linux-0.11-060618-gcc4.tar.gz

我们选择使用 linux-0.11-060618-gcc4.tar.gz 这个版本。

编译内核

Linux 环境下编译 0.11版本内核 kernel

tar -zxvf linux-0.11-060618-gcc4.tar.gz

修改 Makefile 里 -mcpu=i386 为 -march=i386

修改 kernel/blk_drv/blk.h 文件第87行将 #elif 修改为 #else

将所有 Makefile 中的CFLAGS后面加上了-fno-stack-protector

Note：记住 make 之前要记得执行 make clean

make

make: as86: Command not finded

出错原因：as86 汇编器未安装

解决办法：

下载dev86-0.16.3-8.i386.rpm安装下载地址 as86

Ubuntu的软件包格式为deb,而RPM格式的包则是Red Hat。解决方法：

首先，我们要安装alien这一软件：
```
$sudo apt-get install alien ##alien默认没有安装，所以首先要安装它

$sudo alien xxxx.rpm  ##将rpm转换为deb,完成后会生成一个xxxx.deb

$sudo dpkg -i xxxx.deb ##这样xxxx软件就可以安装完成了
```
注意，用alien转换deb包并不能保证完全顺利安装，所以如果能找到deb包，还是用deb包为好。

安装完 as86 汇编器之后，重新执行 make
Read All
[C/C++] 程序在内存中的分布

2016-04-11

C/C++

C Bit

在现代的操作系统中，当我们说到内存，往往需要分两部分来讲：物理内存和虚拟内存。从硬件上讲，虚拟空间是CPU内部的寻址空间，位于MMU之前，物理空间是总线上的寻址空间，是经过MMU转换之后的空间。

一般我们所说的程序在内存中的分布指的就是程序在虚拟内存中的存储方式。

从低地址到高地址，可分为下面几段：

预留内存地址（操作系统维护的内存地址，不可访问）

程序代码区（只读，存代码和一些其他的东西）；

data段（存初始化的全局变量和static变量，另外还有文字常量区，常量字符串就是放在这里，程序结束后有系统释放）；

bss段（存未初始化的全局变量和static变量）；

堆（由低地址向高地址增长，一般new和malloc分配，由程序员分配释放）；

共享库文件（调用的库文件，位于堆和栈之间）；

栈（由高地址向低地址增长，和堆的增长方式相对，对不同的OS来说，栈的初始大小有规定，可以修改，目前默认一般为2M，由编译器自动分配释放）；

Note：再上面存的都是操作系统和内核调用的一些内存地址。

如图所示：

Read All
[数组] 最大子数组之和

2016-04-11

Art

C
题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，因此输出为该子数组的和18。

方法一暴力枚举法

时间复杂度 O(n^2)
```
#include <stdio.h>
#include <iostream>
using namespace std;

const int INF = 0x7fffffff;

int iMaxSubArray(int a[], int n, int & left, int & right)
{
    int iMax = -INF;
    int iSum = 0;
    for (int i = 0; i < n; i++) {
        iSum = 0;
        for (int j = i; j < n; j++) {
            iSum += a[j];
            if(iSum > iMax) {
                iMax = iSum;
                left = i;
                right = j;
            }
        }
    }
    return iMax;
}

int main()
{
    printf("%d %d\n", INF, -INF);

    int iLeft = -1;
    int iRight = -1;
    int a[] = {1, -2, 3, 10, -4, 7, 2, -5};
    int iMax = iMaxSubArray(a, 8, iLeft, iRight);
    printf("%d %d %d\n", iMax, iLeft, iRight);
    return 0;
}
```
方法二：分支界定

这里再介绍一种更高效的算法，时间复杂度为O(nlogn)。这是个分治的思想，解决复杂问题我们经常使用的一种思维方法——分而治之。而对于此题，我们把数组A[1..n]分成两个相等大小的块：A[1..n/2]和A[n/2+1..n]，最大的子数组只可能出现在三种情况：
1. A[1..n]的最大子数组和A[1..n/2]最大子数组相同；
2. A[1..n]的最大子数组和A[n/2+1..n]最大子数组相同；
3. A[1..n]的最大子数组跨过A[1..n/2]和A[n/2+1..n]
前两种情况的求法和整体的求法是一样的，因此递归求得。

第三种，我们可以采取的方法也比较简单，沿着第n/2向左搜索，直到左边界，找到最大的和maxleft，以及沿着第n/2+1向右搜索找到最大和maxright，那么总的最大和就是maxleft+maxright。

而数组A的最大子数组和就是这三种情况中最大的一个。

方法三：动态规划

设sum[i]为以第i个元素结尾且和最大的连续子数组。假设对于元素i，所有以它前面的元素结尾的子数组的长度都已经求得，那么以第i个元素结尾且和最大的连续子数组实际上，要么是以第i-1个元素结尾且和最大的连续子数组加上这个元素，要么是只包含第i个元素，即sum[i] = max(sum[i-1] + a[i], a[i])。可以通过判断sum[i-1] + a[i]是否大于a[i]来做选择，而这实际上等价于判断sum[i-1]是否大于0。由于每次运算只需要前一次的结果，因此并不需要像普通的动态规划那样保留之前所有的计算结果，只需要保留上一次的即可，因此算法的时间和空间复杂度都很小。
```
#include <stdio.h>

int iMaxSubArray(int a[], int n)
{
    int iResult = a[0];
    int iSum = a[0];

    for (int i = 1; i < n; i++)
    {
        if(iSum > 0)
            iSum += a[i];
        else
            iSum = a[i];

        if(iSum > iResult)
            iResult = iSum;
    }

    return iResult;
}

int main()
{
    int a[] = {1, -2, 3, 10, -4, 7, 2, -5};
    int iMax = iMaxSubArray(a, 8);
    printf("%d\n", iMax);
    return 0;
}
```
Read All

[链表] 链表反转

2016-04-11

Art

C List

PList pReverseList(PList head)
{
    PList p1 = NULL;
    PList p2 = head;
    PList p3 = NULL;

    while (p2 != NULL)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }

    return p1;
}

Read All

[链表] 如何找到一个链表的中间元素

2016-04-11

Art

C List

设置两个指针fast和slow，slow一次走一下，fast一次走两下，这样当fast走到链表的尾部的时候，slow应该正好走到链表的中间。

PList pGetMidPoint(PList pList)
{
    PList fast = pList;
    PList slow = pList;
    while (fast!=NULL && fast->next!=NULL) {
        fast = fast->next->next;
        slow = slow->next;
    }
    return slow;
}

Read All

[链表] 链表基础算法

2016-04-11

Art

C List
```cpp #include #include using namespace std;

int iAbs(int a) { int i = a » 31; return ((a^i) - i); }

typedef struct _SListNode { int m_iVal; void *m_pData; _SListNode *next; _SListNode() : m_iVal(0), m_pData(NULL), next(NULL) {} _SListNode(int iVal) : m_iVal(iVal), m_pData(NULL), next(NULL) {} }SListNode, *PList;

void vCreateList(PList * ppList) { SListNode * node1 = new SListNode(1); SListNode * node2 = new SListNode(2); SListNode * node3 = new SListNode(3); SListNode * node4 = new SListNode(4); SListNode * node5 = new SListNode(5); SListNode * node6 = new SListNode(6); SListNode * node7 = new SListNode(7);
```
*ppList = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = node6;
node6->next = node7; }
```
void vCreateLoopList(PList * ppList) { SListNode * node1 = new SListNode(1); SListNode * node2 = new SListNode(2); SListNode * node3 = new SListNode(3); SListNode * node4 = new SListNode(4); SListNode * node5 = new SListNode(5); SListNode * node6 = new SListNode(6); SListNode * node7 = new SListNode(7);
```
*ppList = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = node6;
node6->next = node7;
node7->next = node4; }
```
void vCreateIntersectionList(PList * ppList1, PList * ppList2) { SListNode * node1 = new SListNode(1); SListNode * node2 = new SListNode(2); SListNode * node3 = new SListNode(3); SListNode * node4 = new SListNode(4); SListNode * node5 = new SListNode(5); SListNode * node6 = new SListNode(6); SListNode * node7 = new SListNode(7);
```
*ppList1 = node1;
node1->next = node2;
node2->next = node3;
node3->next = node4;
node4->next = node5;
node5->next = node6;
node6->next = node7;

SListNode * node2_1 = new SListNode(1);
SListNode * node2_2 = new SListNode(2);
SListNode * node2_3 = new SListNode(3);
SListNode * node2_4 = new SListNode(4);
*ppList2 = node2_1;
node2_1->next = node2_2;
node2_2->next = node2_3;
node2_3->next = node2_4;
node2_4->next = node4;
```
}

void vPrintList(PList pList) { PList pHead = pList; while (pHead != NULL) { printf(“%d “, pHead->m_iVal); pHead = pHead->next; } printf(“\n”); }

PList pGetMidPoint(PList pList) { PList fast = pList; PList slow = pList; while (fast!=NULL && fast->next!=NULL) { fast = fast->next->next; slow = slow->next; } return slow; }

PList pReverseList(PList head) { PList p1 = NULL; PList p2 = head; PList p3 = NULL;
```
while (p2 != NULL)
{
    p3 = p2->next;
    p2->next = p1;
    p1 = p2;
    p2 = p3;
}

return p1; }
```
/*
- if list has loop, return loop port.
- else return NULL. */ PList FindLoopPort(PList head) { PList fast = head; PList slow = head;
  
  while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; if(slow == fast) { break; } }
  
  if(fast == NULL || fast->next == NULL) { return NULL; }
  
  slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; }
  
  return slow; }
/*
- if head1, head2 has intersection, return intersection point,
- else return NULL. */ PList pFindIntersectionPoint(PList head1, PList head2) { if(NULL == head1 || NULL == head2) { return NULL; }
  
  PList p1 = head1; PList p2 = head2; int iLen1 = 0; int iLen2 = 0; int iDiffLen = 0;
  
  while (p1 != NULL) { iLen1++; p1 = p1->next; } while (p2 != NULL) { iLen2++; p2 = p2->next; }
  
  if(p1 != p2) { //last point is different. return NULL; }
  
  if(iLen1 > iLen2) { p1 = head1; p2 = head2; } else { p1 = head2; p2 = head1; }
  
  iDiffLen = iAbs(iLen1 - iLen2); for (int i = 0; i < iDiffLen; i++) { p1 = p1->next; }
  
  while (p1 != p2) { p1 = p1->next; p2 = p2->next; }
  
  return p1; }
int main() { printf(“list demo\n”);
```
PList pList = NULL;
vCreateList(&pList);
vPrintList(pList);

PList pMid = pGetMidPoint(pList);
printf("mid point: %d\n", pMid->m_iVal);

pList = pReverseList(pList);
vPrintList(pList);

pList = pReverseList(pList);
vPrintList(pList);

PList pLoopPoint = FindLoopPort(pList);
if(pLoopPoint == NULL) {
    printf("list has no loop\n");
}

PList pLoopList = NULL;
vCreateLoopList(&pLoopList);
pLoopPoint = FindLoopPort(pLoopList);
if(pLoopPoint == NULL) {
    printf("pLoopList has no loop\n");
} else {
    printf("pLoopList has loop\n");
}
```
Read All

88/97

Welcome to MDGSF's Blog!

[Linux] 内核学习

书籍推荐

内核源码下载

编译内核

[C/C++] 程序在内存中的分布

如图所示：

[数组] 最大子数组之和

方法一 暴力枚举法

方法二：分支界定

方法三：动态规划

[链表] 链表反转

[链表] 如何找到一个链表的中间元素

[链表] 链表基础算法

方法一暴力枚举法