실버벨의 Stack Overflow

Maven - 이클립스 Maven 연동 시 plug in 에러 날 경우

대략 이런 에러가 발생했을 경우.

POM.xml을 확인해보면 

이렇게 되어 있을 것이고,
해결방법은 POM.xml에

이런식으로 디펜던시를 추가해주면 된다.(현재 날짜 기준으로 최신버전인 3.2.1은 되지 
않는다.)

이렇게 작성해준 뒤에, 
1. 프로젝트 우클릭 > Run As > Maven Install
2. 이클립스 프로젝트 탐색기에서 해당 프로젝트 클릭 후 F5(새로고침)
3. 프로젝트 우클릭 > Maven > Update Project 
끝

[1 단계] Servers tab에 server.xml source보기 클릭.

[2 단계] path 부분 중복되지 않게 수정해주기.

docBase : Eclipse상의 프로젝트 이름
path : 해당 프로젝트가 웹 상에 노출될 경로

https://www.acmicpc.net/problem/14503

1. 문제 이해

 삼성 기출 문제 입니다. 

 시뮬레이션 문제인데, 과정을 자세히 보면 dfs와는 다른것을 볼 수 있습니다.

처음에 이 문제를 dfs로 접근 하였다가 멘토님의 도움으로 while문으로 해결하는 문제라는것을 깨닳았습니다.

(그러니... 꼭 다시 풀어보자!!)

2. 접근 방법

 문제의 루틴대로 따라가면서 while문을 작성해 봅시다.

여기서 핵심은 flag!!

1) 4방향을 모두 탐색하였는데, 청소할곳(0)을 못찾은 경우에 루틴으로 가기 위한 flag!

2) 뒤로 가봤는데 뒤에가 벽인 경우는 탈출할수 있도록!!

3) 뒤로 가봤는데 뒤에가 벽이 아닌 경우는 방향을 그대로 가져 가도록 합시다!!

위에 3가지를 생각하면서 코딩에 들어가면 문제 끄~~~읏!!!

3. 문제 해결

** 뮤텍스란(Mutex)? **

“Mutual Exclusion 으로 상호배제라고도 한다. Critical Section을 가진 쓰레드들의 Runnig Time이 서로 겹치지 않게 각각 단독으로 실행되게 하는 기술입니다. 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 locking과 unlocking을 사용합니다.

즉, 쉽게 말하면 뮤텍스 객체를 두 쓰레드가 동시에 사용할 수 없다는 의미입니다.

** 세마포어란?(Semaphore) **

세마포어는 운영체제 또는 커널의 한 지정된 저장장치 내 값으로서, 각 프로세스는 이를 확인하고 변경할 수 있습니다. 확인되는 세마포어의 값에 따라, 그 프로세스가 즉시 자원을 사용할 수 있거나, 또는 이미 다른 프로세스에 의해 사용 중이라는 사실을 알게 되면 재시도하기 전에 일정 시간을 기다려야만 합니다. 세마포어는 이진수 (0 또는 1)를 사용하거나, 또는 추가적인 값을 가질 수도 있습니다. 세마포어를 사용하는 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경함으로써 다른 세마포어 사용자들이 기다리도록 해야합니다.

*** 뮤텍스와 세마포어의 차이점 ***

1) Semaphore는 Mutex가 될 수 있지만 Mutex는 Semaphore가 될 수 없습니다.

(Mutex 는 상태가 0, 1 두 개 뿐인 binary Semaphore)

2) Mutex의 경우 Mutex를 소유하고 있는 쓰레드가 이 Mutex를 해제할 수 있습니다. 하지만 Semaphore의 경우 이러한 Semaphore를 소유하지 않는 쓰레드가 Semaphore를 해제할 수 있습니다.

3) Semaphore는 시스템 범위에 걸쳐있고 파일시스템상의 파일 형태로 존재합니다. 반면 Mutex는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 Clean up된다.

★★★

가장 큰 차이점은 관리하는 동기화 대상이 갯수입니다. Mutex는 동기화 대상이 오직 하나뿐일 때,

 Semaphore는 동기화 대상이 하나 이상일 때 사용합니다.

★★★

[출처]: http://jwprogramming.tistory.com/13

#6-4. Process Synchoronization
: 프로세스 동기화에서 생기는 문제점 3가지를 알아보도록 하겠습니다.

* Bounded-Buffer Problem
: 버퍼의 크기가 유한

# 상황 설명
- Circular buffer 형태로 되어있다.
- 여러개의 Producer(생산자) 프로세스와
- 여러개의 Consumer(소비자) 프로세스가 있다.

# 역할
 - Producer : 공유버퍼에다가 데이터를 하나 만들어서 집어넣는역할.
 - Consumer : 데이터를 꺼내가는 역할
(원형 버퍼의 그림을 보면 주황색 색칠 부분은 producer가 데이터를 넣은것이고, 색칠 안된 동그라미는 consumer가 데이터를 쓴것.

???)

여기서 Synchronization과 관련해서 어떤문제들이 발생할까?

1) 공유 버퍼이기 때문에 생산자가 둘이 동시에 도착해서 동시에 데이터를 만들어 집어 넣으면 동기화 문제가 발생.
=> 공유 버퍼에 lock을 걸어서 동기화문제를 해결해야 한다.

2)공유 버퍼이기 때문에 소비자가 둘이 동시에 도착해서 동시에 데이터를 가져가면 동기화 문제가 발생.
=> 역시 공유 버퍼에 lock을 걸어서 동기화문제를 해결하도록 한다.

3) 버퍼가 유한(Bounded) 하기 때문에 생기는 문제
: 즉, 버퍼가 찼는데, 생산자(producer)가 도착하는 경우, 또는 버퍼가 비었는데 소비자(consumer)가 도착하는 경우.
=> producer는 버퍼가 가득 찼는지, consumer는 버퍼가 비었는지 체크 해줘야 한다.

----------------------------------------------------------
!!!)

 Semapore 를 이용해서 해결해야할 문제가 2가지가 있다.

1) 동시에 공유 버퍼에 접근하는것을 막기 위해서 lock을 걸었다가 푸는 작업.

2) 버퍼가 가득 차거나, 비었을 때를 알수 있게 counting Semapore가 필요하다.
----------------------------------------------------------

# 세마포어로 구현한 생산자, 소비자 문제

* Readers - Writers Problem

# 상황 설명

- 프로세스는 2종류(읽는 P, 쓰는 P)
- 공유 데이터 : DB

Sol)

Reader는 동시접근이 가능하게 하고,

Writer는 동시접근이 불가능하게 해야한다.

# 세마포어를 통한 문제 해결 코드

# Reader 부분 설명

1) 노란색 부분인 if(readcount == 1) P(db); 을 보면 1일때에만 db(스몰 db)로 lock을 걸어주게 되고, 1이 아니면 이미 lock이 걸려 있기 때문에 DB에 바로 들어갈 수 있다.

2) But, 여기서 readcount도 공유 변수 이므로 동시에 접근할 경우 동기화 문제가 발생할 수 있다. 그래서 mutex변수를 이용하여 readcount에 접근하는 부분에도 lock과 unlock을 걸어주도록 한다.

!!!)

그렇지만 Writer의 Starvation 현상이 발생한다.

readcount가 0이 되어야 V(db)로 lock이 풀리는데,

Reader가 너무 많아 지면 Writer는 Starvation 현상이 발생하게 된다.

* Dining - Philosopheres Problem (식사하는 철학자 문제)
:  2가지 업무가 있다. (생각하는 업무, 밥을 먹는 업무)

!!!)

노란색 코드 때문에 Deadlock이 발생할 수 있는 위험한 코드이다.

why))

 eat()에 들어가기 전에 모든 철학자가 P(chopstick[i])코드 때문에 자신의 왼쪽 젓가락을 들고 안놓게 된다... 그렇게 될 경우 아무것도 진행이 될 수 없는 Deadlock 현상이 발생하게 된다.

 그럼 어떻게 해결을 해야 할까?

# 식사하는 철학자문제를 세마포어로 해결한 코드

# 변수 설명
- semaphore self : 각각의 5명의 철학자가 젓가락 2개를 잡을수 있어서 젓가락 잡는 권한을 줄것이나 말것인가를 정하는 변수.

 ex>
 - self[1] = 0; // 1번 철학자는 젓가락 잡기 불가능.
 - self[3] = 1; // 3번 철학자는 젓가락 잡기 가능.

- mutex : state변수에 접근에 lock/unlock 을 위한 변수.

- test 함수 : 젓가락 잡을수 있는 권한이 있나?
 즉, 왼쪽 철학자랑 오른쪽 철학자가 먹고 있지 않고, 내가 hungry인 상태일때, 젓가락 잡을수 있는 권한 획득.

* 세마포어의 문제점

=> 세마 포어를 개발자가 잘 지키면 프로그램이 제대로 돌아가겠지만, 제대로 했는지 확인이 힘들다....

* Moniter
: 공유데이터를 접근하기 위해서는 모니터라고 정의된 내부에 프로시저를 통해서만 내부의 공유 데이터에 접근할수 있게 만들어 놓는것. 그리고 모니터가 원천적으로 내부에 프로시저가 동시에 여러개가 실행되지 않도록 만드는것.(=> 이렇게 되면 lock을 걸 필요가 없다.)

(프로그래밍 언어 차원에서 동기화 문제를 해결을하는 High-level Synchronization construct)

semaphore의 lock & unlock기능은 해결!!

???)
자원의 개수를 어떻게 셀까?

# 함수 설명

- wait() : 자원이 없으면 기다리게 하는 함수
- signal() : 접근을 다하고 빠져나갈 때 호출(invoke)하는 함수

* 모니터 내부 형태

* 모니터로 convert한 Bounded-Buffer & Dining - Philosopheres Problem
: 세마포어처럼 lock을 걸 필요가 없다.
(모니터 안에서 하나의 프로세스만 실행되기 때문에!!)

#6-3. Process Synchronization

cf > 추상 자료형 : 논리적으로 정의하는것이지, 실제로 컴퓨터에서 어떻게 구현되는지는 별개의 문제.

* Semapores
: 추상 자료형

# semapore 자료형은 p연산과 v연산이 존재하게 된다.

---------------------------------------------------------
???) Semapore라는것을 왜 사용 하는가?

공유 자원을 획득하고 반환하는것을 세마포어가 처리해준다!

p 연산 : 공유데이터를 획득하는 과정
v 연산 : 다 사용하고 나서 반납하는 과정.

=> p연산을 하면 lock을 거는 과정이고, v연산은 lock을 푸는 과정이다.
---------------------------------------------------------

# 세마포어 값은 Integer(정수) 값을 가지는데, 자원의 갯수를 의미 한다.

cf> p연산과 v연산은 atomic 하게 연산이 된다고 가정한다!

* Critical Section of n Processes
: critical section 문제에다가 semapore를 사용해보자.

# mutex 변수를 1로 놓고,

critical section에 들어가야 할때(lock을 걸때)에는 p연산을 해주고,

  critical section을 나올때(lock을 풀때)에는 v연산을 해준다.

=> 이렇게 되면 critical section문제가 자연스럽게 해결이 된다.

=> 즉, 세마포어를 통해서 프로그래밍을 해주면 개발자는 훨씬 간단한 프로그래밍을 할수 있다. (6-2에서 나왔던 알고리즘을 고려하지 않아도 된다)

But.. 누군가 critical section에 들어가 있다면 p연산에서 while문을 돌면서  기다리기 때문에 busy-waiting (= spin lock)이 해결 되지는 않는다...

cf> Block & Wakeup 방식 (=sleep lock)
: 누군가가 critical section에 있다면, 쓸데없이 while문을 도는(spin)하는 것이 아니라 blocked 상태에서 기다리는 방법!

* Block / Wakeup Implementation
: 세마포어 변수를 획득하지 못한 프로세스는 block상태에 두는것.

# 구체적으로 어떻게 구현되는지 살펴 봅시다!

# p 와 v에 들어있는 s는 세마포어 변수

v. p연산 : 자원을 획득하는 과정
 - 자원에 여분이 있다면 획득!
 - 자원에 여분이 없다면 block();

v. v연산 : 자원반납하고, 자원을 기다리면서 혹시 잠들어 있는 자원이 있다면 그 자원을 깨워주는 연산

???)

v연산에서 if(S.value <= ) { wakeup(P); }

를 보면 자원을 내놓았는(S.value++) 데에도 불구하고

S.value가 음수 인 경우는 block()된것이 많다는것이다.

그래서 wakeup() 으로 깨워준다.
 

=> busy waiting 방식과는 조금 다르다.
: busy waiting 방식에서는 단순히 자원의 갯수를 세는 경우였는데, block-wakeup방식은 조금 다르다. 
 block-wakeup방식에서는 단순히 세는것이 아니라 깨워야할 누군가가 있는지를 확인하기 위해 사용된다.

* 어떤 방법이 더 좋은 방법 일까?

# block / wakeup 하는 방법에도 overhead가 있다. critical section이 짧은 경우에는 busy - waiting도 괜찮다.

* Two Types of Semaphores
: 세마포어의 두가지 타입

* Deadlock and Starvation
: 세마포어를 사용할때 주의해야 원치 않는 문제

1) Deadlock :
: 상대방이 가진것을 기다리면서 자기것은 내놓지 않고, 서로 영원히 기다리는것을 DEADLOCK이라고 한다.

ex> 세마포어 S 와 Q, 두개가 있는데, 세마포어 두개를 모두 획득해야지만, 일을할수 있는 그런 환경.

P0순서에서 S를 획득했다. 그런다음에 P1에 차례가 넘어갔다.
P1순서애서 Q를 획득했다.

=> P0와 P1은 서로를 무한히 기다리게 된다.

=> 해결방법 : 자원을 획득하는 순서를 똑같이 맞춰주자. 즉, 모든 프로세스가 S먼저 획득하고 Q를 획득하게끔 해준다.

2) Starvation
: 특정프로세스만 자원을 받고, 나머지 프로세스는 무한히 기다리는 것.

https://www.acmicpc.net/problem/14891

1. 문제 이해

 이 문제를 풀면서 하나 깨닳은 것은 문제 이해가 개인적으로 정말 중요하다는것을 느꼈습니다....

 뱀문제와 마찬가지로 시뮬레이션 문제 입니다.

2. 접근 방법

[1 단계] 입력되는 dir변수에 따라서 시계방향으로 돌지, 반 시계방향으로 돌지 정하게 됩니다.

[2 단계] 왼쪽, 오른쪽을 검사하여 서로 다른 값이 있다면 반대방향으로 돌려주고, 

                                   서로 같은 값이 있다면 돌려 움직이지 않습니다.

=> 저같은 경우는 이 부분을 왼쪽 오른쪽 으로 나눠서 재귀로 작성하였습니다.

cf> 이 부분에서 논리적으로 잘못생각하여 시간이 꽤 걸렸습니다.

 돌리기전에 양옆을 먼저 확인하여 옆 톱니가 움직이는지 여부를 먼저 결정해줘야 합니다!!!

[3 단계] 12시 방향에 있는것들의 가중치를 곱해 답을 출력합니다.

3. 문제 해결

https://www.acmicpc.net/problem/14502

1. 문제 이해

 벽을 3개 세웠을때, 바이러스가 퍼지고, 그후 바이러스에 전염되지 않은지역을 세는 문제입니다. 이때, 전염되지 않은 지역이 최대가 되는 경우를 알아내는 문제입니다. 

2. 접근 방법

 n이 8보다 작은수 이므로 완전 탐색으로 해결했습니다.

[1단계] dfs로 벽 세우기 (for문을 사용한 완전 탐색)

[2단계] 벽이 3개가 됐을때, bfs로 바이러스 확장시키기

[3단계] 바이러스를 퍼지기 전으로 회복시키면서 전염이 안된 지역 세어주기

3. 문제 해결