Arts

题目： Implement the following operations of a stack using queues. push(x) – Push element x onto stack. pop() – Removes the element on top of the stack. top() – Get the top element. empty() – Return whether the stack is empty. Example: MyStack stack = new MyStack(); stack.push(1); stack.push(2); stack.top(); // returns 2 stack.pop(); // returns 2 stack.empty(); // returns false Notes: You must use only standard operations of a queue – which means only push to back, peek/pop from front, size, and is empty operations are valid. Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue. You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack). 解题： 本地使用queue实现一个stack的功能， queue特点是先进先出， stack的特点是先进后出 ...

调度定义 wiki上的关于scheduler的定义: In computing, scheduling is the method by which work is assigned to resources that complete the work. The work may be virtual computation elements such as threads, processes or data flows, which are in turn scheduled onto hardware resources such as processors, network links or expansion cards. 在计算机领域里，调度是一种将任务分配给完成任务的资源的方法。 任务可能是虚拟计算元素，例如线程，进程或数据流，这些虚拟计算元素又被安排在硬件资源（例如处理器，网络链接或扩展卡）上。 任务的分类: 对于要调度的任务分类: 按照依赖资源： CPU-bound: 任务处理效率受CPU处理速度的影响; I/O-bound: 任务处理效率受I/O处理速度的影响; 按照执行特点: Interactive: 交互式,如shell. Batch: 后台服务式，不需要与用户交互的 ，如数据库引擎. Real-Time: 及时响应式. 调度目标 所有系统 ...

这篇文章 Timers and time management in the Linux kernel. Part 3. 是出自 linux-insides一书中 Timers and time management 章节 The tick broadcast framework and dyntick 内核版本比对5.3-rc8 进行了相关调整, 增加相关备注 Linux内核中的定时器和时间管理.Part 3. tick broadcast框架和dyntick 这是本章 的第三部分，他描述了定时器和时间管理的相关内容，前一部分我们讲到了 clocksource框架. 我们已经开始考虑这个框架，因为它与Linux内核提供的特殊计数器密切相关。在本章的第一部分 已经看到了其中的一个 - jiffies. 正如我在本章的第一部分已经写过的那样，我们将在Linux内核初始化期间逐步考虑与时间管理相关的内容。之前章节调用: register_refined_jiffies(CLOCK_TICK_RATE); 这个函数定义在 kernel/time/jiffies.c 文件中, 并初始化变量 refined_jiffies 时钟源. 被setup_arch 调用， setup_arch定义在arch/x86/kernel/setup.c中,并执行特定于体系结构的(以x86_64 为例)初始化。 查看setup_arch的实现，您将注意到register_refined_jiffies的调用是setup_arch函数完成其工作之前的最后一步。 在setup_arch执行结束后，已经配置了许多不同的x86_64特定的东西。 例如，一些早期interrupt处理程序已经能够处理中断, 为initrd保留的内存空间，DMI扫描，Linux内核日志缓冲区已经设置，这意味着printk函数能够工作，e820的解析，Linux内核已经知道可用内存和许多其他架构特定的东西(如果你感兴趣，您可以在本书的第二章章节中阅读有关setup_arch函数和Linux内核初始化过程的更多信息。 现在，setup_arch完成了它的工作，我们可以回到通用Linux内核代码。回想一下setup_arch函数是从start_kernel函数调用的，该函数在init/ main.c源代码文件中定义。所以，我们将回到这个功能。您可以看到在start_kernel函数内部的setup_arch函数之后有很多不同的函数被调用，但由于我们的章节专门讨论定时器和时间管理相关的部分，我们将跳过所有与此无关的代码话题。与Linux内核中的时间管理相关的第一个函数是： tick_init(); 在start_kernel中。 tick_init函数在kernel/time/tick-common.c源代码文件中定义，做两件事： 初始化tick broadcast框架相关的数据结构; 初始化full tickless模式相关的数据结构。 我们在本书中没有看到与tick broadcast框架相关的任何内容，并且对Linux内核中的tickless模式一无所知。因此，这一部分的要点是研究这些概念并了解它们是什么。 The idle process 首先看下tick_init函数的实现. 正如之前说得这个函数定义在 kernel/time/tick-common.c 源码文件中，由以下两个函数组成: void __init tick_init(void) { tick_broadcast_init(); tick_nohz_init(); } 正如您从段落标题中可以理解的那样，我们现在只对tick_broadcast_init函数感兴趣。 此函数在kernel/time/tick-broadcast.c源代码文件中定义并执行初始化 tick broadcast框架相关的数据结构。 在我们查看tick_broadcast_init函数的实现之前，我们将尝试了解这个函数的作用，我们需要了解tick broadcast框架。 ...

题目： Implement the following operations of a queue using stacks. push(x) – Push element x to the back of queue. pop() – Removes the element from in front of queue. peek() – Get the front element. empty() – Return whether the queue is empty. Example: MyQueue queue = new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false Notes: You must use only standard operations of a stack – which means only push to top, peek/pop from top, size, and is empty operations are valid. Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack. You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue). 解题： 本地使用stack实现一个queue的功能， queue特点是先进先出， stack的特点是先进后出 ...

安装 环境： cenos7， X86_64 kernel： 3.10.0-862.el7.x86_64 依赖安装包 1） graphviz, perl-ExtUtils-MakeMaker yum install graphviz yum install perl-ExtUtils-MakeMaker 2） 通过cpan进行安装 perl-CPAN.noarch yum install perl-CPAN 3） 运行cpan cpan> install Graph::Easy ... Reading '/root/.cpan/sources/modules/03modlist.data.gz' DONE Writing /root/.cpan/Metadata Graph::Easy is up to date (0.76). 下载安装包安装 1） 通过https://metacpan.org查找,Graph::Easy下载, 验证时需要安装 Test::More wget https://cpan.metacpan.org/authors/id/S/SH/SHLOMIF/Graph-Easy-0.76.tar.gz wget https://cpan.metacpan.org/authors/id/E/EX/EXODIST/Test-Simple-1.302168.tar.gz 2） 编译 $ tar -zxvf Test-Simple-1.302167.tar.gz $ cd Test-Simple-1.302167 $ make install $ tar -zxvf Graph-Easy-0.76.tar.gz $ perl Makefile.PL $ make test $ make install demo 画个图验证一下 ...

概述 Linux2.6.23版本引入了CFS调度器,通过sched_child_runs_first设置是否子进程优先运行, 下面是 SUSE Documentation 关于此参数的说明: A freshly forked child runs before the parent continues execution. Setting this parameter to 1 is beneficial for an application in which the child performs an execution after fork. For example make -j performs better when sched_child_runs_first is turned off. The default value is 0. make -j<cpu个数>支持并行编译 设置这个参数后子进程会优先在父进程前执行. 验证 使用The Linux Programming Interface中的例子: fork_whos_on_first.c, fork_whos_on_first.count.awk 来验证一下: ... int main (int argc, char *argv[]) { ... for (j = 0; j < numChildren; j++) { switch (childPid = fork ()) { case -1: exit(-1); case 0: getpid(); printf ("%d child\n", j); _exit (EXIT_SUCCESS); default: getpid(); printf ("%d parent\n", j); wait (NULL); /* Wait for child to terminate */ break; } } exit (EXIT_SUCCESS); } sysctl -w kernel.sched_child_runs_first=1 ./fork_whos_on_first 10000 > fork.txt awk -f ./fork_whos_on_first.count.awk fork.txt All done parent 99983 99.98% child 17 0.02% 虽然设置了 sched_child_runs_first, 并不是子进程每次都能先于父进程被调度。 ...

这篇文章 The Linux Scheduler作者Moshe Bar发表在linuxjournal, 是一篇2000年的文章.从Linux版本时间线可以看到,那时Linux内核版本2.2, 过了一年后2001正式发布2.4版本 图片来源wiki/Linux内核 正文 了解内核如何为单处理器和多处理器计算机调度任务。 上个月，我们开始了一个关于Linux内核内部的新系列。 在第一部分中，我们研究了Linux如何管理流程以及为什么Linux在许多方面比许多商业UNIX系统更好地创建和维护流程。 这一次，我们详细讨论了调度问题。 令我惊讶的是，在这里，Linux走向非传统的方式，无视核心理论中的传统智慧。 结果非常好。 我们来看看如何。 调度类 在Linux 2.2.x中有三类进程，从调度程序的数据定义可以看出（来自linux/include/linux/sched.h）： 调度策略 #define SCHED_OTHER 0 #define SCHED_FIFO 1 #define SCHED_RR 2 SCHED_OTHER任务是正常的用户任务（默认）。 在SCHED_FIFO中运行的任务永远不会被抢占。它们将仅在等待同步内核事件或者如果已从用户空间请求显式睡眠或重新调度,释放CPU资源。 在SCHED_RR中运行的任务是实时(RT)的 ，但如果运行队列中有另一个实时任务，它们将离开CPU。因此CPU资源将在所有SCHED_RR任务之间分配。如果至少有一个实时任务正在运行，则不允许在任何CPU中运行其他SCHED_OTHER任务。每个实时任务都有一个rt_priority，因此允许SCHED_RR类随意在所有SCHED_RR任务之间分配CPU资源。 SCHED_RR类的rt_priority与SCHED_OTHER（默认）类的普通优先级字段完全相同。 只有root用户才能通过sched_setscheduler系统调用更改当前任务的类。 内核的任务之一是确保即使在异常进程的情况下系统仍然处于其控制之下。一个这样异常的程序可能会过快地fork太多进程。因此，内核变得如此忙碌以至于无法满足其他职责。我发现Linux对用户态程序生成子进程的速度没有限制。 HP-UX，Solaris和AIX每个处理器的时间限制(tick)为一个fork（在Linux下称为jiffie）。清单1中的补丁（请参阅参考资料）将允许每个jiffie最多一个fork（一个jiffie通常是1/100秒，除了Alpha架构，它是1/1024）。 文中提到的清单1 （稍微调整了下格式） 2.3.26/kernel/fork.c Thu Oct 28 22:30:51 1999 +++ /tmp/fork.c Tue Nov 9 01:34:36 1999 @@ -591,6 +591,14 @@ int retval = -ENOMEM; struct task_struct *p; DECLARE_MUTEX_LOCKED(sem); + static long last_fork; + while (time_after(last_fork+1, jiffies)) + { + __set_current_state(TASK_INTERRUPTIBLE); + schedule_timeout(1); + } + last_fork = jiffies; if (clone_flags & CLONE_PID) { /* This is only allowed from the boot up thread */ 个人理解,如果last_fork+1>jiffies说明当前进程在1个jiffie内创建,设置进程休眠,类似delay功能(这个地方也不是很确认:(, 后续需要再验证一下) ...

问题 由于Windows与Linux对换行的定义不同,导致Windows应用不能正常按行显示Linux文本，Linux显示Windows文本时会带有^M 解决方法 下面整理一些常用的工具和处理方法: ftp : 服务端支持ASCII模式，使用ftp命令可以实现文本换行之间的转换。(由于ASCII存在一些安全隐患，所以部分ftp服务默认关闭ASCII模式传输)。 vi/vim: :%s/^M//g ^M: ctrl+v, ctrl+m awk: awk '{ sub("\r$", ""); print }' windows.txt > linux.txt awk 'sub("$", "\r")' linux.txt > windows.txt tr: tr -d '\r' < windows.txt > linux.txt sed: $ sed -e 's/$/\r/' linux.txt > windows.txt $ sed -e 's/\r$//' windows.txt > linux.txt perl $ perl -pe 's/\r?\n|\r/\r\n/g' test.txt > windows.txt $ perl -pe 's/\r?\n|\r/\n/g' test.txt > linux.txt $ perl -pe 's/\r?\n|\r/\r/g' test.txt > mac.txt test.txt可以是windows也可以是linux 相关其他命令 file $ file windows.txt windows.txt: ASCII text, with CRLF line terminators $ file linux.txt linux.txt: ASCII text $ file mac.txt mac.txt: ASCII text, with CR line terminators od $ od -a windows.txt 0000000 t e s t cr nl $ od -a linux.txt 0000000 t e s t nl cat $ cat -e windows.txt test^M$ $ cat -e linux.txt test$ hexdump $ hexdump -c windows.txt 0000000 t e s t \r \n $ hexdump -c linux.txt 0000000 t e s t \n

awk中的’数组‘是一种关联数组，又称作maps、字典，他的索引不需要连续， 可以使用字符串、数字做为索引， 此外，不需要事先声明数组的大小 - 数组可以在运行时扩展/收缩。 语法： 赋值： array_name[index] = value 删除： delete array_name[index] 多维数组(使用字符串模拟) array["0,0"] = 100 遍历： for (var in arrayname) actions 实例 统计汇总 数据：Iplogs.txt 180607 093423 123.12.23.122 133 180607 121234 125.25.45.221 153 190607 084849 202.178.23.4 44 190607 084859 164.78.22.64 12 200607 012312 202.188.3.2 13 210607 084849 202.178.23.4 34 210607 121435 202.178.23.4 32 210607 132423 202.188.3.2 167 total.awk: { Ip[$3]++; } END { for (var in Ip) print var, "access", Ip[var]," times" } 注意下END后的{需要和END在一行 输出: $ awk -f total.awk Iplogs.txt 123.12.23.122 access 1 times 164.78.22.64 access 1 times 202.188.3.2 access 2 times 125.25.45.221 access 1 times 202.178.23.4 access 3 times 说明: $3是一个IP地址, Ip做为数组的索引。 对于每一行，它会增加相应IP地址索引的值。 最后在END部分中，所有索引都将是唯一IP地址的列表，其对应的值是出现次数。 ...

FTP ASCII 上传失效 近期在进行AIX到Linux迁移，发现从windows终端ftp时，客户端设置ASCII传输模式, 服务端并不能自动转换换行符号,脚本出现^M,需要手工删除。 Linux环境为RedHat7.3+vsftpd(3.0.2),vsftpd.conf中ascii_download_enable/ascii_upload_enable 注释掉了,未开启. RFC959中的ASCII TYPE 3.1.1.1. ASCII TYPE This is the default type and must be accepted by all FTP implementations. It is intended primarily for the transfer of text files, except when both hosts would find the EBCDIC type more convenient. The sender converts the data from an internal character representation to the standard 8-bit NVT-ASCII representation (see the Telnet specification). The receiver will convert the data from the standard form to his own internal form. In accordance with the NVT standard, the <CRLF> sequence should be used where necessary to denote the end of a line of text. (See the discussion of file structure at the end of the Section on Data Representation and Storage.) Using the standard NVT-ASCII representation means that data must be interpreted as 8-bit bytes. 使用ASCII模式进行ftp传输时， 会把发送端本地NewLine编码， 转为NVT-ASCII格式（ ）， 接收端收到后，再转为本地NewLine编码。 ...