题目： Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1: Input: n = 12 Output: 3 Explanation: 12 = 4 + 4 + 4. Example 2: Input: n = 13 Output: 2 Explanation: 13 = 4 + 9. 解题1： 数学方式的解法：基于四平方和理论（Lagrange’s four-square theorem）， 每个正整数均可表示为4个整数的平方和。 1. 如果整数包含因子4， 可以去掉不影响结果； 2. 如果除8余7的话， 肯定是由四个完全平方数组成； 3. 之后按照两个数的平方和拆解整数， 其中！！逻辑取反判断是否正整数还是0， 正整数！！后为1， 0！！后为0； ...
Linux task_struct 结构中 涉及进程状态的属性有三个，其中进程对应的状态分为两类， 一类是运行中状态， 另一类是进程退出状态。
这篇文章 Delightful User Interfaces: Easter Eggs 是出自 Netflix Technology Blog
在上网下载镜像或安装文件时经常会看到MD5,SHA-1,SHA-256 ，signature，一起显示，这些文件帮助我们验证下载的文件是否损坏或者被篡改以及文件的真实性， 散列值可以使用windows， macOS，Linux内置命令进行验证。 文件签名可以使用工具gpg进行校验。
题目： 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 Techno
定义： 并发与并行： 并发（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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 //线程创建 #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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 //线程取消， 通过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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 // 线程分离， 线程退出后自动释放资源 #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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 #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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 #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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 ## 阻塞模式 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 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 ### 非阻塞模式 #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时报错
题目： 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: 1 2 3 4 5 6 7 Input: 11110 11010 11000 00000 Output: 1 Example 2: Input: 11000 11000 00100 00011 Output: 3 ...
详解 Linux 内核 RCU 的 API 接口和使用方法