24.07.17 day27 메모리 연속할당, 숫자 고르기

메모리 연속할당

first fit, best fit, worst fit에 대해 설명해주세요.

1. first fit

first fit 알고리즘은 메모리 할당 요청이 들어왔을 때, 첫 번째로 발견된 충분한 크기의 빈 메모리 블록에 할당하는 방식이다.

• 장점:
  • 구현이 간단하고, 빠르게 동작한다.
  • 처음에 발견한 블록을 할당하기 때문에 시간 복잡도가 상대적으로 낮다.
• 단점:
  • 메모리의 앞쪽 부분에 작은 빈 공간들이 남아 단편화(fragmentation)가 발생할 수 있다.
  • 시간이 지나면 작은 블록들이 많이 생겨서 큰 블록을 할당하는 것이 어려워질 수 있다.

2. best fit

best fit 알고리즘은 메모리 할당 요청이 들어왔을 때, 충분한 크기의 빈 블록 중에서 가장 작은 블록에 할당하는 방식이다.

• 장점:
  • 빈 메모리 공간을 효율적으로 사용할 수 있어 내부 단편화를 줄일 수 있다.
  • 큰 블록들이 많이 남아서 큰 메모리 요청을 처리하기 유리할 수 있다.
• 단점:
  • 최적의 블록을 찾기 위해 모든 빈 블록을 검색해야 하므로 시간이 많이 걸릴 수 있다.
  • 빈 블록들이 작은 단편화 조각들로 남아 외부 단편화가 발생할 수 있다.

3. worst fit

worst fit 알고리즘은 메모리 할당 요청이 들어왔을 때, 충분한 크기의 빈 블록 중에서 가장 큰 블록에 할당하는 방식이다.

• 장점:
  • 큰 빈 블록을 할당하므로 큰 메모리 조각들이 남아있게 되어 큰 메모리 요청을 처리하기 유리하다.
  • 외부 단편화 문제를 어느 정도 줄일 수 있다.
• 단점:
  • 실제 메모리 공간의 활용이 비효율적일 수 있다.
  • 큰 블록을 할당하고 나면 그 블록이 작게 쪼개져서 작은 메모리 요청들을 처리할 때 내부 단편화가 발생할 수 있다.
  • 최적의 블록을 찾기 위해 모든 빈 블록을 검색해야 하므로 시간이 많이 걸릴 수 있다.

---

worst-fit 은 언제 사용할 수 있을까요?

1. 큰 메모리 요청이 빈번한 경우
   • 시스템에서 큰 메모리 블록을 자주 요청하는 프로그램들이 많은 경우, Worst Fit은 큰 블록을 할당하고 더 큰 블록을 남겨두기 때문에 유용할 수 있다.
   • 이렇게 하면 큰 요청을 처리할 수 있는 충분한 공간을 확보할 수 있다.
2. 외부 단편화 문제를 줄이기 원하는 경우
   • Worst Fit은 항상 가장 큰 블록에 메모리를 할당하기 때문에 작은 단편화 조각들이 많이 남지 않게 된다.
   • 이는 외부 단편화 문제를 어느 정도 완화할 수 있다.
3. 메모리 블록의 재사용이 중요한 경우
   • 메모리 블록이 자주 할당되고 해제되는 환경에서, 큰 블록을 유지하는 것이 재할당에 유리할 수 있는데, 큰 블록을 유지하면 나중에 큰 메모리 요청이 들어왔을 때 할당할 수 있는 가능성이 높아진다.
4. 시스템의 메모리 관리 특성
   • 시스템의 메모리 관리 특성이나 사용 패턴에 따라 worst fit이 다른 알고리즘보다 더 나은 성능을 보일 수 있다.
   • 예를 들어, 시스템에서 메모리 요청이 주로 큰 블록에 집중되거나, 메모리 해제와 할당이 빈번하게 일어나는 경우 등이 이에 해당할 수 있다.

예시)

• 서버 환경: 대규모 데이터 처리나 가상 머신 운영 등에서 큰 메모리 블록의 할당이 빈번하게 일어나는 서버 환경에서는 worst fit이 유리할 수 있다.
• 과학 계산 및 시뮬레이션: 대용량 데이터를 처리하는 과학 계산이나 시뮬레이션 프로그램에서는 큰 메모리 블록을 자주 할당할 필요가 있으므로, worst fit을 사용하면 큰 블록을 확보할 수 있다.
• 클라우드 컴퓨팅: 클라우드 환경에서 여러 가상 머신에 메모리를 동적으로 할당하는 경우, 큰 블록을 남겨두는 것이 향후 큰 메모리 요청을 처리하는 데 도움이 될 수 있다.

---

성능이 가장 좋은 할당 알고리즘은 무엇일까요?

 

할당 알고리즘들은 각각의 장단점을 가지고 있기 때문에 상황에 따른 알고리즘 선택이 필요하다.

• first fit은 빠른 할당 속도가 필요한 경우에 유리하다. 단편화 문제는 발생할 수 있지만, 탐색 시간이 짧아 전체 시스템 성능에 긍정적인 영향을 줄 수 있다.
• best fit은 메모리 공간을 최대한 효율적으로 사용해야 하는 경우에 적합하다. 탐색 시간이 길지만, 메모리 공간을 효율적으로 사용하여 단편화를 줄이는 것이 중요한 환경에서 유리하다.
• worst fit은 큰 메모리 요청이 자주 발생하는 환경에서 유리할 수 있습니다. 큰 블록을 유지하여 큰 요청을 처리하기 쉽게 하지만, 일반적인 메모리 활용도는 떨어질 수 있습니다.
• next fit은 마지막 할당 위치부터 탐색해 빠른 할당 속도를 제공하지만, 불규칙한 메모리 사용 패턴에서 단편화가 증가할 수 있다.

본인의 생각으로는 최근 메모리의 용량증가로 최적화보단 빠른속도를 가진 first fit이 좋지 않을까 생각한다.

 

---

숫자 고르기

 

코드)

n = int(input())
graph = [[] for i in range(n + 1)]

for i in range(1, n + 1):
  graph[i].append(int(input()))


def dfs(s):
  global result, cnt

  visited[s] = True
  for now in graph[s]:
    if visited[now] == False:
      dfs(now)
    elif visited[now] == True and finished[now] == False:
      if now not in result:
        cnt += 1
        result.append(now)
        return
    else:
      return
  finished[s] = True


result = []
cnt = 0

for i in range(1, n + 1):
  visited = [False] * (n + 1)
  finished = [False] * (n + 1)
  dfs(i)

result.sort()
print(cnt)
for i in result:
  print(i)

 

처음에 문제를 이해하는데에도 좀 걸렸다. 백준 문제는 왜이렇게 설명을 꼬아서 하는건지..

각 인덱스에 대해 집합이 되는 값들을 찾아야 해서 방문한 값을 처리하는 dfs방식으로 시도했다.

백준이 너무 불편한게 본인이 어떤 케이스에서 틀린건지 전혀 알려주질 않아서 뭐가 잘못된건지를 못찾고 헤매다가 결국 구글링을 통해 도움을 받았다.

매번 집합 값을 찾으려할 때마다 각 방문값과 집합 배열을 초기화시켜줘야 하는데 본인은 함수를 이용하지 않고 작성하려다 보니 각 값들을 그대로 사용했었다. 

알고리즘 너무 어렵다