java-strategy

发表于 2024-04-17 更新于 2025-03-09 Disqus：

JAVA速成Day5——策略模式

源自于Head First 设计模式第一章

具体的idea是将一组算法封装到一个对象中。一个常见的例子是之前接触过的 Comparator ：

Comparator<Integer> cmp = new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            Integer val = o2 - o1;
            return val.intValue();
        }
    };

自己实现策略模式的排序：

public class Main {
    public static void main(String[] args) throws InterruptedException {
        String[] array = { "apple", "Pear", "Banana", "orange" };
        sort(array, String::compareToIgnoreCase);
        System.out.println(Arrays.toString(array));
    }

    static <T> void sort(T[] a, Comparator<? super T> c) {
        for (int i = 0; i < a.length - 1; i++) {
            for (int j = 0; j < a.length - 1 - i; j++) {
                if (c.compare(a[j], a[j + 1]) > 0) { // 注意这里比较两个元素的大小依赖传入的策略
                    T temp = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = temp;
                }
            }
        }
    }
}

而排序的规则，并不直接体现在 sort 内部。这就避免了面向实现编程。

例如，我们要实现不同的排序规则，我们可以首先定义一个接口：

1
2
3

public interface sortStrategy{
	void sort(int[] array);
}

然后可以定义多个排序算法，实现该接口：

public class QuickSort implements sortStrategy{
	public void sort(int[] array){
		...
	}
}

public class MergeSort implements sortStrategy{
	public void sort(int[] array){
		...
	}
}

要应用策略的话，可以通过多态特性：

1	sortStrategy my_sort = new QuickSort();

如果该接口是一个类的字段，可以通过 setter 方式，很方便地修改其算法行为。这就是策略模式的精髓所在。

lock_lab

发表于 2024-04-12 更新于 2025-03-09 Disqus：

xv6 lock lab

链接：https://pdos.csail.mit.edu/6.828/2021/labs/lock.html

2021和2020是一样的

xv6支持多线程并发。为了保证共享内存中数据的不变性（invariant），需要采用lock机制进行序列化。

但是xv6的内核内部中的一些机制中对lock的使用过于粗粒（coarse-grained），这会导致线程会浪费较多时间在spinlock的自旋上，因此该lab的任务就是细粒化一些功能中的lock机制。

Memory allocator

xv6的内核维护了一个全局的page链表，内部存着尚未被分配的page的物理地址。对于请求/释放内存，xv6为整个链表维护了一个lock。

考虑到可能多个线程会同时请求/释放内存，而链表整体的lock则会序列化这些过程，无法发挥并发优势。因此该任务需要你来细粒化 kalloc.c 中的lock机制。

至于怎么细粒化，其实lab的提示已经给出：为每个CPU分配一个单独的链表，及其对应的lock。

所以直接把 kmem 改成数组：

struct {
  struct spinlock lock;
  struct run *freelist;
} kmem[NCPU];

然后同时修改初始化函数 kinit ，该函数只在xv6启动的时候被一个CPU调用：

void
kinit()
{
  for(int i = 0; i < NCPU; i++)
    initlock(&kmem[i].lock, "kmem");
  freerange(end, (void*)PHYSTOP);
}

我们考虑一下分配内存的过程。对于每个CPU对应的链表，如果链表为空，则需要从其它CPU的链表中偷取。

具体实现如下：

void *
kalloc(void)
{
  struct run *r;
  uint cid;
  push_off();
  cid = cpuid();
  pop_off();

  acquire(&kmem[cid].lock);
  r = kmem[cid].freelist;
  if(r){
    kmem[cid].freelist = r->next;
    release(&kmem[cid].lock);
  }
  else{
    release(&kmem[cid].lock);
    for(int i = 0; i < NCPU; i++){
      if(i == cid) continue;
      acquire(&kmem[i].lock);
      r = kmem[i].freelist;
      if(!r){
        release(&kmem[i].lock);
        continue;
      }
      kmem[i].freelist = r->next;
      release(&kmem[i].lock);
      break;
    }
  }
  

  if(r)
    memset((char*)r, 5, PGSIZE); // fill with junk
  return (void*)r;
}

这里强调一下，无论是在xv6的lab，还是其它并发编程中（例如C++11内的 std::mutex ），我们都需要对每个lock规定其对应的不变量（invariant）。这个是很重要的，它关系到在设置获取和释放锁的时机，以及防止死锁。

例如本任务，对于每个CPU对应的链表，都有一个lock。因此我们规定该lock维护的不变量为其对应的链表结构。

因此，在发现执行CPU对应的链表为空时，我们就可以释放锁了，因为接下来的工作都对该链表没有任何关系。这种细微的细节应该也算是细粒化工作的重要部分。

然后考虑释放内存，只需要在对应CPU的链表加入元素即可：

void
kfree(void *pa)
{
  struct run *r;
  uint cid;
  push_off();
  cid = cpuid();
  pop_off();

  if(((uint64)pa % PGSIZE) != 0 || (char*)pa < end || (uint64)pa >= PHYSTOP)
    panic("kfree");

  // Fill with junk to catch dangling refs.
  memset(pa, 1, PGSIZE);

  r = (struct run*)pa;

  acquire(&kmem[cid].lock);
  r->next = kmem[cid].freelist;
  kmem[cid].freelist = r;
  release(&kmem[cid].lock);
}

Buffer cache

xv6在读/写硬盘IO时，会先检查内存是否存在对应的缓存（buffer cache）。如果存在则直接在缓存上执行操作，然后写入硬盘。

关于xv6在内存中对buffer cache的组织形式，事实上是一个双链表：

// buf.h
struct buf {
  int valid;   // has data been read from disk?
  int disk;    // does disk "own" buf?
  uint dev;
  uint blockno;
  struct sleeplock lock;
  uint refcnt;
  struct buf *prev; // LRU cache list
  struct buf *next;
  uchar data[BSIZE];
  uint time_stamp; // lru time stamp
  int now_hash;  // hash number
};

// bio.c
struct {
  struct spinlock lock;
  struct buf buf[NBUF];

  // Linked list of all buffers, through prev/next.
  // Sorted by how recently the buffer was used.
  // head.next is most recent, head.prev is least.
  struct buf head;
} bcache;

可以发现似乎和上面那个链表似乎很像。但事实上该链表的元素本身也是个结构体 buf ，而不是单纯一个物理地址。

那么我们能不能沿用上个任务的idea，对每个CPU维护一个buffer cache link list呢？

根据lab中的提示，是不行的。给出的原因是每一个buffer cache应当被不同CPU的线程共享。

但是实际上是可以的，只不过我们需要换个角度来看。根据lab的提示，我们应当将原有的大链表进行分割，得到一系列小链表，然后在各自的小链表上并行化工作。

实质是一样的，都是将一个拆分为多个。

如何将block的编号与小链表对应呢？答案是采用哈希函数。这里根据lab，定义13（素数减少冲突概率）个小链表，然后直接将block编号对13取余得到哈希值。

首先，我们需要初始化：

struct bucket{
  struct spinlock lock;
  struct buf head;
}hashtable[BUCKETCNT]; // 13

void
binit(void)
{
  struct buf *b;
  int i;

  initlock(&bcache.lock, "bcache");

  // // Create linked list of buffers
  // bcache.head.prev = &bcache.head;
  // bcache.head.next = &bcache.head;

  for(i = 0; i < BUCKETCNT; i++){
    initlock(&hashtable[i].lock, "bcache_hash");
    hashtable[i].head.prev = &hashtable[i].head;
    hashtable[i].head.next = &hashtable[i].head;
  }
  
  for(i = 0, b = bcache.buf; b < bcache.buf+NBUF; b++, i = (i + 1) % BUCKETCNT){
    b->next = hashtable[i].head.next;
    b->prev = &hashtable[i].head;
    initsleeplock(&b->lock, "buffer");
    hashtable[i].head.next->prev = b;
    hashtable[i].head.next = b;

    b->time_stamp = 0;
    b->now_hash = i;
  }
  
}

这里我将NBUF个buffer cache平均分配了。如果只分配到一个小链表上，则可能会加大冲突概率。

然后考虑我们如何获得buffer cache。我们首先在自己哈希值上的链表上找，如果没有则去其它小链表上轮换查找。

根据lab提示，我们采用lru策略。因此可以看到我上面给出的 buf 结构体相比于原有的结构体，多了时间戳 time_stamp 字段。

话不多说，直接上code：

static struct buf*
bget(uint dev, uint blockno)
{
  struct buf *b;
  struct buf *lru=0;
  uint hash = blockno % BUCKETCNT;
  uint min_time_stamp = ticks + 114514;
  
  acquire(&hashtable[hash].lock);

  for(b = hashtable[hash].head.next; b != &hashtable[hash].head; b = b->next){
    if(b->dev == dev && b->blockno == blockno){
      b->refcnt++;
      release(&hashtable[hash].lock);
      acquiresleep(&b->lock);
      return b;
    }
  }

  // Not cached.
  // printf("ticks = %d\n", ticks);
  // for(b = bcache.buf; b < bcache.buf+NBUF; b++){
  //   if(b->refcnt == 0 && b->time_stamp <= min_time_stamp) {
  //     lru = b;
  //     min_time_stamp = b->time_stamp;
  //   }
  // }

  for(int i = (hash + 1) % BUCKETCNT; i != hash; i = (i + 1) % BUCKETCNT){
    acquire(&hashtable[i].lock);

    for(b = hashtable[i].head.next; b != &hashtable[i].head; b = b->next){
      if(b->refcnt == 0 && b->time_stamp < min_time_stamp) {
        lru = b;
        min_time_stamp = b->time_stamp;
      }
    }

    if(!lru) {
      release(&hashtable[i].lock);
      continue;
    }

    b = lru;
    b->next->prev = b->prev;
    b->prev->next = b->next;
    release(&hashtable[i].lock);


    b->dev = dev;
    b->blockno = blockno;
    b->valid = 0;
    b->refcnt = 1;
    b->now_hash = hash;


    b->next = hashtable[hash].head.next;
    b->prev = &hashtable[hash].head;

    acquiresleep(&b->lock);

    hashtable[hash].head.next->prev = b;
    hashtable[hash].head.next = b;
    release(&hashtable[hash].lock);

    return b;
  }
  // printf("min_time_stamp = %d\n", min_time_stamp);

  if(!lru)
    panic("bget: no buffers");
  return lru;
}

对于每个lock，我们规定它的不变量为：该lock对应双链表的结构，以及链表内元素的本身结构。

所以你可以发现，当我们从其余链表偷取一个 cache 时，我们先释放了其余链表的锁，然后等把该 cache 内部的值设置完成之后再释放当前hash值链表的锁。

在网上看到有些做法，访问全局变量 ticks 前需要 acquire(&tickslock); 。然而实测是不需要的。

最后考虑一下释放的操作：

void
brelse(struct buf *b)
{
  if(!holdingsleep(&b->lock))
    panic("brelse");

  releasesleep(&b->lock);

  acquire(&hashtable[b->now_hash].lock);
  b->refcnt--;
  if (b->refcnt == 0) {
    // no one is waiting for it.
    b->time_stamp = ticks;
  }
  release(&hashtable[b->now_hash].lock);
}

可以发现，由于我们规定了lock的不变量，这里我们上的锁就是哈希值对应的锁。（即lock维护b->refcnt 等不变量）

同时，我们需要修改一下其余函数：

void
bpin(struct buf *b) {
  // printf("!!!\n");
  acquire(&hashtable[b->now_hash].lock);
  b->refcnt++;
  release(&hashtable[b->now_hash].lock);
}

void
bunpin(struct buf *b) {
  acquire(&hashtable[b->now_hash].lock);
  b->refcnt--;
  release(&hashtable[b->now_hash].lock);
}

虽然该lab并没有指出这些函数，但在usertests中是有调用的。事实上函数 bpin 的作用是强制一个buffer cache不被 brelse 掉，这在更新 log block 对应的block时有用到。

最后贴一张完成的图：

java_string

发表于 2024-04-11 更新于 2025-03-09 Disqus：

JAVA速成Day4——字符串

字符串也是ACM里常用的东西，但是java里的字符串我并不是很熟悉，所以这次就稍微速通一下~

String：

首先我们得清楚String类在java中是不可变的。这真的勾八坑爹

equals()

比较两个String是否相等，返回boolean

compareTo()

比较两个字符串的字典序，返回负数/0/正数

substring()

提取子串，左闭右开。第二个参数可选

1	"blackbird".substring(5) // bird

toCharArray()

转化为 Char[] 。

StringBuilder

由于String类部是 final 类型，不可变。因此当你使用 + 连接两个String时，事实上会再new一个String对象，这是没有效率的。

所以java提供了一个类StringBuilder，它是可变的。

public class Main {
    public static void main(String[] args) {
        StringBuilder str = new StringBuilder();
        str.append("i ").append("love ").append("blackbird.");
        String output = str.toString();
        System.out.println(output);
        str.setCharAt(0, 'u');
        System.out.println(str);
    }
}

顺带一提

这里提到了方法equals() 。事实上，对于所有非基本类型，都应该使用这个方法来判断对象之间是否相等。

基本类型	对应的引用类型
boolean	java.lang.Boolean
byte	java.lang.Byte
short	java.lang.Short
int	java.lang.Integer
long	java.lang.Long
float	java.lang.Float
double	java.lang.Double
char	java.lang.Character

例如int对应的引用类型Integer

java_interface

发表于 2024-04-10 更新于 2025-03-09 Disqus：

JAVA速成Day3——接口

java提倡OOP(面向对象编程)，然后有个东西叫做抽象类，需要子类继承来重写其定义的方法。

然后接口这个东西更抽象，相比抽象类，它只有方法，没有字段：

interface bird{
    void fly();
    String getName();
}

当具体的类要实现这些接口时，需要使用 implements 关键字：

class blackbird implements bird{
    private String name;

    public blackbird(String name){
        this.name = name;
    }

    @Override
    public void fly() {
        System.out.println(name + " is flying~");
    }

    @Override
    public String getName() {
        return name;
    }
}

然而，java不能同时继承多个类，但是可以同时实现多个接口。

接口之间可以继承：

interface Hello {
    void hello();
}

interface bird extends Hello {
    void fly();
    String getName();
}

神奇的是，可以通过接口去引用对象：

public class test {
    public static void main(String[] args) {
        bird bb = new blackbird("taffy");
        bb.fly();
    }
}

然而，对于对象自己实现的方法，接口没办法引用。

实际上，在我整的JAVA速成Day1那篇介绍集合的文章中，我留了个坑：用Map引用TreeMap。

实际上这里的Map，以及List，都是接口。

它们引用的对象，只能调用自己即继承的接口内部的方法。

因此对于TreeMap中独属于该类的方法，接口Map不能调用。因此你会发现IDEA的自动补全里少了点API。

另外，接口中可以定义 default 方法，然后直接在接口内部实现：

interface bird{
    void fly();
    String getName();

    default void hello(){
        System.out.println(getName() + " will succeed!");
    }
}

class blackbird implements bird{
    private String name;

    public blackbird(String name){
        this.name = name;
    }

    @Override
    public void fly() {
        System.out.println(name + " is flying~");
    }

    @Override
    public String getName() {
        return name;
    }

    public void hh(){

    }
}

public class test {
    public static void main(String[] args) {
        bird bb = new blackbird("blackbird");
        bb.hello();
    }
}

这样的话，如果对于一个接口新增一个方法，就不需要更改所有实现它的子类了，只需要在需要的地方 override 即可。

晚安

事实上接口是可以有字段的，但是其类型为 public static final ：

public interface Person {
    public static final int MALE = 1;
    public static final int FEMALE = 2;
}

--update 24.4.11

JAVA速成Day2——单例模式

发表于 2024-04-09 更新于 2025-03-09 Disqus：

JAVA速成Day2——单例模式

南软，我的南软

单例模式

确保一个类只有一个实例，并提供该实例的全局访问点。

线程不安全的懒汉式

懒汉代表延迟实例化，即只在需要的时候实例化一个对象。

public class Singleton {
    private static Singleton uniqueInstance;

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
    }

    public static Singleton getUniqueInstance(){ // 必须要是 static 
        if(uniqueInstance == null){
            // 这里是线程不安全的
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
}

线程安全的饿汉式

直接在声明对象的时候创建一个全局静态对象。

public class Singleton {
    private static Singleton uniqueInstance = new Singleton();

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
    }

    public static Singleton getUniqueInstance(){
        return uniqueInstance;
    }
}

这个方式丢失了节约资源的好处。

线程安全的懒汉式

在第一种方式的race condition那里上锁即可。方法是加上 synchronized 关键字。

public class Singleton {
    private static Singleton uniqueInstance;

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
        System.out.println("love u");
    }

    public static synchronized Singleton getUniqueInstance(){ // 必须要是 static
        if(uniqueInstance == null){
            // 这里是线程安全的
            uniqueInstance = new Singleton();
        }
        return uniqueInstance;
    }
}

但是这里序列化了 getUniqueInstance 方法，失去了多线程并发的意义。

双重校验锁

public class Singleton {
    private volatile static Singleton uniqueInstance;

    private Singleton(){
        // 这里使用 private 保证只在类的内部实例化对象
        System.out.println("love u");
    }

    public static Singleton getUniqueInstance(){ // 必须要是 static
        if(uniqueInstance == null){
            synchronized (Singleton.class) {
                if(uniqueInstance == null){
                    uniqueInstance = new Singleton();
                }
            }
        }
        return uniqueInstance;
    }
}

这里必须使用双重 if ，原因相信你能直接看出来。

至于 volatile 关键字，也是必不可少的。这是因为语句 uniqueInstance = new Singleton(); 并不是原子的，它需要进行：

分配内存空间
初始化对象
将 uniqueInstance 指向对应的内存地址。

但是 jvm 可能会将指令重排，将上述执行顺序更改为1>3>2，这在多线程的情况下是有问题的，可能在另一个线程得到未初始化的对象。

静态内部类

静态内部类。。。这个打codeforces倒是经常用。

public class Singleton {
    private static Singleton uniqueInstance;
    private Singleton(){
        System.out.println("love u, blackbird");
    }

    private static class SingletonHolder{
        private static final Singleton INSTANCE = new Singleton();
    }

    public static Singleton getUniqueInstance(){ // 必须要是 static
        return SingletonHolder.INSTANCE;
    }
}

原理有两点：

静态内部类在 Singleton 外部类加载的时候并没有被加载进内存，只有需要的时候（调用 get 方法）才会加载；
虚拟机提供了线程安全，不会多次加载静态内部类。

很神奇是吧？我也觉得~

枚举实现

这东西我第一次看的时候懵了。代码长这样：

1
2
3

public enum Singleton {
    INSTANCE;
}

挖个坑吧，不是很懂。

枚举

讲真之前我连C语言的enum是干啥的我都不知道。。。

在java中，可以通过 static final 来定义常量：

public class Weekday {
    public static final int SUN = 0;
    public static final int MON = 1;
    public static final int TUE = 2;
    public static final int WED = 3;
    public static final int THU = 4;
    public static final int FRI = 5;
    public static final int SAT = 6;
}

可以通过 Weekday.SUN 等形式来访问这些常量。

当然也可以不用int来定义常量，比如String这种。但是在比较的时候需要把 == 改成 equals()。

当我们的需求不依赖于这种int或者String的类型变量时，可以通过 enum 定义枚举类：

enum Weekday {
    SUN, MON, TUE, WED, THU, FRI, SAT;
}

int day = 1;
if (day == Weekday.SUN) { // Compile error: bad operand types for binary operator '=='
}

Weekday x = Weekday.SUN; // ok!
Weekday y = Color.RED; // Compile error: incompatible types

enum定义的枚举类是一种引用类型，但是可以用 == 来比较。这是因为enum类型的每个常量在jvm中都只有一个实例，你无法new一个enum对象。

if (day == Weekday.FRI) { // ok!
}
if (day.equals(Weekday.SUN)) { // ok, but more code!
}

（或许这也是可以使用enum实现单例模式的原因

enum编译后的结果maybe like：

public final class Color extends Enum { // 继承自Enum，标记为final class
    // 每个实例均为全局唯一:
    public static final Color RED = new Color();
    public static final Color GREEN = new Color();
    public static final Color BLUE = new Color();
    // private构造方法，确保外部无法调用new操作符:
    private Color() {}
}

可以发现，每个枚举对象都对应一个唯一的静态实例。同时构造方法是 private 的，不让你new。

但是，其实可以自定义字段与构造方法：

public class Main {
    public static void main(String[] args) {
        Weekday day = Weekday.SUN;
        if (day.dayValue == 6 || day.dayValue == 0) {
            System.out.println("Work at home!");
        } else {
            System.out.println("Work at office!");
        }
    }
}

enum Weekday {
    MON(1), TUE(2), WED(3), THU(4), FRI(5), SAT(6), SUN(0);

    public final int dayValue; // final!!!

    private Weekday(int dayValue) {
        this.dayValue = dayValue;
    }
}

可以重写 toString() 方法，这样调试输出比较方便：

public class Main {
    public static void main(String[] args) {
        Weekday day = Weekday.SUN;
        if (day.dayValue == 6 || day.dayValue == 0) {
            System.out.println("Today is " + day + ". Work at home!"); // 自动调用day.toString()
        } else {
            System.out.println("Today is " + day + ". Work at office!");
        }
    }
}

enum Weekday {
    MON(1, "星期一"), TUE(2, "星期二"), WED(3, "星期三"), THU(4, "星期四"), FRI(5, "星期五"), SAT(6, "星期六"), SUN(0, "星期日");

    public final int dayValue;
    private final String chinese;

    private Weekday(int dayValue, String chinese) {
        this.dayValue = dayValue;
        this.chinese = chinese;
    }

    @Override
    public String toString() {
        return this.chinese;
    }
}

回过来看单例模式

由于enum类部的对象在整个生命周期只会出现一次，而且无论是哪个enum类引用到的对象是同一个，因此可以据此实现单例模式。

public enum Singleton {
    INSTANCE();
    private String bird;
    private int hh;
    Singleton(){}

    public void setBird(String bird) {
        this.bird = bird;
    }

    public void setHh(int hh) {
        this.hh = hh;
    }

    public int getHh() {
        return hh;
    }

    public String getBird() {
        return bird;
    }


    public static void main(String[] args) {
        Singleton singleton = Singleton.INSTANCE;
        singleton.setBird("blackbird");
        singleton.setHh(2333);
        System.out.println(singleton.getBird() + " " + singleton.getHh());
        Singleton singleton1 = Singleton.INSTANCE;
        System.out.println(singleton1.getBird() + " " + singleton1.getHh());
    }
}
// blackbird 2333
// blackbird 2333

很神奇是吧hh