공유메모리상에 링크드리스트를 구현할 수 있나요?

Hyeon9mak의 이미지

컴공과 학부생입니다. socket programming 공부중 shared memory단계까지 왔습니다.

이번학기 내내 구현해왔던 web server 구현 프로젝트에서 client connection(accept) history를 링크드리스트로 추가 및 출력하고 있었는데요,
이번에는 shared memory를 이용해서 자식프로세스들이 가지고 있던 최대 10개의 connection history를 부모쪽으로 넘겨서
한꺼번에 정렬한 후 출력시켜야 합니다.

shared memory에 링크드리스트를 직접 추가하는 방식으로 구현하면
모든 프로세스가 노드만 추가로 연결하는식으로 간단할 것 같은데 역시 간단치 않더라구요.

나름대로 조사해본 결과
"매 프로세스마다 shared memory를 매핑했을 때 할당받는 메모리주소값이 달라(가상메모리) 쓰는 측과 읽는 측이 서로 다른곳에 접속할 수밖에 없다..
때문에 포인터를 이용하면 안된다." -> 즉 malloc을 이용하는 일반적인 링크드리스트는 불가능하다. 라는 결론이 나왔습니다.

혹시 링크드리스트 비스무리하게 사용할 방법이나 예시가 있을까요?
도저히 떠오르지 않아 정말 무식한 방법으로 구현하게 될 것 같습니다..ㅠㅠ

익명 사용자의 이미지

할 수 있습니다. 물론 그냥 되지는 않지만요.

(1) 공유 메모리를 (i)모든 프로세스에서 동일한 주소에 올리거나 (ii)동일한 주소에 올리지 않더라도 사용 가능한 형태로 linked list를 구현해야 합니다.

(i)는 c library의 능력을 벗어나는 일입니다. platform-dependent한 방법을 써야 하지요. mmap(linux)이나 MapViewOfFileEx(Windows) 같은 함수를 쓰면 됩니다만, 이런 함수들이 공유 메모리를 원하는 주소에 올리는 데 실패하는 경우도 있다는 걸 염두해 둬야 합니다.

(ii)는 좀 더 안전하지만 번거로운 방법입니다. 공유 메모리 내부의 객체에 대해서 포인터를 직접 기록하는 대신, 공유 메모리 내부의 어떤 점에 대한 상대 주소를 기록하면 되지요. 물론 역참조할 때는 적절한 변환을 통해서 진짜 포인터로 만들어야 합니다.

가장 손쉬운 구현은 공유 메모리 안에 list의 노드들을 1차원 배열 형태로 배치하고, 포인터 대신 배열 인덱스를 기록하고 사용하는 겁니다. 이런 형태의 구현은 list 크기 확장이 다소 번거로운 반면 나름 성능상의 이점이 있어서, node 단위로 malloc하는 구현 대신 사용되는 경우도 많지요.

(2) 학부생인데 shared memory까지 배웠다고 하시니 synchronization 관련 내용을 이미 배웠거나 곧 배우시겠군요. 이론으로 배우는 것과 실제로 구현할 때 문제가 안 되게 하는 것 사이엔 상당한 차이가 있으니 바짝 긴장하시길. 내 컴퓨터에선 잘 돌았는데 조교 컴에서 안 돌아서 점수가 깎이는 일이 안 벌어질 것 같죠?

bushi의 이미지

커널과 어플 사이에 shared memory 를 만들고, 그곳에 링크드 리스트를 만들어 본 적은 있습니다.
링크된 노드의 주소 대신 offset 을 기록해서 사용하면 되는데, 어렵진 않지만 더럽죠.

라스코니의 이미지

한가지 유의할 점은 뭐든지 프로세스(쓰레드) 간에 공유된 자원(e.g. shared memory, file 등)을 사용하기 위해서는 필수적으로 원자성(atomic operation)을 요구하게 되는데 이것을 어찌 제공할 지 고민해야 한다는 것입니다.

그래서 저라면 최대 10개 정도밖에 안되기 때문에 각 자식 프로세스마다 10개씩의 connection 정보를 보관할 수 있는 shared memory를 만들고 각 자식 프로세스는 자신에게 할당된 공간(slot)에만 추가하는 방법을 선택할 것 같습니다. 한계가 분명있지만 이런 상황에서는 잘 돌아갈 겁니다.

익명 사용자의 이미지

물론 그런 종류의 문제는 늘 먼저 고민했던 사람들이 있지요:

https://en.wikipedia.org/wiki/Concurrent_data_structure

그래도 어쨌건 구현하기 정말 번거로운 게 사실입니다. 차라리 프로세스간 데이터 송수신은 본격적인 IPC 메커니즘을 활용해서 synchronization까지 겸하고, 자료 구조 관리는 프로세스 하나가 혼자 떠맡는 게 편할지도 모르지요.

보아하니 shared memory 사용이 과제 조건인 듯한데.. 그럼 어쩔 수 없지만요.

Hodong Kim@Google의 이미지

shared memory에 링크드리스트를 사용하라는 조건만 아니면 일반적인 방법으로 만들 수 있겠는데요.

자식프로세스들이 가지고 있던 최대 10개의 connection history를 부모쪽으로 넘겨서 한꺼번에 정렬한 후 출력시켜야 합니다.
만약 시간순으로 정렬하는 것이라면 정말 쓸모없는 짓입니다. 최대 10개로 제한을 했는데 그게 더 어렵겠네요.

각각의 자식이 부모에 로그를 보낼 것이 아니라 그냥 syslogd, systemd 쪽으로 보내면 더 좋겠는데요. 아무래도 파일에 쓰는게 좋죠.
파일에 저장된 거를 편집기나 로그 분석기로 열어서 정렬을 하는게 더 좋겠죠.

만약 과제라면 과제를 낸 사람이 실용적인 과제를 냈으면 좋겠고,
만약 귀하께서 설계한 거라면 두루두루 공부하셔서 실용적인 설계를 하셨으면 좋겠습니다.

공유 메모리를 제대로 사용하려면 동시접근 안 되게 임계 영역 잡아줘야 됩니다.
뮤텍스 락 걸고 poll 디스패치 하면 될 것 같은데...
위 과제의 경우 공유 메모리를 사용하지 않고 일반적이고 단순한 방법으로 구현하는게 답입니다.
과제가 안습이라 폭망했네요.

댓글 달기

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.