커널2.6에서 새롭게 도입된다는 O(1) algorithm이 무엇인가요?

hyangii의 이미지

안녕하세요.

커널 2.6에 대해 분석한 기사를 보던 중에, 이번 커널에 새로운 스케쥴러 알고리즘 O(1) algorithm을 사용해서 성능이 향상됬다고 하는데,

이것이 어떤것이며, 과거 커널과 비교해 무슨 효과가 있는 것인지 궁금합니다.

eungkyu의 이미지

자세히는 모르지만, 알고리즘이 O(1)이 되었으니, 일단 전체적은 퍼포먼스가 올라갔을 테고, 특히 SMP의 경우 scalability가 매우 향상되었다고 합니다. 한마디로 좀 더 enterprise급으로 갔다고 할 수 있겠죠.

자세한 것는 다른 분이...

elecguy의 이미지

O(1) 이 어떤 특정알로리즘을 가리키는 것이 아니라 알고리즘 성능 표기법인것 같은데요.
O(1)이니까 개체개수(n)에 상관없이 상수시간에 처리한다는 뜻입니다.

폐인, 노가다 그 끝은..?

eungkyu의 이미지

elecguy wrote:
O(1) 이 어떤 특정알로리즘을 가리키는 것이 아니라 알고리즘 성능 표기법인것 같은데요.
O(1)이니까 개체개수(n)에 상관없이 상수시간에 처리한다는 뜻입니다.

그런 뜻도 되지만, 이름마저도 O(1)이 되어버렸습니다 8)

mastercho의 이미지

소켓 처리 방식 방식의 향상이 아닌가 싶습니다

기존의 poll이나 select 방식은 검색 시간이 O(n)이있습니다

불필요한 검색 시간이 아마 epoll 같은 방식을 써서 O(1)정도로

줄여서 렇게 된게 아닌가 싶습니다

그럼

승자는 자기보다 우월한 사람을 보면 존경심을 갖고 그로부터 배울 점을 찾지만 패자는 자기보다 우월한 사람을 만나면 질투심을 갖고 어디 구멍난 곳이 없는지 찾는다.
- 하비스

Tony의 이미지

Process scheduling을 위해 run queue를 뒤질때 O(n)걸리던걸 O(1)알고리즘으로 바꾼걸로 알고있습니다.
전체적으로 프로세스 스케줄링 알고리즘이 향상되어 시스템 성능은 향상됐는데
굶어죽는 프로세스(큭큭) 가 생기는 문제가 있어서 알고리즘 보완중이었는데 요즘 커널 메일링리스트에서
그이야기가 다시는 등장 안하는걸로 보아 해결된 모양....

-이상에서 이해안되는 용어가 나오는분은.. 궁금하면 공룡책이라도 한번 읽어주시길.

eungkyu의 이미지

Tony wrote:
Process scheduling을 위해 run queue를 뒤질때 O(n)걸리던걸 O(1)알고리즘으로 바꾼걸로 알고있습니다.
전체적으로 프로세스 스케줄링 알고리즘이 향상되어 시스템 성능은 향상됐는데
굶어죽는 프로세스(큭큭) 가 생기는 문제가 있어서 알고리즘 보완중이었는데 요즘 커널 메일링리스트에서
그이야기가 다시는 등장 안하는걸로 보아 해결된 모양....

처음에는 웹브라우저 버튼을 누를때마다 mp3가 끊기곤 했는데, 이번에 test6부터는 사라졌습니다 :) (mm시리즈에서는 좀 더 예전부터 사라졌지만...)

Quote:

-이상에서 이해안되는 용어가 나오는분은.. 궁금하면 공룡책이라도 한번 읽어주시길.
fibonacci의 이미지

자세한 내용은 모르겠지만,
SMP스케줄링이 비약적으로 향상되었다면, 계산서버를 이용하는 유저로써 즐거운 일입니다.
2.6 정식 나오자마다 컴파일 해봐야 겠군요 :o
참 글쓴님, O(1)에 대한 참고 기사링크좀 부탁드립니다. 꾸벅

No Pain, No Gain.

댓글 달기

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
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.