网站建设合同的主要内容手机网速

当前位置： 首页 > news >正文

网站建设合同的主要内容,手机网速,网站开发需要干什么,广告联盟推荐PriorityBlockingQueue无界阻塞优先级队列 PriorityBlockingQueue 是带优先级的无界阻塞队列#xff0c;每次出队都返回优先级最高的元素#xff0c;是二叉树最小堆的实 现#xff0c;研究过数组方式存放最小堆节点的都知道#xff0c;直接遍历队列元素是无序的。 如图 P…  PriorityBlockingQueue无界阻塞优先级队列  PriorityBlockingQueue 是带优先级的无界阻塞队列每次出队都返回优先级最高的元素是二叉树最小堆的实 现研究过数组方式存放最小堆节点的都知道直接遍历队列元素是无序的。  如图 PriorityBlockingQueue 内部有个数组 queue 用来存放队列元素size 用来存放队列元素个数allocationSpinLockOffset是用来在扩容队列时候做cas的目的是保证只有一个线程可以进行扩容。  由于这是一个优先级队列所以有个比较器comparator用来比较元素大小。lock独占锁对象用来控制同时只能有一个线程可以进行入队出队操作。notEmpty条件变量用来实现take方法阻塞模式。这里没有notFull 条件变量是因为这里的put操作是非阻塞的为啥要设计为非阻塞的是因为这是无界队列。  最后PriorityQueue q用来搞序列化的。  如下构造函数默认队列容量为11默认比较器为null; private static final int DEFAULT_INITIAL_CAPACITY 11;  public PriorityBlockingQueue() {   this(DEFAULT_INITIAL_CAPACITY, null);  } public PriorityBlockingQueue(int initialCapacity) {   this(initialCapacity, null);  } public PriorityBlockingQueue(int initialCapacity,   Comparator? super E comparator) {  if (initialCapacity 1)   throw new IllegalArgumentException();   this.lock new ReentrantLock();   this.notEmpty lock.newCondition();   this.comparator comparator;   this.queue new Object[initialCapacity];  } PriorityBlockingQueue方法  ✓  Offer操作  在队列插入一个元素由于是无界队列所以一直为成功返回true;  public boolean offer(E e) {   if (e null)  throw new NullPointerException();   final ReentrantLock lock this.lock;   lock.lock();  int n, cap;  Object[] array;  //如果当前元素个数队列容量则扩容(1)  while ((n size) (cap (array queue).length))   tryGrow(array, cap);   try {  Comparator? super E cmp comparator;   //默认比较器为null  if (cmp null)(2)   siftUpComparable(n, e, array);   else  //自定义比较器(3)  siftUpUsingComparator(n, e, array, cmp);   //队列元素增加1并且激活notEmpty的条件队列里面的一个阻塞线程   size n 1;9   notEmpty.signal();   } finally {  lock.unlock();  }  return true; } 主流程比较简单下面看看两个主要函数  private void tryGrow(Object[] array, int oldCap) {  lock.unlock(); //must release and then re-acquire main lock  Object[] newArray null;   //cas成功则扩容(4)  if (allocationSpinLock 0    UNSAFE.compareAndSwapInt(this, allocationSpinLockOffset,   0, 1)) {  try {  //oldGap64则扩容新增oldcap2,否者扩容50%并且最大为MAX_ARRAY_SIZE  int newCap oldCap ((oldCap 64) ?   (oldCap 2) : // grow faster if small  (oldCap 1));  if (newCap - MAX_ARRAY_SIZE 0) {    // possible overflow  int minCap oldCap 1;   if (minCap 0 || minCap MAX_ARRAY_SIZE)   throw new OutOfMemoryError();  newCap MAX_ARRAY_SIZE;   }  if (newCap oldCap queue array)   newArray new Object[newCap];   } finally {  allocationSpinLock 0;   }  }  //第一个线程cas成功后第二个线程会进入这个地方然后第二个线程让出cpu尽量让第一个线程执行下面点获取锁但 是这得不到肯定的保证。(5)  if (newArray null) // back off if another thread is allocating   Thread.yield();  lock.lock();(6) if (newArray ! null queue array) {   queue newArray;  System.arraycopy(array, 0, newArray, 0, oldCap);   } } tryGrow 目的是扩容这里要思考下为啥在扩容前要先释放锁然后使用 cas 控制只有一个线程可以扩容成功。 我的理解是为了性能因为扩容时候是需要花时间的如果这些操作时候还占用锁那么其他线程在这个时候是不能进 行出队操作的也不能进行入队操作这大大降低了并发性。  所以在扩容前释放锁这允许其他出队线程可以进行出队操作但是由于释放了锁所以也允许在扩容时候进行 入队操作这就会导致多个线程进行扩容会出现问题所以这里使用了一个spinlock用cas控制只有一个线程可以进 行扩容失败的线程调用Thread.yield()让出cpu目的意在让扩容线程扩容后优先调用lock.lock重新获取锁但是 这得不到一定的保证有可能调用Thread.yield()的线程先获取了锁。  那copy元素数据到新数组为啥放到获取锁后面那?原因应该是因为可见性问题因为queue并没有被volatile修 饰。另外有可能在扩容时候进行了出队操作如果直接拷贝可能看到的数组元素不是最新的。而通过调用Lock后获 取的数组则是最新的并且在释放锁前 数组内容不会变化。  具体建堆算法  private static T void siftUpComparable(int k, T x, Object[] array) {   Comparable? super T key (Comparable? super T) x;   //队列元素个数0则判断插入位置否者直接入队(7)   while (k 0) {  int parent (k - 1) 1;  Object e array[parent];   if (key.compareTo((T) e) 0)   break;  array[k] e;  k parent;  }  array[k] key;(8) } 下面用图说话模拟下过程  假设队列容量为2 •  第一次offer(2)时候  执行1)为false所以执行2由于knsize0;所以执行8元素入队然执行9size1;  执行1)为false所以执行2由于k1,所以进入while循环parent0;e2;key4;keye所以break;然后把4存到数据下标为1的地方这时候队列状态为  •  第三次offer(4)时候 执行1)为true,所以调用tryGrow,由于264所以newCap2  (22)6;然后创建新数组并拷贝然后调用siftUpComparablek20进入循环  parent0;e2;key6;keye所以break;然后把6放入下标为2的地方现在队列状态  •  第四次offer(1)时候  执行1)为false所以执行2由于k3,所以进入while循环parent0;e2;key1; keye所以把2 复制到数组下标为3的地方然后k0退出循环然后把2存放到下标为0地方现在状态  ✓  Poll操作  在队列头部获取并移除一个元素如果队列为空则返回null public E poll() {  final ReentrantLock lock this.lock;   lock.lock();  try {  return dequeue();  } finally {  lock.unlock();  } } 主要看dequeue  private E dequeue() {  //队列为空则返回null  int n size - 1;  if (n 0)  return null;  else {  //获取队头元素(1) Object[] array queue;   E result (E) array[0];   //获取对尾元素并值null(2)  E x (E) array[n];   array[n] null;  Comparator? super E cmp comparator;  if (cmp null)//cmpnull则调用这个把对尾元素位置插入到0位置并且调整堆为最小堆(3)  siftDownComparable(0, x, array, n);   else  siftDownUsingComparator(0, x, array, n, cmp);   size n;4   return result;  } } private static T void siftDownComparable(int k, T x, Object[] array,   int n) {  if (n 0) {  Comparable? super T key (Comparable? super T)x;   int half n 1;           // loop while a non-leaf  while (k half) {   int child (k 1) 1; // assume left child is least   Object c array[child];5   int right child 1;6)  if (right n   ((Comparable? super T) c).compareTo((T) array[right]) 0)(7)  c array[child right];   if (key.compareTo((T) c) 0)(8)   break;  array[k] c;   k child;  }  array[k] key;(9)   }  } 下面用图说话模拟下过程  •  第一次调用poll() 首先执行1  result1然后执行2x2;这时候队列状态  下面重点说说siftDownComparable这个屌屌的建立最小堆的算法 首先说下思想其中k一开始为0x为数组里面最后一个元素由于第0个元素为树根被出队时候要被搞掉所以建堆要从它的左右孩子节点找一个最小的值来当树根子树根被搞掉后会找子树的左右孩子最小的元素来代替直到树节点为止还不明白没关系看图说话  假如当前队列元素  然后看leftChildVal  4;rightChildVal  6; 46;所以c4;也就是获取根节点的左右孩子值小的那一个 然后看 114也就是keyc然后把c放入树根现在树为  然后看根的左边孩子4为根的子树我们要为这个字树找一个根节点。  看leftChildVal   8;rightChildVal  10; 810;所以c8;也就是获取根节点的左右孩子值小的那一个 然后看118也就是keyc然后把c放入树根现在树为  这时候k3;half3所以推出循环执行9后结果为  这时候队列为  ✓  Put操作  内部调用的offer,由于是无界队列所以不需要阻塞  public void put(E e) {  offer(e); // never need to block  } ✓  Take操作  获取队列头元素如果队列为空则阻塞。  public E take() throws InterruptedException {   final ReentrantLock lock this.lock;   lock.lockInterruptibly();   E result;  try {  //如果队列为空则阻塞把当前线程放入notEmpty的条件队列   while ( (result dequeue()) null)   notEmpty.await();   } finally {  lock.unlock();  } return result; } 这里是阻塞实现阻塞后直到入队操作调用notEmpty.signal 才会返回。  ✓  Size操作  获取队列元个数由于加了独占锁所以返回结果是精确的  public int size() {  final ReentrantLock lock this.lock;   lock.lock();  try {  return size;  } finally {  lock.unlock();  } } PriorityBlockingQueue小结 PriorityBlockingQueue类似于ArrayBlockingQueue内部使用一个独占锁来控制同时只有一个线程可以进行入队和出队另外前者只使用了一个 notEmpty 条件变量而没有 notFull这是因为前者是无界队列当put 时候永远不会处于await所以也不需要被唤醒。  PriorityBlockingQueue 始终保证出队的元素是优先级最高的元素并且可以定制优先级的规则内部通过使用一个二叉树最小堆算法来维护内部数组这个数组是可扩容的当当前元素个数最大容量时候会通过算法扩容。  值得注意的是为了避免在扩容操作时候其他线程不能进行出队操作实现上使用了先释放锁然后通过 cas 保证同时只有一个线程可以扩容成功。  PriorityBlockingQueue示例 PriorityBlockingQueue类是JDK提供的优先级队列 本身是线程安全的 内部使用显示锁 保证线程安全。  PriorityBlockingQueue 存储的对象必须是实现 Comparable 接口的 因为 PriorityBlockingQueue 队列会根据内部存储的每一个元素的 compareTo 方法比较每个元素的大小。这样在 take 出来的时候会根据优先级 将优先级最小的最先取出 。  下面是示例代码  public static PriorityBlockingQueueUser queue new PriorityBlockingQueueUser();
public static void main(String[] args) { queue.add(new User(1,wu));    queue.add(new User(5,wu5));    queue.add(new User(23,wu23));    queue.add(new User(55,wu55));    queue.add(new User(9,wu9));    queue.add(new User(3,wu3));    for (User user : queue) {    try {    System.out.println(queue.take().name);    } catch (InterruptedException e) {    e.printStackTrace();    }    }    }
//静态内部类  static class User implements ComparableUser{ public User(int age,String name) {    this.age age;    this.name name;    }    int age;    String name;    Override    public int compareTo(User o) {    return this.age  o.age ? -1 : 1;    }