Monthly Archives: August 2021

Design Elevators

电梯调度
停车场
Elevator
max people capacity
max weight
airstairs[only to living area], goods stair[to storage area]

Building
Each elevator can each level or certain levels?
Inside building the button controls all elevator or just one elevator.

Scheduler
same direction > static > different direction

when elevator is running, can we press the button for different direciton level.
+, public
-, private
#, protected
~, package

Use case
ElevatorSystem
handle request

Elevator
external request
internal request
open door
close door
check weight

ElevatorButton
press

Class diagram

class ElevatorSystem {
Lst<Elevator> elevators;
void handleRequest(ExternalRequest r);
}

class Elevator {
List<ElevatorButton> buttons
boolean[] stops;

public void handleExternalRequest();
public void handleInternalRequest();
}

class InvalidExternalRequestException;
open to extension, close to modification
different schedules on different days(weekday/weekend)
Strategy Pattern

interface HandleRequestStrategy
class PeakHourHandleRequestStrategy;
class NormalHourHandleRequestStrategy;

try

class InvalidRequestException extends Exception;

interface HandleRequestStrategy {
    void handleRequest();
}

enum ACTION {
    UP,DOWN,OPEN,CLOSE;
}

class ExternalRequest {
    int currentLevel;
    ACTION action;
}


// 
class NormalHourHandleRequestStrategy {
    void handleRequest(List<Elevator> elevators, Request request) {
        // all elevators go to every floor
    }
}

// 
class NormalHourHandleRequestStrategy {
    void handleRequest(List<Elevator> elevators, Request request) {
        // first half elevator go to half floors. 2nd half elevators go to 2nd half floors.
    }
}

class ElevatorSystem implement HandleRequestStrategy {
    List<Elevator> elevators;
    handleRequest(List<Elevator> elevators);
}

class Elevator {
    List<Buttons> buttons;
    boolean[] stops;
    int currentLevel;
    STATUS status;

    void handleInternalRequest();
    void handleExternalRequest();

    void openDoor();
}

enum {
    UP,DOWN,STOP;
}

https://www.youtube.com/watch?v=CsWFuFdlBVU

Producer, Consumer with ReentrantLock, Condition 

public class PC {

    public static void main(String[] args) {
        ReentrantLock lock = new ReentrantLock();
        Condition added = lock.newCondition();
        Condition removed = lock.newCondition();
        int[] resource = new int[1];
        Consumer c1 = new Consumer(lock, added, removed, resource);
        Producer p1 = new Producer(lock, added, removed, resource);
        Producer p2 = new Producer(lock, added, removed, resource);
        new Thread(c1).start();
        new Thread(p1).start();
        new Thread(p2).start();
    }


    public static class Consumer implements Runnable {

        ReentrantLock lock;
        Condition added;
        Condition removed;
        int[] resource;

        public Consumer(ReentrantLock lock, Condition added, Condition removed, int[] resource) {
            this.lock = lock;
            this.resource = resource;
            this.added = added;
            this.removed = removed;
        }

        @SneakyThrows
        public void run() {
            while (true) {
                lock.lock();
                while (resource[0] <= 0) {
                    added.await();
                }
                resource[0]--;
                System.out.println(Thread.currentThread().getId() + " consume: " + resource[0]);
                removed.signalAll();
                lock.unlock();
                Thread.sleep(1000l);
            }
        }

    }

    public static class Producer implements Runnable {

        ReentrantLock lock;
        Condition added;
        Condition removed;
        int[] resource;
        int MAX = 5;

        public Producer(ReentrantLock lock, Condition added, Condition removed, int[] resource) {
            this.lock = lock;
            this.resource = resource;
            this.added = added;
            this.removed = removed;
        }

        @SneakyThrows
        public void run() {
            while (true) {
                lock.lock();
                while (resource[0] >= MAX) {
                    removed.await();
                }
                resource[0]++;
                System.out.println(Thread.currentThread().getId() + " produce: " + resource[0]);
                added.signalAll();
                lock.unlock();
                Thread.sleep(1000l);
            }
        }

    }

}

Token Bucket 

public class TokenBucket {

    private long maxBucketSize;
    private long refillRate; // per second
    private long currentBucketSize;
    private long lastRefillTimestamp;

    synchronized public boolean allowRequest(int token) {
        refill();
        if (currentBucketSize >= token) {
            currentBucketSize -= token;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.nanoTime();
        double add = (now - lastRefillTimestamp) / 1e9 * refillRate;
        currentBucketSize = Math.min(currentBucketSize + (long)add, maxBucketSize);
        lastRefillTimestamp = now;
    }

}

groupon design 

rule: {
    rule_id,
    type: discount/one-time
    value: 30%/50$
    limited_user: [usr1, usr2]
    limited_user_grp: [grp1, grp2]
    number_of_usage: 1,
    service: [LYFT, CHIPOTLE]
}

groupon: {
    g_id,
    code: XMASCODE
    rule_id: xxx
    expire_date: 2021/12/31
}

usage: {
    user_id,
    groupon_id,
    time
}

ConcurrentHashMap

Each segment has multiple entries. Each entry, it starts with a LinkedList. When it has too many, it changes to Black-Red-Tree.

When write, if two writes are for different segment, then it allows. When multiple writes to same segment, it uses CAS(compare-and-set) to write and handle conflict.

Each operation on segment has a counter. The counter only increases. When resize, it will get the counter first. Then it does resize. After resize, compare if the counter changes. If no change, then resize done, if not will do it again. If still fails, it tries to acquire lock on each segment.

 

ReentrantLock, ReentrantReadWriteLock

RentrantLock is almost the same as synchronized keyword. Only difference is that synchrnozied keyword needs a block. It maintains a queue for the threads.

RentrantLock lock = new ReentrantLock();

lock.lock();
try {
    do something..
} finally {
    lock.release();
}

ReentrantReadWriteLock. It also maintains a queue for threads. When it has queue:
[readThread1, readThread2, writeThread3, readThread4]

When it is released, readThread1, readThread2 can read the resource concurrently. However, readThread4 will be blocked, until writeThread3 finishes the write.

ReentrantReadWriteLock lock = new ReentrantReadWriteLock();
ReentrantReadWriteLock.ReadLock readLock = lock.readLock();
ReentrantReadWriteLock.WritLock writeLock = lock.writeLock();

private void readResource() {
    readLock.lock();
    // read
    readLock.unlock();
}

private void writeResource() {
    writeLock.lock();
    // write
    writeLock.unlock();
}