ARTS-week21

发表于 分类于 本文字数： 2.3k 阅读时长 ≈ 2 分钟

Algorithms

Single Number
思路: 位操作。

1
2
3
4
5
6
7
8
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (auto num : nums) res ^= num;
        return res;
    }
};

Linked List Cycle
思路: 快慢指针。

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) {
            return false;
        }
        ListNode *slow = head;
        ListNode *fast = head;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

Review

本周阅读英文文章:
“The Pragmatic Programmer” Is Essential Reading for Software Developers

Keep it Simple, Stupid!

Technique

《Linux/Unix系统编程手册》文件加锁

1.劝告式和强制式加锁

在默认情况下，文件锁是劝告式的，这表示一个进程可以简单地忽略另一个进程在文件上放置的锁。要使得劝告式加锁模型能够正常工作，所有访问文件的进程都必须要配合，即在执行文件I/O之前首先需要在文件上放置一把锁。与之对应，强制式加锁系统会强制一个进程在执行I/O时需要遵从其他进程持有的锁。

在使用劝告式锁时，应用程序设计需要:
1)为文件设置合适的所有权(或组所有权)和权限以防止非协作进程执行文件I/O;
2)通过在执行I/O之前获取恰当的锁来确保构成应用程序的进程相互协作。

如果在一个文件上启用强制式加锁时，那么执行数据传输的系统调用(如read()或write())在碰到锁冲突(即在当前被读或写操作锁住的区域上执行一个写入操作或在当前被写锁住的区域上执行一个读操作)时，取决于阻塞模式还是非阻塞模式打开文件。如果以阻塞模式打开文件，系统调用就会阻塞，未指定O_NONBLOCK时，那么I/O系统调用可能会导致死锁情形出现。如果在打开文件时，使用了O_NONBLOCK标记，那么系统调用就会立即失败并返回EAGAIN错误。

如果存在进程持有了一个文件任意部分上的强制式读锁或者写锁，那么就无法在该文件上创建一个共享内存映射(即mmap()指定了MAP_SHARED标记)。同样，如果一个文件参与了一个共享内存映射，那么就无法在该文件任意部分上放置一把强制式锁。

2./proc/locks文件

通过Linux特有的/proc/locks文件中的内容能够查看系统中当前存在的锁，显示了flock()和fcntl()创建的锁的信息。 

1
2
3
4
5
6
$ cat /proc/locks 
1: FLOCK  ADVISORY  WRITE 1759 00:12:1026 0 EOF
2: POSIX  ADVISORY  WRITE 1748 00:12:907 0 EOF
3: FLOCK  ADVISORY  WRITE 1162 fd:01:124961 0 EOF
4: FLOCK  ADVISORY  WRITE 1162 fd:01:124955 0 EOF
5: FLOCK  ADVISORY  WRITE 1162 fd:01:124951 0 EOF

每个锁的8个字段的含义:
1.锁在该文件上所有锁中的序号。
2.锁的类型。其中FLOCK表示是由flock()创建的锁，POSIX表示fcntl()创建的锁。
3.锁的模式。其值是ADVISORY或MANDATORY。ADVISORY: 仅阻止其他进程进行加锁，不会阻止其他进程进行文件的读写；MANDATORY: 加锁期间，其他进程不能再加锁，也不能进程读写。
4.锁的类型。其值是READ或WRITE(对应于fcntl()的共享锁和互斥锁)。
5.持有锁的进程的进程ID。
6.三个用冒号分隔的数字，他们标识出了锁所属的文件。这些数字是文件所处的文件系统的主要和次要设备号，后面跟着文件的i-node号。
7.锁的起始字节。对于flock()锁来讲，其值永远是0。
8.锁的结尾字节。其中EOF表示锁延伸到文件的结尾(即对于fcntl()创建的锁来讲是将l_len指定为0)。对于flock()锁来讲，这一列值永远是EOF。

Share

最近在读《C语言程序设计现代方法》第二版，重新温习一遍C语言的基础知识。和其他书比，这本书的优点还是很多的，比如注重代码风格、每章结尾的Q&A很友好，会解答一些学习中遇到的问题、习题也是不错的。”温故而知新”，挺好。