# K-server问题

## 引例和问题

• 度量空间可能是无限或有限的（分别对应于连续和离散的情况）
• (h,k)-server problem: 在线k-server算法比较的对象是离线h-server算法，$h \le k$

## 基本概念

### k-server猜想

• k-server猜想：对于任何度量空间，k-server问题都存在k-竞争的在线算法。
• 无法推广到到非对称度量空间
• 对任何度量空间，已知最好的竞争比是$2k-1$ (work function算法)

### 确定算法的一个竞争比下界

• 对于至少有$k+1$个点的度量空间（请求出现的位置是离散且有限的），任何确定性k-server算法的竞争比不可能小于$k$
• 更强的结论：对于至少有$k+1$个点的度量空间，任何(h,k)-server问题的算法竞争比不可能小于$\frac{k}{k-h+1}$

## 简单环境下的k-server问题

### 线(Line)

DC算法是k-竞争的。

• 势函数方法(potential function method) （关于势函数方法应用于竞争比的分析，将在下次组会用一个经典模型来讲解）

### 树(Tree)

• 不考虑树枝的权重
• 定义“邻居”：对一个服务者$s_i$，如果它到请求的最短路径上没有其他服务者，则称$s_i$是该请求的一个邻居。

## 其他算法

### 推广到高维空间？

• 高效 = 计算复杂度不随着输入规模的增大而指数增加
• 坏消息：即便对于二维欧式空间，尚未发现高效的k-server算法
• 好消息：对于任意欧式空间的2-server问题，存在3-竞争的算法

$\gamma$松弛覆盖（Slack-Coverage,SC$_\gamma$）设r是当前要服务的请求，x与r的距离更近（如果与r的距离相等，随机选一个），将y向r移动$\gamma \cdot \text{slack}(x,y,r)$距离，同时选择x去服务r。

## 功函数方法(Work Function Method)

### 符号说明

• $C$: 组态（configuration），表示服务者集合的（瞬时）位置状态。是一个多重集合，即集合中允许存在多个位于同一位置的服务者。$C$中的一个元素用小写字母表示
• 两个组态$X,Y$的距离用$D(X,Y)$表示，等于$X$和$Y$之间的最小权匹配
• 按时间先后到达的请求序列$\sigma = { r_1, r_2, \ldots, r_n }$

### 功函数

$w_{\sigma_0}(C) = D(C_0, C)$, 当$i = 0$

## 现实中k-server问题的简单实例

### 进程调度

• 先来先服务(FCFS)
• 短作业优先(SJF)
• 优先级调度
• 按新的更高优先级的进程能否抢占正在执行的进程分类：非抢占式优先级调度、抢占式优先级调度
• 按进程创建后其优先级是否可以改变：静态优先级、动态优先级
• 高响应比优先：是对SJF算法的一种改进，改进点在于作业的优先级随着等待时间的增加而增加，有利于克服“饥饿”现象。作业的优先权由下式定义：$R_p = \frac{\text{等待时间} + \text{要求服务时间}}{\text{要求服务时间}}$，$R_p$又称作响应比。
• 时间片轮转：主要适用于分时系统。时间片的长短通常由以下因素决定：系统的响应时间、就绪队列中的进程数目和系统的处理能力。
• 多级反馈队列：集合了前几种算法的优点

### 磁盘调度

• FCFS
• 最短寻找时间优先(Shortest Seek Time First, SSTF)
• 扫描(SCAN, 又称电梯算法)
• 循环扫描(Circular SCAN)：扫描算法的一种变形
-----EOF-----

Categories: 算法 Tags: 组合优化 在线算法
{"ft_lang_label":"__label__zh","ft_lang_prob":0.906026,"math_prob":0.99058604,"size":5335,"snap":"2023-14-2023-23","text_gpt3_token_len":4278,"char_repetition_ratio":0.103732884,"word_repetition_ratio":0.014814815,"special_character_ratio":0.28603563,"punctuation_ratio":0.073085845,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9861883,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-06-07T10:07:07Z\",\"WARC-Record-ID\":\"<urn:uuid:e04ee1ce-3e3b-4540-8b8f-e825a4b63bbf>\",\"Content-Length\":\"23876\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:af0d26e3-5cf7-44b2-a018-51ca5d05b7a7>\",\"WARC-Concurrent-To\":\"<urn:uuid:0de3c24a-94c6-4e99-826c-3606b0c9d0f0>\",\"WARC-IP-Address\":\"185.199.108.153\",\"WARC-Target-URI\":\"http://ihuafan.com/%E7%AE%97%E6%B3%95/k-server-problem\",\"WARC-Payload-Digest\":\"sha1:TCKYVWTSIBCHFHYEDGB5DRM33R7AL2UU\",\"WARC-Block-Digest\":\"sha1:S7O5VR6JMSWAF4V4DTVZOJNQJJ64MJUC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-23/CC-MAIN-2023-23_segments_1685224653631.71_warc_CC-MAIN-20230607074914-20230607104914-00113.warc.gz\"}"}