rooanlee
探索云世界
rooanlee
暂无个人介绍
操作系统如何处理IO Linux 会把所有的外部设备都看成一个文件来操作，对外部设备的操作可以看成是对文件的操作。 我们对一个文件的读写，都会通过内核提供的系统调用，内核会给我们返回一个 File Descriptor，这个描述符是一个数字，指向内核的一个结构体，我们应用程序对文件的读写就是对描述符指向的结构体的读写。 系统调用是如何完成IO操作？ Linux 会把内存分为 内核区和用户区。Linux 的内核区会帮我们管理所有的硬件资源，并且会提供系统调用，我们应用程序的读操作，就会通过系统调用 read 发起一个读操作，这个时候，内核就会创建一个文件描述符，通过驱动向硬件发送读指令，并且把读的数据放在描述符指向的结构体的缓冲区中。当这个数据传到用户区的时候，就完成了一次 IO。 Linux 系统调用的 read，是一个阻塞函数。这个我们应用程序在发起read系统调用的时候，就必须要阻塞，进程挂起，等待文件描述符的读就绪。 从上面我们可以知道，应用程序的一个 read系统调用，需要经过： 硬件读取文件数据到文件描述符指向的结构体的缓冲区。 结构体的缓冲区的数据 传输到 用户区。 五种网络 IO 模型 阻塞式 IO 在进行网络IO的时候，进程发起一个 recvform 系统调用，然后进程就会被阻塞，什么也不干，等待上述 所说的 1 和 2步骤完成（也就是硬件读取内容到内核的结构体缓冲区，结构体缓冲区的内容到用户区），最后进程再被处理。大致如下图： 非阻塞式 IO 在上述的 阻塞式 IO中，可以看到，进程在发起了 recvform 系统调用的时候，就会阻塞，那么非阻塞式 IO 和 阻塞式 IO 的一个区别就在这里，它并不会阻塞，而是马上返回一个错误码，进程在得到错误码之后，可以干点别的事情，然后再重复上述的步骤，也就是又发起一个 recvform 系统调用。这个过程就成为轮询。 IO 复用 由上面的非阻塞式IO可以看出，轮询占了很大一部分过程，这个过程会消耗很多CPU时间。这个轮询是由用户区发起的，但是，这个轮询如果是由内核区发起的，那么效率就有提升。IO复用提供了两个 系统调用 ：select 和 poll。select 系统调用是内核级别的，它和 非阻塞式的轮询 有一个区别，就是select 轮询 可以等待多个 socket，任何一个socket 的数据准备好了，那么就可以返回进行读。 select 和 poll调用之后，会阻塞进程，那么这种阻塞进程不同于 第一种 阻塞式IO的阻塞，此时的select不是等到socket数据全部到达后再处理，而是有一部分数据就会调用用户进程处理。 打个比方：钓鱼的时候，雇佣一个帮手，他可以同时抛下多个鱼竿，任何一杆的鱼上钩，他就会拉杆，他只负责帮我们，不负责帮我们处理，所有我们还得在一边等着，等到他拉杆，我们再处理。 如下图: IO复用图 Ps：实际上 select/poll 是落后的，因为 select 的句柄数有限，为1024 个，也就是说，同次检测 1025 个句柄死 是不可能。另外，内核的select是采用轮询的方法，select检测的句柄数越大就会越耗时，这些都是问题。那么epoll就能够解决这些问题，epoll 实际上也是 select/poll 的增强版。 信号驱动式IO 也就是说，数据未准备就绪的时候，那么就进行等待，但是这个等待不会进行轮询，也不会阻塞。而是在某一时刻如果数据准备好了，那么内核会通知进程启动IO操作，将数据从内核区复制到用户区。如下图4 所示：信号驱动式IO图 异步 IO 异步 IO 是指 相当于 信号式驱动 IO 的一个升级版本。异步 IO 是等 内核完成整个操作之后再通过应用程序，这整个过程包括了 硬件读取数据到 内核结构体的缓冲区中，以及缓冲区的数据复制到 用户区中，这整个过程进程都不会阻塞。如下图:异步IO图 总结： 以上就是 操作系统如何处理IO，以及常用的 5种 网络 IO模型。包括（阻塞式IO（java的传统IO），非阻塞式IO（NIO），多路复用IO，信号驱动IO，异步IO）。
Collection 与 List Collection 是 Java 集合的一个根接口，JDK 没有它的实现类。 内部仅仅做 add()，remove()，contains()，size() 等方法的声明。 List 接口是Collection 接口的一个子类，在Collection 基础上扩充了方法。同时可以对每个元素插入的位置进行精确的控制，它的主要实现类有 ArrayList，Vector，LinkedList。 LIST接口实现的类：插入值允许为空，也允许重复。 ArrayLIst ArrayList实现了List接口，意味着可以插入空值，也可以插入重复的值，非同步，它是 基于数组的一个实现。 部分成员变量如下： //默认初始值 private static final int DEFAULT_CAPACITY = 10 //存放数据的数组 transient Object[] elementData; **这里可以看出，elementData提示了是基于数组的实现，DEFAULT_CAPACITY指定了默认容器为10.下面重点理解add()方法，这将有助于理解ArrayList的应用场景和性能消耗：** add() public boolean add(E e){ ensureCapacityInternal(size + 1); elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity){ if(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA){ minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int mincapacity){ modcount++; if(minapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity){ int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if(newCapacity - minCapacity < 0) newCapacity = minCapacity; if((newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); elementData = Arrays.copyOf(elementData, newCapacity); } 这里可以看到，进行一个 add()方法，首先通过 ensureCapacityInternal(size + 1); 判断需不需要扩容;然后再进行 elementData[size++] = e。 插入的时间复杂度O(1)。是非常高效的。（But，这不是在固定位置插入的情况下），如果在固定位置插入，那么代码： public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // Increments modCount!! System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; } System.arraycopy(elementData, index, elementData, index + 1, size - index); 这个可以看出，这时候就是比较低效的了。 那么网上很多说 ArrayList 不适合 增删操作非常多的操作，这是怎么回事呢？首先可以看到这句话： elementData = Arrays.copyOf(elementData, newCapacity); 需要知道的是， Arrays.copyOf 函数的内部实现是再创建一个数组，然后把旧的数组的值一个个复制到新数组中。当经常增加操作的时候，容量不够的时候，就会进行上述的扩容操作，这样性能自然就下来了。或者说，当我们在固定位置进行增删的时候，都会进行 System.arraycopy(elementData, index, elementData, index + 1, size - index); 也是非常低效的。 分析了低效出现的原因，那么我们就可以知道：如果我们需要经常进行特定位置的增删操作，那么最好还是不要用这个了，但是，如果我们基本上没有固定位置的增删操作，最好是要预估数据量的大小，然后再初始化最小容量，这样可以有效的避免扩容。如下代码： ArrayList arrayList = new ArrayList(20); 总结: ArrayList 可以插入空值，也可以插入重复值 ArrayList 是基于数组的时候，所以很多数组的特性也直接应用到了 ArrayList。 ArrayList 的性能消耗主要来源于扩容和固定位置的增删。 ArrayList 创建的时候 需要考虑是否要初始化最小容量，以此避免扩容带来的消耗。 Vector 上述的 ArrayList 不是线程安全的。那么 Vector 就可以看作是 ArrayList 的一个线程安全版本。由于也是实现了 List 接口，所以也是 可以插入空值，可以插入重复的值。 内部成员变量： protected Object[] elementData; public Vector() { this(10); } 可以看到，也是基于 数组的实现，初始化也是 10 个容量。 那么，再来看看 add()方法是否和 ArrayList 相同。 public synchronized boolean add(E e) { modCount++; ensureCapacityHelper(elementCount + 1); elementData[elementCount++] = e; return true; } 可以看到，和 ArrayList 也是一样的，只是加了 synchronized 进行同步， 其实很多其他方法都是通过加 synchronized 来实现同步。 总结: 可以插入空值，也可以插入重复值 也是基于数组的时候，所以很多数组的特性也直接应用到了 VVector。 性能消耗也主要来源于 扩容。 创建的时候 需要考虑是否要初始化最小容量，以此避免扩容带来的消耗。 相当于 ArrayList 的线程安全版本，实现同步的方式 是通过 synchronized。 LinkedList LinkedList 实现了 List 接口，所以LinkedList 也可以放入重复的值，也可以放入空值。LinkedList不支持同步。LinkedList 不同于ArrayList 和Vector，它是使用链表的数据结构，不再是数组。 成员变量： transient int size = 0; //数量 transient Node<E> first; //首节点 transient Node<E> last; //最后节点 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } } 那么，在进行 add() 方法的时候： public boolean add(E e) { linkLast(e); return true; } void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } 当进行增删的时候，只需要改变指针，并不会像数组那样出现整体数据的大规模移动，复制等消耗性能的操作。 ArrayList，Vector，LinkedList 的整体对比 实现方式： ArrayList，Vector 是基于数组的实现。 LinkedList 是基于链表的实现。 同步问题： ArrayList,LinkedList 不是线程安全的。 Vector 是线程安全的，实现方式是在方法中加 synchronized 进行限定。 适用场景和性能消耗： ArrayList 和 Vector 由于是基于数组的实现，所以在固定位置插入，固定位置删除这方面会直接是 O(n)的时间复杂度，另外可能会出现扩容的问题，这是非常消耗性能的。 LinkedList 不会出现扩容的问题，所以比较适合增删的操作。但是由于不是数组的实现，所以在 定位方面必须使用 遍历的方式，这也会有 O(n)的时间复杂度
发表了文章
2016-07-22
发表了文章
2016-07-22
