Posts

题目： You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9'. The wheels can rotate freely and wrap around: for example we can turn '9' to be '0', or '0' to be '9'. Each move consists of turning one wheel one slot. The lock initially starts at '0000', a string representing the state of the 4 wheels. ...

 这篇文章 Predictive CPU isolation of containers at Netflix 是出自 Netflix Technology Blog 现存问题： 应用在云中共享空间内性能隔离。 解决方案： 操作系统级别的方案： Linux CFS（Completely Fair Scheduler）， 公平的方式将正在运行的进程分配给CPU时间片。 方案问题： 应用规模： millions of containers on thousands of machines 。 千台以上的机器上运行百万级别的容器。 组合优化： 数学中 组合优化 combinatorial optimization方法解决， 给定一组K个容器，每个容器在具有d个线程的实例上请求特定数量的CPU，目标是找到大小为（d，K）的二进制分配矩阵M， 使得每个容器获得它请求的CPU的数量。 可以使用的一些策略如： 避免将容器分散到多个NUMA socket； 尽量减少超线程 平衡L3 的缓存压力 减少容器的防止决策的操作 实现： 通过Titus是Netflix的容器平台， 管理容器 使用Linux cgroup实现CFS为每个容器操作的策略。 用户空间通过 titus-isolate Titus子系统定义三个优化时间： add：新增容器； remove：移除完成的容器， rebalance：根据CPU使用率重新评估放置策略； 每次发生时间后， 触发远程查询优化动作， 通过查询GBRT模型， 通过上下文功能 与容器关联的元数据：谁启动它，图像，内存和网络配置，应用程序名称等，以及CPU Accounting Controller（统计cgroup cpu使用情况）来预测未来10分钟内 每个CPU 95%使用率。 使用用cvxpy作为前端，将预测送入MIP（混合整数程序）求解。 服务将放置策略返回主机， 主机通过修改容器的cpusets来执行它。 后续： 支持 CPU超额预定(CPU oversubscription) 利用内核PMC事件来更直接地优化最小的缓存噪声

定义： 并发与并行： 并发（concurrency）:实际上串行发生的事情好像同时发生，表述了单核处理器中线程或者进程的行为特点 并行（parallelism）：并发序列同时执行， 真正的并行只能在多处理其上存在。 异步与同步： 异步（asynchronous）与同步（synchronous）区别在于发需求的人是否需要等到需要完成才可以执行其他事情。 线程安全和可重入： 线程安全：能够被多个线程调用而不会产生灾难性结果，大部分函数可以利用互斥量，条件变量，线程私有数据实现线程安全。 可重入：采用比将函数和库转换为一系列更为复杂方式使得代码成为线程安全。可重入函数应该避免任何静态数据和共享全局数据，避免依赖线程间任何形式的同步。 数据类型： 线程相关数据类型 类型 描述 pthread_t 线程标识符 pthread_mutex_t 互斥量 pthread_spinlock_t 自旋锁 pthread_cond_t 条件变量 pthread_key_t 线程私有数据访问键 pthread_attr_t 线程属性对象 pthread_mutexattr_t 互斥量属性对象 pthread_rwlockattr_t 读写锁属性 pthread_condattr_t 条件变量属性对象 pthread_once_t 一次性初始化属性对象 sigevent 线程通知机制 线程POSIX API： 基本操作 建立与终止 pthread_create pthread_exit 等待 pthread_join 取消 pthread_cancel 线程分离 pthread_detach 获取线程标识符 pthread_self 比较线程标识符 pthread_equal 基本操作 example 建立与终止 pthread_create pthread_exit 等待 pthread_join //线程创建 #include <pthread.h> #include <stdlib.h> #include <stdio.h> void * thread (void *arg) { char *ret; printf ("thread() entered with argument '%s'\n", arg); if ((ret = (char *) malloc (20)) == NULL) { perror ("malloc() error"); exit (2); } strcpy (ret, "This is a test"); pthread_exit (ret); } main () { pthread_t thid; void *ret; if (pthread_create (&thid, NULL, thread, "thread 1") != 0) { perror ("pthread_create() error"); exit (1); } if (pthread_join (thid, &ret) != 0) { perror ("pthread_create() error"); exit (3); } printf ("thread exited with '%s'\n", ret); } [root@centosgpt threaddemo]# ./create thread() entered with argument 'thread 1' thread exited with 'This is a test'. 取消 pthread_cancel //线程取消， 通过pthread_cancel 取消正在运行的线程 #include <errno.h> #include <pthread.h> #include <stdio.h> #include <string.h> #include <unistd.h> #include <stdlib.h> int thstatus; void * thread (void *arg) { puts ("thread has started. now sleeping"); while (1) sleep (1); } main (int argc, char *argv[]) { pthread_t thid; void *status; if (pthread_create (&thid, NULL, thread, NULL) != 0) { perror ("pthread_create failed"); exit (2); } if (pthread_cancel (thid) == -1) { perror ("pthread_cancel failed"); exit (3); } if (pthread_join (thid, &status) == -1) { perror ("pthread_join failed"); exit (4); } if (status == (int *) -1) puts ("thread was cancelled"); else puts ("thread was not cancelled"); exit (0); } [root@centosgpt threaddemo]# ./cancel thread has started. now sleeping thread was cancelled 线程分离 pthread_detach // 线程分离， 线程退出后自动释放资源 #include <stdlib.h> #include <stdio.h> void * thread (void *arg) { char *ret; printf ("thread() entered with argument '%s'\n", arg); if ((ret = (char *) malloc (20)) == NULL) { perror ("malloc() error"); exit (2); } strcpy (ret, "This is a test"); pthread_exit (ret); } main () { pthread_t thid; void *ret; if (pthread_create (&thid, NULL, thread, "thread 1") != 0) { perror ("pthread_create() error"); exit (1); } if (pthread_detach (&thid) != 0) { perror ("pthread_detach() error"); exit (4); } sleep(2); printf ("thread exited with '%s'\n", ret); } [root@centosgpt threaddemo]# ./detach thread() entered with argument 'thread 1' thread exited with '(null)' [root@centosgpt threaddemo]# ./detach pthread_detach() error: Success 获取线程标识符 pthread_self 比较线程标识符 pthread_equal #include <pthread.h> #include <stdio.h> pthread_t thid, IPT; void * thread (void *arg) { if (pthread_equal (IPT, thid)) puts ("the thread is the IPT...?"); else puts ("the thread is not the IPT"); } main () { IPT = pthread_self (); if (pthread_create (&thid, NULL, thread, NULL) != 0) { perror ("pthread_create() error"); exit (1); } if (pthread_join (thid, NULL) != 0) { perror ("pthread_create() error"); exit (3); } } [root@centosgpt threaddemo]# ./self the thread is not the IPT [root@centosgpt threaddemo]# 私有数据 私有数据创建 pthread_key_create pthread_key_delete 私有数据使用 pthread_setspecific pthread_getspecific 私有数据 example 私有数据创建 pthread_key_create pthread_key_delete 私有数据使用 pthread_setspecific pthread_getspecific #include <stdio.h> #include <stdlib.h> #include <errno.h> #include <pthread.h> #define threads 3 #define BUFFSZ 48 pthread_key_t key; void * threadfunc (void *parm) { int status; void *value; int threadnum; int *tnum; void *getvalue; char Buffer[BUFFSZ]; tnum = parm; threadnum = *tnum; printf ("Thread %d executing\n", threadnum); if (!(value = malloc (sizeof (Buffer)))) printf ("Thread %d could not allocate storage, errno = %d\n", threadnum, errno); sprintf (value, "Thread %d executing\n", threadnum); status = pthread_setspecific (key, (void *) value); if (status < 0) { printf ("pthread_setspecific failed, thread %d, errno %d", threadnum, errno); pthread_exit ((void *) 12); } printf ("Thread %d setspecific value: %d\n", threadnum, value); getvalue = 0; getvalue = pthread_getspecific (key); if (status < 0) { printf ("pthread_getspecific failed, thread %d, errno %d", threadnum, errno); pthread_exit ((void *) 13); } printf("key = %s\n", getvalue); if (getvalue != value) { printf ("getvalue not valid, getvalue=%d", (int) getvalue); pthread_exit ((void *) 68); } pthread_exit ((void *) 0); } void destr_fn (void *parm) { printf ("Destructor function invoked\n"); free (parm); } main () { int getvalue; int status; int i; int threadparm[threads]; pthread_t threadid[threads]; int thread_stat[threads]; if ((status = pthread_key_create (&key, destr_fn)) < 0) { printf ("pthread_key_create failed, errno=%d", errno); exit (1); } for (i = 0; i < threads; i++) { threadparm[i] = i + 1; status = pthread_create (&threadid[i], NULL, threadfunc, (void *) &threadparm[i]); if (status < 0) { printf ("pthread_create failed, errno=%d", errno); exit (2); } } for (i = 0; i < threads; i++) { status = pthread_join (threadid[i], (void *) &thread_stat[i]); if (status < 0) { printf ("pthread_join failed, thread %d, errno=%d\n", i + 1, errno); } if (thread_stat[i] != 0) { printf ("bad thread status, thread %d, status=%d\n", i + 1, thread_stat[i]); } } exit (0); } [root@centosgpt threaddemo]# ./key Thread 1 executing Thread 2 executing Thread 1 setspecific value: -1140848448 key = Thread 1 executing Thread 2 setspecific value: -1275066176 key = Thread 2 executing Thread 3 executing Thread 3 setspecific value: -1207957312 key = Thread 3 executing Destructor function invoked Destructor function invoked Destructor function invoked 同步： 互斥量 互斥量创建与销毁 pthread_mutex_init pthread_mutex_destroy 加锁解锁互斥量（阻塞） pthread_mutex_lock pthread_mutex_unlock 加锁解锁互斥量（非阻塞） pthread_mutex_trylock 互斥变量优先级上限 pthread_mutex_getprioceiling pthread_mutex_setprioceiling 互斥量 example 互斥量创建与销毁： pthread_mutex_init pthread_mutex_destroy 加锁解锁互斥量（阻塞） pthread_mutex_lock pthread_mutex_unlock ## 阻塞模式 pthread_mutex_lock #include <pthread.h> #include <stdio.h> #include <errno.h> #include <stdlib.h> pthread_mutex_t mutex; void * thread (void *arg) { if (pthread_mutex_lock (&mutex) != 0) { perror ("pthread_mutex_lock() error"); exit (1); } puts ("thread was granted the mutex"); if (pthread_mutex_unlock(&mutex) != 0) { perror("pthread_mutex_unlock() error"); exit(2); } } main () { pthread_t thid; if (pthread_mutex_init (&mutex, NULL) != 0) { perror ("pthread_mutex_init() error"); exit (2); } if (pthread_create (&thid, NULL, thread, NULL) != 0) { perror ("pthread_create() error"); exit (3); } if (pthread_mutex_lock (&mutex) != 0){ perror ("pthread_mutex_lock() error"); exit (4); } puts ("IPT was granted the mutex"); if (pthread_mutex_unlock(&mutex) != 0) { perror("pthread_mutex_unlock() error"); exit(2); } if (pthread_join (thid, NULL) != 0) { perror ("pthread_mutex_trylock() error"); exit (5); } if (pthread_mutex_destroy(&mutex) != 0) { perror("pthread_mutex_destroy() error"); exit(2); } } [root@centosgpt threaddemo]# ./mutexb IPT was granted the mutex thread was granted the mutex 加锁解锁互斥量（非阻塞） pthread_mutex_trylock ### 非阻塞模式 #include <pthread.h> #include <stdio.h> #include <errno.h> #include <stdlib.h> pthread_mutex_t mutex; void * thread (void *arg) { int rc; while (1){ if ((rc=pthread_mutex_trylock (&mutex))!=0){ if (rc == EBUSY){ puts ("thread was denied access to the mutex"); continue; } else { perror ("sub pthread_mutex_trylock() error"); exit (1); } puts ("sub thread can do other thing"); } else { puts ("thread was granted the mutex"); break; } } if (pthread_mutex_unlock(&mutex) != 0) { perror("pthread_mutex_unlock() error"); exit(2); } } main () { pthread_t thid; int rc; if (pthread_mutex_init (&mutex, NULL) != 0) { perror ("pthread_mutex_init() error"); exit (2); } if (pthread_create (&thid, NULL, thread, NULL) != 0) { perror ("pthread_create() error"); exit (3); } while(1){ if ((rc=pthread_mutex_trylock (&mutex)) != 0){ if (rc == EBUSY){ puts ("IPT was denied access to the mutex"); continue; } else { perror ("main pthread_mutex_trylock() error"); exit (4); } puts ("main thread can do other thing"); } else { puts ("IPT was granted the mutex"); break; } } if (pthread_mutex_unlock(&mutex) != 0) { perror("pthread_mutex_unlock() error"); exit(2); } if (pthread_join (thid, NULL) != 0) { perror ("pthread_mutex_trylock() error"); exit (5); } if (pthread_mutex_destroy(&mutex) != 0) { perror("pthread_mutex_destroy() error"); exit(2); } } [root@centosgpt threaddemo]# ./mutex IPT was granted the mutex thread was denied access to the mutex thread was granted the mutex 互斥变量优先级上限 pthread_mutex_getprioceiling pthread_mutex_setprioceiling 依赖于互斥锁属性的协议的设置 ...

问题： 在实际编译运行 什么是RCU ：API 中的例子 **rcu_example**时报错 [root@centosgpt rcu]# insmod list_rcu.ko insmod: ERROR: could not insert module list_rcu.ko: Unknown symbol in module [root@centosgpt rcu]# dmesg|tail [13084.720516] list_rcu: Unknown symbol synchronize_rcu (err -2) [13084.720561] list_rcu: Unknown symbol call_rcu (err -2) 原因： 在写代码的时候漏掉了原来例子中的 MODULE_LICENSE(“GPL”); __class_create函数仅为 GPL模块导出（标记为使用 EXPORT_SYMBOL_GPL导出）的模块， 需要使用MODULE_LICENSE(“GPL”)，才能使用相关功能。 /kernel/rcu/tree.c ... void synchronize_rcu(void) { RCU_LOCKDEP_WARN(lock_is_held(&rcu_bh_lock_map) || lock_is_held(&rcu_lock_map) || lock_is_held(&rcu_sched_lock_map), "Illegal synchronize_rcu() in RCU read-side critical section"); if (rcu_blocking_is_gp()) return; if (rcu_gp_is_expedited()) synchronize_rcu_expedited(); else wait_rcu_gp(call_rcu); } EXPORT_SYMBOL_GPL(synchronize_rcu); ... void call_rcu(struct rcu_head *head, rcu_callback_t func) { __call_rcu(head, func, -1, 0); } EXPORT_SYMBOL_GPL(call_rcu); 参考： How to Resolve – insmod: ERROR: could not insert module hello.ko: Unknown symbol in module – unknown symbol class_unregister ...

题目： Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Example 1: Input: 11110 11010 11000 00000 Output: 1 Example 2: Input: 11000 11000 00100 00011 Output: 3 解题： ‘1’ 未访问的位置， ‘v’ 访问的位置 ，‘0’ 水面 ...

这篇文章 RCU part 3: the RCU API 作者： Paul E. McKenney, IBM Linux Technology Center 做为 “What is RCU”系列文章的最后一篇， 第三篇文章主要介绍了RCU API设计 基本操作 rcu_read_lock() 读者在读取由RCU保护的共享数据时使用该函数标记它进入读端临界区。 rcu_read_unlock() 该函数与rcu_read_lock配对使用，用以标记读者退出读端临界区。 synchronsize_rcu() 该函数由RCU写端调用，它将阻塞写者，直到经过grace period后，即所有的读者已经完成读端临界区，写者才可以继续下一步操作。 call_rcu() 写端调用不会阻塞 链表操作 list_for_each_entry_rcu（） 链表遍历 list_add_rcu() list_add_tail_rcu() list_del_rcu() list_replace_rcu() list_splice_init_rcu() 链表更新 作者对RCU判断是会在 the reader-writer-locking（读写锁）, reference-counting（引用技术）, and existence-guarantee constructs（存在保证结构）有更多的扩展。 更新 文章中列的API后续又更新到2010，2014，2019版本。 实验 rcu_example 是GitHub一个关于RCU调用的代码。 参考 Linux 2.6内核中新的锁机制–RCU

题目： Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called “Ring Buffer”. One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values. ...

方法： 1 bc命令 [root@centosgpt ~]# echo “ibase=16; FF” |bc 255 2. bash [root@centosgpt ~]# echo $((0xFF)) 255 3. printf [root@centosgpt ~]# printf “%d\n” 0xFF 255 4. dc [root@centosgpt ~]# dc -e ‘16i FF p’ 255 限制： 其中bc，dc 可以不受整数位数限制 如：64-bit integer limit of 2^64， 当大于64位时验证下各个脚本的处理结果 1 bc [root@centosgpt ~]# echo “ibase=16; 7FFFFFFFFFFFFFFFF” |bc 147573952589676412927 2 echo [root@centosgpt ~]# echo $((0x7FFFFFFFFFFFFFFFF)) -1 3. printf [root@centosgpt ~]# printf “%ld\n” 0x7FFFFFFFFFFFFFFFF -bash: printf: warning: 0x7FFFFFFFFFFFFFFFF: Numerical result out of range 9223372036854775807 ...

这篇文章 What is RCU? Part 2: Usage 作者： Paul E. McKenney, IBM Linux Technology Center ， 这篇文章主要通过与几以下几类机制的比较，深入对RCU进行了分析： RCU与读写锁机制； RCU是一种严格引用计数机制 Restricted Reference-Counting Mechanism RCU与GC机制； RCU与Existence guarantees（出自论文Gamsa等。[PDF]） RCU是一种事件等待机制； RCU优势： 性能优势：实验中与读写机制rwlock比较， 随着CPU增加RCU CPU开销没有明显增长； 死锁免疫（Deadlock Immunity）：由于读取端没有阻塞， 理论上不会有死锁。 实时性、低延时：同样也是由于RCU读端的不阻塞，使他有更出色的实时性和低延时。 RCUreader与updater同时运行 rwlock保证读者总是读到更新后的数据， 但是作者也提到了现实中类似路由表的应用， 对于旧数据影响并时不时很大，而rwlock这种机制也依赖于reader/writer优先级的设定 可以方便的替换rwlock 1 struct el { 1 struct el { 2 struct list_head list; 2 struct list_head list; 3 long key; 3 long key; 4 spinlock_t mutex; 4 spinlock_t mutex; 5 int data; 5 int data; 6 /* Other data fields */ 6 /* Other data fields */ 7 }; 7 }; 8 rwlock_t listmutex; 8 spinlock_t listmutex; 9 struct el head; 9 struct el head; 1 int search(long key, int *result) 1 int search(long key, int *result) 2 { 2 { 3 struct list_head *lp; 3 struct list_head *lp; 4 struct el *p; 4 struct el *p; 5 5 6 read_lock(&listmutex); 6 rcu_read_lock(); 7 list_for_each_entry(p, head, lp) { 7 list_for_each_entry_rcu(p, head, lp) { 8 if (p->key == key) { 8 if (p->key == key) { 9 *result = p->data; 9 *result = p->data; 10 read_unlock(&listmutex); 10 rcu_read_unlock(); 11 return 1; 11 return 1; 12 } 12 } 13 } 13 } 14 read_unlock(&listmutex); 14 rcu_read_unlock(); 15 return 0; 15 return 0; 16 } 16 } 1 int delete(long key) 1 int delete(long key) 2 { 2 { 3 struct el *p; 3 struct el *p; 4 4 5 write_lock(&listmutex); 5 spin_lock(&listmutex); 6 list_for_each_entry(p, head, lp) { 6 list_for_each_entry(p, head, lp) { 7 if (p->key == key) { 7 if (p->key == key) { 8 list_del(&p->list); 8 list_del_rcu(&p->list); 9 write_unlock(&listmutex); 9 spin_unlock(&listmutex); 10 synchronize_rcu(); 10 kfree(p); 11 kfree(p); 11 return 1; 12 return 1; 12 } 13 } 13 } 14 } 14 write_unlock(&listmutex); 15 spin_unlock(&listmutex); 15 return 0; 16 return 0; 16 } 17 } example taken from Wikipedia. 可以方便的替换rwlock 参考计数机制 Reference-Counting Mechanism：看上去和rwlock模式一致 1 rcu_read_lock(); /* acquire reference. */ 2 p = rcu_dereference(head); 3 /* do something with p. */ 4 rcu_read_unlock(); /* release reference. */ 1 spin_lock(&mylock); 2 p = head; 3 head = NULL; 4 spin_unlock(&mylock); 5 synchronize_rcu(); /* Wait for all references to be released. */ 6 kfree(p); 但是由于要求读不阻塞， 所以在与rwlock进行性能比较时大概在4个cpu时rcu与rwlock的cpu开销已经趋于一致。 ...

定义： ELF： Executable and Linkable Format ELF文件常见的三种文件类型： relocatable （可重定位） executable（可执行） shared object（共享目标） core dumps (核心转储) [root@centosgpt 10]# file process.oprocess.o: ELF 64-bit LSB relocatable, x86-64, version 1 (SYSV), not stripped[root@centosgpt 10]# file dynamiccreateprocessdynamiccreateprocess: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked (uses shared libs), for GNU/Linux 2.6.32, BuildID[sha1]=d6fa7d670a47b7aaf05d17c92c82508bcabc48dc, not stripped[root@centosgpt 10]# file libdynamicprocess.solibdynamicprocess.so: ELF 64-bit LSB shared object, x86-64, version 1 (SYSV), dynamically linked, BuildID[sha1]=0a9fb4457819ecf54d9762f3aff5eda0c19600fc, not stripped 组成： ELF header program header table section header table binary data 常用的elf文件分析工具， readelf， objdump， nm， hexdump ...