cf#369 div2

很久没做题了,昨天这场codeforces时间比较早就做了一下。A
A.Bus to Udayland x5233
签到题

#include<stdio.h>
#include<string.h>
char mat[1000+10][5];
int main()
{
    int i,j;
    int n;
    char tmp;
    while(~scanf("%d",&n))
    {
        getchar();
        bool flag=0;
        for(i=1;i<=n;i++)
        {
            scanf("%c%c%c%c%c",&mat[i][1],&mat[i][2],&tmp,&mat[i][3],&mat[i][4]);
            getchar();
            if(flag) continue;
            if((mat[i][1]=='O') && (mat[i][2]=='O'))
            {
                mat[i][1]='+';mat[i][2]='+';
                flag=1;
                continue;
            }
            if((mat[i][3]=='O') && (mat[i][4]=='O'))
            {
                mat[i][3]='+';mat[i][4]='+';
                flag=1;
                continue;
            }
        }
        if(!flag) {printf("NO\n");continue;}
        printf("YES\n");
        for(i=1;i<=n;i++)
            printf("%c%c|%c%c\n",mat[i][1],mat[i][2],mat[i][3],mat[i][4]);
    }
    return 0;
}

B.Chris and Magic Square x3112
也很简单

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll a[510][510];
int main()
{
    int i,j;
    int n;
    while(~scanf("%d",&n))
    {
        int x,y;
        int flag=1;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                scanf("%I64d",&a[i][j]);
                if(!a[i][j]) {x=i,y=j;}
            }
        if(n==1) {printf("1\n");continue;}
        ll ans=-1,tmp=0;
        for(i=1;i<=n;i++)
        {
            if(i==x) continue;
            for(j=1;j<=n;j++) tmp+=a[i][j];
            if(ans==-1) {ans=tmp;tmp=0;continue;}

            if(tmp!=ans)
            {
                flag=0;
                break;
            }
            tmp=0;
        }
        if(!flag){printf("-1\n");continue;}
        tmp=0;
        for(j=1;j<=n;j++)
        {
            if(j==y) continue;
            for(i=1;i<=n;i++) tmp+=a[i][j];
            if(tmp!=ans)
            {
                flag=0;
                break;
            }
            tmp=0;
        }
        if(!flag){printf("-1\n");continue;}
        tmp=0;
        for(i=1;i<=n;i++) tmp+=a[i][y];
        ll ret1=ans-tmp;
        tmp=0;
        for(j=1;j<=n;j++) tmp+=a[x][j];
        ll ret2=ans-tmp;
        if(ret1!=ret2 || ret1<1){printf("-1\n");continue;}
        a[x][y]=ret1;
        ll c1=0,c2=0;
        for(i=1;i<=n;i++) c1+=a[i][i],c2+=a[i][n+1-i];
        if(c1!=c2 || c1!=ans) {printf("-1\n");continue;}
        printf("%I64d\n",ret1);
    }
    return 0;
}

C.Coloring Trees x1710
题意:有一排树。每棵树有一种颜色或者还没被涂色,如果一棵树原本就有颜色,那么不能改色,只有没被上色的树可以涂颜色。相邻且颜色相同的树属于同一组。p[i][j]表示将第i棵树涂成颜色j的代价。问:通过上色将这些树分成k组的最小代价是多少?
树的数量、颜色的数量均<=100
序列?分组?最优解?直接往dp上去想
dp[i][j][t]表示将前i个分成t组且第i个涂成颜色j的最小代价。
转移如下:
(1)如果第i个是已经有颜色,且颜色为a[i]
dp[i][a[i]][t]=min(dp[i-1][a[i]][t],min of dp[i-1][not a[i]][t-1])(注意t==1时后一项时没有的)
(2)如果第i个没有颜色
dp[i][j][t]=min(dp[i-1][j][t],min of dp[i-1][not j][t-1])+p[i][j];
初始化dp[1][j][1]时也要如上分类讨论,其余初始化为inf。
时间复杂度O(n*m*n*n), 大概10^8数量级,能过。。。
这题耗费了比较多的时间,现在熟练度下降很多~

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll inf=100000000000000000LL;
int n,m,k,t,s;
ll dp[110][110][110],p[110][110];
int a[110];
ll min(ll a,ll b){return a<b?a:b;}
int main()
{
    int i,j;
    while(~scanf("%d%d%d",&n,&m,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                scanf("%I64d",&p[i][j]);
        if(k>n){printf("-1\n");continue;}
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                for(t=1;t<=n;t++)
                    dp[i][j][t]=inf;
        if(a[1]!=0)
        {
            dp[1][a[1]][1]=0;
        }
        else
        {
            for(i=1;i<=m;i++)
                dp[1][i][1]=p[1][i];
        }
        for(i=2;i<=n;i++)
            for(j=1;j<=m;j++)
                for(t=1;t<=k;t++)
                {
                    if(a[i]!=0)
                    {
                        if(j!=a[i]) continue;
                        ll tmp=inf;
                        dp[i][a[i]][t]=dp[i-1][a[i]][t];
                        if(t>1){
                            for(s=1;s<=m;s++)
                            {
                                if(s==a[i]) continue;
                                if(dp[i-1][s][t-1]<tmp) tmp=dp[i-1][s][t-1];
                            }
                        }
                        dp[i][a[i]][t]=min(dp[i][a[i]][t],tmp);
                        continue;
                    }
                    ll tmp=inf;
                    dp[i][j][t]=dp[i-1][j][t]+p[i][j];
                    if(t>1)
                    {
                        for(s=1;s<=m;s++)
                        {
                            if(s==j) continue;
                             if(dp[i-1][s][t-1]+p[i][j]<tmp) tmp=dp[i-1][s][t-1]+p[i][j];
                        }
                    }
                    dp[i][j][t]=min(dp[i][j][t],tmp);
                }
        ll ans=inf;
        for(i=1;i<=m;i++)
            ans=min(ans,dp[n][i][k]);
        if(ans<inf) printf("%I64d\n",ans);
        else printf("-1\n");
    }
    return 0;
}

D.Directed Roads x948
这题其实比上一题简单,个人感觉。
n个点,n条边。没有圈(自环)。每条弧可以反向,问有多少种将边反向的方案可以使得图没有环,两个方案不同当且仅当两个方案中至少存在一条不同的弧。
n<=2*10^5
容易想到对于一个环中的弧,只要不全部反向或者一条弧都不反向,其它方案都可以去掉改环。所以方案数是(2^len)-2.len 是环中弧的数量。
对于不在环中的弧,选不选无所谓,所以针对这些弧,所有方案都行, 方案数是2^k.k是这类弧的数量。最后乘法原理。
最后答案:∏((2^len)-2)*(2^k)
∏ 表示连乘
可见最后是一个简单的快速幂模mod

-_-#速度太慢了,这题没来得及submit。。。

#include<stdio.h>
#include<string.h>
typedef long long ll;
const int mod=(1e9)+7;
int n;
int a[200000+10];
int order[200000+10];
ll cal(int k)
{
    ll ans=1,p=2;
    while(k)
    {
        if(k%2)
        {
            ans=(ans*p)%mod;
            k--;
        }
        p=(p*p)%mod;
        k/=2;
    }
    return ans;
}
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(order,0,sizeof(int)*(n+5));
        int cnt=0;
        ll ans=1;
        int m=n;
        for(i=1;i<=n;i++)
        {
            if(order[i]) continue;
            j=i;
            int end=cnt+1;
            while(!order[j])
            {
                //printf("%d ",j);
                order[j]=++cnt;
                end=order[j];
                j=a[j];
            }
            if(order[j]<order[i]) continue;
            int len=end-order[j]+1;
            //printf("%d\n",len);
            m-=len;
            ans=(ans*((cal(len)-2+mod)%mod))%mod;
        }
        ans=(ans*cal(m))%mod;
        printf("%I64d\n",ans);

    }
    return 0;
}

E.ZS and The Birthday Paradox x241

google code jam2016资格赛题解

A. Counting Sheep
小数据暴力呗。大数据也一样。。
B. Revenge of the Pancakes
小数据暴力呗。大数据没做。。
C. Coin Jam
小数据暴力呗。大数据没做。。
D. Fractiles
题意:一个序列由两种字符组成:L、G.给出k,c,s。表示序列初始长度k,变换了c次。每次变换:L的地方用最初始序列代替,G的地方用k个G代替。
现序列各个位置的值是看不到的,你可以选择查看其中的s个位置的值。问:能否通过小于等于s次查看,来推断出现序列是否包含G。
这题我是这样做的。小数据大数据一个做法。
如果查看一个位置发现是G,那么我们就知道序列是含有G的了,所以问题其实是在问:有没有一种查看的策略使得在查看的值都是L的情况下,可以断定序列必定没有G。
我们可以把整个变换的过程画出来,可以发现是一棵k叉树(注意一点这里我把原始序列的k个结点最为统一的“根结点”)。叶子节点是现序列。关键一点在于当得到了位置pos的值是L之后,我们就知道了pos位置的值是L之后,就知道了pos的父节点是L,它的父节点也是L。换言之,pos到树根的路径上的结点都是L。
那么为了尽可能通过一次查看得到最多信息,我们可以查看根节点的第二个子结点的第三个子结点的…………(一直到叶子结点)的值。这样就得到了min(c,k)个连续位置的值,接下来重复这个查看过程就行。
这个还是有个图比较好解释。。下次加个图。

#include<stdio.h>
#include<string.h>
typedef long long ll;
ll a[110];
ll ans[110],cnt;
inline ll min(ll a,ll b){return a<b?a:b;}
int main()
{
    //freopen("D-large.in","r",stdin);
    //freopen("D-large.out","w",stdout);
    ll i,j;
    int k,c,s;
    int t,cases=0;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&k,&c,&s);
        printf("Case #%d:",++cases);
        if(c==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            for(i=1;i<=k;i++) printf(" %d",i);
            printf("\n");
            continue;
        }
        if(k==1)
        {
            if(s<k) {printf(" IMPOSSIBLE\n");continue;}
            printf(" 1\n");continue;
        }
        cnt=0;
        a[0]=1;a[1]=k;
        for(i=2;i<=c;i++)
            a[i]=a[i-1]*(ll)k;
        for(i=1;i<=k;)
        {
            ll tmp=0;
            for(j=-1;j<=c-2;j++)
            {
                if(i+j+1<=k)
                    tmp+=(i+j)*a1;
                else
                    tmp+=(k-1)*a1;
            }
            ans[++cnt]=tmp+1;
            i+=min(c,k-i+1);
        }
        if(s<cnt) {printf(" IMPOSSIBLE\n");continue;}
        for(i=1;i<=cnt;i++) printf(" %I64d",ans[i]);
        printf("\n");
    }

    return 0;
}

linux内核模块编程笔记

最近因为实验室项目,开始接触了一点linux内核模块编程
内核编译选项.config所在路径:/usr/src/相应内核版本/.config
内核符号表:在编写内核模块的时候,因为LKM是动态加载到内核中,也就是说这时的内核是在内存中运行的,所以正确获取内核函数和变量的地址很重要。如果我们在内核模块中直接将地址写死,那么显然不通用,在另一个内核上可能地址就变了。内核符号表就是用于解决这个问题。每个内核都有其内核符号表,里面是内核导出的符号及其地址。我们编写的内核模块通过访问这个内核符号表就可以得到当前正在运行的内核的可用函数和变量的确切地址。
那么怎样使用内核未导出的符号呢?
我们可以使用kallsyms_lookup_name(char*)这个函数,该函数参数是符号名,返回unsigned long型的函数/变量地址。这个方法有个前提,那就是kallsyms_lookup_name(char*)这个符号本身是被内核导出的,所以要用CONFIG_KALLSYMS=y来编译内核,或者修改内核源码中的kallsyms.c文件,增加EXPORT_SYMBOL(kallsyms_lookup_name);手动将该符号导出
————————————————————————————————————————————————————————————————————————————
过程中的问题和要点:
linux内核的三种内存模型
page结构中的_count和_mapcount
_mapcount:在页表中每增加一个映射项,_mapcount就加1.初始值是-1

使用page_address之后发现所有页帧的虚拟地址都是在内核地址空间?what the fuck
__________________________
x86_64的内存地址空间需要研究
——————————————————————————————
读某个内核虚拟地址出错。BUG: unable to handle kernel paging request at ffff880020000000

找到读取物理内存内容的方法了,如下:
前面失败的原因是较新版本的linux内核限制了对/dev/mem的读取,默认只能读取前1M字节的数据。解决方法时修改.config中的CONFIG_X86_PAT=n,CONFIG_STRICT_DEVMEM=n.然后重新编译内核
编译内核过程(抱歉,不要嫌弃我菜,我经常忘。所以记一下)
make menuconfig生成.config(如果要编译的内核和现有内核版本相同,可以从/boot/config-版本号 copy一份放到源码根目录)
make modules 编译一下内核模块
make modules_install 安装内核模块(到/lib/modules目录)
make install 安装内核(copy 生成的内核映像到/boot下面,修改gurb启动项等)

由于/dev/mem是整个物理地址空间的映像,包括了IO端口、ROM的地址,并不全是RAM,所以要先读取/proc/iomem文件得到System RAM的地址分布,之后读取System RAM的部分即可
代码如下,注意不要读到RAM之外的地方,可能会导致出错。

#include<stdio.h>
#include<string.h>
#include<unistd.h>
#include<sys/mman.h>
#include<sys/types.h>
#include<sys/stat.h>
#include<fcntl.h>
typedef long long ll;
const ll max_read=10000000;
char buf[max_read+10];
typedef struct Node{
	ll be,en;
}Node;
Node node[10010];
int cnt;
int main()
{
	freopen("/proc/iomem","r",stdin);
	cnt=0;
	int i;
	while(gets(buf))
	{
		int len=strlen(buf);
        if(strstr(buf,"System RAM")==NULL) continue;
        char *s=buf;
        strtok(s,":");
        printf("%s\n",s);
        char tmp;
        cnt++;
        sscanf(s,"%llx-%llx",&node[cnt].be,&node[cnt].en);
    }
	
    int fdmem,fdout;
    fdmem=open("/dev/mem", O_RDWR|O_SYNC);
	fdout=open("memdump.txt",O_CREAT|O_RDWR|O_SYNC);
    if ((fdmem == -1) || (fdout==-1))
    {
		printf("open err\n");
        return -1;
    }
	for(i=1;i<=cnt;i++)
    {
        ll be=node[i].be,en=node[i].en;
        lseek(fdmem,be,SEEK_SET);
        printf("read %llx-%llx\n",be,en);
        while(1)
        {
            if(en-be+1<=max_read)
            {
                read(fdmem,buf,en-be+1);
                printf("read %llx-%llx\n",be,en);
                write(fdout,buf,en-be+1);
                break;

            }
            read(fdmem,buf,max_read);
            printf("read %llx-%llx\n",be,be+max_read-1);
            write(fdout,buf,max_read);
            be+=max_read;
        }
    }
	close(fdmem);
	close(fdout);
	
    return 0;
}

虚拟化笔记

VMM进程地址空间中存储了各个虚拟机具体的硬件环境(如PC值、EAX值等等,PC值指向guestOS的代码),guestOS在运行时(其实就是VMM将真实寄存器等硬件环境改为guestOS的环境,PC改为指向guestOS的代码,这样guestOS的代码就开始运行了),其代码是真正运行在真实cpu上的,由于guestOS是在ring3,所以执行特权指令时触发异常,VMM的异常处理模块截获异常,然后再做安排。

设备模拟

1.guestOS中的驱动程序称为前端(Front-End,FE)设备驱动,而VMM中的驱动程序为后端(Back-End,BE)设备驱动。

硬件辅助虚拟化:硬件本身加入虚拟化功能,就可以截获操作系统对敏感指令的执行或者对敏感资源的访问,从而通过异常的方式报告给VMM,这样就解决了虚拟化的问题。

硬件辅助虚拟化的典型:Intel的VT-x技术。VT-x技术在处理器上引入了一个新的执行模式用于运行虚拟机。当虚拟机执行在这个特殊模式中时,它仍然面对的是一套完整的处理器寄存器集合和执行环境,只是任何特权操作都会被处理器截获并报告给VMM

这几天发现自己一直以来有个特点,决定做一件事的时候犹豫起来没完没了。现在索性想简单点,既然还年轻,那么有喜欢的事情,就竭尽全力坚持到底就好了,不要想乱七八糟的问题。

linux伙伴系统

前段时间由于实验室相关项目的需要+OS课的presentation,看了linux2.6.24内核伙伴系统的源码。写一下总结。

引言
    伙伴系统作为一种古老而历经检验的系统,也被Linux内核所采用。伙伴系统的提出是为了管理和记录内存的分配和使用。在X86架构的Linux内核版本 2.6.24及之后,Linux对原本的伙伴系统做了改进,在原来的基础上加入了反碎片机制,使得内核能够更好的管理内存的外部碎片。
    本文的分析针对X86架构。首先介绍了什么是伙伴系统,以及伙伴系统的相关数据结构。然后分析了X86架构上Linux 2.6.24这个版本对伙伴系统做的改进(加入了反碎片机制)。最后从源代码出发,深入揭示了伙伴系统的内核工作流程。
什么是伙伴系统
    伙伴系统的宗旨就是用最小的内存块来满足内核对于内存的请求。在最初,只有一个块,也就是整个内存,假如为1M大小,而允许的最小块为64K,那么当我们申请一块200K大小的内存时,就要先将1M的块分裂成两等分,各为512K,这两份之间的关系就称为伙伴,然后再将第一个512K的内存块分裂成两等分,各为256K,将第一个256K的内存块分配给内存,这样就是一个分配的过程。下面我们结合示意图来了解伙伴系统分配和回收内存块的过程。
图1 伙伴系统示意图
1. 初始化时,系统拥有1M的连续内存,允许的最小的内存块为64K,图中白色的部分为空闲的内存块,着色的代表分配出去了的内存块。
2. 程序A申请一块大小为34K的内存,对应的order为0,即2^0=1个最小内存块
   2.1 系统中不存在order 0(64K)的内存块,因此order 4(1M)的内存块分裂成两个order 3的内存块(512K)
   2.2 仍然没有order 0的内存块,因此order 3的内存块分裂成两个order 2的内存块(256K)
   2.3 仍然没有order 0的内存块,因此order 2的内存块分裂成两个order 1的内存块(128K)
   2.4 仍然没有order 0的内存块,因此order 1的内存块分裂成两个order 0的内存块(64K)
   2.5 找到了order 0的内存块,将其中的一个分配给程序A,现在伙伴系统的内存为一个order 0的内存块,一个order 1的内存块,一个order 2的内存块以及一个order 3的内存块
3.程序B申请一块大小为66K的内存,对应的order为1,即2^1=2个最小内存块,由于系统中正好存在一个order 1的内存块,所以直接用来分配
4 程序C申请一块大小为35K的内存,对应的order为0,同样由于系统中正好存在一个order 0的内存块,直接用来分配
5 程序D申请一块大小为67K的内存,对应的order为1
   5.1 系统中不存在order 1的内存块,于是将order 2的内存块分裂成两块order 1的内存块
   5.2 找到order 1的内存块,进行分配
6 程序B释放了它申请的内存,即一个order 1的内存块
7 程序D释放了它申请的内存
   7.1 一个order 1的内存块回收到内存当中
   7.2由于该内存块的伙伴也是空闲的,因此两个order 1的内存块合并成一个order 2的内存块
8 程序A释放了它申请的内存,即一个order 0的内存块
9 程序C释放了它申请的内存
   9.1 一个order 0的内存块被释放
   9.2 两个order 0伙伴块都是空闲的,进行合并,生成一个order 1的内存块m
   9.3 两个order 1伙伴块都是空闲的,进行合并,生成一个order 2的内存块
   9.4 两个order 2伙伴块都是空闲的,进行合并,生成一个order 3的内存块
   9.5 两个order 3伙伴块都是空闲的,进行合并,生成一个order 4的内存块
 从上述例子中,我们可以总结出伙伴系统分配内存释放内存的算法:
分配内存
1.寻找大小合适的内存块(大于等于所需大小并且最接近2的幂)
  • 1.1.如果找到了,分配给应用程序
  • 1.2.如果没找到,分出合适的内存块
  • 1.2.1.对半分离出高于所需大小的空闲内存块
  • 1.2.2.如果分到最低限度,分配这个大小
  • 1.2.3.回溯到步骤1
  • 1.2.4.重复该步骤直到一个合适的块
释放内存
1.释放该内存块
  • 1.1.寻找相邻的块,看其是否释放了。
  • 1.2.如果相邻块也释放了,合并这两个块,重复上述步骤直到遇上未释放的相邻块,或者达到最高上限(即所有内存都释放了)
伙伴系统的数据结构
    我们首先来看一下伙伴系统相关的数据结构,首先看一下free_area。
<include/linux/mmzone.h>
struct free_area {
    struct list_head    free_list;
    unsigned long     nr_free;
};
    其中nr_free指定了当前内存区中空闲页块的数目。free_list是用于链接空闲页的链表,页链表包含大小相同的连续内存区。是伙伴系统里非常重要的概念,它描述了内存分配的数量单位,例如2^order,order就是阶,并且其范围从0到MAX_ORDER。order通常设置为11,这意味着一次分配可以请求的页的最大数是2^11=2048。
    free_area[]数组中的各个元素索引也可以理解为索引,第0个链表代表内存管理区里的单页,第1个链表代表内存管理区里的两页。从下图可以看出,free_area[0]每个元素代表单个页帧,free_area[2]的每个元素代表4个页帧。
伙伴系统的反碎片机制
    本文研究的是X86平台Linux2.6.24版本的内核。在该版本中,对于伙伴系统加入了反碎片机制(anti-fragmentation),试图从最初开始就尽可能防止碎片。
    首先我们必须知道,内核将已分配页分为以下三种不同的类型:
  不可移动页(UNMOVABLE): 这些页在内存中有固定的位置,不能够移动。
  可回收页(RECLAIMABLE): 这些页不能移动,但可以删除。内核在回收页占据了太多的内存时或者内存短缺时进行页面回收。
  可移动页(MOVABLE): 这些页可以任意移动,用户空间应用程序使用的页都属于该类别。它们是通过页表映射的。当它们移动到新的位置,页表项也会相应的更新。
  在内存子系统初始化期间,所有的页都被标记为可移动的。在启动期间,核心内核分配的内存是不可移动的。此时内核的策略是分配一个尽可能大的连续内存块,将其从可移动列表转换到不可移动列表。原因如下:
   例如:现有一块可移动的具有16页的连续空闲内存块。当内核需要分配1页不可移动内存页时。分配器选择后8页(而不是一页)转移到不可移动列表,然后从 不可移动列表中选择1页用于分配。如果内核又需要分配1页不可移动内存页则从不可移动列表中选择一页用于分配,下图显示了进行4次分配后内存的分布。
        但如果内核只选择1页用于分配将其加入到不可移动列表,当下次需要分配时又选择一页加入到不可移动列表,下图显示了按照这种方式进行4次分配后内存的分布。
        因此,当没有满足可用于分配的不可移动空闲块时,分配器会在可移动列表中迁移一个尽可能大的连续内存块给不可移动列表。这样避免了启动期间内核分配的内存散列到物理内存各处,从而使其他类型的内存分配免受碎片的干扰。
        内核定义了一些宏来表示不同的迁移类型:
<include/linux/mmzone.h>
    #define MIGRATE_UNMOVABLE     0
    #define MIGRATE_RECLAIMABLE   1
    #define MIGRATE_MOVABLE       2
    #define MIGRATE_RESERVE       3
    #define MIGRATE_ISOLATE       4 /*用于跨越NUMA结点移动物理内存页*/
    #define MIGRATE_TYPES         5
    2.6.24版本对伙伴系统结构的主要调整,是将空闲列表分解成MIGRATE_TYPE个列表,数据结构如下(注意变化的部分):
<include/linux/mmzone.h>
struct free_area {
    struct list_head    free_list[MIGRATE_TYPE];
    unsigned long     nr_free;
};
    也就是说每一个free_area又根据MIGRATE_TYPE分成了5种类型,每种类型里面分别都有一个head_list结构体。
    如果内核无法满足针对某一给定迁移类型的分配请求的话,内核提供了一个备用列表,规定了在指定列表中无法满足分配请求时,接下来应使用哪一种迁移类型:
static int fallbacks[MIGRATE_TYPES][MIGRATE_TYPES-1] = {  
  • [MIGRATE_UNMOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
  • [MIGRATE_RECLAIMABLE] = { MIGRATE_UNMOVABLE,   MIGRATE_MOVABLE,   MIGRATE_RESERVE },  
  • [MIGRATE_MOVABLE] = { MIGRATE_RECLAIMABLE, MIGRATE_UNMOVABLE, MIGRATE_RESERVE },  
  • [MIGRATE_RESERVE] = { MIGRATE_RESERVE,     MIGRATE_RESERVE,   MIGRATE_RESERVE }, 
}; 
    内核想要分配不可移动页时,如果对应链表为空,则后退到可回收链表,接下来到可移动页链表,最后到紧急分配链表。
    在X86架构中存在着三种内存域ZONE_DMA、ZONE_NORMAL、ZONE_HIGHMEM,那么每个内存域都有一个free_area数据结构:
<mm/mmzone.h>
struct zone {
  • struct free_area    free_area[MAX_ORDER];
}
    而如果是在NUMA架构中,可能存在着多块物理内存,其结构可能是如下图所示:
    基于伙伴系统的内存管理专注于某个节点的某个内存域,例如DMA或高端内存域。但所有内存管理区和节点的伙伴系统都通过备用分配列表链接起来。在首选内存 管理区或节点无法满足分配请求时,首先尝试用同一节点的另一个内存管理区分配,反复尝试下一个结点直到满足请求。

页的分配以及源代码剖析
       就伙伴系统的接口而言,NUMA或UMA体系结构是没有差别的,二者的调用语法都是相同的。所有函数的一个共同点是:只能分配2的整数幂个页。

从函数关系图上可以看到,最终的分配任务落在__alloc_pages()上。我们来看这个函数的代码
————————————————————————————待续————————————————-——————

关于圣诞节

不知道为什么今天心情真的不好,今天唯一的收获是学会了弹奏《you are my sunshine》,但是真的不适合在今天弹这么欢快的歌曲。感谢朋友的邀请,但是真的不想出去玩。晚上一个人去街上走了走,本来想一个人练下台球,好久没打了。怎么说呢,还是算了,本来平安夜那天决定以后认真去做心里决定的事情,但是这个愿望还是被一下子浇灭了,我太傻了。恩,就这样吧。lonely Christmas.
-
-
-
但是呢,我可以有更多时间去达成另一个目标,我要去我想去的那个地方。它一定会被实现。

Shortest Palindrome

leetcode的一道题
题意:给出一个字符串,只能在首部加上字符使其成为回文串,求所加字符数最少的方案。
这题以前搞acm的时候碰到过,如果是以前,就直接上KMP了。但是前面有道题是用manacher算法求字符串的最长回文子串。突然发现这题也可以用manacher来做,时间复杂度也是O(n)。
manacher确实是一种思路巧妙,代码简短的算法。
https://leetcode.com/problems/shortest-palindrome/

char str[1000010],ans[1000010];
int r[1000010];
int min(int a,int b){return a<b?a:b;}
int max(int a,int b){return a>b?a:b;}
char* shortestPalindrome(char* s) {
    int i,j,k,cnt;
    int len=strlen(s);
    if(len<=1)  return s;
    r[0]=0;
    str[0]='?';
    for(i=0;i<=len;i++)
    {
        str[(i<<1)+1]=s[i];
        str[(i<<1)+2]='*';
    }
    str[len<<1]='#';str[(len<<1)+1]='\0';
    i=1;j=0;
    while(i<=(len<<1))
    {
        while(str[i-j-1]==str[i+j+1]) j++;
        r[i]=j;
        for(k=1;k<=j;k++)
            if(r[i]-k!=r[i-k]) r[i+k]=min(r[i]-k,r[i-k]);
            else break;
        j=max(0,r[i]-k);
        i+=k;
    }
    for(i=(len<<1);i>=1;i--)
    {
        if(i-r[i]==1) break;
    }
    i=(i+r[i])/2;
    cnt=0;
    for(j=len-1;j>=i+1;j--) ans[cnt++]=s[j];
    for(j=0;j<=len-1;j++) ans[cnt++]=s[j];
    ans[cnt++]='\0';
    return ans;
}

pmfs+nvm与ext4+pmbd+nvm性能比较

这周开始做nvm相关的一个性能测试。nvm是非易失性内存,是一类比较新的存储硬件的总称,其读写速率比DRAM慢,比ssd快。之前看了一些相关的论文,nvm的应用大概分这么几种:

1.用来完全替代DRAM作为主存.(并用DRAM做cache)

2.和DRAM一起构成一个混合的内存模型

3.作为块设备。

4.作为其他块设备的cache(如ssd)

这里把nvm作为块设备。

实验用dram模拟nvm,试验机总共8g内存,前4g仍作为dram使用,后4g作为nvm。

现在存在两种方案来使用它。

一是用新的filesystem来管理,这里使用pmfs这个文件系统.

pmfs项目的github:https://github.com/linux-pmfs/pmfs

二是在现有filesystem的基础上加上一层转换层,使得能够用现有的filesystem,如ext4来管理nvm。

这个中间层在这里是pmbd:https://github.com/linux-pmbd/pmbd

这两种方案下的体系结构图大概如下:

pmbd是作为内核模块启动的,可以按照README进行

pmfs对内核改动比较大,因此github给出的是修改后的整个内核。需要下载后重新编译内核。

注意不要下载zip文件然后解压,会导致文件不全。请用git clone到试验机。

对内核进行编译,请参照:http://zjuedward.blog.51cto.com/1445231/461376

make menuconfig时记得选上File sytems->Miscellaneous filesystems->Persistent and Protected PM file system support

这里声明一点:由于pmfs是基于内核3.11,而pmbd只能运行在3.2.1的内核上,所以我们只能在不同的内核下进行测验,但是内核版本的不同对实验结果影响不大,内存那块的差异非常小。

 
实验主要测试io带宽。使用的benchmark是fio-2.1.10
由于需要多次测试取平均值,并且生成的结果需要以特定格式导入到excel中生成图表,所以我写了个脚本来进行测试(只列举了针对pmbd的测试,pmfs的测试时类似的),如下:

import commands
io_type=["read","write","randread","randwrite"];
blocksize=["1KB","2KB","4KB","8KB"];
job_num=["1","2","4","8"];
result='type-job';
for num in range(1,4):
	for i in blocksize:
		result+="	"+i;
	result+="\n";
	for iotype in io_type:
		for job in job_num:
			result+=iotype+'-'+job;
			for bs in blocksize:
#				commands.getstatusoutput('touch /mnt/1.txt');
				cmd='fio -filename=/dev/pma -direct=1 -iodepth 1 -thread -rw='+iotype+' -ioengine=psync -bs='+bs+' -size=8G -numjobs='+job+' -runtime=30 -group_reporting -name=mytest';
				print str(iotype)+"  "+str(bs)+"  "+str(job)+"  begin\n";
				(status,output)=commands.getstatusoutput(cmd);
				word=output.split();
				bw_val=0.0;
				for i in word:
					if i.startswith('bw='):
						i=i.lstrip('bw=');
						if i.endswith('KB/s,'):
							bw_val=float(i.rstrip('KB/s,'))/1024.0;
							bw_val=float('%0.3f' %bw_val);
							bw_val=str(bw_val);
						else:bw_val=i.rstrip('MB/s,');
						break;
				result+="	"+str(bw_val);
				print str(iotype)+"  "+str(bs)+"  "+str(job)+"\t"+str(bw_val)+"  end\n";
				tmp_result=str(iotype)+"  "+str(bs)+"  "+str(job)+"\t"+str(bw_val)+"  end\n";
				ret1="echo '"+tmp_result+"' >>tmp_fio_log.txt";
				commands.getstatusoutput(ret1);
			result+="\n";
	ret="echo '"+result+"' >>resultlog.txt";
	commands.getstatusoutput(ret);
	result='type-job';

最终得到如下性能:


注意两个图纵坐标的不同,初步的比较可知使用pmfs对nvm进行管理的性能更好。
job=4比job=8性能更好是因为实验机为四核,用8个线程去跑反而增加切换的开销。
顺序读比随机读性能稍好可能是因为预取和cache的原因,我们的nvm实际上是DRAM模拟的,所以cache对其是有影响的
顺序写比随机写性能稍好也可能是cache的原因。
目前进行的是没有虚拟化的情况下的性能比较,后期还要加入kvm,在kvm下进行性能测试,io栈大致如下:

bestcoder#64 div1

还是做出两题。。
1001(hdu5586) Sum
题意:给出n个数,给出函数f(x),现在可以对连续的一段区间的数使用f(x)转换,也可以不用。问最后这n个数之和最大是多少.
简单dp。可以先对这n个数都使用f(x)得到新的数组b(设原数组为a),b[]-a[],得到数组c。对c[]求最大子串和,这个最大子串和就是对某一段数施加f(x)之后可以达到的最大增益。如果是负的,那么显然不应该进行f(x)的转换。a数组的和加上这个增益就是答案。

#include<stdio.h>
#include<string.h>
int n;
int a[100010],dp[100010];
int main()
{
    int i,j;
    while(~scanf("%d",&n))
    {
        int sum=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            sum+=a[i];
            a[i]=(1890*a[i]+143)%10007-a[i];
        }
        dp[1]=a[1];
        int ans=dp[1];
        for(i=2;i<=n;i++)
        {
            dp[i]=(dp[i-1]>0?dp[i-1]+a[i]:a[i]);
            if(dp[i]>ans) ans=dp[i];
        }
        if(ans>0) sum+=ans;
        printf("%d\n",sum);
    }


    return 0;
}

1002(hdu5587) Array
题意:第一次操作,数列为{1}。总共做一百次操作,每次都是在原先数列末尾增加一个0,并复制原数列增加在0后面。再将新增加的数全部加1.
给出一系列的m,表示求前m个数之和。m<=10^16
第一次:1
第二次:1 1 2
第三次:1 1 2 1 2 2 3
……
解法:因为题意是递推的,比较容易想到用递归去解。对于给定的m,我们可以二分求出最少几次操作可以使数列长度达到m,设为num.设num次操作得到的数列长度为c[num],数列和为s[num].那么前c[num-1]个数的和就是s[num-1],剩余x-c[num-1]个数可以递归解决(设剩余tmp个数,那么转化为求前(tmp-1)个数的和+tmp-1+1)

#include<stdio.h>
#include<string.h>
typedef long long ll;
int t;
ll m;
ll c[110],s[110];
int bs(ll x)
{
    int l=1,r=63;
    while(l<=r)
    {
        int m=(l+r)>>1;
        if(c[m]==x) return m;
        if(x>c[m]) l=m+1;
        else r=m-1;
    }
    return l;
}
ll f(ll x)
{
    int num=bs(x);
    //printf("num:%d\n",num);
    if(num==1) return 1;
    if(c[num]==x) return s[num];
    ll tmp=x-c[num-1];
    if(tmp==1) return s[num-1]+1;
    return s[num-1]+1+f(tmp-1)+tmp-1;
}
int main()
{
    int i,j;
    c[1]=1;
    for(i=2;i<=100;i++) c[i]=2*c[i-1]+1;
    s[1]=1;
    for(i=2;i<=100;i++) s[i]=2*s[i-1]+1+c[i-1];
    //for(i=1;i<=100;i++) printf("c[%d]:%I64d\n",i,c[i]);
    //printf("\n");
    //for(i=1;i<=100;i++) printf("s[%d]:%I64d\n",i,s[i]);
    //printf("\n");
    scanf("%d",&t);
    while(t–)
    {
        scanf("%I64d",&m);
        ll ans=f(m);
        printf("%I64d\n",ans);


    }
    return 0;
}

bestcoder#63 div1

第一次做div1,解出两道题,能做的也只有两道。但是第一题罚时有点厉害,一直不太相信需要高精度(因为output里写了integer。。)
1001(hdu5568) sequence2
一个整数序列有多少种长度为k的不同的递增子序列,两个子序列只要有一个元素对应位置不同就算不同。
如1 2 2有两个长度为2的不同子序列1 2和1 2(这两个2位置不同)
简单的dp题。dp[i][j]表示前i个数组成的序列中有多少个长度为j的不同子序列。
dp[i][j]=sigma(dp[t][j-1]),其中a[i]>a[t]。

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
using namespace std;
class BigNum;
istream& operator>>(istream&,  BigNum&);
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
};
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;
	return t;
}

int n,k;
BigNum dp[110][110];
int a[110];
int main()
{
    int i,j,t;
    while(~scanf("%d%d",&n,&k))
    {
        for(i=1;i<=n;i++) scanf("%d",&a[i]);
        memset(dp,0,sizeof(dp));
        for(i=1;i<=n;i++) dp[i][1]=1;
        for(j=2;j<=k;j++)
            for(i=1;i<=n;i++)
                for(t=1;t<=i-1;t++)
                    if(a[i]>a[t]) dp[i][j]=dp[i][j]+dp[t][j-1];
        BigNum ans=0;
        for(i=1;i<=n;i++) ans=ans+dp[i][k];
        cout<<ans<<endl;


    }
    return 0;
}

1002(hdu5569) matrix
也是比较简单的dp题,转移方程容易想到,具体见代码。

#include<stdio.h>
#include<string.h>
typedef long long ll;
int n,m;
int a[1010][1010];
int dp[1010][1010];
const int inf=0x3f3f3f3f;
bool judge(int x,int y)
{
    if(1<=x && x<=n && 1<=y && y<=m) return 1;
    return 0;

}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int main()
{
    int i,j;
    while(~scanf("%d%d",&n,&m))
    {
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                dp[i][j]=0;
            }
        dp[1][2]=a[1][1]*a[1][2];
        dp[2][1]=a[1][1]*a[2][1];

        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
            {
                if((i==1) && (j==2)) continue;
                if((i==2) && (j==1)) continue;
                if((i+j)%2==0) continue;
                int tmp1=-1,tmp2=-1,tmp=0;
                if(judge(i,j-1))
                {
                    tmp1=a[i][j]*a[i][j-1];
                    tmp=inf;
                    if(judge(i,j-2)) tmp=dp[i][j-2];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp1+=tmp;
                }
                if(judge(i-1,j))
                {
                    tmp2=a[i][j]*a[i-1][j];
                    tmp=inf;
                    if(judge(i-2,j)) tmp=dp[i-2][j];
                    if(judge(i-1,j-1)) tmp=min(tmp,dp[i-1][j-1]);
                    tmp2+=tmp;
                }
                if((tmp1==-1) || (tmp2==-1)) dp[i][j]=max(tmp1,tmp2);
                else dp[i][j]=min(tmp1,tmp2);
            }
        printf("%d\n",dp[n][m]);

    }


    return 0;
}

1003 balls
做不出来,看了题解还没完全清楚。。

bestcoder#61 div2

1001(hdu5522) Numbers
签到题



#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[110];
bool judge(int x,int y,int z)
{
    if((x+y==z) || (x+z==y) || (y+z==x)) return 1;
    return 0;
}
int main()
{
    int i,j,k;
    int t;
    int n;
    while(~scanf("%d",&n))
    {
        bool flag=0;
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(i=1;i<=n;i++)
        {
            for(j=i+1;j<=n;j++)
            {
                for(k=j+1;k<=n;k++)
                {
                    if(judge(a[i],a[j],a[k])) {flag=1;break;}
                }
                if(flag) break;
            }
            if(flag) break;
        }
        printf("%s\n",flag?"YES":"NO");
    }


    return 0;
}

1002(hdu5523) Game
简单题,考虑s和t的位置,分情况讨论即可



#include<stdio.h>
#include<string.h>
int main()
{
    int i,j;
    int n,s,t;
    while(~scanf("%d%d%d",&n,&s,&t))
    {
        if((s==t) && n>1){printf("-1\n");continue;}
        if(((s==1) && (t==n))||((s==n) && (t==1))){printf("0\n");continue;}
        if(((s==1)||(s==n)) && t!=1 && t!=n)
        {
            printf("1\n");continue;
        }
        if(((t==1)||(t==n)) && s!=1 && s!=n)
        {
            if((s-t==1) || (t-s==1)) {printf("1\n");continue;}
            printf("2\n");continue;
        }
        if((s-t==1) || (t-s==1))
            printf("1\n");
        else
            printf("2\n");
    }


    return 0;
}

1003(hdu5524) Subtrees
我看了下别人的代码,似乎有很简单的做法。。但是我还没研究。我说下自己的解法
问题是问n个结点的完全二叉树有多少种结点个数不同的子树。n是long long 范围
可以递归来做,由于是完全二叉树,所以以根结点的两个儿子为根的两棵子树一定有一棵是满二叉树,而满二叉树有log2(结点总数)种结点数不同的子树,对于另一棵子树,我们递归求解。
这样。递归次数是树高h(=log2(n)),每次递归都要往结果set中加log2(n)个数据,set加一次数据复杂度log2级别,由于set中数据总数很少,所以看成常数。所以复杂度大概O(lg(n)^2)
易错点:算树高h的时候,浮点函数log()精度不够,要用二分去求树高。。

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<set>
using namespace std;
typedef long long ll;
set<ll> num;
ll pow2(ll k)
{
    ll ans=1,p=2;
    while(k)
    {
        if(k%2)
        {
            k--;
            ans*=p;
            continue;
        }
        else
        {
            k/=2;
            p*=p;
        }
    }
    return ans;
}
ll bs(ll n)
{
    if(!n) return 0;
    ll l=0,r=63;
    while(l<=r)
    {
        ll m=l+((r-l)>>1);
        if((pow2(m)-1>=n) && (pow2(m-1)<n)) return m;
        if(pow2(m)-1<n) l=m+1;
        else r=m-1;
    }
    return l;
}
void f(ll n)
{
    ll i;
    if(!n) return;
    if(n==1) {num.insert(1);return;}
    ll l,r;
    ll h=bs(n);
    ll non_ye=pow2(h-1)-1;
    ll ye=n-non_ye;
    ll xh=pow2(h-2);
    num.insert(n);
    if(ye<=xh)
    {
        l=(non_ye-1)/2+ye;
        r=(non_ye-1)/2;
        ll hr=bs(r);
        for(i=1;i<=hr;i++)
            num.insert(pow2(i)-1);
        f(l);
    }
    else
    {
        l=(non_ye-1)/2+xh;
        r=n-1-l;
        ll hl=bs(l);
        for(i=1;i<=hl;i++)
            num.insert(pow2(i)-1);
        f(r);

    }
    return;
}
int main()
{
    int i,j;
    ll n;
    while(~scanf("%I64d",&n))
    {
        if(!num.empty()) num.clear();
        f(n);
        printf("%I64d\n",(ll)num.size());
    }


    return 0;
}

1004(hdu5525) Product
不知道为什么TLE,按道理不应该啊。。看了下官方解答,基本思路相同,只是我没用费马小定理。有时间再回来改~
待修改

#include<stdio.h>
#include<string.h>
typedef long long ll;
const ll N=100010;
const ll mod=1000000007LL;
ll pr[N],p[N/10];
ll pi[N][20],ki[N][20];
ll cnt,lp;
void gp()
{
	for(int i=2;i<N;i++)
	{
		if(!pr[i])
			p[++lp]=pr[i]=i;
		for(int j=1;j<=lp && i*p[j]<N;j++)
		{
			pr[i*p[j]]=p[j];
			if(i%p[j]==0)break;
		}
	}
	return;
}
void fenjie(ll n)
{
	cnt=0;
	ll num=n;
	memset(ki[num],0,sizeof(ki[num]));
	while(n!=1)
	{
		ll t=pr[n];
        pi[num][++cnt]=t;
        ki[num][cnt]=0;
        while(n%t==0)
        {
            n/=t;
            ki[num][cnt]++;
        }
	}
	pi[num][0]=cnt;
	return;
}
ll ret;
ll pow(ll p,ll k)
{
    ll ans=1;
    while(k)
    {
        if(k%2) {k--;ans=(ans*p)%mod;}
        k/=2;
        p=(p*p)%mod;
    }
    return ans;
}
ll n,a[100000+10],b[100000+10];
ll zyz[20],cc[20];
void scan(ll &num)    //对G++使用
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in<'0') && in!='-') ;
    if(in=='-')
    {
        neg=true;
        while((in=getchar()) >'9' || in<'0');
    }
    num=in-'0';
    while(in=getchar(),in>='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}
int main()
{
    ll i,j;
    gp();
    for(i=2;i<=100000;i++) fenjie(i);
    /*debug
    for(i=2;i<=100000;i++)
    {
        printf("%d的约数为:",i);
        for(j=1;j<=pi[i][0];j++) printf("%d ",pi[i][j]);
        printf("\n");
        printf("%d的次数为:",i);
        for(j=1;j<=pi[i][0];j++) printf("%d ",ki[i][j]);
        printf("\n");
    }
    */
    while(~scanf("%I64d",&n))
    {
        for(i=1;i<=n;i++) scan(a[i]);
        memset(b,0,sizeof(ll)*(n+2));
        ret=1;
        for(i=2;i<=n;i++)
        {
            for(j=1;j<=pi[i][0];j++)
                b[pi[i][j]]+=ki[i][j]*a[i];
        }
        ll cn=0;
        for(i=2;i<=n;i++)
        {
            if(!b[i]) continue;
            zyz[++cn]=i;
            cc[cn]=b[i];
        }
        for(i=1;i<=cn;i++)
        {
            ll tmp=pow(zyz[i],cc[i]*(cc[i]+1)/2);
            for(j=1;j<=cn;j++)
            {
                if(i==j) continue;
                tmp=pow(tmp,1+cc[j]);
            }
            ret=(ret*tmp)%mod;
        }
        printf("%I64d\n",ret);



    }
    return 0;
}