PainterKarelProgram3 (KarelOOP2)

/*
 * Copyright 2020 Sangwon Park @ DISLab, HUFS
 *
 * 10명의 페이트 칠쟁이들이 무작위로 돌아다니며 바닥을 칠하는 프로그램이다.
 * 
 * 서로 부딪혀서 캐럴이 망가지지 않도록 하기 위하여 lock을 준비하였다.
 * 이 lock들은 코너 마다 하나씩 준비되어 있고, 좌표를 이용하여 락을 획득한다.
 * 
 * 만약 락을 거는 프로토콜이 아래와 같다면 데드락이 발생한다.
 * 1. 앞으로 전진할 위치의 락을 획득한다.
 * 2. 캐럴을 앞으로 한 칸 전진한다.
 * 3. 이전 위치의 락을 해제한다.
 * 
 * 그래서 위 프로토콜을 사용하지 않고 다음과 같이 동작한다.
 * 1. 앞으로 전진할 위치의 락을 요청한다. 이때 락 요청에 대하여 wait(sleep)하지 않는다.
 *    그러므로 데드락이 발생할 수 없다.
 * 2. 락 획득이 성공할 경우에만 앞으로 전진한다.
 * 
 * 이렇게 하면 시간이 지나도 데드락이 발생하지 않는다.
 */
package cp.java.week11.thread;
 
import java.awt.Color;
import java.awt.Point;
import java.util.Random;
 
import hufs.dislab.karel.IKarelProgram;
 
class NoWaitLockManager {
	private LockItem[][] table;
 
	private class LockItem {
		private boolean value = false;
 
		/**
		 * 락을 걸지 못하면 즉시 함수를 빠져나온다.
		 * 락을 거는 쓰레드를 sleep 상태로 빠뜨리지 않는다.
		 * @return 락 성공 여부
		 */
		public synchronized boolean lock() {
			if (value)
				return false;
			value = true;
			return true;
		}
 
		public synchronized void unlock() {
			value = false;
		}
	}
 
	public NoWaitLockManager(int width, int height) {
		table = new LockItem[width][height];
		for (int i = 0; i < width; i++) {
			for (int j = 0; j < height; j++)
				table[i][j] = new LockItem();
		}
	}
 
	public boolean lock(int x, int y) {
		//String name = Thread.currentThread().getName();
		//System.out.println(name + ":  lock " + x + "," + y);
		return table[x - 1][y - 1].lock();
	}
 
	public void unlock(int x, int y) {
		//String name = Thread.currentThread().getName();
		//System.out.println(name + ":unlock " + x + "," + y);
		table[x - 1][y - 1].unlock();
	}
 
	public boolean peek(int x, int y) {
		return table[x - 1][y - 1].value;
	}
}
 
/**
 * DEADLOCK 발생하지 않음.
 * 락을 요청할 때 sleep 상태로 가지 않기 때문임.
 * @author Sangwon Park
 * @since KarelOOP 2
 */
@SuppressWarnings("serial")
public class PainterThreadProgram3 extends IKarelProgram {
	public static final int NO_KARELS = 10;
 
	MyKarel[] list = new MyKarel[NO_KARELS];
 
	NoWaitLockManager lmgr;
 
	class Crazy extends Thread {
		MyKarel karel;
		Random r = new Random();
 
		Crazy(MyKarel karel) {
			this.karel = karel;
		}
 
		@Override
		public void run() {
			while (true) {
				switch (r.nextInt(4)) {
				case 0:
					karel.turnLeft();
					break;
				case 1:
					karel.turnRight();
					break;
				case 2:
					karel.turnAround();
					break;
				}
 
				if (karel.frontIsClear()) {
					Point pt = karel.getLocation();
					Point nextpt = new Point(pt);
					if (karel.facingEast())
						nextpt.x++;
					else if (karel.facingWest())
						nextpt.x--;
					else if (karel.facingNorth())
						nextpt.y++;
					else
						nextpt.y--;
 
					/*
					 * 락 획득이 성공한 경우에만 앞으로 전진한다.
					 * 그렇지 않은 경우에는 아무 일도 하지 않는다.
					 * 그렇게 함으로써 락 획득이 실패했다고 sleep 하지 않는다.
					 * 즉, 내가 락을 쥐고 있으면서 다른 락을 요청하지 않기 때문에
					 * 데드락이 발생하지 않는다.
					 */
					if (lmgr.lock(nextpt.x, nextpt.y)) {
						karel.move();
						karel.paintCorner();
						lmgr.unlock(pt.x, pt.y);
					}
				}
			}
		}
	}
 
	static Color[] colors = new Color[] { BLUE, RED, YELLOW, ORANGE, CYAN, GREEN, GRAY, 
			PINK, MAGENTA, LIGHT_GRAY, BLACK, DARK_GRAY, WHITE};
 
	@Override
	protected void onInit() {
		int width = getWorldWidth();
		int height = getWorldHeight();
 
		lmgr = new NoWaitLockManager(width, height);
 
		list[0] = (MyKarel) getKarel();
		Point pt = list[0].getLocation();
		lmgr.lock(pt.x,  pt.y);
 
		Random r = new Random();
		for (int i = 1; i < list.length; i++) {
			int x, y;
			do {
				x = r.nextInt(width) + 1;
				y = r.nextInt(height) + 1;
			} while (lmgr.peek(x, y));
 
			lmgr.lock(x,  y);
			int dir = r.nextInt(4);
			Color color = colors[i % colors.length];
 
			MyKarel karel = new MyKarel(x, y, dir, color);
			list[i] = karel;
		}
 
		for (int i = 1; i < list.length; i++) {
			addIKarel(list[i]);
		}
	}
 
	@Override
	public void onStart() {
		for (MyKarel karel : list) {
			new Crazy(karel).start();
		}
	}
 
	public static void main(String[] args) {
		IKarelProgram.main(args, new MyKarel(1, 1, EAST, BLUE));
	}
}